Презентация по информатике "Определение и свойства алгоритма"

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

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

Верно, ли что

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

Налить воду в чайник

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

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

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

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

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

Исполнитель

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

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

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

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

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

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

Учебный алгоритмический язык (УАЯ) Общий вид программы алг <название алгоритма> нач команда № 1 команда № 2 … команда № n кон Налить воду в чайник

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

алг Кипяток нач

кон

Телефонный справочник: Телефонный справочник: Ф.И.О. / номер телефона Телефонный справочник: Ф.И.О. / адрес / номер телефона Только имея полный набор данных, можно точно решить задачу.

• Исходные данные

Определение

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

Определение

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

Задача Определить исполнителя, команды, которые может выполнять исполнитель (СКИ), исходные данные и результат. Составить алгоритм на УАЯ. Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного “пассажира”. В каком порядке старик перевезет пассажиров? Не забудь, что волк может съесть козу, а коза – капусту. Решение

	Левый берег	Способ действия	Правый берег
Исходное состояние	Старик, Волк, Коза, Капуста
1 шаг	Волк, Капуста	→ Старик, Коза
2 шаг	Волк, Капуста	← Старик	Коза
3 шаг	Капуста	→ Старик, Волк	Коза
4 шаг	Капуста	← Старик, Коза	Волк
5 шаг	Коза	→ Старик, Капуста	Волк
6 шаг	Коза	← Старик	Волк, Капуста
7 шаг		→ Старик, Коза	Волк, Капуста
Результат			Старик, Волк, Коза, Капуста

Решение Алгоритм на УАЯ алг переправа нач перевезти козу на берег В перевезти волка на берег В перевезти козу на берег А перевезти капусту на берег В переправиться на берег А перевести капусту на берег В кон