Презентация "Топологическая сортировка отсечением вершин" по информатике – проект, доклад

Скачать презентацию (0.65 Мб) Смотреть похожие презентации Конспекты для презентации

Слайд 1

Слайд 2

Слайд 3

Слайд 4

Слайд 5

Слайд 6

Слайд 7

Слайд 8

Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

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

Скачать презентацию (0.65 Мб) Смотреть похожие презентации Конспекты для презентации

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

Слайд 1

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

Слайд 2

Нахождение компонент связности

В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер неориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output.txt вывести единственное число — количество компонент связности графа. Ограничение по времени — 1 сек. Ограничение по памяти — 16 Мб.

Слайд 3

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

Сколько различных путей есть в дереве с n вершинами? Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами? Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами и k компонентами связности? Написать программу, определяющую количество компонент связности, с использованием матрицы смежности. Написать программу, определяющую максимальный размер компоненты связности, с использованием списка смежности.

Слайд 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 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() 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 изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей. Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке. Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.

Слайд 11

Первая строка входного файла 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 Мб.

Слайд 12

Слайд 13

Источники

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

Список похожих презентаций

Поиск и сортировка информации в базах данных

Задача № 1. Результаты тестирования представлены в таблице:. Сколько записей в ней удовлетворяют условию «Пол =’ж’ ИЛИ Химия > Биология»? Решение. ...

Конспекты

Хранение, поиск и сортировка информации

Конспект урока по теме «Хранение, поиск и сортировка информации». Практическая работа №15 Создание и редактирование базы данных «Записная книжка». ...

Советы как сделать хороший доклад презентации или проекта

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