Цей архів містить матеріал курсу "Розширені теми в алгоритмах графів" ©, який викладає Рон Шамір на кафедрі комп'ютерних наук Тель-Авівського університету , 10/91-2/92 (осінь 92), 4-6/94 ( Весна 94) та 4-6/97 (Весна 97). Це був односеместровий випускний курс, відкритий також для людей похилого віку, з однією тригодинною зустріччю щотижня.
Курс підкреслював алгоритмічні та структурні аспекти "приємних" сімейств графіків, зокрема досконалі графіки, інтервальні графіки, хордові графіки та графіки порівнянності.
Восени 92 року курс значною мірою базувався на класичній книзі Мартіна Голумбіка «Теорія алгоритмічних графіків та досконалі графіки» (Academic Press, 1980), а в деяких частинах також на рукописі «Мистецтво комбінаторики», по Дугласу Б. Захід.
Весна 94 і навесні 97 курсу був подібна основа, але підкреслив , більш свіжий матеріал, і зробив багато посилань на додатки в області молекулярної біології (див . веб - сторінці алгоритмів для молекулярної біології набагато більше з цих аспектів .)
Переклади на кілька мов див. Нижче.
Доступний матеріал:
- Матеріал курсу весни 1997 року (неорганізований; деякі посилання не оновлювалися, а деякі матеріали можна читати лише браузерам TAU. Вибачте.)
- Лекції «Писарі весни 94»
Розмови були написані студентами та переглянуті лектором. Повний комплект нотаток згодом відредагував і відформатував Саріель Хар-Пелед . Дякую, Саріель!
Ви можете завантажити цілі нотатки як єдиний файл післяпису (150 сторінок), або кожну лекцію окремо.
Переклад конспектів лекцій іншими мовами дивіться тут.
- Обкладинка
- Зміст
- Список фігур
Лекція №1: Вступ до теорії графів
- Основні визначення та позначення
- Графи перетину
- Кругові дугові графіки
- Інтервальні графіки
- Лінійні графіки дводольних графіків
- Визначення ідеального графа
- Деякі визначення та властивості
- Теорема досконалого графа
Лекція №3: Ідеальні та трикутні графіки
- Ідеальні графіки
- $ p $ -критичні графіки
- Поліедральна характеристика ідеальних графів
- Сильна досконала гіпотеза про графік
- Трикутні графіки
- Вступ
- Характеристика трикутних графіків
- Розпізнавання трикутних графіків
- Складність часу
Лекція №4: Розпізнавання трикутних графіків
- Розпізнавання трикутних графіків
- Створення PEO
- Тестування схеми ліквідації
- Наївний алгоритм
- Ефективний алгоритм
- Приклад
- Правильність алгоритму
- Складність алгоритму
- Трикутні графіки як графі перетину
- Еволюційні дерева
- Трикутні графіки як графі перетину
Лекція №5: Трикутні графіки ідеальні
- Трикутні графіки ідеальні
- Доведення цієї властивості
- Інші результати
- Обчислення мінімального заповнення
- Проблема
- Заповнити NP-Hard
- Ланцюгові графіки
- Оптимальне лінійне розташування (OLA)
- Завершення графічного ланцюжка (CGC)
- Результат для заповнення
- Проблеми
Лекція №6: Алгоритми триангульованих графіків та графіків порівнянності
- Деякі алгоритми оптимізації на трикутних графіках
- Обчислення хроматичного числа та всіх максимальних кліків
- Знаходження $ \ alpha $ і $ k $
- Графіки порівнянності
- Деякі визначення
- Класи наслідків
- Лема про трикутник
- Розкладання графіків
Лекція №7: Унікально частково впорядковані графіки
- Унікально частково упорядковані графіки
- Характеристика та алгоритми розпізнавання
Лекція №8: Деякі цікаві сімейства графіків, що характеризуються перетином
- Вступ
- Перестановочні графіки
- $ F $-Графіки
- `` Удари диспетчерів повітря ''
- Склад діаграми перестановок.
- Графіки допусків
- Інтервальні графіки як підмножина графіків допусків.
- Графіки обмежених та необмежених допусків.
Лекція №9: Графіки порівнянності
- Графічне розпізнавання порівнянності
- Складність розпізнавання графіків порівнянності
- Реалізація
- Аналіз складності
- Забарвлення та інші проблеми на графіках порівнянності
- Графіки порівнянності ідеальні
- Максимально зважена кліка
- Обчислення $ \ alpha (G) $
- Вимір часткових порядків
Лекція № 10: Інваріанти порівнянності та інтервальні графіки
- Інваріанти порівнянності
- Інтервальні графіки
- Перевага та байдужість
- Розпізнавання інтервальних графіків
- Квадратний алгоритм 1
- Лінійний алгоритм
- Докладніше про властивість послідовного 1
Лекція No12 : Тимчасові міркування
- Алгебри часового розумування та інтервалу
- Проблеми задоволення інтервалів
- Проблеми інтервальних сендвічів та ISAT
- Лінійний алгоритм часу для ISAT ($ \ Delta _1} $)
- Пропускна здатність, ширина траси та правильна ширина траси
Будь ласка, надсилайте всі відгуки та коментарі на адресу: rshamir@tau.ac.il