Рабочий лист на тему:

Алгоритмы моделирования кратчайших путей и элементы теории игр

Информатика10 класс10 заданий
Множественный выборИстина / ЛожьЗаполни пропускиТаблицаСравни числаСоединениеПоследовательностьРеши задачуНайти лишнее

Типы заданий

Множественный выборИстина / ЛожьЗаполни пропускиТаблицаСравни числаСоединениеПоследовательностьРеши задачуНайти лишнее
Алгоритмы моделирования кратчайших путей и элементы теории игр

10 класс · дифференцированный

Ф.И.
Класс


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

№1 · Алгоритм дейкстры

1 вопрос · 1 балл

1. Допустимые веса рёбер

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

  • Хотя бы одно ребро имеет отрицательный вес.
  • В графе обязательно должен быть цикл отрицательного веса.
  • Все веса рёбер неотрицательны.
  • Все вершины графа имеют одинаковые названия.

№2 · Проверка понятий

4 утверждения · 1 балл

2. Метки и восстановление пути

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

  1. Начальной вершине присваивают метку 0.
  2. Для всех остальных вершин в начале можно записать бесконечность.
  3. Окончательная метка вершины может уменьшиться после её фиксации.
  4. Для восстановления маршрута достаточно хранить только итоговое расстояние.

№3 · Динамическое программирование

3 пропуска · 1 балл

3. Рекуррентная формула пути

Заполни пропуски в записи перехода динамического программирования для слоистого графа.

Минимальная стоимость попадания в вершину v равна по всем предшественникам u: d(v) = . Для восстановления пути сохраняют вершины.

№4 · Таблица меток

5 вершин · 2 балла

4. Расстояния и предки в графе

Для ориентированного графа с рёбрами A→B (4), A→C (2), C→B (1), B→D (3), C→D (5), D→E (2) заполни скрытые ячейки таблицы после работы алгоритма Дейкстры из вершины A.

ВершинаКратчайшее расстояние от AПредок
A0—
B
C
D
E

№5 · Сравнение маршрутов

3 сравнения · 2 балла

5. Стоимость альтернативных путей

Сравни стоимость маршрутов. В каждой строке поставь знак между левым и правым выражением.

1)4 + 73 + 9
2)2 + 5 + 14 + 3 + 2
3)6 + 2 + 45 + 3 + 3

№6 · Термины алгоритма

4 связки · 2 балла

6. Понятие и его назначение

Соедини каждый термин с его точным описанием.

+5 заданий в этом листе

Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.

№7 · Порядок шагов

5 шагов · 2 балла

7. Выполнение алгоритма Дейкстры

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

  1. Расслабить рёбра выбранной вершины и при необходимости изменить метки соседей.
  2. Повторять выбор и расслабление, пока нужная вершина не будет обработана.
  3. Присвоить начальной вершине метку 0, остальным — бесконечность.
  4. Пометить выбранную вершину как посещённую.
  5. Выбрать непосещённую вершину с минимальной временной меткой.

№8 · Слоистый граф

1 задача · 3 балла

8. Оптимальный путь методом динамического программирования

В слоистом графе есть рёбра: A→B со стоимостью 2, A→C со стоимостью 5, B→D со стоимостью 4, B→E со стоимостью 7, C→D со стоимостью 1, C→E со стоимостью 3, D→F со стоимостью 2, E→F со стоимостью 1. Найди минимальную стоимость пути из A в F и восстанови сам путь.

№9 · Теория игр

5 позиций · 3 балла

9. Поиск проигрышной позиции

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

  1. 0
  2. 4
  3. 10
  4. 8
  5. 12

№10 · Анализ ограничений

1 задача · 3 балла

10. Почему Дейкстра неприменим

Рассмотри граф с рёбрами A→B (2), A→C (5), B→C (-4), C→D (1), B→D (7). Определи, можно ли корректно применить алгоритм Дейкстры из A. Если нельзя, объясни причину и найди кратчайший путь из A в D перебором допустимых маршрутов.

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

  • Любая тема, любой уровень
  • 20+ типов заданий
  • 100% уникальный контент
  • Со страницей ответов
  • Защита от списывания
  • Готово за 1 минуту

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

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

Чем удобны рабочие листы Нейрум

  • По действующей программеТемы и задания совпадают со школьной программой 1–11 классов. Открыли — дали классу, без правок.
  • Готово к печати, с ответамиPDF в формате A4 и ключ ответов на отдельной странице. Скачали, распечатали, раздали — без правок в Word.
  • Свой лист за минутуНе нашли нужный? ИИ-конструктор соберёт лист по вашей теме, классу и типам заданий.

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

Как скачать рабочий лист «Алгоритмы моделирования кратчайших путей между вершинами (Алгоритм Дейкстры, Метод динамического программирования). Элементы теории игр (выигрышная стратегия)»?

Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.

Сколько заданий в листе и какие они?

В листе 10 заданий: множественный выбор, истина / Ложь, заполни пропуски, таблица, сравни числа, соединение, последовательность, реши задачу, найти лишнее.

Соответствует ли лист ФГОС?

Да, задания ориентированы на школьную программу по информатике для 10 класса по ФГОС.

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

Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.