Практические, проверочные и домашние работы

Тест по теме "Поиск алгоритма минимальной длины для исполнителя" (А.И. Козлов, г. Северобайкальск)

Понятие алгоритма известно в математике давно. Термин происходит от имени великого ученого мусульманского мира - узбека, жителя города Хорезм Абу-Абдуллы-Мухаммеда ибн Мусы аль Маджуса аль Хорезми (VIII-IXв). Его труд "Китаб мухтасар аль джебр ва-л-мукабала" в XII веке был переведен на латынь и стал доступным для европейцев. В нем были изложены правила 4-х арифметических действий над числами в десятичной системе счисления и правила решения уравнений первой степени. Эти правила и были названы в Европе АЛГОРИТМАМИ.
Кстати, в этом же труде впервые был введен и термин АЛГЕБРА (восстановление, перенос отрицательных членов уравнения с изменением знака). Затем понятие алгоритма переместилось в область логики, где появилась теория алгоритмов, изучавшая процесс доказательств или разрешимость и неразрешимость математических задач. Само понятие алгоритма до XX века оставалось не определённым в строгой форме, меняющим свой смысл во времени, часто понимаемым только интуитивно. Но при возникновении перед человеком необходимости создания вычислительных устройств более высокого уровня это понятие обрело свой законченный научный смысл. Это произошло в 1937 году, когда английский математик Алан Тьюринг доказал теоретически возможность построения устройства, осуществляющего алгоритм. Такое абстрактное устройство получило название МАШИНА ТЬЮРИНГА. Аналогичный, но более простой исполнитель алгоритма - МАШИНА ПОСТА. Когда же были созданы первые ЭВМ, понятие алгоритма и теория алгоритмов переместились в новую науку, связанную с этими вычислительными устройствами - информатику.

Алгоритм - это точное описание упорядоченной последовательности действий, приводящей за конечное число шагов к необходимому результату.

Свойства алгоритмов:

1. понятность
2. однозначность
3. дискретность (пошаговость)
4. массовость (универсальность)
5. результативность
6. конечность
7. безошибочность

Очевидно, что предписание "Пойди туда, не знаю куда, принеси то, не знаю что" алгоритмом не является.

В качестве исполнителя алгоритмов в "докомпьютерную" эру подразумевался человек (в крайнем случае, животное - в цирке). Человек постоянно пользуется алгоритмами при решении задач, не задумываясь над этим, машинально (автоматически). Наглядными примерами алгоритмов являются различные инструкции, правила, рецепты. Открывая дверь ключом, никто не размышляет над тем, как это сделать. Но чтобы научить этому другого, придется составить алгоритм. Например, так:

1. Достать ключ.

2. Вставить ключ в замочную скважину.

3. Повернуть ключ против часовой стрелки на 2 оборота.

4. Вынуть ключ.

Этот алгоритм обладает всеми необходимыми свойствами. Но если переставить второе и третье действия, алгоритм тоже можно будет выполнить, но дверь не откроется! Вот почему важен не только набор действий, но и их порядок. Кроме того, в приведённом примере следует обратить внимание на два обстоятельства. Первое не требует пояснений: всякий алгоритм должен иметь имя. Второе состоит в том, что перед выполнением алгоритма задаётся или определяется некоторое начальное состояние, исходные условия алгоритма: открывающий дверь должен находиться перед ней, а не переходить улицу перед подъездом. И ключ также должен находиться под рукой.

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

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

1. словесный;

2. табличный;

3. графический;

4. программа на алгоритмическом языке.

Для словесного представления алгоритма используется естественный язык (пример - любые инструкции, рецепты и т.п.)
С табличным способом представления алгоритма Вы сталкиваетесь в расчетных книжках при плате за квартиру, в бухгалтерских ведомостях, в таблицах инженерных расчетов и т.п.
Графический способ представления алгоритма - это блок-схема (рассмотрим на следующем уроке) является наиболее наглядным. Схема алгоритма состоит из графических блоков.
Программа - изложение алгоритма специально для ЭВМ в понятных ей символах, словах и командах (иначе говоря - языком программирования). Четвёртый способ - единственный 'понятный' компьютеру как автоматическому исполнителю. Первые три служат для понимания решения задачи самим человеком.

В любом алгоритмическом языке (языке программирования) можно выделить четыре основные конструкции (виды алгоритмов):

1. линейный алгоритм (образование последовательности из нескольких команд);

2. алгоритм ветвления (выбор одной или нескольких команд);

3. циклический алгоритм (повторение одной или нескольких команд с заданным количеством повторов или в зависимости от некоторого условия);

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

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

ЗАДАНИЯ:

1. Можно ли создать исполнителя алгоритмов, который может всё?

2. Запишите алгоритм рыбной ловли (или заварки чая).

3. Какими допустимыми командами Вы снабдили бы автомат, заменяющий: а) кассира в магазине; б) дворника; в) охранника; г) директора школы?

4. Имеются два кувшина ёмкостью 3 л и 8 л. Напишите алгоритм для того, чтобы набрать из реки 7 л воды (можно пользоваться только этими кувшинами).

5. (Старинная русская задача). Некий человек должен перевезти в лодке через реку волка, козу и капусту. За один перевоз он может перевезти только кого-то одного. Составьте алгоритм перевоза так, чтобы никто никого не съел.

6. С числом разрешается производить только два действия: умножать на два и стирать последнюю цифру. Составьте алгоритм получения из числа 458 числа 14.
   
   Исполнитель может заменять в слове одну букву на другую так, чтобы новое слово имело смысл. Например: 'слон' - 'слог'. Составьте алгоритм превращения 'мухи' в 'слона'.

Указание учителю. Для выполнения практических работ на Basic-256 рекомендуется использовать версию 0.9.6.56. Под Windows дистрибутив можно скачать здесь. Версия из пакета Альт Линукс 5.0. Школьный к сожалению зависает, да и устарела. Лучше скачать ее здесь и установить в соответствии с инструкцией. Если Вам хочется изучать Pascal, рекомендуем отечественную разработку PascalABC, возможна работа online, т.е. без привязки к ОС. Под Windows дистрибутив можно скачать здесь: PascalABC.NET StandardPack (Setup, 6.1 Mb).

Приложения

И.Г. Семакин и др.  27 [2]

Н.Д. Угринович 4.1.1 [6]

swf Презентация
"Возникновение понятия алгоритм"
(И.Г. Семакин)

Видеоурок
"Понятие алгоритма. Способы записи алгоритма."
(Дмитрий Тарасов)

swf Презентация
"Исполнители алгоритмов"
(И.Г. Семакин)

swf Презентация
"Свойства алгоритма"
(И.Г. Семакин)

pdf Презентация "Алгоритм"

Тренажёры для изучения универсальных исполнителей Поста и Тьюринга (К. Поляков)

Интерактивные материалы к учебнику Л.Л. Босовой