Десята лекція четвертого сезону відбудеться 14 лютого о 18 годині у 265 аудиторії головного корпусу університету імені Івана Франка.
Лекцію ведуть: Igor та LeBron.
Тема: Елементарні алгоритми на графах.
На порядку денному:
- Означення та способи представлення графів.
- Обхід графа в ширину і в глибину.
- Алгоритм Дейкстри.
- Алгоритм Флойда-Воршелла.
http://en.wikipedia.org/wiki/Glossary_of_graph_theory – термінологія.
http://informatics.mccme.ru/moodle/course/view.php?id=6 – багато задач на теми, які сьогодні розглядались, а також на складніші алгоритми на графах. Також там можете знайти теор.матеріал.
http://e-maxx.ru/algo/bridge_searching
http://e-maxx.ru/algo/cutpoints – розумне використання DFS для пошуку мостів і точок сполучення, про яке було згадано на лекції.
Почитати теорію, уточнити щось, глянути на код – також на можна на е-максі,
http://e-maxx.ru/algo/dijkstra – простий алго Дейкстри
http://e-maxx.ru/algo/dijkstra_sparse – алго для розріджених графів (розглянуто як варіант черги з пріоритетом, так і варіант сету)
http://e-maxx.ru/algo/floyd_warshall_algorithm – Флойд-Уоршелл
http://e-maxx.ru/algo/ford_bellman – згаданий на лекції Форд-Беллмен
http://acmp.ru – в розділі Теорія графів є чимало хороших задачок (деякі з них повторюють задачі з informatics)
http://www.spoj.com/problems/AMBIG/ – згадана мною задача з “обходом великого графа”. Зверніть увагу, що на сфері нема можливості здавати на майкрософтівських плюсах.
http://codeforces.ru/problemset/tags/dfs%20and%20similar – можете подивитись на те, які різноманітні задачки потребують обходу графа, як основної складової чи у вигляді підзадачі. Ці задачки принципово відрізняються від тих, котрі було згадано вище – тим, що там переважно йшлось про навчальні задачі для освоєння алгоритмів, а тут майже всі задачі схожі на ті, які можуть бути на змаганнях – тобто є якась легенда і розв’язок не зовсім очевидний.
Якщо є запитання по чомусь з вище названого, або якісь зауваження – пишіть.
http://acm.timus.ru/problem.aspx?space=1&num=1227 – ще приклад задачі на dfs.
http://codeforces.ru/gym/100160 – хороше тренування на тему DFS/BFS.