» » » Топологическая сортировка отсечением вершин
Топологическая сортировка отсечением вершин

Презентация на тему Топологическая сортировка отсечением вершин


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

Слайды презентации

Слайд 1
Алгоритмы на графах Топологическая сортировка отсечением вершин Югов Иван Олегович МОУ Гимназия №10, г. Тверь
Слайд 2
Нахождение компонент связности В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер неориентированного графа (1 ≤ n ≤  10 000, 0 ≤ m ≤  50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output.txt вывести единственное число — количество компонент связности графа. Ограничение по времени — 1 сек. Ограничение по памяти — 16 Мб.
Слайд 3
Домашнее задание 1. Сколько различных путей есть в дереве с n вершинами? 2. Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами? 3. Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами и k компонентами связности? 4. Написать программу, определяющую количество компонент связности, с использованием матрицы смежности. 5. Написать программу, определяющую максимальный размер компоненты связности, с использованием списка смежности.
Слайд 4
Топологическая сортировка Дан ориентированный ациклический граф. Топологической сортировкой называется присвоение номеров вершинам: любая дуга направлена из вершины с меньшим номером в вершину с бóльшим номером.
Слайд 5
Топологическая сортировка Почему это возможно? Всегда найдётся вершина, в которую не входит ни одно ребро. Такой вершине можно присвоить минимальное значение, после чего убрать её из графа.
Слайд 6
Топологическая сортировка Как быстро определить вершины, в которые не входит ни одно ребро? Будем хранить входящую степень каждой вершины:  массив deg_in длины n , deg_in[i] — число соседей i -й вершины. Pascal ... a[u, v] := True; Inc(deg_in[v]); ... C ... a[u, v] = TRUE ; deg_in[v]++; ...
Слайд 7
Топологическая сортировка  массив order длины n , order[i] — присвоенный i -й вершине порядковый номер при топологической сортировке;  currorder — текущий присваиваемый номер. Pascal for i := 1 to n do order[i] := 0; currorder := 0; TopSort; TopSort: for i := 1 to n do for j := 1 to n do if (deg_in[j] = 0) and (order[j] = 0) then begin Inc(currorder); order[j] := currorder; for <u - сосед j-й вершины> do Dec(deg_in[u]); end ; C for (i = 0; i < n; i++) order[i] = 0; currorder = 0; TopSort; TopSort: for (i = 0; i < n; i++) for (j = 0; j < n; j++) if ((!deg_in[j]) && (!order[j])) { order[j] = ++currorder; for ( <u - сосед i-й вершины> ) deg_in[u]--; };
Слайд 8
Топологическая сортировка В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1 ≤ n ≤  10 000, 0 ≤ m ≤  50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output.txt вывести номера, которые приобретут вершины после топологической сортировки. i -е число означает номер, приобретённый i -й вершиной. Ограничение по времени — 3 сек. Ограничение по памяти — 16 Мб.
Слайд 9
Топологическая сортировка В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1 ≤ n ≤  10 000, 0 ≤ m ≤  50 000). В следующ и х m строках файла заданы пары номеров вершин, соединённых рёбра ми. В файл output.txt вывести упорядоченные топологически номера вершин. Ограничение по времени — 3 сек. Ограничение по памяти — 16 Мб.
Слайд 10
Домашнее задание Предприятие «Авто-2010» выпускает двигатели известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n , при этом деталь с номером i изготавливается за p i секунд. Специфика предприятия «Авто- 2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей. Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке. Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.
Слайд 11
Домашнее задание Первая строка входного файла details.in содержит число n (1 ≤ n ≤  10 000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p 1 , p 2 , …, p n , определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10 9 секунд. Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i -я строка содержит число деталей k i , которые требуются для производства детали с номером i , а также их номера. Сумма всех чисел k i не превосходит 200000. Известно, что не существует циклических зависимостей в производстве деталей. В первой строке выходного файла details.out должны содержаться два числа: минимальное время ( в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимы для этого производства. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором их следует производить для скорейшего производтсва детали с номером 1. Ограничение по времени — 2 сек. Ограничение по памяти — 64 Мб.
Слайд 12
Домашнее задание
Слайд 13
Источники Курс «Базовые алгоритмы для школьников» (Станкевич А. С., Абакумов К. В., Мухачёва М. А.) «Интернет-уинверситет информационных технологий» http://www.intuit.ru/department/algorithms/basicalgos/

Другие презентации по информатике



  • Яндекс.Метрика
  • Рейтинг@Mail.ru