Понятие алгоритма. Виды алгоритмов и их свойства.. - презентация

1 Понятие алгоритма. Виды алгоритмов и их свойства.

2 Повседневные задачи " Мы редко до конца понимаем, чего мы в действительности хотим" Франсуа де Ларошфуко 1. Приготовление завтрака 2. Решение квадратного уравнения 3. Определение рода существительного

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

4 Первый алгоритм ЕВКЛИД (расцвет деятельности около 300 до н.э.), также Эвклид, древнегреческий математик, известный прежде всего как автор «Начал», самого знаменитого учебника в истории.ЕВКЛИД (расцвет деятельности около 300 до н.э.), также Эвклид, древнегреческий математик, известный прежде всего как автор «Начал», самого знаменитого учебника в истории.

5 Происхождение слова «алгоритм» В IX веке жил Ал-Хорезми сын зороастрийского жреца, прозванный за это ал-Маджуси (маг). Заведовал библиотекой «Дома мудрости», изучал индийские и греческие знания. В IX веке жил Ал-Хорезми сын зороастрийского жреца, прозванный за это ал-Маджуси (маг). Заведовал библиотекой «Дома мудрости», изучал индийские и греческие знания. Ал-Хорезми написал книгу Ал-Хорезми написал книгу «Об индийском счёте», способствовавшую популяризации позиционной системы во всём Халифате, вплоть до Испании. В XII веке эта книга переводится на латинский, от имени её автора происходит наше слово «алгоритм» «Об индийском счёте», способствовавшую популяризации позиционной системы во всём Халифате, вплоть до Испании. В XII веке эта книга переводится на латинский, от имени её автора происходит наше слово «алгоритм»

6 Верно ли, что… 1.Налить воду в чайник 2.Открыть кран газовой горелки 3.Поставить чайник на плиту 4.Ждать, пока вода закипит 5.Поднести спичку к горелке 6.Зажечь спичку 7.Выключить газ

7 Верно, что… 1.Налить воду в чайник 2.Поставить чайник на плиту 3.Зажечь спичку 4.Открыть кран газовой горелки 5.Поднести спичку к горелке 6.Ждать, пока вода закипит 7.Выключить газ

8 Свойства алгоритма дискретность: состоит из отдельных шагов (команд)дискретность: состоит из отдельных шагов (команд) результативность: применение алгоритма обязательно приводит к конечному результату за конечное число шаговрезультативность: применение алгоритма обязательно приводит к конечному результату за конечное число шагов массовость: может применяться многократно при различных исходных данныхмассовость: может применяться многократно при различных исходных данных детерминированность: выполнение команд в строго определенной последовательностидетерминированность: выполнение команд в строго определенной последовательности понятность: должен включать только команды, известные исполнителю (входящие в СКИ)понятность: должен включать только команды, известные исполнителю (входящие в СКИ) определенность: при одинаковых исходных данных всегда выдает один и тот же результатопределенность: при одинаковых исходных данных всегда выдает один и тот же результат корректность: дает верное решение при любых допустимых исходных данныхкорректность: дает верное решение при любых допустимых исходных данных

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

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

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

12 Исполнитель алгоритма Исполнитель алгоритма – это человек, животное или устройство способные выполнять определенный набор команд.Исполнитель алгоритма – это человек, животное или устройство способные выполнять определенный набор команд. Набор команд – СКИ (Система Команд Исполнителя).Набор команд – СКИ (Система Команд Исполнителя). Алгоритм составляют с ориентацией на определенного исполнителя:Алгоритм составляют с ориентацией на определенного исполнителя: …формального или неформального?

13 Задача 2 Выполните предложенные действия.Выполните предложенные действия. 1.Задумайте целое число от 1 до Прибавьте к нему 2. 3.Результат умножьте на 2. 4.К полученному произведению прибавьте 3. 5.От суммы отнимите задуманное число. 6.К разности прибавьте 5. 7.От суммы отнимите задуманное число. 8.Сообщите ответ. Ответ: 12; мы выступали в роли формального исполнителя

14 Задача 3 Какому исполнителю под силу решить такую задачу: «Отгадай пословицу, обойдя поле ходом шахматного коня»?Какому исполнителю под силу решить такую задачу: «Отгадай пословицу, обойдя поле ходом шахматного коня»? НА ЕШ ИЛ ГЬ ЁИ Т РК АУ Ответ: Не игла шьёт, а руки а руки A B C D E F G H Неформальный исполнитель

15 Способы записи алгоритмов Словесный – на естественном языке;Словесный – на естественном языке; На языке блок – схем;На языке блок – схем; На языке программирования.На языке программирования. Блок-схема – это графическое изображение алгоритма в виде определенным образом связанных между собой нескольких типов блоков. Язык программирования формальная знаковая система, предназначенная для записи компьютерных программ.

16 Существует 4 вида алгоритмов: линейный, циклический, разветвляющий, вспомогательный Виды алгоритмов

17 Линейный алгоритм Линейный алгоритм – это набор команд, выполняемых последовательно во времени, друг за другом.Линейный алгоритм – это набор команд, выполняемых последовательно во времени, друг за другом.

18 Алгоритмическая структура «ветвление» Алгоритм, содержащий хотя бы одно условие, в результате которого обеспечивается переход на один из двух возможных шагов, называется разветвляющимся.Алгоритм, содержащий хотя бы одно условие, в результате которого обеспечивается переход на один из двух возможных шагов, называется разветвляющимся.

19 Алгоритмические структуры Какие алгоритмические структуры изображены на рисунках? Вставьте пропущенные слова: 2. Алгоритм, в котором команды выполняются последовательно друг за другом, называется… 1. Алгоритм – это последовательность… 3. Алгоритмическая структура выполняющая выбор при истинности или ложности условия называется …

20 Алгоритмическая структура «цикл» В алгоритмической структуре «цикл» серия команд (тело цикла) выполняется многократно. Циклические алгоритмические структуры бывают двух типов: 1.Цикл со счетчиком, в котором тело цикла выполняется определенное количество раз; 2.Цикл с условием, в котором тело цикла выполняется пока истинно условие. Такая последовательность команд называется «телом цикла».