Задание 8. Элемент содержания 11 класса: ЕГЭ по информатике

Задание 8 ЕГЭ по информатике проверяет умение анализировать информационные модели из различных предметных областей, чаще всего — формальные описания объектов и их связей (графы, таблицы, схемы). В демоверсиях и реальных вариантах задание обычно представлено как задача на поиск кратчайшего пути в…

Что нужно знать

Задание 8 проверяет умение анализировать информационные модели (графы, таблицы, схемы) и находить кратчайший путь или количество путей.
Основные типы моделей: таблица смежности (симметричная для неориентированного графа), весовая матрица (с указанием длин дорог), схема дорог с условиями (например, через определённые пункты).
Для поиска кратчайшего пути в взвешенном графе применяется алгоритм Дейкстры; для небольших графов допустим полный перебор маршрутов.
В таблице смежности на пересечении строки i и столбца j указывается вес ребра между пунктами i и j; если ребра нет, ставится прочерк или бесконечность.
Если граф неориентированный, таблица симметрична относительно главной диагонали; для ориентированного графа симметрии нет.
При поиске количества путей используется динамическое программирование: количество путей в пункт равно сумме количеств путей в предшествующие пункты, из которых есть ребро.

Термины и понятия

Граф: совокупность вершин и соединяющих их рёбер.
Вершина: объект (пункт, город, узел), который может быть соединён с другими.
Ребро: связь между двумя вершинами; может иметь вес (длину, стоимость).
Взвешенный граф: граф, каждому ребру которого сопоставлено число (вес).
Ориентированный граф: граф, в котором рёбра имеют направление (дуги).
Таблица смежности: таблица, где на пересечении строки и столбца указывается наличие ребра или его вес.
Матрица весов: квадратная таблица, содержащая веса рёбер между парами вершин.
Кратчайший путь: путь между двумя вершинами с минимальной суммой весов рёбер.

Частые ошибки

Неверное чтение таблицы: путают строки и столбцы, не учитывают, что таблица симметрична для неориентированного графа, и берут вес из ячейки, где стоит прочерк.
При использовании алгоритма Дейкстры забывают обновлять метки соседей после выбора текущей вершины или неправильно выбирают вершину с минимальной меткой.
В задачах на количество путей учитывают пути, не удовлетворяющие направлению (если граф ориентированный) или дополнительные условия (например, прохождение через определённый пункт).
При подсчёте путей динамическим программированием неправильно определяют порядок обхода вершин (например, не учитывают топологическую сортировку для ориентированного графа).

Как пройти тему

В курсе «Информатика» тема «Задание 8. Элемент содержания 11 класса» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Задание 7. Объём памяти для графической и звуковой информации
Следующая тема: Задание 9. Обработка числовой информации в электронных таблицах

Все темы: ЕГЭ по информатике