- Главная
- Разное
- Образование
- Спорт
- Естествознание
- Природоведение
- Религиоведение
- Французский язык
- Черчение
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, фоны, картинки для презентаций
- Экология
- Экономика
Презентация, доклад на тему Решение логических задач с помощью графов
Содержание
- 1. Решение логических задач с помощью графов
- 2. Денеш КенигВенгерский математик в 1936 году впервые
- 3. Основные понятия:Графы – это рисунки, которые состоят из
- 4. Примеры графов:
- 5. Граф вида «Дерево»Данная форма модели применяется тогда,
- 6. Примеры решения задач:Задача 1. У Юры два
- 7. Примеры решения задач:Задача 2. Винни-Пух решил навестить
- 8. Примеры решения задач:Построить граф, используя условия задачи,
- 9. Рассуждения:1. Выстраиваем вспомогательные линии2. Строим граф, используя
- 10. Задача на закрепление:Пятачок решил навестить своих друзей
- 11. Слайд 11
Денеш КенигВенгерский математик в 1936 году впервые ввел термин «граф»Но первая работа по теории графов принадлежала перу великого Леонардо Эйлера и была написана еще в 1736 году
Слайд 1Решение логических задач
с помощью графов
Подготовил:
Учитель информатики МБОУ «ЦО №34»
Титова Галина Юрьевна
Слайд 2Денеш Кениг
Венгерский математик
в 1936 году впервые ввел
термин «граф»
Но первая
работа по теории графов принадлежала перу великого Леонардо Эйлера и была написана еще в 1736 году
Слайд 3Основные понятия:
Графы – это рисунки, которые состоят из точек и линий, соединяющих
эти точки.
Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками.
Точки называются вершинами графа, а линиями рёбрами.
Ребро может иметь направление, которое указывается стрелочкой.
У графа обязательно есть вершины.
Граф без рёбер называется пустым.
Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками.
Точки называются вершинами графа, а линиями рёбрами.
Ребро может иметь направление, которое указывается стрелочкой.
У графа обязательно есть вершины.
Граф без рёбер называется пустым.
Слайд 5Граф вида «Дерево»
Данная форма модели применяется тогда, когда элементы моделируемого объекта
находятся в состоянии какого-либо подчинения и соподчинения, когда есть отношение иерархичности.
Примеры графов вида «Дерево»
Слайд 6Примеры решения задач:
Задача 1.
У Юры два автомобиля, четыре медвежонка и
три мяча. Он хочет выбрать из
этих игрушек один автомобиль, одного медвежонка и один мяч.
Сколько у него есть вариантов выбора?
этих игрушек один автомобиль, одного медвежонка и один мяч.
Сколько у него есть вариантов выбора?
Ответ: 24 варианта.
Слайд 7Примеры решения задач:
Задача 2.
Винни-Пух решил навестить своих друзей: Пяточка, Кролика
и Ослика. Ему нужно побывать у каждого из них и вернуться домой. Если он к кому-то не зайдет, то его друг обидится. Но Винни-Пух не любит длительных путешествий. Помогите ему выбрать кратчайший путь, если известно, как расположены домики друзей и на каком расстоянии они находятся друг от друга:
Слайд 8Примеры решения задач:
Построить граф, используя условия задачи, расставить на нем расстояния.
Определить
пары симметричных вариантов (например: В – К – П – И – В и В – И – П – К – В) и вычеркнуть на графе один вариант из каждой пары.
Выписать оставшиеся варианты и подсчитать расстояния:
В – К – П – И – В = 60 + 50 + 55 + 30
В – К – И – П – В = 60 + 45 + 55 + 40
В – И – К – П – В = 30 + 45 + 50 + 40
Выписать оставшиеся варианты и подсчитать расстояния:
В – К – П – И – В = 60 + 50 + 55 + 30
В – К – И – П – В = 60 + 45 + 55 + 40
В – И – К – П – В = 30 + 45 + 50 + 40
Дано:
И – Ослик
В – Винни-Пух
П – Пяточек
К – Кролик
Найти:
Кратчайший путь
Рассуждения:
Слайд 9Рассуждения:
1. Выстраиваем вспомогательные линии
2. Строим граф, используя условия задачи
К
П
И
В
П
И
К
И
К
П
И
П
И
К
П
К
В
В
В
В
В
В
3. Расставляем расстояния,
используя данные рисунка
60
40
30
50
45
50
55
55
45
55
55
45
45
50
50
30
40
30
60
60
40
4. Определяем пары симметричных вариантов
5. Выписываем оставшиеся варианты и подсчитываем результаты
В – К – П – И – В = 60 + 50 + 55 + 30 =
В – К – И – П – В = 60 + 45 + 55 + 40 =
В – И – К – П – В = 30 + 45 + 50 + 40 =
195
200
165
Слайд 10Задача на закрепление:
Пятачок решил навестить своих друзей – Винни-Пуха, Кролика и
Ослика. Ему надо побывать у каждого и вернуться домой. Помогите Пятачку выбрать кратчайший путь. Расположение домиков:
Ответ: 165
