Определение и свойства алгоритма

• Само слово «алгоритм» происходит от имени средневекового ученого аль Хорезми.
• Родился в 783 году.
• Первый известный арабский трактат по алгебре.
• Algorithmi – латинское написание имени аль-Хорезми.

• Налить воду в чайник
• Открыть кран газовой горелки
• Поставить чайник на плиту
• Ждать, пока вода не закипит
• Поднести спичку к горелке
• Зажечь спичку
• Выключить газ

• Налить воду в чайник
• Поставить чайник на плиту
• Зажечь спичку
• Открыть кран газовой горелки
• Поднести спичку к горелке
• Ждать, пока вода не закипит
• Выключить газ

Исполнитель – это объект, выполняющий алгоритм .

Исполнителем может быть человек, робот, животное, компьютер.

Система команд исполнителя (СКИ) – это перечень команд, которые исполнитель может выполнять.

Среда исполнителя – обстановка, в которой функционирует исполнитель.

• Дискретность.
• Понятность.
• Точность.
• Конечность.

Процесс решения задачи должен быть разбит на последовательность отдельно выполняемых шагов

Алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в систему команд исполнителя

Каждая команда алгоритма должна определять однозначное действие исполнителя

Исполнение алгоритма должно завершиться за конечное число шагов

Общий вид программы

алг

нач

команда № 1

команда № 2

…

команда № n

• команда № 1 команда № 2 … команда № n
• команда № 1 команда № 2 … команда № n

кон

• кон

• Налить воду в чайник
• Поставить чайник на плиту
• Зажечь спичку
• Открыть кран газовой горелки
• Поднести спичку к горелке
• Ждать, пока вода не закипит
• Выключить газ

Телефонный справочник:

Ф.И.О. / номер телефона

Телефонный справочник:

Ф.И.О. / адрес / номер телефона

Только имея полный набор данных, можно точно решить задачу.

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

• Программа – алгоритм, записанный на языке исполнителя.

Определить исполнителя, команды, которые может выполнять исполнитель (СКИ), исходные данные и результат. Составить алгоритм на УАЯ.

Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного “пассажира”. В каком порядке старик перевезет пассажиров? Не забудь, что волк может съесть козу, а коза – капусту.

Левый берег

Исходное состояние

Старик, Волк, Коза, Капуста

Способ действия

1 шаг

Правый берег

Волк, Капуста

2 шаг

Волк, Капуста

3 шаг

→ Старик, Коза

Капуста

4 шаг

← Старик

Коза

Капуста

→ Старик, Волк

5 шаг

6 шаг

Коза

Коза

← Старик, Коза

Волк

Коза

→ Старик, Капуста

7 шаг

Волк

Результат

← Старик

Волк, Капуста

→ Старик, Коза

Волк, Капуста

Старик, Волк, Коза, Капуста

алг переправа

нач

перевезти козу на берег В

перевезти волка на берег В

перевезти козу на берег А

перевезти капусту на берег В

переправиться на берег А

перевести капусту на берег В

кон

• перевезти козу на берег В перевезти волка на берег В перевезти козу на берег А перевезти капусту на берег В переправиться на берег А перевести капусту на берег В кон
• перевезти козу на берег В перевезти волка на берег В перевезти козу на берег А перевезти капусту на берег В переправиться на берег А перевести капусту на берег В кон