Переборные алгоритмы Автор: Басангова Е.О., преподаватель ГОУ ВПО Калмыцкий госуниверситет. - презентация

1 Переборные алгоритмы Автор: Басангова Е.О., преподаватель ГОУ ВПО Калмыцкий госуниверситет

2 Переборные алгоритмы 2 Информатика, класс Ознакомление с методами выбора оптимального решения, с понятием переборного алгоритма.

3 Переборные алгоритмы 3 КАК ПРИНЯТЬ ПРАВИЛЬНОЕ РЕШЕНИЕ ? использовать опыт других людей? интуитивно Использовать алгоритмы ?

4 Переборные алгоритмы 4 Сенека Для корабля, который не знает куда плыть, нет попутного ветра.

5 Переборные алгоритмы 5 Задача имеет n вариантов возможных решений. Как найти и выбрать лучшее? Можно найти алгоритм улучшенного ПЕРЕБОРА, когда конструируется сразу наилучшее решение Один способ есть всегда - перебрать ВСЕ варианты.

6 Переборные алгоритмы 6 Как сформулировать понятие "хорошее решение"? Чем хорошее решение отличается от плохого? Как можно найти "хорошее" решение, если допустимых решений конечное число? Почему метод полного перебора всех решений для нахождения наилучшего невыгодно использовать? Можно ли ускорить метод полного перебора? Направляющие вопросы

7 Переборные алгоритмы 7 Работа по группам Группа разработчиков модели Группа историков Группа, демонстрирующая работу алгоритма Группа, демонстрирующая работу алгоритма

8 Переборные алгоритмы 8 Построить схему возможных маршрутов из пункта А в пункт В:схему Группа 1: «разработчики модели» АВ школа стадион «Уралан» площадь Ленина Сити-Чесс пример назад

9 Переборные алгоритмы 9 1) А: школа, В: стадион «Уралан» Модель задачи А В Пример решения А В Схема города

10 Переборные алгоритмы 10 Собрать сведения об авторах алгоритмов улучшенного перебора: Группа 2: «историки» задача автор Нахождение минимального дерева Р.Прим Д.Краскал Нахождение кратчайшего пути Э.Дейкстра назад

11 Переборные алгоритмы 11 Создать презентацию, показывающую на примере работу алгоритма Дейкстры (нахождения кратчайшего пути): Группа 3: «демонстраторы алгоритма» назад

12 Переборные алгоритмы 12 найти кратчайший путь из вершины 1 в вершину 6 методом перебора Задание для всех групп:

13 Переборные алгоритмы 13 Представление результатов исследований Результаты Коды программ Презентации ПубликацииВикистатьи Сайт Аннотированные ссылки Карты знаний