- Главная
- Разное
- Образование
- Спорт
- Естествознание
- Природоведение
- Религиоведение
- Французский язык
- Черчение
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, фоны, картинки для презентаций
- Экология
- Экономика
Презентация, доклад по математике на тему Решение логических задач
Содержание
- 1. Презентация по математике на тему Решение логических задач
- 2. Содержание проектаЧто такое граф? Какие бывают графы?История
- 3. Что такое граф?Граф- это схема, состоящая из
- 4. Состав графаНаправленная линия (со стрелкой) называется дуга.Линия
- 5. Степень вершины графаСтепень A – 1Степень B
- 6. Количество ребер графаABCDEF(1+3+2+3+2+1):2=6равно сумме степеней всех его вершин, деленной на 2
- 7. Задание матрицы смежности(компьютерное представление графа) Граф может
- 8. Какие бывают графы?НеориентированныеОриентированныеСвязные или несвязныеПолныеВзвешенные Сети и семантические сети
- 9. Неориентированный графНа схеме представлены дружеские связи в
- 10. Ориентированный графМашаЮраКоляВитяАняОриентированный граф - граф, вершины которого
- 11. Связные и несвязные графыСвязный граф можно нарисовать не отрывая карандаша от бумаги
- 12. Полный графГраф называется полным, если каждая вершина
- 13. Взвешенный графВладимир, 1108Взвешенный граф – это граф,
- 14. ДеревоДерево – граф иерархической структуры. Между любыми
- 15. КоляЦепь – путь по вершинам и ребрам,
- 16. История возникновения теории графов
- 17. Л. Эйлер (1707-1782, российский математик, швейцарец по
- 18. В 1736 году Эйлер нашел решение головоломки, носящей название «проблема кёнигсбергских мостов».
- 19. Задача ЭйлераЗадача, для решения которой Эйлер впервые
- 20. Я здесь уже был!
- 21. План города Эйлер заменил его упрощенной схемой,
- 22. Получился следующий граф:
- 23. В итоге Эйлер доказал общее утверждение:
- 24. Решение задачи о Кенигсбергских мостахГраф кёнигсбергских мостов
- 25. Графы в современном мире
- 26. Науки, опирающиеся на знание ТЕОРИИ ГРАФОВ:МедицинаКибернетикаИнформатикаХимияФизикаТранспортСтроительствоПрикладная математикаЭкономика
- 27. Какие задачи можно решить с помощью графов?Логические задачиГрафические задачиПостроение генеалогических деревьев и каталоговЗадачи анализа текстовУправление проектами
- 28. Решение логических задач с помощью графовЗадача 1.В
- 29. Задача 2.Может ли в государстве, в котором
- 30. Задача 3Аркадий, Борис, Владимир, Григорий и Дмитрий
- 31. Решение: Пусть каждому из молодых
- 32. Задача 4Алексей, Борис, Виталий и Геннадий –
- 33. Изобразим все данные условия на рисунке с помощью графов и ответ станет очевиднымАлексейБорисГеннадийВиталийстроительтренержурналистврач
- 34. Графические задачиВ каком случае можно нарисовать фигуру
- 35. Правило: - Если все вершины графа четные,
- 36. Задача 5. Можно ли нарисовать фигуру одним
- 37. Задача 6Земля-МеркурийПлутон- ВенераЗемля – ПлутонПлутон – МеркурийМеркурий
- 38. Решение: Нам будет достаточно изобразить в виде графа все маршруты и ответ очевиден Сатурн
- 39. Генеалогическое деревоВершины – члены рода.Связывающие отрезки –
- 40. Генеалогическое дерево
- 41. Семантическая сеть строится по подчинению слов в тексте
- 42. Теория графов и анализ художественного текстаС помощью
- 43. 1. Количество узлов дерева (т.е. количество слов
- 44. Текст ПушкинаТекст Лермонтова
- 45. Графы в сетевом планировании
- 46. Сетевое планирование – это изображение сложных проектов
- 47. Сетевое планирование используется:при создании больших проектов;при планировании работ в строительстве или других областях;при конструировании сложных механизмов.
- 48. Пример построения сетевого графикаНекоторый издатель готовится к
- 49. Слайд 49
- 50. Составляем граф или сетевой график проекта123456780A(3)B(2)E(2)H(1)D(3)I(2)J(4)C(4)F(4)G(2)
- 51. В данном графе можно составить различные пути
- 52. СПАСИБО ЗА ВНИМАНИЕ
Содержание проектаЧто такое граф? Какие бывают графы?История возникновения теории графовГрафы в современном миреКакие задачи можно решить с помощью графов?
Слайд 2Содержание проекта
Что такое граф?
Какие бывают графы?
История возникновения теории графов
Графы в
современном мире
Какие задачи можно решить с помощью графов?
Какие задачи можно решить с помощью графов?
Слайд 3Что такое граф?
Граф- это схема, состоящая из точек и отрезков, соединяющих
эти точки.
Точки – вершины графа,
отрезки – ребра графа
Точки – вершины графа,
отрезки – ребра графа
Слайд 4
Состав графа
Направленная линия (со стрелкой) называется дуга.
Линия ненаправленная (без стрелки) называется
ребро.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петля.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петля.
дуга
ребро
петля
А
В
С
А,В,С – вершины графа
Слайд 5Степень вершины графа
Степень A – 1
Степень B – 3
Степень C –
2
Степень D – 2
Это количество ребер, выходящих из данной вершины
Слайд 6Количество ребер графа
A
B
C
D
E
F
(1+3+2+3+2+1):2=6
равно сумме степеней всех его вершин, деленной на 2
Слайд 7Задание матрицы смежности
(компьютерное представление графа)
Граф может быть изображен в виде
таблицы (матрицы смежности), где по строкам и по столбцам записаны вершины графа, а внутри цифрой 1 отмечается наличие ребра между этими вершинами.
Слайд 8Какие бывают графы?
Неориентированные
Ориентированные
Связные или несвязные
Полные
Взвешенные
Сети и семантические сети
Слайд 9Неориентированный граф
На схеме представлены дружеские связи в компании. Отношения являются двухсторонним,
поэтому вершины соединены линиями без стрелок.
Граф называется неориентированным, если его вершины соединены ребрами.
Слайд 10Ориентированный граф
Маша
Юра
Коля
Витя
Аня
Ориентированный граф - граф, вершины которого соединены дугами.
С помощью
таких графов могут быть представлены схемы односторонних отношений. На рисунке представлена схема переписки
Слайд 12Полный граф
Граф называется полным, если каждая вершина связана со всеми другими
вершинами графа.
Если полный граф имеет n вершин, то количество ребер будет равно
n(n-1)/2
Если полный граф имеет n вершин, то количество ребер будет равно
n(n-1)/2
Слайд 13Взвешенный граф
Владимир, 1108
Взвешенный граф – это граф, у которого вершины или
рёбра (дуги) несут дополнительную информацию (вес).
Слайд 14Дерево
Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует
единственный путь. Дерево не содержит циклов и петель.
Слайд 15Коля
Цепь – путь по вершинам и ребрам, включающий любое ребро графа
не более одного раза.
Цикл – цепь, начальная и конечная вершины которой совпадают.
Граф с циклом называют сетью
Цикл – цепь, начальная и конечная вершины которой совпадают.
Граф с циклом называют сетью
Сеть
Слайд 17Л. Эйлер (1707-1782, российский математик, швейцарец по происхождению, академик Петербургской и
Берлинской академии наук)
Г. Кирхгоф (1824-1871, иностранный член-корреспондент Петербургской академии наук разработал теорию деревьев)
Основоположники теории графов
Слайд 18В 1736 году Эйлер нашел решение головоломки, носящей название «проблема кёнигсбергских
мостов».
Слайд 19Задача Эйлера
Задача, для решения которой Эйлер впервые применил графы, - это
задача о мостах Кенигсберга.
В XVIII веке город Кенигсберг (сейчас Калининград) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами.
В XVIII веке город Кенигсберг (сейчас Калининград) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами.
Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз?
Слайд 21План города Эйлер заменил его упрощенной схемой, на которой части города
изображены точками (вершинами), а мосты - линиями (ребрами).
Слайд 23 В итоге Эйлер доказал общее утверждение: для того чтобы обойти
все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и
достаточно выполнения следующих двух условий:
1. из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (граф должен быть связным);
2. из каждой вершины должно выходить чётное количество рёбер.
Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой.
достаточно выполнения следующих двух условий:
1. из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (граф должен быть связным);
2. из каждой вершины должно выходить чётное количество рёбер.
Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой.
Слайд 24Решение задачи о Кенигсбергских мостах
Граф кёнигсбергских мостов имел четыре нечётные вершины,
следовательно невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Слайд 26Науки, опирающиеся на знание
ТЕОРИИ ГРАФОВ:
Медицина
Кибернетика
Информатика
Химия
Физика
Транспорт
Строительство
Прикладная математика
Экономика
Слайд 27Какие задачи можно решить с помощью графов?
Логические задачи
Графические задачи
Построение генеалогических деревьев
и каталогов
Задачи анализа текстов
Управление проектами
Задачи анализа текстов
Управление проектами
Слайд 28Решение логических задач с помощью графов
Задача 1.
В государстве 100 городов, а
из каждого города выходит 4 дороги. Сколько всего дорог в государстве?
Решение:
Воспользуемся формулой:
Количество ребер в графе равно сумме степеней всех его вершин, деленной на 2
Слайд 29
Задача 2.
Может ли в государстве, в котором из каждого города выходит
3 дороги, быть ровно 100 дорог?
Нет, не может, так как
если X- число городов
Решение:
Воспользуемся формулой:
Количество ребер в графе равно сумме степеней всех его вершин, деленной на 2
Слайд 30Задача 3
Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями
(каждый пожал руку каждому по одному разу).
Сколько всего рукопожатий было сделано?
Сколько всего рукопожатий было сделано?
Слайд 31Решение:
Пусть каждому из молодых людей соответствует точка на
плоскости, а произведенные рукопожатия – отрезок, который будет соединять точки.
Количество ребер полного графа 5*4/2=10. Значит, было сделано 10 рукопожатий
Слайд 32Задача 4
Алексей, Борис, Виталий и Геннадий – друзья.
Один из них
–врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель.
Журналист написал статьи об Алексее и Геннадие.
Тренер и журналист вместе с Борисом ходили в поход.
Алексей и Борис были на приеме у врача.
У кого какая пофессия?
Журналист написал статьи об Алексее и Геннадие.
Тренер и журналист вместе с Борисом ходили в поход.
Алексей и Борис были на приеме у врача.
У кого какая пофессия?
Слайд 33Изобразим все данные условия на рисунке с помощью графов и ответ
станет очевидным
Алексей
Борис
Геннадий
Виталий
строитель
тренер
журналист
врач
Слайд 34Графические задачи
В каком случае можно нарисовать фигуру не отрывая карандаша от
бумаги и не проводя дважды ни одной линии, а в каком случае нет?
(задача о Кенигсбергских мостах)
(задача о Кенигсбергских мостах)
Слайд 35Правило:
- Если все вершины графа четные, то нарисовать фигуру возможно,
и начать можно с любой вершины.
-Если же из этих вершин две нечетные, то нарисовать фигуру можно, но только начинать необходимо в одной из этих двух нечетных вершин, а заканчивать во второй нечетной вершине.
-В других случаях нарисовать фигуру нельзя.
-Если же из этих вершин две нечетные, то нарисовать фигуру можно, но только начинать необходимо в одной из этих двух нечетных вершин, а заканчивать во второй нечетной вершине.
-В других случаях нарисовать фигуру нельзя.
Слайд 36Задача 5. Можно ли нарисовать фигуру одним росчерком, не отрывая карандаша
от бумаги и не проводя по одной линии дважды?
Слайд 37Задача 6
Земля-Меркурий
Плутон- Венера
Земля – Плутон
Плутон – Меркурий
Меркурий – Венера
Уран – Нептун
Нептун
– Сатурн
Сатурн – Юпитер
Юпитер – Марс
Марс – Уран
Сатурн – Юпитер
Юпитер – Марс
Марс – Уран
Между девятью планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Слайд 39Генеалогическое дерево
Вершины – члены рода.
Связывающие отрезки – отношение родственности, ведущие от
родителей к детям.
Граф-дерево всегда можно изобразить так, чтобы его ребра не пересекались.
Граф-дерево всегда можно изобразить так, чтобы его ребра не пересекались.
Слайд 42Теория графов и анализ художественного текста
С помощью графов можно определить, как
фразы одного писателя или поэта отличаются от других. На язык деревьев переводятся трудноуловимые особенности стиля.
На основании этих графов можно определить автора текста.
Например, основная черта стихов А.С. Пушкина – ритмичность и лаконизм (краткость) выражений, а у М.Ю. Лермонтова поэзия более цветистая, фразы более длинные.
На основании этих графов можно определить автора текста.
Например, основная черта стихов А.С. Пушкина – ритмичность и лаконизм (краткость) выражений, а у М.Ю. Лермонтова поэзия более цветистая, фразы более длинные.
Слайд 431. Количество узлов дерева (т.е. количество слов во фразе).
2. Количество простых
предложений в сложном (помечание стрелок, соответствующих связям между частями сложного предложения)
3. Число уровней в дереве (длина самого длинного из путей дерева)
4. Ширина ветвления корня (число узлов подчинённых корню)
3. Число уровней в дереве (длина самого длинного из путей дерева)
4. Ширина ветвления корня (число узлов подчинённых корню)
А теперь выясним; по какому принципу лингвисты проводят анализ художественного текста. И.Л. Севбо привёл следующие 4 признака:
Слайд 46
Сетевое планирование – это изображение сложных проектов в виде сети на
основании опыта в проведении таких работ.
При этом учитывается последовательность их выполнения, возможность одновременного проведения работ и их длительность.
Сетевое планирование позволяет рассчитать максимальную или минимальную длительность всего проекта.
При этом учитывается последовательность их выполнения, возможность одновременного проведения работ и их длительность.
Сетевое планирование позволяет рассчитать максимальную или минимальную длительность всего проекта.
Слайд 47Сетевое планирование используется:
при создании больших проектов;
при планировании работ в строительстве или
других областях;
при конструировании сложных механизмов.
при конструировании сложных механизмов.
Слайд 48Пример построения сетевого графика
Некоторый издатель готовится к подписанию контракта с автором
на издание его книги.
Необходимо с помощью сети просчитать максимальную длительность проекта для заключения контракта
Необходимо с помощью сети просчитать максимальную длительность проекта для заключения контракта
Слайд 51В данном графе можно составить различные пути
Очевидно, в самом худшем
случае, издание книги займет 17 недель. Причем, быстрее чем за 8 недель издать книгу не удастся
