Информатика 11 класс (Урок№7 - Моделировние на графах.)

Информатика 11 класс (Урок№7 - Моделировние на графах.) Цель урока: Получить знания о графах, их видах, свойствах. Задачи урока: Получить навыки преобразования матрицы смежности (табличной формы представления информации) в граф; Сформировать навык построения путей в графе и поиска кратчайшего пути. мы узнаем: Что такое граф, как наглядное средство представления и состава системы. мы научимся: применять графы при решении различных задач; представлять информацию на графах. мы сможем: находить кратчайший путь по графу. На уроке вы узнали: Что такое граф, как наглядное средство представления и состава системы. Как применять графы при решении различных задач. Как представлять информацию на графах. ·Как находить кратчайший путь по графу. Графы делятся на: Неориентированные и ориентированные (когда движение по ребру возможно только в одну сторону). Взвешенные (когда у вершины или у ребра есть вес, отличающий его от другого) и невзвешенные. И другие более сложные графы (мультиграф, псевдограф, изоморфный граф и другие). Кратчайшим путем мы будем называть путь, если вершины соединены минимальным числом ребер (в случае, если граф невзвешенный) сумма ребер, соединяющих эти вершины, минимальна (для взвешенного графа). Существует огромное количество алгоритмов, находящих кратчайший путь и один из них — это алгоритм Дейсктры. Еще один способом нахождения кратчайшего пути может служить «метод динамического программирования».