Теория графов и синтез больших интегральных схем

Название спецкурса на английском языке
Graph theory and design of large integrated circuits
Авторы курса
Часовских Анатолий Александрович, Половников Владимир Сергеевич, Ронжин Дмитрий Владимирович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2026/27
Список тем
Основы технологии синтеза БИС.
Логический синтез. Конечный автомат как модель БИС.
Задача трассировки. Минимальные прямоугольные деревья Штейнера: теорема существования, алгоритмы построения, алгоритм для приближенного решения.
Задача укладки. Минимальные разрезы в графе: алгоритмы точного и приближенного решения. Задача разбиения: эвристические алгоритмы.
Специализированные схемы (сортировки, сложения, умножения).
Плоские клеточные схемы. Оценки сложности специализированных плоских клеточных схем.
Эвристические алгоритмы укладки. Gordian алгоритм.
Список источников
Емеличев В.А. и др. Лекции по теории графов.
Lengauer Thomas, Combinatorial Algorithms for Integrated Circuit Layout
https://edu.ikit.sfu-kras.ru/drupal/node/305.html
https://edu.ikit.sfu-kras.ru/drupal/node/313.html
А. Ф. Сидоренко О минимальных прямоугольных штейнеровых деревьях// Дискрет. матем., 1989, 1:2, 28–37
Н. А. Шкаликова О реализации булевых функций схемами из клеточных элементов//Математические вопросы кибернетики, вып. 2
Дополнительная информация

Канал в Telegram: https://t.me/+6LiFWjBAnsBmMTc6

День недели
понедельник
Время
15:00-16:35
Аудитория
473
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.