Лекции по "Языкам и методам программирования" (PascalABC)

 

Интуитивное понятие  алгоритма.

Термин «алгоритм» –  транскрипция имени великого узбекского математика Мухаммеда аль-Хорезми (Мухаммеда  из Хорезма, области нынешнего Узбекистана). Мухаммед аль-Хорезми еще в IX веке разработал правила выполнения четырех действий арифметики. Эти правила до сих пор служат простейшими примерами математических алгоритмов.

 Многие годы понятие «алгоритм»  использовалось математиками для  описания правил решения математических  задач. Например, существуют алгоритм  вычисления квадратного корня положительного числа, алгоритм нахождения наибольшего общего делителя двух целых чисел.

Однако не следует считать алгоритм чисто математическим понятием. Каждый из нас с раннего детства, даже не замечая этого, ежедневно решает задачи, для описания которых используется тот или иной алгоритм, сформулированный в виде конечной последовательности однозначных предписаний. Например, чтобы приготовить вкусное блюдо, вы раскрываете поваренную книгу, отыскиваете рецепт (иными словами, алгоритм приготовления) и, следуя его конкретным указаниям (на два стакана муки – 250 г масла, 1 яйцо,…, тесто разрезать на полоски …, в духовке 20—25 минут…), за конечное число шагов решаете поставленную перед собой задачу.

Носителями алгоритмов являются рецептурные  справочники, инструкции по использованию бытовой и технической аппаратуры, медицинские рекомендации, кулинарные книги и многое другое.

В белорусско-русском  терминологическом словаре «Информатика» (авторы Быкодоров Ю.А., Кузнецов А.Т., Павловский А.И., Пономаренко В.К., Морозов А.А.) понятие алгоритма трактуется так: «алгоритм – это конечная последовательность точно сформулированных правил, формальное исполнение которых позволяет за конечное время получить искомый результат, основываясь на варьируемых исходных данных».

Отметим, что все эти фразы  не являются определением алгоритма  в математическом смысле, а лишь отражают интуитивное понятие алгоритма, сложившееся за долгие годы. Из этого определения вытекают все свойства алгоритмов.

Точное определение  понятия алгоритма было разработано в математической логике в 30-40-е годы ХХ века. Примерами могут служить: машина Тьюринга, нормальный алгоритм Маркова, рекурсивные функции и другие. На языке каждой из этих математических теорий можно дать математическое определение алгоритма. Более того, последующая математическая практика показала, что эти определения в некотором смысле эквивалентны.

 

 Эмпирические свойства алгоритмов.

Для решения любой  задачи надо знать, что дано и что  следует получить, т.е. у задачи есть исходные данные (некие объекты) и искомые результаты. Для получения результатов необходимо знать способ решения задачи, т.е. располагать алгоритмом (инструкцией, правилом), в котором указано, какие действия и в каком порядке следует выполнить, чтобы решить задачу (получить искомые результаты).

Рассмотрим ряд присущих всем алгоритмам свойств. Перечисленные ниже свойства алгоритмов являются эмпирическими  свойствами, т.е. свойствами, подмеченными в результате длительной работы с  разнообразными алгоритмами.

1.Выполнение алгоритма разбивается на последовательность законченных действий – шагов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит к исполнению следующего действия. Это свойство алгоритма называется дискретностью. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.

2. Детерминированность – объединяет в себе одновременное выполнение свойств точности и понятности. Поясним эти свойства.

Точность – запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду надо выполнить следующей.

Понятность  – алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Это означает, что одно и то же предписание после исполнения должно давать один и тот же результат. То есть запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма. Алгоритм всегда рассчитан на выполнение «не размышляющего» исполнителя.

Рассмотрим известный  пример «бытового» алгоритма – алгоритм перехода улицы: «Посмотри налево. Если машин нет – дойди до середины улицы. Если есть – подожди, пока они  проедут.» и т.д. Представьте себе ситуацию: машина слева есть, но она не едет – у нее меняют колесо. Если вы думаете, что надо ждать, то вы правильно поняли этот алгоритм. Если  же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредвиденных (по вашему мнению!) обстоятельств, то вы не усвоили понятие алгоритма.

3. Результативность – каждый шаг (и алгоритм в целом) после своего завершения дает среду, в которой все объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует. При точном исполнении команд алгоритма процесс должен прекратиться за конечное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть установление того факта, что задача решений не имеет.

4. Конечность – завершение работы алгоритма за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.

5. Массовость – алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма, т.е. алгоритм пригоден для решения любой задачи из некоторого класса задач. Это свойство не следует понимать, как возможность решить много задач.

 

 

 Понятие исполнителя алгоритма.

Любой алгоритм существует не сам по себе, а предназначен для  определенного исполнителя. Исполнителем будем называть человека или некоторое устройство, которое способно к восприятию и исполнению команд алгоритма. Перечень команд, которые понимает и может исполнить исполнитель, называют системой команд исполнителя.

Любой алгоритм описывается  в командах исполнителя, который  этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.

