Презентация на тему: Теория алгоритмов

АЛГОРИТМЫ

* * Алгоритм – это последовательность действий, которые должен выполнить исполнитель для достижения конкретной цели. Алгоритм содержит несколько шагов. Шаг – отдельное законченное действие.

* * Исполнитель - это объект, умеющий выполнять определенный набор действий. (человек, животное, робот, компьютер). Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять. Среда исполнителя – обстановка, в которой функционирует исполнитель.

* * Свойства алгоритма Дискретность (прерывность, раздельность) – разбиение алгоритма на шаги; Понятность – каждый шаг алгоритма должен быть понятен исполнителю; Точность - указание последовательности шагов; Результативность - получение результата за конечное число шагов; Массовость – использование алгоритма для решения однотипных задач.

* * Задание Назови исполнителей следующих видов работ: уборка мусора во дворе; обучение детей в школе; вождение автомобиля; ответ у доски; приготовление пищи; печатание документа на принтере. Сформулируй СКИ для каждого из этих исполнителей, назови среду каждого исполнителя.

* * Способы описания алгоритма: Словесный (письменно или устно); Графический (стрелками, рисунками, блок – схемами); Программный.

* * Задание Составь алгоритм сбора портфеля. Продумай СКИ. _____________________________________________________________ _____________________________________________________________ _____________________________________________________________ _____________________________________________________________ Способ описания ________________________ Число шагов ____________________________ Исполнитель ___________________________ Среда исполнителя ______________________

* * Задание Пройди по заданному стрелками пути: ↑ ↑ ↓↓ ↑↑ ↓ ↓ ↓ ↓ ↓ ↑↑ ↓↓ ↑ ↑ ↑ Продумай СКИ. Способ описания ________________________ Число шагов ____________________________ Исполнитель ___________________________ Среда исполнителя ______________________

* * Задание (д/з) Напиши алгоритм приготовления любого блюда. _______________________________________ _______________________________________ _______________________________________ Способ описания ________________________ Число шагов ____________________________ Исполнитель ___________________________ Среда исполнителя ______________________

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

* * Задача. Переправа. К берегу реки, где была лодка, вмещающая только двух человек, подошли два разбойника и два путешественника. Разбойники не решались напасть на путешественников. В случае если на берегу останется один путешественник и два разбойника, они нападут на него. Как надо переправиться через реку разбойникам и путешественникам, чтобы последние смогли избежать нападения? Обозначения: П1 – первый путешественник П2 – второй путешественник; Р1 – первый разбойник; Р2 – второй разбойник.

* * № Первый берег Второй берег Нач. П1 П2 Р1 Р2 1 П2 Р2 П1 Р1 П2 Р2 П1 Р1 2 П2 Р2 П1 Р1 П1 П2 Р2 Р1 3 Р2 П1 П2 Р1 Р2 П1 П2 Р1 4 Р2 Р1 П1 П2 Р1 Р2 П1 П2 5 Р1 Р2 Р1 Р2 П1 П2 Кон. П1 П2 Р1 Р2

* * Виды алгоритмов: Линейный – содержит несколько шагов и все шаги выполняются последовательно друг за другом; Разветвляющийся – порядок выполнения шагов изменяется в зависимости от некоторых условий; Циклический – определенная последовательность шагов повторяется несколько раз в зависимости от заданной величины (параметра цикла).

* * Задание. Найдите произведение произвольных чисел А и В. Этот алгоритм будет _______________ , потому что он содержит _____ шага, которые выполняются ______________ друг за другом от ______ до _____. Исполнитель ______________________ Среда исполнителя _________________

* * Задание. Найдите произведение произвольных чисел А и В. Этот алгоритм будет линейным , потому что он содержит 3 шага, которые выполняются последовательно друг за другом от начала до конца. Исполнитель ученик Среда исполнителя класс

* * Задание. Составь алгоритм перехода на другую сторону улицы на перекрестке со светофором. Шаги алгоритма Горит зелёный свет? Посмотреть на сигнал светофора; Перейти улицу; Подойти к перекрестку; Дождаться, зажжется зеленый свет. Этот алгоритм будет ____________, потому что порядок выполнения шагов _________ в зависимости от __________ Исполнитель __________________________ Среда исполнителя _____________________

* * Задание. Составь алгоритм перехода на другую сторону улицы на перекрестке со светофором. Шаги алгоритма Горит зелёный свет? Посмотреть на сигнал светофора; Перейти улицу; Подойти к перекрестку; Дождаться, зажжется зеленый свет. Этот алгоритм будет разветвляющимся, потому что порядок выполнения шагов происходит в зависимости от выполнения условия Исполнитель пешеход Среда исполнителя улица (перекресток)

* * Задание. Составь алгоритм работы автомата по продаже банок «Pepsi». Шаги: Посмотреть цену; Опустить монету; Подойти к автомату; Набралась нужная сумма; Достать деньги; Взять банку; Нажать кнопку. Этот алгоритм будет _______, потому что ______ шаги повторяются ____________ в зависимости от _________________________________________ Исполнитель __________________________________ Среда исполнителя ____________________________

* * Задание. Переправа. (д/з) Два мальчика и двое взрослых должны переправиться на другую сторону реки на плоту, который выдерживает либо двух мальчиков, либо одного мальчика и одного взрослого. Как осуществить переправу? Найди несколько способов решения этой задачи. Обозначения: 1м – один мальчик; 2м – два мальчика; 1в – один взрослый.

* * Способ описания ________________________ Число шагов ____________________________ Исполнитель ___________________________ Среда исполнителя ______________________ 1 способ 2 способ 3 способ 1 шаг 2 шаг 3 шаг 4 шаг 5 шаг