Четверта лекція другого сезону відбудеться 14 жовтня о 18 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: GeKa та CUPIDON.
Тема: Вступ до алгоритмів на графах.
На порядку денному:
- Означення та приклади графів.
- Способи представлення графів.
- Орієнтовані та неорієнтовані графи.
- Обхід графа в ширину і в глибину.
- Зважені графи та алгоритми пошуку найкоротших шляхів.
ого! супер! вже не можу дочекатись коли почую цю лекцію! графи дуже цікава тема!
Ой, мій улюблений лектор буде
1) Коли і де можна буде скачати відеозаписи пропущених лекцій?
2) В силу обмеженості місця в авдиторії, коли можна буде під’єднатися до лекції, маючи навушники і камеру через скайп оовоо або подібні технології?
Дякую.
шукаючи цитати Dragonspirit’a знайшов цікаву цитату:
http://ukrbash.org/quote/2310
“Плем’я людожерів узяло у полон красуню білявку. Відпустити її чи з’їсти має вирішити зібрання 100 старійшин, які дуже полюбляють банани. «Доброму» вождю людожерів білявка дуже сподобалась і він хоче прийняття зборами рішення про її звільнення, але «зла» дружина вождя проти цього. При вирішенні долі білявки кожен старійшина віддасть свій голос за ту пропозицію, за яку одержить більше бананів. Якщо старійшина одержує однакову кількість бананів від протилежних сторін, то при голосуванні він утримується. Щоб будь-яке рішення було прийняте необхідно, щоб «ЗА» проголосував принаймні 51 старійшина. Вождь знає, що дружина може роздати старійшинам не більше 1000 бананів. Яку мінімальну кількість бананів і по скільки повинен роздати вождь, щоб гарантувати прийняття рішення на свою користь, не зважаючи на те, у який спосіб роздасть банани його дружина.
хм… на олімпіаді для абітурієнтів дали задачу про хабарюків О_о”
До речі, цікава задачка з теорії чисел:
нехай р – просте число. Знайдіть усі натуральні n, такі що число (р-n)!(n-1)!+(-1)^n-1 ділиться на р
До речі, про графи найкраще написано у цих двох книжках:
Cormen, Leiserson, Rivest, Stein. Introduction to algorithms
mainika_optimization_network_graph
Э.Майника
АЛГОРИТМЫ ОПТИМИЗАЦИИ НА СЕТЯХ И ГРАФАХ
М.: Мир, 1981, 324 стр.
Предисловие редактора перевода 5
Предисловие 7
Глава 1. Введение в теорию графов и сетей 9
1.1. Вводные замечания 9
1.2. Некоторые понятия и определения 11
1.3. Линейное программирование 15
Упражнения 21
Литература 22
Глава 2. Алгоритмы построения деревьев 23
2.1. Алгоритмы построения покрывающих деревьев 23
2.2. Алгоритм построения максимального ориентированного леса 30
Упражнения 40
Литература 41
Глава 3. Алгоритмы поиска путей 42
3.1. Алгоритм поиска кратчайшего пути 42
3.2. Алгоритмы поиска всех кратчайших путей 51
3.3. Алгоритм поиска k кратчайших путей 63
3.4. Поиск других оптимальных путей 77
Упражнения 81
Литература 83
Глава 4. Потоковые алгоритмы 84
4.1. Введение 84
4.2. Алгоритм поиска максимального потока 91
4.3. Алгоритм поиска потока минимальной стоимости 100
4.4. Алгоритм дефекта 111
4.5. Алгоритм поиска динамического потока 122
4.6. Потоки с усилениями 146
Упражнения 166
Литература 170
Глава 5. Алгоритмы поиска паросочетаний и покрытий 171
5.1. Введение 171
5.2. Алгоритм решения задачи о паросочетаний максимальной мощности 175
5.3 Алгоритм выбора паросочетания с максимальным весом 189
5.4. Алгоритм построения покрытия с минимальным весом 201
Упражнения 216
Литература 218
Глава 6. Задача почтальона 219
6.1. Введение 219
6.2. Задача почтальона для неориентированного графа 222
6.3. Задача почтальона для ориентированного графа 227
6.4. Задача почтальона для смешанного графа 231
Упражнения 239
Литература 240
Глава 7. Задача коммивояжера 241
7.1. Формулировка и некоторые свойства решений задачи коммивояжера 241
7.2. Условия существования гамильтонова контура 244
7.3. Нижние границы 251
7.4. Методы решения задачи коммивояжера 255
Упражнения 262
Литература 264
Глава 8. Задачи размещения 265
8.1. Введение 265
8.2. Задачи поиска центра 273
8.3. Задачи поиска медиан 279
8.4. Обобщения 287
Упражнения 288
Литература 289
Глава 9. Сетевые графика 290
9.1. Метод критического пути (МКП) 290
9.2. Определение длительности выполнения операции из условия
обеспечения минимальной стоимости 302
9.3. Обобщенные сетевые графики 309
Упражнения 315
Литература 318
Предметный указатель 319
Предметный указатель
Абсолютная медиана 272, 281
Абсолютный центр графа 272, 275
Алгебраическое направление теории
графов 10
Алгоритм 11, 15
- Данцига 51, 57—60, 63, 249
- – обобщенный 74—77
- Дейкстры 44—49, 61—63, 81
- дефекта 111, 113, 117—122, 304
- Джевелла 153
- Флойда 53, 58, 61—63
- – обобщенный 74—77
- Форда 49—51, 61—63
- – и Фалкерсона 92—101
- Эдмондса 178, 189
Анализ вычислительной сложности
60—63
Базисное решение 20, 21
Букет 25
Величина дефекта 116—118
Венгерское дерево 181—183
Вершина 10
- внешняя 180
- внутренняя 180
- конечная 12
- концевая 25
- насыщенная 203, 204
- начальная 12
- ненасыщенная 203, 205
- открытая 179
- паросочетания 179
- пустая 203
Вершинное число 105, 109, 151
Вес дерева 23
@patlatus
Ось вона ця легендарна цитата
http://ukrbash.org/quote/31972
@kilotaras:
Ти мене не зрозумів.
Я її знайшов. Точніше, я її ще бачив набагато раніше за згадування на цьому сайті.
Але мене заінтригувало інше, мене заінтригувала фраза автора: “До речі, з усіх мною доданих цитат, ця дійшла до кондиції в 200 голосів найшвидше! Я здивований.” – я вирішив пошукати інші цитати цього автора, цікаво було, що він ще про коледж писав. Я інших цитат не бачив. Виявляється, інші його цитати не про коледж, тому я розчарувався.
Домашка:
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1218&rid=4cb609dfdb2fe (1218 Котигорошко)
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1302&rid=4cb609dfdb2fe (1302 Сузір’я)
Клас – http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1078&
Цивілізація – http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1087&
Сусіднє село – http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1209&
Музикант заразний – http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1224&
Мені здається, що ми забагато часу тратимо на вступ та загальні поняття. Наприклад, сьогодні ми половину лекції розбирали, а що ж таке той граф (e.g. “а давайте проголосуємо з ким з’єднувати вершину один…”, “а яку вершину виберемо…”, “а давайте проголосуємо за те якими числами заповняти матрицю суміжності замість одиничок…” і т.д.), якщо на нього треба 5хв., і нехай по 5хв. на кожен із способів відображення. Чи наприклад на, здається, 2 лекції ми робирали лінійний пошук в масиві 8 хв.!! лінійний пошук! А бінарний лише 3-4 хв.! Хоча які він має способи застосування!
Можливо це лише на перших лекціях так, але тенденція не дуже хороша.
Про пошук: бінарний взагалі не входив в ту лекцію. По ньому буде окрема. Про нього я згадав тільки щоб ніхто не думав, що той лінійний пошук єдиний і найкращий =).
А на рахунок вступів, то думаю, варто провести опитування і визначити рівень відвідувачів. Думаю, не кожен і за 45 хз зрозумів, з якого ж графства той граф… =) Хоча, якщо 80% людей знає, що це таке, то може дійсно краще трохи менше часу на то приділяти і звертати УВАГУ на анонси лекцій – щоб читали щось ще до лекції. Тут пропоную ще в анонсі вказати задачки на домашнє завдання і якісь матеріали для підготовки.
Погоджуюсь із ідеєю про анонси. Краще коли слухачі будуть хоч мінімально ознайомлюватись вдома із темою майбутньої лекції. Тоді вони:
1) матимуть загальне уявлення про тему
2) знатимуть що для них важко сприймалось вдома і на що треба звернути увагу на лекції
3) зможуть підготувати питання, які їх зацікавили
4) звертатимуть більшу увагу на деталі
5) не відчуватимуть себе, мов “куди ми попали”
6) на лекції встигатимуть опрацювати більше
P.S. можна попробувати, а якщо буде погано, то повернутись до старого стилю
P.P.S. я думаю, що при наявності бажання знайти хоч 1 годину в тиждень, щоб ознайомитись із темою наступної лекції не є складно
Я теж не проти.
Треба буде на наступній лекції провести голосування про це
А змагання сьогодні будуть?
Ну шо… Я скажу дещо у своє оправдання… На базові знання на лекції було витрачено (чи використано?!) 40 хвилин часу. Я вважаю, шо ценормально, бо:
…
1)тема лекції “Вступ(!) до алгоритмів на графах”. Хіба Вам було не очевидно шу буде на лекції?!
2)Я вважаю, шо перша половина лекції НЕ була аж такою банальною… Я впевнений, шо , як мінімум, 50% слухачів не зали раніше про список суміжності. Особисто я ше рік тому не знав про список суміжності
До речі, саме через список суміжності робиться задачка “Котигорошко” та “Сузір’я”. Якшо я не помиляюсь, то матрицею суміжності та списком ребер ви того не зробите.
І… Якщо Вам не вдалось зробити ці дві задачки, не переживайте – ці задачки трохи випереджають тему, насправді про нихговоритимуть на наступній лекції. Але подумати над ними не завадить – це своєрідна підготовка до наступної лекції.
А, ледь не забув. На сайті E-Olimp розпочнеться в понеділок змагання на тиждень на тематику ГРАФІВ, а саме пошуку в ширину та глибину. Участь у цьому змаганні було б чудовим закріпленням теми. Ось посилання на це змагання:
http://www.e-olimp.com/ua/competitions/348
Якшо я не помиляюсь, то там досить цікава система таких замагань на тиждень – там кожного дня дописують нову задачу, тому не лякайтесь, якшо в понеділок побачите ЛИШЕ одну задачку – далі будуть і інші
… Ну шо, удачі вам на змаганні !)
CUPIDON, ти не подумай, це зауваження не до тебе
, а до усіх лекцій загалом, щоб зробити їх трішки складнішими. Це ж цікаво!
Треба колись провести лекцію “зібрання пропущеного”… Там сортування підрахунком не було, тут Флойда… Отак потрохи набереться.
Спробував це: http://www.e-olimp.com/ua/competitions/348
Першу задачу щось дуже довго мучив, написав спочатку один розв’язок, через рекурсію. Він пройшов 2,3,4,5-тий тест, по 8-мому тесту сказало, що вичерпано ліміт часу, решту тестів не пройшов.
Я подумав, ну, через рекурсію, це дуже тупо, це ж експоненціальний алгоритм, перебір усіх можливих випадків, спробую заюзати логіку. Задача схоже, на динамічне програмування, аналог дискретної задачі з рюкзаком. Скачав з вікіпедії код розв’язку дискретної задачі з рюкзаком, підправив з сішарпу на паскаль, замінив масив цін на той самий масив мас, підігнав під свою задачу, запустив, 1 тест пройшов – №1, решта не пройшло. Кумедно!
Пробував якось заюзати логіку по-іншому, зберігати вже пораховані значення рекурсивної процедури в матричку, не пройшло жодного тесту.
Потім подумав, а ну, зроблю так, якщо тест №1 підсуну розв’язок задачі з рюкзаком, а якщо решта, рекурсію, думав, точно 50% буде. Нєа, не канає, знову 40%, я в шоці)))
А друга задача про хід конем взагалі елементарна. Там навіть пошук в глибину підходить, не кажучи, що там можна значно оптимізувати, використавши пошук в ширину з поверненням – якщо знайшов значення то можна вертатися і для решти клітинок не обчислювати значення