PPt4Web Хостинг презентаций

Главная / Информатика / Алгоритмы на графах. Топологическая сортировка поиском в глубину
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

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

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Алгоритмы на графах. Топологическая сортировка поиском в глубину


Скачать эту презентацию

Презентация на тему: Алгоритмы на графах. Топологическая сортировка поиском в глубину


Скачать эту презентацию



№ слайда 1 Алгоритмы на графах Топологическая сортировка поиском в глубину Югов Иван Олегов
Описание слайда:

Алгоритмы на графах Топологическая сортировка поиском в глубину Югов Иван Олегович МОУ Гимназия №10, г. Тверь

№ слайда 2 Домашнее задание Предприятие «Авто-2010» выпускает двигатели известных во всём м
Описание слайда:

Домашнее задание Предприятие «Авто-2010» выпускает двигатели известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей. Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке. Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.

№ слайда 3 Домашнее задание Первая строка входного файла details.in содержит число n (1&nbs
Описание слайда:

Домашнее задание Первая строка входного файла details.in содержит число n (1 ≤ n ≤ 10 000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2, …, pn, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 109 секунд. Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. Сумма всех чисел ki не превосходит 200000. Известно, что не существует циклических зависимостей в производстве деталей. В первой строке выходного файла details.out должны содержаться два числа: минимальное время ( в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимы для этого производства. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором их следует производить для скорейшего производтсва детали с номером 1. Ограничение по времени — 2 сек. Ограничение по памяти — 64 Мб.

№ слайда 4 Домашнее задание
Описание слайда:

Домашнее задание

№ слайда 5 Топологическая сортировка Для топологической сортировки можно использовать поиск
Описание слайда:

Топологическая сортировка Для топологической сортировки можно использовать поиск в глубину. Используем поиск в глубину от всех вершин со входящей степенью 0. Будем нумеровать вершины, из которых выходим, в обратном порядке. При этом окажется, что граф отсортирован топологически.

№ слайда 6 Топологическая сортировка
Описание слайда:

Топологическая сортировка

№ слайда 7 Топологическая сортировка Почему так происходит? Не бывает рёбер из вершин, кото
Описание слайда:

Топологическая сортировка Почему так происходит? Не бывает рёбер из вершин, которые были покинуты раньше, в вершины, которые были покинуты позже. Как это доказать? Предположим, что это не так. Пусть имеются вершины A и B, причём в процессе DFS вершина A была покинута раньше, чем вершина B. Пусть теперь существует ребро из A в B.

№ слайда 8 Топологическая сортировка Рассмотрим момент времени, когда мы покидаем A (но ещё
Описание слайда:

Топологическая сортировка Рассмотрим момент времени, когда мы покидаем A (но ещё не покинули B). Два случая: Покидаем A и ещё не посещали B. Покидаем A и посетили B. Однако: Из чёрной вершины в белую не бывает рёбер. Есть серый путь из B в A, что с ребром из A в B даёт цикл, но граф ациклический.

№ слайда 9 Топологическая сортировка Альтернативное начало — фиктивная вершина.
Описание слайда:

Топологическая сортировка Альтернативное начало — фиктивная вершина.

№ слайда 10 Топологическая сортировка Если оказалось, что граф содержит циклы: как будет вес
Описание слайда:

Топологическая сортировка Если оказалось, что граф содержит циклы: как будет вести себя алгоритм топологической сортировки отсечением вершин? как будет вести себя алгоритм топологической сортировки поиском в глубину?

№ слайда 11 Домашнее задание Какое максимальное количество рёбер может быть в ориентированно
Описание слайда:

Домашнее задание Какое максимальное количество рёбер может быть в ориентированном ациклическом графе с n вершинами? Может ли быть так, что правильным результатом топологической сортировки графа оказывается любой порядок его вершин? Решить задачу о производстве деталей с помощью DFS. Как использовать топологическую сортировку для определения наличия циклов в графе?

№ слайда 12 Источники Курс «Базовые алгоритмы для школьников» (Станкевич А. С., Абакумов К.
Описание слайда:

Источники Курс «Базовые алгоритмы для школьников» (Станкевич А. С., Абакумов К. В., Мухачёва М. А.) «Интернет-уинверситет информационных технологий» http://www.intuit.ru/department/algorithms/basicalgos/

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru