ВойтиПопробовать бесплатно

Презентация к уроку на тему:

Графы: как находить оптимальный маршрут

Презентация для урока информатики в 9 классе о графах и поиске оптимального маршрута. На слайдах — понятия вершин, рёбер и весов, схема алгоритма Дейкстры, критерии выбора маршрута и вопросы для самопроверки.

Информатика9 класс10 слайдов
Алгоритм поиска кратчайшего пути
Для графа с неотрицательными весами часто применяют алгоритм Дейкстры.

Идея: выбрать ещё не обработанную вершину с наименьшим известным расстоянием, затем попытаться улучшить расстояния до её соседей. Процесс повторяется, пока нужная вершина не будет обработана.

Посмотрите презентацию целиком

Открыто 5 из 10 слайдов — зарегистрируйтесь и скачайте в PDF или PPTX

Три шага работы алгоритма
1. Старт
Начальной вершине присваивается расстояние , остальным — условно бесконечные значения.
2. Выбор
Выбирается непосещённая вершина с минимальным известным расстоянием.
3. Проверка
Расстояния до соседей пересчитываются, если новый путь оказался короче.

Посмотрите презентацию целиком

Открыто 5 из 10 слайдов — зарегистрируйтесь и скачайте в PDF или PPTX

«Лучший маршрут зависит от критерия»
— Время, расстояние и стоимость могут привести к разным оптимальным решениям

Посмотрите презентацию целиком

Открыто 5 из 10 слайдов — зарегистрируйтесь и скачайте в PDF или PPTX

Проверь себя
Понятие
Чем вершина отличается от ребра?
Модель
Что могут обозначать вершины и рёбра в карте дорог?
Сравнение
Почему маршрут с меньшим числом рёбер не всегда самый короткий?
Практика
Составьте граф из пяти вершин и найдите путь между двумя выбранными вершинами.

Посмотрите презентацию целиком

Открыто 5 из 10 слайдов — зарегистрируйтесь и скачайте в PDF или PPTX

Итоги
  • Граф состоит из вершин и рёбер
  • Путь соединяет вершины последовательностью рёбер
  • Вес ребра задаёт стоимость перехода
  • Оптимальный маршрут определяется выбранным критерием
  • Алгоритм Дейкстры помогает находить кратчайшие пути при неотрицательных весах

Посмотрите презентацию целиком

Открыто 5 из 10 слайдов — зарегистрируйтесь и скачайте в PDF или PPTX

1 / 10
Текст презентации

  1. Слайд 1. Графы: как находить оптимальный маршрут

    Информатика, 9 класс

  2. Слайд 2. Что такое граф

    Граф — это модель объектов и связей между ними. Объекты называют вершинами, а связи между ними — рёбрами.

    Графы помогают описывать дороги между городами, связи между страницами сайта, взаимодействие пользователей и структуру компьютерной сети.

  3. Слайд 3. Основные понятия

    Вершина — объект, представленный точкой графа

    Ребро — связь между двумя вершинами

    Путь — последовательность вершин, соединённых рёбрами

    Длина пути — сумма весов его рёбер

    Вес ребра — стоимость, расстояние или время перехода

  4. Слайд 4. Граф с весами рёбер

  5. Слайд 5. Как сравнивать маршруты

    Минимизируется суммарный вес рёбер. Например, это может быть расстояние или время поездки.

    Выбирается маршрут с лучшим результатом по заданному критерию: минимальным временем, стоимостью или числом пересадок.

  6. Слайд 6. Алгоритм поиска кратчайшего пути

    Для графа с неотрицательными весами часто применяют алгоритм Дейкстры.

    Идея: выбрать ещё не обработанную вершину с наименьшим известным расстоянием, затем попытаться улучшить расстояния до её соседей. Процесс повторяется, пока нужная вершина не будет обработана.

  7. Слайд 7. Три шага работы алгоритма

    Начальной вершине присваивается расстояние , остальным — условно бесконечные значения.

    Выбирается непосещённая вершина с минимальным известным расстоянием.

    Расстояния до соседей пересчитываются, если новый путь оказался короче.

  8. Слайд 8. «Лучший маршрут зависит от критерия»

    — Время, расстояние и стоимость могут привести к разным оптимальным решениям

  9. Слайд 9. Проверь себя

    Чем вершина отличается от ребра?

    Что могут обозначать вершины и рёбра в карте дорог?

    Почему маршрут с меньшим числом рёбер не всегда самый короткий?

    Составьте граф из пяти вершин и найдите путь между двумя выбранными вершинами.

  10. Слайд 10. Итоги

    Граф состоит из вершин и рёбер

    Путь соединяет вершины последовательностью рёбер

    Вес ребра задаёт стоимость перехода

    Оптимальный маршрут определяется выбранным критерием

    Алгоритм Дейкстры помогает находить кратчайшие пути при неотрицательных весах

Создайте уникальную презентацию по своей теме

  • Любая тема, любой класс
  • Иллюстрации к каждому слайду
  • 18 стилей оформления
  • Таблицы, схемы и диаграммы
  • Экспорт в PDF и PPTX
  • Готово за 1 минуту

Создайте дополнительно

Похожие презентации

Другие темы по информатике для 9 класса

Путешествие в мир ИнтернетаМир глобальных сетей и больших данныхБольшие данныеИнтерфейс и основы электронных таблицИскусственный интеллект и машинное обучениеМир в сети: Интернет и информационная безопасностьМоделирование и графыРоль информационных технологий в экономикеПредпринимательская деятельностьАнимация в информатикеТвой цифровой щит: Информационная безопасностьИскусственный интеллект и информационная безопасность

Чем удобны презентации Нейрум

  • Слайды с иллюстрациямиК каждому слайду — картинка, таблица или схема по теме. Открыли на доске и повели урок, без поиска картинок.
  • PDF или PPTXСкачайте презентацию как есть или откройте в PowerPoint и доработайте под свой класс.
  • Своя презентация за минутуНе нашли нужную? ИИ-конструктор соберёт презентацию по вашей теме, классу и количеству слайдов.

Вопросы и ответы

Как скачать презентацию «Графы: как находить оптимальный маршрут»?

Зарегистрируйтесь бесплатно — презентация «Графы: как находить оптимальный маршрут» сохранится в личном кабинете, откуда её можно скачать в PDF или PPTX и показать классу.

Сколько слайдов в презентации «Графы: как находить оптимальный маршрут»?

В презентации 10 слайдов по теме «Графы: как находить оптимальный маршрут» для урока по информатике в 9 классе: заголовки, текст, иллюстрации, таблицы и схемы. Здесь открыты первые пять — остальные после регистрации.

Соответствует ли презентация «Графы: как находить оптимальный маршрут» ФГОС?

Да, слайды по теме «Графы: как находить оптимальный маршрут» построены по школьной программе по информатике для 9 класса по ФГОС.

Можно ли сделать похожую презентацию по теме «Графы: как находить оптимальный маршрут»?

Да. ИИ-конструктор Нейрума соберёт свою презентацию по теме «Графы: как находить оптимальный маршрут» под ваш класс и нужное число слайдов — за минуту.

Как получить рабочий лист и план урока к теме «Графы: как находить оптимальный маршрут»?

В Нейруме к теме «Графы: как находить оптимальный маршрут» можно собрать рабочий лист с заданиями и ответами и план урока по ФГОС для 9 класса — в конструкторе после бесплатной регистрации.

Можно ли изменить слайды под свой класс?

Да. После регистрации презентация «Графы: как находить оптимальный маршрут» открывается в редакторе: текст, картинки и порядок слайдов можно поменять или перегенерировать.