Линейные автоматы
Название спецкурса на английском языке
Linear automata
Пререквизиты
Знание курса Дискретной математики, читаемого на 1-м курсе и курса Алгебры, читаемого на 1-м и 2-м курсах
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Линейный автомат как преобразователь степенных рядов.
Операторы замыкания в классе линейных автоматов. Проблема полноты.
Аппроксимационно предполные классы. Решение задачи об аппроксимационной полноте в классе линейных автоматов над простым полем.
Решение задачи об аппроксимационной полноте в классе линейных автоматов над конечным полем.
Предполные классы по операциям композиции. Решение задачи о полноте в классе линейных автоматов над простым полем.
Решение задачи о полноте в классе линейных автоматов над конечным полем.
Операторы замыкания в классе линейных автоматов. Проблема полноты.
Аппроксимационно предполные классы. Решение задачи об аппроксимационной полноте в классе линейных автоматов над простым полем.
Решение задачи об аппроксимационной полноте в классе линейных автоматов над конечным полем.
Предполные классы по операциям композиции. Решение задачи о полноте в классе линейных автоматов над простым полем.
Решение задачи о полноте в классе линейных автоматов над конечным полем.
Список источников
Гилл А. Линейные последовательные машины, М. : Наука, 1974, 287 с.
Часовских А. А. Условия полноты линейно-p-автоматных функций // Интеллектуальные системы. Теория и приложения. – 2014.– Т. 18, вып. 3.– С. 203 –252.
Часовских А. А. Проблема полноты для класса линейно-автоматных функций // Дискретная математика. – 2015.– Т. 27, № 2.– С. 134—151; Discrete Math. Appl., 26:2 (2016), 89 – 104.
Часовских А. А. Максимальные подклассы в классах линейных автоматов над конечными полями // Дискретная математика. – 2019.– Т. 31, № 4.– С. 88—101; Discrete Math. Appl., 30:6 (2020), 365 – 374.
Часовских А. А. Замкнутые классы линейно-автоматных функций // Математические вопросы кибернетики. – 2004.– Вып. 13.– С. 113 –136. (https://library.keldysh.ru/mvk.asp?id=2004-113)
Часовских А. А. Линейно-автоматные функции с операциями суперпозиции // Нейрокомпьютеры: разработка, применение. – 2013.– № 8.– С. 3 –13.
Часовских А. А. О полноте в классе линейных 2-адических автоматов // Интеллектуальные системы. Теория и приложения. – 2016.– Т. 20, вып. 4.– С. 209 –227.
Часовских А. А. Условия полноты линейно-p-автоматных функций // Интеллектуальные системы. Теория и приложения. – 2014.– Т. 18, вып. 3.– С. 203 –252.
Часовских А. А. Проблема полноты для класса линейно-автоматных функций // Дискретная математика. – 2015.– Т. 27, № 2.– С. 134—151; Discrete Math. Appl., 26:2 (2016), 89 – 104.
Часовских А. А. Максимальные подклассы в классах линейных автоматов над конечными полями // Дискретная математика. – 2019.– Т. 31, № 4.– С. 88—101; Discrete Math. Appl., 30:6 (2020), 365 – 374.
Часовских А. А. Замкнутые классы линейно-автоматных функций // Математические вопросы кибернетики. – 2004.– Вып. 13.– С. 113 –136. (https://library.keldysh.ru/mvk.asp?id=2004-113)
Часовских А. А. Линейно-автоматные функции с операциями суперпозиции // Нейрокомпьютеры: разработка, применение. – 2013.– № 8.– С. 3 –13.
Часовских А. А. О полноте в классе линейных 2-адических автоматов // Интеллектуальные системы. Теория и приложения. – 2016.– Т. 20, вып. 4.– С. 209 –227.
Дополнительная информация
Канал в Telegram: t.me/sk_lin_auto
День недели
среда
Время
16:45-18:20
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
434
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Теория графов и синтез больших интегральных схем
Название спецкурса на английском языке
Graph theory and design of large integrated circuits
Пререквизиты
Дискретная математика за 1-й курс
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Основы технологии синтеза БИС.
Логический синтез. Конечный автомат как модель БИС.
Задача трассировки. Минимальные прямоугольные деревья Штейнера: теорема существования, алгоритмы построения, алгоритм для приближенного решения.
Задача укладки. Минимальные разрезы в графе: алгоритмы точного и приближенного решения. Задача разбиения: эвристические алгоритмы.
Специализированные схемы (сортировки, сложения, умножения).
Плоские клеточные схемы. Оценки сложности специализированных плоских клеточных схем.
Эвристические алгоритмы укладки. Gordian алгоритм.
Логический синтез. Конечный автомат как модель БИС.
Задача трассировки. Минимальные прямоугольные деревья Штейнера: теорема существования, алгоритмы построения, алгоритм для приближенного решения.
Задача укладки. Минимальные разрезы в графе: алгоритмы точного и приближенного решения. Задача разбиения: эвристические алгоритмы.
Специализированные схемы (сортировки, сложения, умножения).
Плоские клеточные схемы. Оценки сложности специализированных плоских клеточных схем.
Эвристические алгоритмы укладки. 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,
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
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
465
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.