Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web development, networking and server security. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.
Складні теми в графіку алгоритми
Original on http://www.math.tau.ac.il/~rshamir/atga/atga.html
Цей архів містить матеріал по курсу "Складні теми у графіку Алгоритми" © вчив Рон Шамір у відділі комп'ютерних наук Тель-Авівського університету, на 10/91-2/92 (осінь 92), 4-6/94 ( Весна 94) і 4-6/97 (Весна 97). Це був один семестр аспірантуру відкритий також для літніх людей, з одного тригодинної зустрічі щотижня.
Звичайно підкреслив, алгоритмічного та структурні аспекти "добре" сім'ї графа, зокрема, скоєних графів, графів інтервалів, акордових діаграм і порівнянності графіків.
Восени 92 звичайно був заснований в значній мірі на класичний книзі
"Алгоритмічні Теорія графів і досконалих графів "(М.: Наука, 1980), а в деяких районах і на рукопис" Мистецтво Комбінаторика ", за
Б. Дуглас Заходу.
Весна 94 і 97 Весна курс був аналогічній основі, але підкреслив, останні матеріал, і зробив багато посиланням на застосування в молекулярній біології. (Див. сторінки
для більш з цих аспектів.)
Матеріал в альбомі:
- Детальна схема звичайно.
- Весна 97 (HTML)
- Весна 94 (ASCII)
- Падіння 92 (ASCII)
- Навесні 1997 року навчальний матеріал (неорганізовані;.. деякі посилання не оновлювалися, і якийсь матеріал для читання тільки для браузерів Вибачте ТАУ)
-
Книжники весни 94 лекцій
Переговори були описується студентів і переглянутий лектора. Повний набір нотаток був згодом відредагований і відформатовано . Дякую, Sariel!Ви можете завантажити повну зазначає в якості одного файлу постскриптум (150 сторінок), або кожної лекції окремо.
Покриття
- Обкладинка
- Зміст
- Список малюнків
Лекція № 1: Введення в теорії графів
- Основні визначення та позначення
- Перетин графіків
- Циркуляр-дугового Графіки
- Інтервал Графіки
- Лінії графіків дводольних графів
Лекція № 2: скоєних графів
- Визначення досконалий графік
- Деякі визначення та властивості
- Ідеальний графік теореми
Лекція № 3: Досконалі і Тріангулірованние Графіки
- Досконалих графів
- $ Р $-критичні графи
- Багатогранні Характеристика скоєних графів
- Сильні Ідеальний Гіпотеза Графік
- Тріангулірованние Графіки
- Введення
- Характеризуючи Тріангулірованние Графіки
- Визнаючи Тріангулірованние Графіки
- Час Складність
Лекція № 4: Визнаючи Тріангулірованние Графіки
- Визнаючи Тріангулірованние Графіки
- Створення ПЕО
- Тестування ліквідації схеми
- Наївний алгоритм
- Ефективний алгоритм
- Приклад
- Коректність алгоритму
- Складність алгоритму
- Тріангулірованние Графіки як перетин графіків
- Еволюційні дерева
- Тріангулірованние Графіки як перетин графіків
Лекція № 5: Тріангулірованние Графіки ідеально
- Тріангулірованние Графіки ідеально
- Доказ готель
- Інші результати
- Обчислювальна Мінімальні Fill In
- Проблема
- Fill In є NP-жорсткий
- Мережа Графіки
- Оптимальне лінійне розташування (УПВ)
- Мережа Графік завершення (CGC)
- Результат для Заповнити
- Проблеми
Лекція № 6: Алгоритми для тріангулірованних графіки та порівнянності графи
- Деякі Алгоритми оптимізації на Тріангулірованние Графіки
- Обчислювальна хроматичної число і всі максимальні кліки
- Пошук $ \ альфа $ і $ K $
- Порівнянність Графіки
- Деякі визначення
- Наслідки Класи
- Трикутник леми
- Розкладання Графіки
Лекція № 7: Унікально Частково замовлений Графіки
- Унікально Частково замовлений Графіки
- Характеристики та алгоритми розпізнавання
Лекція № 8: Деякі цікаві сім'ї графа характеризується перетином
- Введення
- Перестановка графи
- $ F $-графіки
- `` Авіадиспетчерів страйк''
- Склад перестановки діаграми.
- Толерантність графи
- Інтервал графів як підмножина толерантності графіків.
- Обмежені і необмежені терпимості графіків.
Лекція № 9: Порівнянність Графіки
- Визнання Порівнянність Графік
- Складність Порівнянність Визнання Графік
- Реалізація
- Складність аналізу
- Фарбування та інші проблеми на порівнянність Графіки
- Порівнянність Графіки ідеально
- Максимальний зважений Clique
- Розрахунок $ \ альфа (G) $
- Розмірності часткових порядків
Лекція № 10: Порівнянність інваріанти і графи інтервалів
- Порівнянність інваріанти
- Інтервальних графів
Лекція № 11: графи інтервалів
- Привілейовані і байдужість
- Визнаючи інтервальних графів
- Квадратичний алгоритм 1
- Лінійний алгоритм
- Детальніше про послідовні власності 1 в
Лекція № 12: Тимчасові Міркування
- Часовий інтервал мислення та алгебри
- Інтервал проблеми здійсненності
- Інтервал сендвіч проблеми і ISAT
- Лінійний алгоритм часу для ISAT ($ \ Delta _1} $)
- Пропускна здатність, Pathwidth і належне Pathwidth
Індекс
Будь ласка, надсилайте всі коментарі та відгуки: shamir@math.tau.ac.il
Повернутися на головну сторінку Рона