English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

Перейти к полному списку специальных курсов кафедры

Программа специального курса "Теория графов и синтез БИС"

Руководители курса: доц. Часовских А.А., н.с. Половников В.С.
Время и место проведения: понедельник 18:30 в ауд. 14-05.

2013/14 учебный год.

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



Литература.

  1. В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. – М.: Наука Гл. Ред. Физ.-мат. Лит., 1990. – 384 с.

  2. А.Ф. Сидоренко. О минимальных прямоугольных штейнеровых деревьях. Журнал «Дискретная математика». Том 1, вып. 2, 1989 г., с. 28 – 37.

  3. Дискретная математика и математические вопросы кибернетики. Под общей редакцией С.В. Яблонского и О.Б. Лупанова. Том 1. – М.: Наука Гл. Ред. Физ.-мат. Лит., 1974. – 312 с.

  4. В.Н. Нефедов, В.А. Осипов. Курс дискретной математики. Учеб. пособие. – М.: Изд-во МАИ, 1992. – 264 с.

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru