Формальные описания реальных объектов и процессов

Слайд 1. Формальные описания реальных объектов и процессов

Занятие №4.

Автор: Лейсан Расиловна

https://vk.com/id319328759

Слайд 2. Основные виды формальных моделей

Таблицы расстояний (матрицы смежности)

Схемы дорог (графы)

Карты и планы местности

Деревья вариантов

Логические схемы

Слайд 3. Сравнение способов описания

Удобна для хранения данных и автоматизированной обработки. Содержит точные значения весов ребер (расстояний).

Наглядно показывает структуру связей. Позволяет быстро визуализировать возможные маршруты между пунктами $A$ и $B$.

Слайд 4. Анализ матрицы расстояний

В таблице числа указывают на протяженность дорог. Если ячейка пуста, значит прямого сообщения между пунктами нет. Обратите внимание на симметрию относительно главной диагонали: дорога из $A$ в $B$ равна дороге из $B$ в $A$.

Слайд 5. Переход от таблицы к графу

Для решения задачи 4 ОГЭ рекомендуется перерисовать таблицу в виде графа.

1. Обозначьте пункты точками (вершинами).

2. Соедините их линиями (ребрами), если в таблице есть число.

3. Подпишите длины дорог.

Это поможет не пропустить кратчайший обходной путь.

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

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

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

Сравните суммарные длины всех найденных маршрутов и выберите минимальную.

Слайд 7. Типичная ловушка в ОГЭ

Прямой путь — не всегда самый короткий.

Путь $A\to C$ может быть длиннее, чем $A\to B\to C$.

Всегда проверяйте условия: иногда требуется проехать через обязательный пункт.

Внимательно следите за единицами измерения (если они указаны).

Слайд 8. Пример №1.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Слайд 9. Пример №2.

Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяженность дорог между пунктами, через которые он может пройти.

Укажите длину самого длинного участка кратчайшего пути от Ивана-Царевича до Марьи-Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице.

Слайд 10. Пример №3.

Учитель Иван Петрович живет на станции Антоновка, а работает на станции Дружба. Чтобы успеть с утра на уроки, он должен ехать по самой короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего пути от станции Антоновка до станции Дружба.

Слайд 11. Пример №4.

Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и B. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Слайд 12. Пример №5.

Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами B и E (при условии, что передвигаться можно только по построенным дорогам).

Слайд 13. Пример №6.

Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых в (километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт С. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Дважды передвигаться по любой из дорог нельзя.

Слайд 14. Задания для самостоятельной работы

Задача №1. Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Задание №2. Сельская малокомплектная школа находится в поселке Ивановское. Коля Иванов живет в деревне Вершки. Определите, какое минимальное расстояние ему надо пройти, чтобы добраться до школы:

Слайд 15. Задания для самостоятельной работы (продолжение)

Задача №3. Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых в (километрах) приведена в таблице.




Задача №4. Между населенными пунктами А, В, C, D, E протяженность которых приведена в таблице. Определите длину кратчайшего пути между пунктами А и С (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.