Определение и свойства алгоритма
Определение и свойства алгоритма
Из истории Само слово «алгоритм» происходит от имени средневекового ученого аль
Из истории
Само слово «алгоритм» происходит от имени средневекового ученого аль Хорезми.
Родился в 783 году.
Первый известный арабский трактат по алгебре.
Algorithmi – латинское написание имени аль-Хорезми.
Налить воду в чайник Открыть кран газовой горелки
Налить воду в чайник
Открыть кран газовой горелки
Поставить чайник на плиту
Ждать, пока вода не закипит
Поднести спичку к горелке
Зажечь спичку
Выключить газ
Верно, ли что
Налить воду в чайник Поставить чайник на плиту
Налить воду в чайник
Поставить чайник на плиту
Зажечь спичку
Открыть кран газовой горелки
Поднести спичку к горелке
Ждать, пока вода не закипит
Выключить газ
Исполнитель – это объект, выполняющий алгоритм
Исполнитель – это объект, выполняющий алгоритм.
Исполнителем может быть человек, робот, животное, компьютер.
Система команд исполнителя (СКИ) – это перечень команд, которые исполнитель может выполнять.
Среда исполнителя – обстановка, в которой функционирует исполнитель.
Исполнитель
Свойства алгоритма Дискретность
Свойства алгоритма
Дискретность.
Понятность.
Точность.
Конечность.
Процесс решения задачи должен быть разбит на последовательность отдельно выполняемых шагов
Алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в систему команд исполнителя
Каждая команда алгоритма должна определять однозначное действие исполнителя
Исполнение алгоритма должно завершиться за конечное число шагов
Учебный алгоритмический язык (УАЯ)
Учебный алгоритмический язык (УАЯ)
Общий вид программы
алг <название алгоритма>
нач
команда № 1
команда № 2
…
команда № n
кон
Налить воду в чайник Поставить чайник на плиту
Налить воду в чайник
Поставить чайник на плиту
Зажечь спичку
Открыть кран газовой горелки
Поднести спичку к горелке
Ждать, пока вода не закипит
Выключить газ
алг Кипяток нач
кон
Телефонный справочник: Ф.И.О. / номер телефона
Телефонный справочник:
Ф.И.О. / номер телефона
Телефонный справочник:
Ф.И.О. / адрес / номер телефона
Только имея полный набор данных, можно точно решить задачу.
Исходные данные
Определение Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату
Определение
Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
Определение Программа – алгоритм, записанный на языке исполнителя
Определение
Программа – алгоритм, записанный на языке исполнителя.
Задача Определить исполнителя, команды, которые может выполнять исполнитель (СКИ), исходные данные и результат
Задача
Определить исполнителя, команды, которые может выполнять исполнитель (СКИ), исходные данные и результат. Составить алгоритм на УАЯ.
Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного “пассажира”. В каком порядке старик перевезет пассажиров? Не забудь, что волк может съесть козу, а коза – капусту.
Решение Левый берег Способ действия
Решение
Левый берег | Способ действия | Правый берег | |
Исходное состояние | Старик, Волк, Коза, Капуста | ||
1 шаг | Волк, Капуста | → Старик, Коза | |
2 шаг | ← Старик | Коза | |
3 шаг | Капуста | → Старик, Волк | |
4 шаг | ← Старик, Коза | Волк | |
5 шаг | Коза | → Старик, Капуста | |
6 шаг | ← Старик | Волк, Капуста | |
7 шаг | → Старик, Коза | ||
Результат | Старик, Волк, Коза, Капуста | ||
Решение Алгоритм на УАР алг переправа нач перевезти козу на берег
Решение Алгоритм на УАР
алг переправа
нач
перевезти козу на берег В
перевезти волка на берег В
перевезти козу на берег А
перевезти капусту на берег В
переправиться на берег А
перевести капусту на берег В
кон
© ООО «Знанио»
С вами с 2009 года.
