лекции 1-3. Лекция Понятие алгоритма. Свойства алгоритмов
 Скачать 241.48 Kb.
|
|
Лекция 1. Понятие алгоритма. Свойства алгоритмов Каждый из нас ежедневно решает задачи различной сложности: как быстрее добраться в школу или на ра- боту в условиях нехватки времени; в каком порядке выполнять дела, намеченные на текущий день, и т.д. Некото- рые задачи настолько сложны, что требуют длительных размышлений для нахождения решения (иногда решение так и не удается найти), другие задачи мы решаем автоматически, так как выполняем их ежедневно на протяже- нии многих лет (выключить звенящий будильник; почистить утром зубы; позвонить другу по телефону). Но в любом случае решение каждой задачи можно подразделить на простые этапы. Пример. Задача "Звонок другу по телефону" подразделяется на следующие этапы (шаги): 1) поднять телефонную трубку; 2) если услышал длинный гудок, то набрать номер друга, иначе конец решения задачи с отрицательным результатом (телефон неисправен); 3) определить тип гудков: "вызов" или "занято". Если "вызов", перейти на п. 4, если "занято", перейти на п. 6; 4) дождаться 5 вызывающих гудков; 5) если за это время абонент не поднял трубку, то конец решения задачи с отрицательным результатом (абонент не отвечает), иначе начать разговор. Задача "Позвонить другу" решена успешно; 6) положить телефонную трубку; конец решения задачи с отрицательным результатом (абонент занят). Если вы будете разбирать алгоритм "Звонок другу по телефону", то следует обратить внимание на п. 4 ("дождаться 5 вызывающих гудков"): если по этому алгоритму будет работать человек, который никогда не поль- зовался телефоном, то ему надо обязательно указать, как долго ждать вызов абонента (иначе алгоритм не будет обладать свойством дискретности). Естественно, вместо цифры "5" в алгоритме может стоять любая разумная цифра. Приведенная последовательность шагов является алгоритмом, решения задачи "Звонок другу по телефо- ну". Исполнитель этого алгоритма — человек. Объекты алгоритма — телефон и телефонные сигналы. Компьютер нужен человеку для решения задач практики. Примерами таких задач могут быть: описание поведе- ние тела, двигающегося в среде с сопротивлением; описание последствий ядерной войны; построение оптимального варианта транспортных перевозок; прогнозирование результатов сброса промышленных отходов в водоем и т.п. Не- смотря на значительное различие задач, просматриваются общие моменты в порядке их решения: • во-первых, требуется выделить систему и построить ее информационную модель - ею определяется набор дан- ных и их взаимосвязи; • во-вторых, должен быть установлен порядок обработки данных. Это звенья одной последовательности решения, поэтому представляется вполне оправданным рассмотреть их совместно, причем с обсуждения второй составляющей - обработки данных. В общем случае обработка состоит в преобразовании по некоторым правилам исходной данных, в результате чего появляются новые данные. Бесспорно, важным оказывается то обстоятельство, что преобразование должно осу- ществлять некоторое техническое устройство в автоматическом режиме (т.е. без участия человека на каждом этапе преобразования). В связи с этим возникает ряд взаимосвязанных задач, требующих разрешения: • определение правил обработки информации с учетом того, что она представлена в дискретной форме; • установление, каким требованиям должно удовлетворять устройство, производящее обработку; • определение того, каким образом данные и последовательность обработки может быть представлена для исполнения устройству. Общие подходы к решению проблем обработки дискретной информации изучаются в теории алгоритмов, к рассмотрению элементов которой и приступим. Для решения любой задачи надо знать, что дано и что следует получить, т.е. у задачи есть исходные данные (некие объекты) и искомые результаты. Для получения результатов необходимо знать способ решения задачи, то есть располагать алгоритмом (инструкцией, правилом), в котором указано, какие действия и в каком порядке сле- дует выполнить, чтобы решить задачу (получить искомые результаты). В базовом курсе информатики вы знако- мились с основами теории алгоритмов, в частности, вы знакомы со следующим неформальным определением алгоритма. Определение. Алгоритм — это точная конечная система правил, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения (после конечного числа шагов) искомого результата. Приведенное выше определение не является определением в математическом смысле слова, т.е. это не фор- мальное определение, а довольно подробное описание понятия алгоритма, раскрывающее его сущность. Это опреде- ление не является формальным потому, что в нем используются такие не уточняемые понятия, как "система правил" и "действия исполнителя". Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин. Само же слово алгоритм появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математи- ком Мухаммедом бен Муса аль-Хорезми ("аль-Хорезми" означает "хорезмиец", человек из города Хорезм, в настоящее вре- мя Хорезм — город Хива в Хорезмской области Узбекистана). Слово алгоритм — европеизированное произношение слов аль-Хорезми. Первоначально под словом алгоритм понимали способ выполнения арифметических действий над 2 десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи. Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Алгоритм опи- сывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм. Значение слова алго- ритм очень схоже со значением слов рецепт, процесс, метод, способ. Однако любой алгоритм, в отличие от ре- цепта или способа, обязательно обладает следующими свойствами. 1. Дискретность. Выполнение алгоритма разбивается на последовательность законченных действий - ша- гов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит к исполнению следующего действия. Это свойство алгоритма называется дискретностью. Произвести каждое отдельное действие исполни- телю предписывает специальное указание в записи алгоритма, называемое командой. 2. Детерминированность — на каждом шаге однозначно определено преобразование объектов среды ис- полнителя, полученной на предыдущих шагах алгоритма. Если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат. Замечание. Свойство детерминированности объединяет в себе одновременное выполнение свойств точностии понят- ности. Поясним эти свойства. Точность— запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду надо выполнить следующей. Понятность(для данного исполнителя) — алгоритм не должен содержать предписаний, смысл которых мо- жет восприниматься неоднозначно. Это означает, что одно и то же предписание после исполнения должно давать один и тот же результат. То есть запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем ал- горитма. Алгоритм всегда рассчитан на выполнение "не размышляющего" исполнителя. Рассмотрим известный пример "бытового" алгоритма — алгоритм перехода улицы: "Посмотри налево. Если машины нет — дойди до середины улицы. Если есть — подожди, пока они проедут". И т.д. Представьте себе ситуа- цию: машина слева есть, но она не едет — у нее меняют колесо. Если вы думаете, что надо ждать, то вы поняли этот алгоритм. Если же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредви- денных (по вашему мнению!) обстоятельств, то вы не усвоили понятие алгоритма. 3. Результативность — каждый шаг (и алгоритм в целом) после своего завершения дает среду, в которой все объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сооб- щать, что решение задачи не существует. При точном исполнении команд алгоритма процесс должен прекра- титься за конечное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть и установление того факта, что задача решений не имеет. 4. Конечность — завершение работы алгоритма за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов ос- тается за рамками теории алгоритмов. 5. Массовость — алгоритм правильно работает на некотором множестве исходных данных, которое назы- вается областью применимости алгоритма, т.е. алгоритм пригоден для решения любой задачи из некоторого класса задач. Это свойство не следует понимать как возможность решить много задач. Дадим уточненное понятие алгоритма, которое опять же не является определением в математическом смысле слова, но более формально описывает понятие алгоритма, раскрывающее его сущность. Определение. Алгоритм — это конечная система правил, сформулированная на языке исполнителя, кото- рая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами дискретности, детерминированности, результативности, конечности и массовости. Отметим, что для каждого исполнителя набор допустимых действий всегда ограничен — не может существо- вать исполнителя, для которого любое действие является допустимым. Перефразированное рассуждение И.Канта обосновывает сформулированное утверждение следующим образом: «Если бы такой исполнитель существовал, то среди его допустимых действий было бы создание такого камня, который он не может поднять. Но это противо- речит допустимости действия "Поднять любой камень"». Ограничение над допустимыми действиями означает, что для любого исполнителя имеются задачи, которые нельзя решить с его помощью. 3 Лекция 2. Нестрогое определение алгоритма Понятие алгоритма, в какой-то мере определяемое перечислением свойств 1-5, также нельзя считать строгим, по- скольку в формулировках свойств использованы термины «величина», «способ», «простой», «локальный» и другие, точ- ный смысл которых не установлен. В дальнейшем данное определение будем называть нестрогим (иногда его называют интуитивным) понятием алгоритма. Возникает вопрос: так ли уж важно и необходимо иметь точное определение алгоритма, если и без него возмож- но составление и применение алгоритмов (причем, даже без употребления самого термина)? Тем более что интуитивное понятие алгоритма хотя и не обладало строгостью, но было настолько ясным, что практически до XX в. не возникало ситуаций, когда математики разошлись бы в суждениях относительно того, является ли алгоритмом тот или иной конкретный процесс. Положение существенно изменилось в начале XX в., когда были сформулированы такие пробле- мы, алгоритмическое решение которых было не очевидным. Действительно, для доказательства существования алго- ритма необходимо просто решить данную задачу, пользуясь набором известных приемов, или в их отсутствии пред- ложить новые приемы - в таких ситуациях достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм. Гораздо сложнее доказать факт невозможности построения алгоритма решения некоторой задачи (или класса задач) - без точного определения алгоритма эта проблема теряет смысл. Другим основанием, потребовавшим построения точного определения алгоритма, явилось неопределенность по- нятия «элементарность шага» при выполнении алгоритмических действий. Пока математика изучала числовые объек- ты, действия с ними сводились к некоторой последовательности вычислительных операций, и элементарными счита- лись арифметические операции, а также несколько логических, связанных с проверкой отношений между величинами (равенство, неравенство, больше, меньше и пр.). Однако позднее математика перешла к исследованию свойств и дей- ствий со сложными объектами - векторами, матрицами, множествами, функциями - и понятие элементарности шага алгоритма перестало быть очевидным. Например, можно ли считать элементарным шагом взятие интеграла или транс- понирование матрицы? В тех ситуациях, когда задача допускает построение нескольких алгоритмов решения, с теоретической и с прак- тической точек зрения оказывается существенным вопрос их сопоставления и выбора наиболее эффективного алгоритма, что также невозможно без его строгого определения. Таким образом, возникла необходимость в точном определении понятия «любой алгоритм", т.е. максимально общем определении, под которое подходили бы все мыслимые виды алгоритмов. В 20-е гг. XX в. построение опреде- ления алгоритма стало одной из центральных математических проблем. Определение это, с одной стороны, должно было соответствовать сущности интуитивного понятия алгоритма, а с другой стороны, быть формально строгим. Попытки формулировки такого понятия привели к появлению в 30-х гг. XX века теории алгоритмов как самостоя- тельной науки, которая вместе с математической логикой изучает основные средства математики - методы дока- зательств, способы построения аксиоматических теорий, свойства математических процедур и пр. Когда же в 40-е - 50-е гг. началось бурное развитие вычислительной техники и наук, связанных с ее функционированием и использованием, то выяснилось, что в основе этих наук также должна лежать теория алгоритмов, поскольку компьютер может реализовать только такие процедуры, которые представимы в виде алгоритмов. Любая программа есть ни что иное, как запись алгоритма на языке, который может «понять» исполнитель - компью- тер. Таким образом, с практической точки зрения также представляется важным уточнение понятия алгоритма. Уточнение понятия алгоритма производится в рамках алгоритмических моделей. Модель определяет набор средств, использование которых допустимо при решении задачи, т.е. перечень элементарных шагов, способы опре- деления следующего шага и т.п. Алгоритмические модели могут быть теоретическими и практическими. С тео- ретической точки зрения наибольший интерес представляют модели, которые, с одной стороны, были бы универ- сальными, т.е. позволяли бы описать любой алгоритм, а с другой стороны -максимально простыми, т.е. использо- вали бы минимум средств решения задачи. Требование простоты важно для того, чтобы выделить действительно необходимые элементы и свойства алгоритма и обеспечить доказательство общих утверждений об этих свойствах. В практических и прикладных моделях более значимым является удобство программирования и эффективность вы- числений, поэтому их средства - набор элементарных шагов и пр.- намного богаче и сложнее, что затрудняет теоретический анализ. В теоретических подходах к построению строгого определения понятия алгоритма исторически выделились три основные направления. Первое направление связано с рассмотрением алгоритмов, позволяющих вычислить значение числовых функций, зависящих от целочисленных значений аргументов - такие функции получили название вычислимых. Понятие вычислимой функции не является строгим, как и понятие алгоритма. Однако, благодаря работам А. Черча, К. Геделя, С. Клини, была обоснована тождественность класса всюду определенных вычислимых функ- ций с классом частично рекурсивных функций, который определяется строго. Это позволило свести проблему алгоритмической разрешимости к доказательству возможности (или невозможности) построения рекурсивной функции, решающей задачу. Именно этим путем А. Черчу удалось доказать неразрешимость одной из проблем математической логики - ис- числения истинности предикатов. 4 Второе направление связано с машинной математикой. Основная идея этого направления состоит в том, что алгоритмические процессы - это процессы, которые может совершать соответствующим образом устроенная «машина». В соответствии с этой идеей ими были описаны в точных математических терминах довольно узкие классы машин, однако при этом было доказано, что посредством этих машин можно осуществить или имитиро- вать все алгоритмические процессы, которые фактически когда-либо описывались математиками. Данный под- ход развивался в работах Э. Поста и А. Тьюринга одновременно с упомянутым выше подходом. Доказательство алгоритмической разрешимости задачи сводится к доказательству существования машины, ее решающей. Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным россий- ским математиком А. А. Марковым в начале 50-х гг. XX в. В последующих разделах все три направления будут рассмотрены подробнее. Но прежде чем перейти к этому, хотелось бы отметить то обстоятельство, что строго формализованный подход в определении понятия «ал- горитм» используется лишь непосредственно в самой математической теории алгоритмов, где исследуются об- щие свойства алгоритмов, проводится доказательство алгоритмической разрешимости и пр. В практических же приложениях, в том числе в информатике, строгая формализация может привести к значительному усложнению задачи; в то же время, можно указать ряд ситуаций, в которых допустимо отступление от нее. 1. Применение исполнителей, способных выполнять сложные команды. Определение термина «исполни- тель алгоритма» достаточно очевидно: Исполнитель алгоритма - это субъект или устройство способные правильно интерпретировать описа- ние алгоритма и выполнить содержащийся в нем перечень действий. Указания по выполнению действий для каждого исполнителя формулируются посредством некоторого языка, включающего набор служебных слов, обозначающих действия (команды), а также синтаксические правила их объединения. Совокупность допустимых команд образует систему команд исполнителя (СКИ). Различаться СКИ разных исполнителей могут детальностью описания действий. Как будет показано ниже, элемен- тарным (простейшим) действием при обработке дискретной информации является замена одного знака другим. Од- нако можно построить абстрактное или реальное устройство, которое будет способно выполнять целую цепочку по- добных элементарных действий по заложенному в него правилу - некое комплексное (интегральное) действие. При построении алгоритма для такого исполнителя разработчику достаточно указать последовательность интегральных команд, а их преобразование в цепочку истинно элементарных шагов будет производиться самим исполнителем. Та- кая «многоступенчатая» алгоритмизация широко применяется при управлении компьютером. Истинно элементарными следует считать действия процессора (хотя их общее число у современных процессоров достигает нескольких сотен и даже тысяч) - их называют машинными командами, а их обозначения - машинными ко- дами. Первым (низшим) уровнем, на котором происходит отход от машинных кодов, является код ассемблера - внут- ренний (т.е. аппаратно-зависимый) язык. Объединения элементарных действий в сложные команды на этом уровне еще не происходит и общее количество команд ассемблера совпадает с числом команд процессора, однако, ис- пользуется символьная форма представления машинных кодов и регистров процессора - мнемоники, что удобнее для пользователя, чем двоичный машинный код. Перевод мнемоник в машинные команды осуществляет программа - ассемблер; именно с ней имеет дело про- граммист как с исполнителем. Команды, объединяющие ряд элементарных действий, появляются в языках программиро- вания высокого уровня, например, в тексте программы достаточно написать «Write», а уже транслятор языка переведет ее в последовательность элементарных шагов: прерываний, пересылок и пр. По отношению к программисту исполните- лем в этом случае оказывается транслятор языка программирования. Еще большую степень интеграции элементарных команд может обеспечить прикладная программа, которая является исполнителем по отношению к конечному пользо- вателю. СКИ такого исполнителя включает все команды управления, представленные в виде меню, экранных кнопок, окон настройки и других элементов интерфейса. Использование одной команды может вызвать цепочку сложных дей- ствий, например, выравнивание многих строк текста. Таким образом, при записи алгоритмов возможны ситуации, когда язык представления алгоритма является фор- мальным, но в нем используются сложные команды, которые самим исполнителем переводятся на уровень ис- тинно элементарных действий. 2. Допустимость нестрогой формализации представления алгоритмов, если исполнителем является че- ловек. Человек обладает собственным мышлением и знаниями, опираясь на которые он может компенсировать неточности алгоритма, выполнить действия и добиться результата. Подобные алгоритмы следует считать еще менее строгими, чем те, что были рассмотрены в начале параграфа, поскольку они, как правило, не обладают всеми перечисленными свойствами. Примерами могут служить кулинарные рецепты, инструкции по приме- нению бытовых приборов, алгоритмы решения школьных задач. 3. Расширение применимости понятия алгоритма на последовательность любых дискретных действий. По определению алгоритм должен быть обязательно связан с обработкой дискретной информации. Однако этот же термин используется и для обозначения действий по управлению исполнителем, напрямую не производящим преобразование информации. Например, в школьном курсе информатики широко применяются учебные испол- нители «Чертежник», «Паркетчик», «Черепашка», СКИ которых включает перемещение по экрану и выполне- ние некоторых операций («начертить линию», «положить плитку» и т.п.). То же относится к инструкциям 5 по управлению какими-либо агрегатами и устройствами. Лекция 3. Виды алгоритмов. Способы записи алгоритмов Способы записи алгоритмов При изучении алгоритмов важно осознать, что существует много разных возможностей для представления (описания) одного и того же алгоритма: • текстовая форма записи; • запись в виде блок-схемы; • псевдокоды; • запись алгоритма на каком-либо алгоритмическом языке; • представление алгоритма в виде машины Тьюринга или машины Поста. Кроме того, если задача имеет алгоритмическое решение, то всегда можно придумать множество различ- ных способов ее решения, т.е. различных алгоритмов. Однако в практике человека возникают задачи, которые он, вообще говоря, умеет решать, не зная при этом алгоритма их решения. Пример 5. Перед человеком лежат фотографии, на которых изображены только кошки и собаки. Человек должен определить, кошка или собака снята на конкретной фотографии. Человек решает эту задачу на интуитив- ном уровне. Формализация этой задачи чрезвычайно сложна и практически невозможна. Способ записи алгоритма зависит от нескольких причин. Если для вас наиболее важна наглядность записи алгоритма, то разумно записать алгоритм в виде блок-схемы. Если алгоритм небольшой, то его можно записать в текстовой форме. При этом команды могут быть пронумерованы или записаны в виде сплошного текста. Во втором случае команды разделяются либо точкой, либо точкой с запятой. При таком оформлении алгоритма исполнитель выполняет команды в порядке их естественного следования в тексте. Такая форма записи алгоритма хороша в случае, когда алгоритм небольшой или когда для описания алгоритма отводится мало места. Недостат- ком такого оформления является его малая наглядность. На практике наиболее распространены следующие формы представления алгоритмов: • словесная (записи на естественном языке); • графическая (изображения из графических символов); • псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включа- ющие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математи- ческие обозначения и др.); • программная (тексты на языках программирования). Словесный способ записи алгоритмов Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел. Алгоритм может быть следующим: 1. задать два числа; 2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3. определить большее из чисел; 4. заменить большее из чисел разностью большего и меньшего из чисел; 5. повторить алгоритм с шага 2. Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставлен- ной задачи. Убедитесь в этом самостоятельно, определив с помощью этого алгоритма наибольший общий дели- тель чисел 125 и 75. Словесный способ не имеет широкого распространения по следующим причинам: • такие описания строго не формализуемы; • страдают многословностью записей; • допускают неоднозначность толкования отдельных предписаний. Графический способ записи алгоритмов Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между со- бой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий, и называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, провер- ке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фи- 6 гура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяю- щими очередность выполнения действий. В таблице приведены наиболее часто употребляемые символы. Название символа Обозначение и пример заполнения Пояснение Процесс Вычислительное действие или последовательность действий Решение Проверка условий Модификация Начало цикла Предопреде- ленный про- цесс Вычисления по стандартной подпрограмме Ввод-вывод Ввод-вывод в общем виде Пуск-останов Начало, конец алгоритма, вход и выход в подпрограмму Документ Вывод результатов на печать Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдель- ных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно. Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «реше- ние» должны быть указаны вопрос, условие или сравнение, которые он определяет. Блок «модификация» используется для организации циклических конструкций. Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения. Блок «предопределенный процесс» используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным под- программам. Псевдокод Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записы- ваться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные кон- струкции и математическая символика, что приближает запись алгоритма к общепринятой математической запи- си. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным язы- кам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более ши- рокий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некото- 7 рые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алго- ритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные сло- ва, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукопис- ном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возмож- ны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций. Напри- мер, алг (алгоритм), лог (логический). Общий вид алгоритма: алг название алгоритма (аргументы и результаты) дано условия применимости алгоритма надо цель выполнения алгоритма нач описание промежуточных величин последовательность команд (тело алгоритма) кон Программный способ записи алгоритмов При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компью- теры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера. |