Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
12 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
644.00 kB
Просмотров:
56
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img0.jpg)
№2 слайд![Домашнее задание Предприятие](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img1.jpg)
Содержание слайда: Домашнее задание
Предприятие «Авто-2010» выпускает двигатели известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.
Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.
Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.
№3 слайд![Домашнее задание Первая](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img2.jpg)
Содержание слайда: Домашнее задание
Первая строка входного файла 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 слайд![Домашнее задание](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img3.jpg)
Содержание слайда: Домашнее задание
№5 слайд![Топологическая сортировка Для](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img4.jpg)
Содержание слайда: Топологическая сортировка
Для топологической сортировки можно использовать поиск в глубину.
№6 слайд![Топологическая сортировка](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img5.jpg)
Содержание слайда: Топологическая сортировка
№7 слайд![Топологическая сортировка](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img6.jpg)
Содержание слайда: Топологическая сортировка
Почему так происходит?
№8 слайд![Топологическая сортировка](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img7.jpg)
Содержание слайда: Топологическая сортировка
Рассмотрим момент времени, когда мы покидаем A (но ещё не покинули B).
Два случая:
Покидаем A и ещё не посещали B.
Покидаем A и посетили B.
№9 слайд![Топологическая сортировка](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img8.jpg)
Содержание слайда: Топологическая сортировка
Альтернативное начало —
фиктивная вершина.
№10 слайд![Топологическая сортировка](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img9.jpg)
Содержание слайда: Топологическая сортировка
Если оказалось, что граф содержит циклы:
как будет вести себя алгоритм топологической сортировки отсечением вершин?
как будет вести себя алгоритм топологической сортировки поиском в глубину?
№11 слайд![Домашнее задание Какое](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img10.jpg)
Содержание слайда: Домашнее задание
Какое максимальное количество рёбер может быть в ориентированном ациклическом графе с n вершинами?
Может ли быть так, что правильным результатом топологической сортировки графа оказывается любой порядок его вершин?
Решить задачу о производстве деталей с помощью DFS.
Как использовать топологическую сортировку для определения наличия циклов в графе?
№12 слайд![Источники Курс Базовые](/documents/e1bc24609c5830e7f5448ba9fb6c087e/img11.jpg)
Содержание слайда: Источники
Курс «Базовые алгоритмы для школьников» (Станкевич А. С., Абакумов К. В., Мухачёва М. А.)
«Интернет-уинверситет информационных технологий»
http://www.intuit.ru/department/algorithms/basicalgos/