Получите свидетельство
Вход
В начале урока давайте вспомним, что такое алгоритм.
Алгоритм – это строгий порядок правил, которые определяют последовательность шагов обработки информации.
Ранее говорилось о том, что люди хотели создать машину, которая будет исполнять формальный алгоритм без помощи человека.
Для создания такой машины необходимо было выполнить некоторые условия: соответствие техническим требованиям; доскональное изучение работы алгоритма для обработки информации; разработка формализованного способа представления таких алгоритмов.
На этом уроке мы познакомимся с моделями алгоритмических машин в теории алгоритмов, а также вспомним свойства алгоритма.
Само понятие алгоритма исследовалось и совершенствовалось на протяжении многих лет. Но несмотря на все усилия, строгого определения понятия «алгоритм» не было. Поэтому начали появляться различные определения алгоритма. Но в тоже время все они были равнозначными.
Например, Андрей Николаевич Колмагоров, русский советский математик предложил следующее определение: алгоритм – это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
А вот Андрей Андреевич Марков, советский математик, дал следующее определение для алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Несмотря на то, что было много вариаций определения алгоритма, все они сводились к одним и тем же требованиям:
· алгоритм должен содержать конечное количество простых для выполнения команд, то есть удовлетворять требованию конечности записи;
· алгоритм должен выполнять конечное количество шагов при решении задачи, то есть удовлетворять требованию конечности действий;
· алгоритм должен быть единым для всех допустимых исходных данных, то есть удовлетворять требованию универсальности;
· алгоритм должен приводить к правильному по отношению к поставленной задачи решению, то есть удовлетворять требование правильности.
В 1930-х гг. возникает новая наука – теория алгоритмов. Она занимается изучением алгоритмов. Главным толчком для этого была работа Курта Гёделя, австрийского логика, математика и философа математики.
Он сформулировал и доказал теоремы о неполноте. Его работы были опубликованы в 1931 году. В теореме о неполноте символических логик было показано, что некоторые математические проблемы не могут быть решены при помощи алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма.
Основной вопрос, на который ищет ответ теория алгоритмов таков: для всякой ли задачи обработки информации может быть построен алгоритм решения? Для того, чтобы найти ответ на этот вопрос нужно было изначально договориться об исполнителе, на которого будет ориентирован алгоритм.
Алан Тьюринг, английский математик, логик, криптограф, предложил в качестве исполнителя машину Тьюринга.
Машина использовалась для расшифровки сообщений. На основе открытого текста (стандартные отрывки текста, значение которых известно аналитику), машина Тьюринга искала возможные настройки, использованные для шифрования сообщений. Она производила ряд логических предположений, основываясь на открытом тексте, а затем находила противоречия, отбрасывала набор параметров и переходила к следующему. Таким образом, большая часть всевозможных наборов отсеивалась и для более тщательного анализа оставалось всего несколько вариантов. В 1940 году была запущена такая первая машина.
В 1936–1937 годах американский математик и логик, Эмиль Пост описал другую модель алгоритмической машины. Она называется машиной Поста.
Можно сказать, что эта машина является более упрощённой версией машины Тьюринга. Работа машины Поста основана на двоичном алфавите. Поэтому она представляет для нас наибольший интерес, так как все компьютеры работают с двоичным алфавитом. Более подробно с этой машиной мы познакомимся чуть позже.
Язык программирования алгоритмических машин представляет собой описание конечного числа простых команд, которые могут быть реализованы в автоматическом устройстве.
Таким образом, система команд исполнителя (СКИ) – это совокупность всех команд языка исполнителя.
Алгоритм управления работой алгоритмической машины – это конечная последовательность команд, с помощью которой машина решает задачу обработки информации.
Для алгоритма управления такой машиной существуют свои требования:
· Дискретность. Этот пункт говорит о том, что исполнитель должен выполнять каждый шаг отдельно от других;
· Понятность. В алгоритме используются только команды СКИ, предназначенные конкретно для этого исполнителя;
· Точность. Каждая команда должна конкретно говорить о действии, которое должен выполнять исполнитель;
· Конечность. Для исполнителя должно быть задано определённое (конечное) число шагов, после выполнения которых должен получится искомый результат.
Рассмотрим пример. Нам необходимо записать алгоритм перемещения исполнителя Робот в клетку с домом. Данному исполнителю доступны три команды: вперёд, налево и направо.
Итак, наш алгоритм будет звучать следующим образом:
· вперёд;
· вперёд;
· вперёд;
· налево;
· вперёд;
· направо;
· вперёд;
· вперёд;
· направо;
· вперёд;
· вперёд;
· налево;
· вперёд;
· вперёд;
· вперёд.
При выполнении этого алгоритма исполнитель Робот дошёл до клетки с домом. В этом алгоритме мы с вами можем увидеть все вышеприведённые требования. Давайте разберёмся.
Дискретность. Исполнитель будет выполнять каждый шаг отдельно от других, так как, например, он не сможет одновременно идти вперёд и выполнять поворот.
Далее идёт критерий «Понятность». То есть в алгоритме должны использоваться только команды, которые поймёт данный исполнитель. Так, например, в нашем случае нельзя было бы использовать команду «Назад», иначе исполнитель бы просто не понял, что мы хотим этим сказать, потому что такой команды в его системе нет по условию.
Следующий пункт «Точность». В нашем алгоритме все действия записаны в том порядке, в котором нужно их выполнять, и записаны конкретные команды для выполнения действий.
И последний критерий «Конечность». У нас задано определённое количество ходов, после выполнения которых исполнитель робот попадёт в клетку, где находится дом.
Таким образом мы можем видеть, что в составленном алгоритме действий соблюдены все требования для управления исполнителем.
Также необходимо различать такие понятия, как команда и шаг.
Команда – это отдельная инструкция в описании алгоритма.
А шаг алгоритма – это отдельное действие, которое исполнитель выполняет по команде.
Давайте разберёмся на примере. Мама попросила Катю помочь собрать ягоды малины.
Девочка взяла корзину и подошла к кусту.
Она срывала ягоду и опускала её в корзину. Так Катя делала до тех пор, пока на кусте не осталось ни одной ягоды.
Из этих ягод сварили варенье.
Записать действия Кати в виде блок-схемы.
Рисуем овал и впишем в него слово начало. Затем будет идти блок процесса. Впишем внутрь первое действие «Взять корзину». Далее снова идёт блок процесса. Впишем в него словосочетание «Подойти к кусту». Затем Катя должна посмотреть есть ли на кусте ягода. Для этого нарисуем блок принятия решения и впишем в него вопрос «Куст с ягодами?». От блока будут идти две стрелки «Да» и «Нет». Если идти по стрелке «Да», то у нас снова будут два блока процесса, в которых будут записаны следующие действия: «Сорвать ягоду», «Положить в корзину», после чего возвращаемся к нашему блоку принятия решения. Катя будет выполнять все эти действия до тех пор, пока куст не опустеет. Тогда в блоке принятия решения с вопросом «Куст с ягодами?» мы получим ответ «Нет». Идём по стрелке, после которой будет идти блок процесса, где будет написано «Сварить варенье». Конец.
У нас получилась блок-схема с циклическим алгоритмом. Мы можем видеть, что если выполнить данную блок-схему для этого рисунка, то число команд у нас будет меньше, чем число шагов, так как действия «Сорвать ягоду» и «Положить в корзину» будут повторяться несколько раз.
Пришла пора подвести итоги урока. Сегодня мы с вами узнали, что в 1930-х годах были предложены две модели алгоритмических машин в теории алгоритмов: машина Тьюринга и машина Поста. Для нас наибольший интерес представляет машина Поста, так как работа этой машины основана на двоичном алфавите.
Также сегодня мы с вами узнали, что любой алгоритм должен обладать следующими свойствами: дискретность (каждый шаг алгоритма выполняется отдельно от других), понятность (в алгоритме используются только команды из СКИ), точность (каждая команда определяет однозначное действие исполнителя), конечность (за конечное число шагов алгоритма получается искомый результат).
10179
