П’ята лекція другого сезону відбудеться 21 жовтня о 17 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: Олександр та Мар’ян.
Тема: Алгоритми на графах.
На порядку денному:
- Компоненти зв’язності графа та способи їх відшукання.
- Означення дерева.
- Способи задання та представлення дерев.
- Алгоритми Крускала та Пріма для пошуку каркаса мінімальної ваги.
А на лекції буде розглядатися структура disjoint sets?
Ну.. Мабуть частково за Пріма…
Хтозна чи прийду. Прихворів.
Класна лекція!
dispoint sets не розглядалась =). Думаю, далеко не всім на лекції таке цікаво. А якщо такі знайдуться, то думаю, без значних проблем вичитають то в гуглі…
А щодо відсутніх (і присутніх) лекції, то ось домашнє завдання:
* Мишка-норушка http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1034& (не зовсім по цій темі, але застосовується дуже схожий алгоритм на Краскала чи Пріма)
* ОУНШ http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1047& (мін остове дерево. Алгоритм краскала чи Пріма)
* Клас http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1078& (зв”язні компоненти)
* Сузір’я http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1302&rid=4cbe0161962c9 (зв”язні компоненти)
* ЛЕП http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1351&rid=4cbe01a6e8417 (зв”язні компоненти або пошук мостів графа)
О Боже… Як же то всьо без тебе відбулось?)
Жахливо… Виділили якусь кімнатку на 4 поверсі замість залу на третьому… Початок затримався через це. Народу менше, ніж в попередні рази, одразу десь так на 15-20 людей (Артур, ти де? Це ж твій обов’язок рахувати?)…
Хоча сама лекція класна, нам такі перешкоди не заважають) Особливо сподобалась ідея з чарівним маркером, після якого граф сам видаляє з себе зайві ребра, щоб утворилось дерево, а потім ще показово розбиває це дерево на ліс дерев, а потім залишає від себе лише множину вершин для наглядності…
Да з дошкою нам везе, або треба витирати з неї все довго і нудно, або все саме щезає за 10 секунд)))
До речі прима з фібаначівими кучами працює все таки швидше. Там операція зміни пріоритету амортизаційно відбувається за O(1). Тому, якщо зі звичайною чергою з пріоритетами ми отримуємо: O(V + E lg V), то у випадку з ф.кучами ми отримаємо O(E + V lg V), але насправді їх ніхто не використовує
Мене не було, бо в п’ятницю мав бути колоквіум з лінійної алгебри, до якого я звісно ж не був достатньо готовий.
Імовірно, щось схоже було і в тих 15-20 людей.