Сьома лекція відбудеться 18 лютого о 18 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: brus07 та Sergij.
Тема: Елементарні алгоритми на графах.
На порядку денному:
- Що таке граф?
- Способи представлення графів у програмі.
- Обходи графів у глибину та в ширину.
- Зважені та орієнтовані графи.
- Що таке дерево?
- Алгоритми Пріма та Краскала.
- Алгоритми Дейкстри та Флойда.
Рекомендація: Перед лекцією ознайомитися з графами та пов’язаними поняттями.
Я писав магістерську на цю тему)
До речі, про інтернет-олімпіади з математики.
Тут умови інтернет-олімпіади, що проводилася 17 грудня 2009 року:
http://bogdancdj.narod.ru/olymp/olymp_u9.pdf.
Список учасників з балами: http://bogdancdj.narod.ru/olymp/2009.pdf
Новий список учасників без балів: http://bogdancdj.narod.ru/olymp/2009_1.pdf
Оголошення про олімпіаду http://www.ariel.ac.il/cs/projects/dom/itpm/.
Наступна олімпіада буде відбуватися 15 квітня 2010 року о 10:00.
А основний результат в моїй магістерській роботі зводився до вправи з однієї книжки про алгоритми на графах.
Хоча я заюзав дещо інший варіант: в класиці та штука має реберне представлення, а мені не подобалося те, що у цьому представленні можливі паралельні дуги та інші глюки, тому я придумав вершинне представлення, яке, можливо, не таке очевидне чи наглядне, але в ньому нема приколів з паралельними дугами і тому подібним.
Віталій відібрав номери задачі на графи, що доступні на АСМКонтестері (acm.lviv.ua):
“1027, 1034, 1047, 1070, 1077, 1079, 1144, 1184, 1218, 1237, (між 1249 і 1258 має бути ще одна), 1273, 1276, 1282, 1294.”
Мені сподобалась задача “1144 – Мережі”
Переглянув всі запропоновані Віталеєм задачі, так вони всі на графи, але майте наувазі, що вони не є тривіальними (тобто не прості).
На обласній учнівскій проста задача на графи була (на АСМКонтестері вона буде на онлайнверсії змагання і потім у загальному архіві).
мене на жаль не було на лекції, але чув, що майже не наводили псевдокодів у звязку з браком часу. Можливо не варто так багато давати на одну лекцію? На мою думку половина теорії графів на 2 години це дуже багато.
P.S. Мене повідомили, що вийшла моя стаття з цієї тематики.
Ця стаття була каркасом моєї магістерської роботи, тобто, містила основні результати.
Бажаючі можуть ознайомитися з її вмістом тут: http://www.nbuv.gov.ua/portal/natural/VNULP/Komp-nauky/2009_650/36.pdf
P.P.S. Я цілий тиждень провів у лікарні, мені вирізали апендикс, тому я не зміг прийти в четвер