Перейти к полному списку специальных курсов кафедры
Программа специального курса "Теория графов и синтез БИС"
2013/14 учебный год.
- Планарная технология. Фотолитография. Принцип работы МОП-транзистора. КМОП реализация базовых логических элементов. Реализация автоматных функций КМОП-схемами.
- Основные понятия теории графов. Дерево. Критерии, определяющие свойство графа быть деревом. Минимальное остовное дерево (м.о.д.) в связном взвешенном графе. Алгоритмы Краскала и Прима нахождения м.о.д. в связном взвешенном графе.
- Формализация понятия большой интегральной схемы (БИС). Логическая схема. Укладка логической схемы. Гиперребра и граф противоречий. Определение БИС. Задача укладки элементов БИС и задача трассировки проводников.
- Прямоугольная задача Штейнера. Теорема о существовании решения. Алгоритм нахождения минимального прямоугольного Штейнерова дерева.
- Число вершинной связности и число реберной связности для графа. Связь этих характеристик графа между собой и с минимумом степеней вершин. Критерии двусвязности графа. Блоковый граф для данного графа, его свойства. Теорема о существовании в 3-связном графе двух вершин, удаление которых приводит к графу, не содержащему точек сочленения. Теорема Менгера.
- Плоские графы. Грань плоского графа. Планарные графы. Теорема Эйлера. Доказательство непланарности графов K5 и K3,3. Критерий двусвязности плоского графа. Сведение задачи укладки графа к задачи укладки его блоков. Плоский граф, как подграф плоской триангуляции. Максимальный плоский граф и плоская триангуляция. Связь между числом вершин и числом ребер в плоской триангуляции. Сведение проверки планарности графа к аналогичному вопросу для трехсвязных графов. Теорема Понтрягина-Куратовского. Теорема Вагнера. Гамма-алгоритм для проверки планарности графа и укладки графа на плоскости (в случае его планарности ).
- Степенная последовательность графа, n-последовательность, графическая последовательность. Теорема о возможности перехода от одной реализации графической последовательности к другой с использованием операции переключения. Критерии графичности последовательности: теоремы Гавела-Хакими и Эрдеша-Галлаи.
- Хроматическое число графа. Критерий бихроматичности графа. Сведение задачи определения хроматического числа графа к определению хроматических чисел его блоков. Теорема Брукса. Достижимость оценки, доставляемой теоремой Брукса. Теорема Зыкова. Неравенства, связывающие число вершин графа, число его независимости и хроматическое число. Точность этих неравенств. Представление хроматической функции графа суммой хроматических функций полных графов. Хроматическая функция дерева. Теорема о возможности раскраски планарного графа не более чем в 5 цветов. Проблема 4-х красок. Теорема Крола.
- Сортирующие сети. Правило нуля и единицы. Битонический сортировщик. Сортирующая сеть с глубиной равной по порядку квадрату логарифма от числа входов.
- Реализация схем сложения и умножения n-разрядных двоичных чисел с глубиной O(log n). Метод Уолеса.
- Задача отыскания кратчайшего пути между двумя заданными вершинами во взвешенном графе. Алгоритм Дийкстры. Корректность алгоритма Дийкстры, оценка времени его работы на графе с n вершинами. Применение алгоритма Дийкстры при решении задачи поиска кратчайшего пути на плоскости с многоугольными препятствиями между двумя заданными точками, а также к решению дискретной геодезической задачи.
- Двудольные графы. Критерий двудольности графов. Алгоритм поиска наибольшего паросочетания в двудольном графе и оценка времени его работы на графах с n вершинами. Алгоритм построения совершенного паросочетания минимального веса во взвешенном графе Kn,n и оценка времени его работы.
- Потоки в сетях. Максимальный поток, минимальный разрез. Теорема Форда-Фалкерсона. Алгоритмы Эдмондса-Карпа и 'проталкивания предпотока' поиска максимального потока, оценки времени работы этих алгоритмов.
- Алгоритмы Кернигана-Лина и Федосия-Матеуса для нахождения минимального сбалансированного разреза в графе, оценки времени работы этих алгоритмов.
- Гордиан-алгоритм для приближенного поиска наилучшей укладки графа.
Литература.
В.А. Емеличев, О.И.
Мельников, В.И. Сарванов, Р.И. Тышкевич.
Лекции по теории графов. - М.: Наука Гл.
Ред. Физ.-мат. Лит., 1990. - 384 с.
А.Ф. Сидоренко. О
минимальных прямоугольных штейнеровых
деревьях. Журнал 'Дискретная математика'.
Том 1, вып. 2, 1989 г., с. 28 - 37.
Дискретная математика
и математические вопросы кибернетики.
Под общей редакцией С.В. Яблонского и
О.Б. Лупанова. Том 1. - М.: Наука Гл. Ред.
Физ.-мат. Лит., 1974. - 312 с.
В.Н. Нефедов, В.А.
Осипов. Курс дискретной математики.
Учеб. пособие. - М.: Изд-во МАИ, 1992. - 264
с.
Наверх
|