Описание:Планарная технология. Фотолитография. Принцип работы МОП-транзистора. КМОП реализация базовых логических элементов. Реализация автоматных функций КМОП-схемами.
Основные понятия теории графов. Дерево. Критерии, определяющие свойство графа быть деревом. Минимальное остовное дерево (м.о.д.) в связном взвешенном графе. Алгоритмы Краскала и Прима нахождения м.о.д. в связном взвешенном графе.
Формализация понятия большой интегральной схемы (БИС). Логическая схема. Укладка логической схемы. Гиперребра и граф противоречий. Определение БИС. Задача укладки элементов БИС и задача трассировки проводников.
Прямоугольная задача Штейнера. Теорема о существовании решения. Алгоритм нахождения минимального прямоугольного Штейнерова дерева.
Число вершинной связности и число реберной связности для графа. Связь этих характеристик графа между собой и с минимумом степеней вершин. Критерии двусвязности графа. Блоковый граф для данного графа, его свойства. Теорема о существовании в 3-связном графе двух вершин, удаление которых приводит к графу, не содержащему точек сочленения. Теорема Менгера.
Плоские графы. Грань плоского графа. Планарные графы. Теорема Эйлера. Доказательство непланарности графов K5 и K3,3. Критерий двусвязности плоского графа. Сведение задачи укладки графа к задачи укладки его блоков. Плоский граф, как подграф плоской триангуляции. Максимальный плоский граф и плоская триангуляция. Связь между числом вершин и числом ребер в плоской триангуляции. Сведение проверки планарности графа к аналогичному вопросу для трехсвязных графов. Теорема Понтрягина-Куратовского. Теорема Вагнера. Гамма-алгоритм для проверки планарности графа и укладки графа на плоскости (в случае его планарности ).
Степенная последовательность графа, n-последовательность, графическая последовательность. Теорема о возможности перехода от одной реализации графической последовательности к другой с использованием операции переключения. Критерии графичности последовательности: теоремы Гавела-Хакими и Эрдеша-Галлаи.
Хроматическое число графа. Критерий бихроматичности графа. Сведение задачи определения хроматического числа графа к определению хроматических чисел его блоков. Теорема Брукса. Достижимость оценки, доставляемой теоремой Брукса. Теорема Зыкова. Неравенства, связывающие число вершин графа, число его независимости и хроматическое число. Точность этих неравенств. Представление хроматической функции графа суммой хроматических функций полных графов. Хроматическая функция дерева. Теорема о возможности раскраски планарного графа не более чем в 5 цветов. Проблема 4-х красок. Теорема Крола.
Сортирующие сети. Правило нуля и единицы. Битонический сортировщик. Сортирующая сеть с глубиной равной по порядку квадрату логарифма от числа входов.
Реализация схем сложения и умножения n-разрядных двоичных чисел с глубиной O(log n). Метод Уолеса.
Задача отыскания кратчайшего пути между двумя заданными вершинами во взвешенном графе. Алгоритм Дийкстры. Корректность алгоритма Дийкстры, оценка времени его работы на графе с n вершинами. Применение алгоритма Дийкстры при решении задачи поиска кратчайшего пути на плоскости с многоугольными препятствиями между двумя заданными точками, а также к решению дискретной геодезической задачи.
Двудольные графы. Критерий двудольности графов. Алгоритм поиска наибольшего паросочетания в двудольном графе и оценка времени его работы на графах с n вершинами. Алгоритм построения совершенного паросочетания минимального веса во взвешенном графе Kn,n и оценка времени его работы.
Потоки в сетях. Максимальный поток, минимальный разрез. Теорема Форда-Фалкерсона. Алгоритмы Эдмондса-Карпа и «проталкивания предпотока» поиска максимального потока, оценки времени работы этих алгоритмов.
Алгоритмы Кернигана-Лина и Федосия-Матеуса для нахождения минимального сбалансированного разреза в графе, оценки времени работы этих алгоритмов.
Гордиан-алгоритм для приближенного поиска наилучшей укладки графа.