Отметим, что для каждого  исполнителя набор допустимых действий всегда ограничен – не может существовать исполнителя, для которого любое действие является допустимым. Ограничение над допустимыми действиями означает, что для любого исполнителя имеются задачи, которые нельзя выполнить с его помощью.

 

Способы представления алгоритмов.

В информатике сложились  вполне определенные традиции представления  алгоритмов, которые рассчитаны на разных исполнителей. Если исполнителем является человек, то на первое место  при описании алгоритма выступают  понятность и наглядность. Сюда можно отнести представление алгоритмов в словесной форме, в графической форме, в виде таблиц и т.д. Если же исполнителем алгоритма является некоторый автомат, то на первое место выходит точная формализация записи алгоритма. К таким формам можно отнести представление алгоритмов в виде программ на языках программирования. Рассмотрим каждую из этих форм более подробно.

 

Словесно-формульное описание алгоритма.

 При словесной форме записи алгоритмов форма записи предложений вообще-то не формализуется, т.е. при записи предложений можно использовать как слова, так и математические символы. Однако предложения при такой записи алгоритма нумеруются, чтобы иметь возможность обратиться к нужному предложению. Также смысл предложения должен пониматься однозначно.

Пример. Записать алгоритм перехода улицы без светофора.

Начало.

1.Подойти к краю дороги.

2.Посмотреть налево.

3.Если есть идущие машины, то  пропустить их.

4.Дойти до середины улицы.

5.Посмотреть направо.

6.Если есть идущие машины, то  пропустить их.

7.Дойти до края дороги.

8.Конец.

В этом алгоритме все шаги были записаны только с помощью слов русского языка.

Пример. Найти наибольший общий  делитель целых чисел А и В по алгоритму Евклида.

Начало.

1.Х=А.

2.У=В.

3.Если Х=У, то перейти к  пункту 6.

4.Если  Х>У, то Х=Х-У, иначе У=У-Х.

5.Перейти  к пункту 3.

6.Наибольший  общий делитель чисел А и В равен Х.

7.Конец.

Этот  алгоритм кроме слов русского языка  использует математическую символику.

 

Графический способ представления алгоритмов.

К этому способу относят блок-схемы, граф-схемы, структурограммы. Мы будем рассматривать представление алгоритмов в виде блок-схем. При таком способе представления алгоритма каждый шаг алгоритма представляется геометрической фигурой внутри которой записана команда. Такие геометрические фигуры называются блоками. Для указания порядка исполнения блоков используются стрелки. Таким образом, под блок-схемой будем понимать графическое представление последовательности шагов алгоритма, которое наглядно показывает очередность и взаимосвязь операций, осуществляемых в алгоритме на каждом его шаге. Иначе говоря, блок-схема служит для графического представления структуры алгоритма.

 

Исходные элементы блок-схем

Исходными элементами блок-схемы являются следующие блоки:

1.               

                                                                     

           

Блоки начала и конца изображаются овалами, внутри которых записаны соответствующие  слова. В блок со словом «конец» входит одна стрелка, из блока со словом «начало» выходит одна стрелка.

2.Блоки обмена информацией (информационный блок):

                                                      

 

Блоки обмена информацией  используются для ввода исходных значений, т.е. для процесса, при котором  исполнитель получает исходные данные; и для вывода информации, т.е. когда исполнитель получив результат выдает его для обозрения. В эти блоки входит одна стрелка и выходит одна стрелка.

3.Функциональные блоки  (арифметические):

Внутри функционального блока  обычно записывается операция для вычисления какого-либо значения. Изображается прямоугольником, в который входит одна стрелка и выходит также одна стрелка.

4.Блок проверки условия (логический  блок):

                                                                                                  

                                                                                                          

                                                                                          

                                                                                                            

                                                                                         

                                                                                             

Блок изображается ромбом, в который  входит одна стрелка, а выходят две  стрелки, на которых записаны слова  «Да» и «Нет».Такой блок используется для определения порядка дальнейшего  исполнения алгоритма в зависимости  от истинности или ложности условия. Если условие истинно, то управление передается очередному блоку по стрелке «Да». Если условие ложно, то управление передается блоку по стрелке «Нет». 

5.Блок слияния изображается  кружочком, в который входят  две стрелки, а выходит одна.

                                           

 

 

 

 Базовые  структуры.

Из исходных элементов  можно составить более крупные  кирпичики блок-схем, которые носят  название базовые структуры. Каждая базовая структура имеет свое название и должна состоять из блоков определенного вида. Каждая базовая структура имеет всегда один вход и один выход.

1.Следование. Эта базовая структура может состоять из блоков обмена информацией, функциональных блоков, которые должны следовать один за другим. Такую структуру схематически можно изобразить так:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.Ветвление. Ветвление может быть двух видов:

А) полное ветвление, которое может состоять из блока проверки условия и действий, одно из которых выполняется по стрелке «да», второе – по стрелке «нет». Схематически такую структуру можно представить так: