Теория дискретных функций и приложения
Название спецкурса на английском языке
Discrete functions theory and applications
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2026/27
Список тем
Методы понижения размерности
Линейное предсказание
Графы, наруженные графы, теорема Форда-Фалкерсона, минимальное остовное дерево
Цепи Маркова
Источники и автоматы
Теорема Клини
Автоматы преобразователи информации
Теоремы о полноте для суперптозиции
Обратная связь, о задаче выразимости
Линейное предсказание
Графы, наруженные графы, теорема Форда-Фалкерсона, минимальное остовное дерево
Цепи Маркова
Источники и автоматы
Теорема Клини
Автоматы преобразователи информации
Теоремы о полноте для суперптозиции
Обратная связь, о задаче выразимости
Список источников
Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979
Кудрявцев В.Б., Гаврилов Г.П., Яблонский С.В., Функции алгебры логики и классы Поста. Наука, М., 1966.
Кудрявцев В.Б., Алешин С.В., Подколзин А.С. "Введение в теорию конечных автоматов".- М.:Наука,1985
Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.
Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.
Чегис И.А., Яблонский С.В., Логические способы контроля электрических схем // Труды МИАН им. В.А. Стеклова т.51, 1958, с. 270-360.
Алешин С.В. Распознавание динамических образов, изд. МГУ, 1996.
Кудрявцев В.Б., Гаврилов Г.П., Яблонский С.В., Функции алгебры логики и классы Поста. Наука, М., 1966.
Кудрявцев В.Б., Алешин С.В., Подколзин А.С. "Введение в теорию конечных автоматов".- М.:Наука,1985
Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.
Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.
Чегис И.А., Яблонский С.В., Логические способы контроля электрических схем // Труды МИАН им. В.А. Стеклова т.51, 1958, с. 270-360.
Алешин С.В. Распознавание динамических образов, изд. МГУ, 1996.
Дополнительная информация
специальный курс для студентов включает следующие разделы дискретной математики: «Теория графов; «Теория кодирования»; «Дискретная оптимизация», «Теория вероятностей» и др.
Дополнительные дискуссии в Zoom Meeting ID: 452 832 0761, Passcode: 8gdJck
День недели
четверг
Время
16:45-18:20
Аудитория
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Нейронные сети
Название спецкурса на английском языке
Neural networks
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2026/27
Список тем
Биологические нейронные сети, построение математической модели. Искусственные нейронные сети. Задачи, решаемые нейронными сетями.
Модель МакКаллока-Питтса. Нейронный базис, нейронные схемы. Понятие кусочно-линейных, кусочно-постоянных и кусочно-параллельных функций в действительном многомерном пространстве.
Теорема о выразимости нейронных схем. Понятие эквивалентности. Следствие о существовании нейронной схемы нелинейной глубины не более двух.
Теорема о существовании нейронных функций не представимых нейронными схемами нелинейной глубины один. Критерий однослойности нейронных схем.
Задача проверки полноты в пространстве кусочно-параллельных функций.
Теорема о нелинейной сложности нейронных схем без памяти.
Персептрон. Строгая линейная отделимость. Алгоритм Розенблатта. Теорема Новикова.
Алгоритмы обучения (алгоритм обратного распространения ошибки и его вариации), выбор гиперпараметров. Функции потерь.
Разнообразие архитектур нейронных сетей. Свёрточные нейронные сети. Базовые слои и принципы построения сети.
Сложности процедуры обучения нейронных сетей. Затухающие градиенты, градиентный взрыв, переобучение. Регуляризация, слой dropout, пакетная и другие виды нормализации. Подходы к инициализации весов.
Открытые базы данных MNIST, CIFAR, ImageNet, MS COCO, Pascal VOC и др. Платформа Kaggle. Соревнования нейросетевых алгоритмов.
Задача классификации. Основные архитектуры VGG, Resnet, WideResnet, MobileNet, Inception, Xception, ConvNext.
Масштабирование нейронных сетей. Архитектура EfficientNet. Подходы к автоматическому построению архитектур (NAS).
Модель МакКаллока-Питтса. Нейронный базис, нейронные схемы. Понятие кусочно-линейных, кусочно-постоянных и кусочно-параллельных функций в действительном многомерном пространстве.
Теорема о выразимости нейронных схем. Понятие эквивалентности. Следствие о существовании нейронной схемы нелинейной глубины не более двух.
Теорема о существовании нейронных функций не представимых нейронными схемами нелинейной глубины один. Критерий однослойности нейронных схем.
Задача проверки полноты в пространстве кусочно-параллельных функций.
Теорема о нелинейной сложности нейронных схем без памяти.
Персептрон. Строгая линейная отделимость. Алгоритм Розенблатта. Теорема Новикова.
Алгоритмы обучения (алгоритм обратного распространения ошибки и его вариации), выбор гиперпараметров. Функции потерь.
Разнообразие архитектур нейронных сетей. Свёрточные нейронные сети. Базовые слои и принципы построения сети.
Сложности процедуры обучения нейронных сетей. Затухающие градиенты, градиентный взрыв, переобучение. Регуляризация, слой dropout, пакетная и другие виды нормализации. Подходы к инициализации весов.
Открытые базы данных MNIST, CIFAR, ImageNet, MS COCO, Pascal VOC и др. Платформа Kaggle. Соревнования нейросетевых алгоритмов.
Задача классификации. Основные архитектуры VGG, Resnet, WideResnet, MobileNet, Inception, Xception, ConvNext.
Масштабирование нейронных сетей. Архитектура EfficientNet. Подходы к автоматическому построению архитектур (NAS).
Список источников
Хайкин С. «Нейронные сети: полный курс», Вильямс 2006.
Гудфеллоу Я., Бенджио И. «Глубокое обучение», ДМК Пресс, 2017
Ф. Шолле «Глубокое обучение на Python», Питер, 2018 г.
Емеличев В.А. и др. Лекции по теории графов. – М.: Наука, 1990.
Половников В.С. «Об оптимизации структурной реализации нейронных сетей» диссертация на соискание степени кандидата наук, 2007
O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. «Imagenet large scale visual recognition challenge», 2014 http://www.image-net.org/
Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, Piotr Dollár «Microsoft COCO: Common Objects in Context» https://arxiv.org/abs/1405.0312 http://cocodataset.org
Everingham, M., Eslami, S. M. A., Van Gool, L., Williams, C. K. I., Winn, J. and Zisserman, A. «The PASCAL Visual Object Classes Challenge: A Retrospective» International Journal of Computer Vision, 111(1), 98-136, 2015 http://host.robots.ox.ac.uk/pascal/VOC/
Lecun, Yann & Bottou, Leon & Bengio, Y & Haffner, Patrick. «Gradient-Based Learning Applied to Document Recognition», 1998. Proceedings of the IEEE. 86. 2278 - 2324. 10.1109/5.726791.
Alex Krizhevsky, Ilya Sutskever, Geoffrey Hinton «ImageNet Classification with Deep Convolutional Neural Networks», NIPS 2012
Karen Simonyan, Andrew Zisserman «Very deep convolutional networks for large scale image recognition», ICLR 2015 https://arxiv.org/abs/1409.1556
Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun «Deep Residual Learning for Image Recognition» https://arxiv.org/abs/1512.03385
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, Andrew Rabinovich «Going Deeper with Convolutions» Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1–9, 2015 https://arxiv.org/abs/1409.4842
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, Zbigniew Wojna «Rethinking the Inception Architecture for Computer Vision» https://arxiv.org/abs/1512.00567
Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, Alex Alemi «Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning» https://arxiv.org/abs/1602.07261
Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi «You Only Look Once: Unified, Real-Time Object Detection», ECCV 2016 https://arxiv.org/abs/1506.02640
Joseph Redmon, Ali Farhadi «YOLOv3: An Incremental Improvement»
Ross Girshick, Jeff Donahue, Trevor Darrell, Jitendra Malik «Rich feature hierarchies for accurate object detection and semantic segmentation» https://arxiv.org/abs/1311.2524
Ross Girshick «Fast R-CNN» https://arxiv.org/abs/1504.08083
Shaoqing Ren, Kaiming He, Ross Girshick, Jian Sun «Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks» https://arxiv.org/abs/1506.01497
Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, Piotr Dollár «Focal Loss for Dense Object Detection» https://arxiv.org/abs/1708.02002
Olaf Ronneberger, Philipp Fischer, Thomas Brox «U-Net: Convolutional Networks for Biomedical Image Segmentation» https://arxiv.org/abs/1505.04597
Kaiming He, Georgia Gkioxari, Piotr Dollár, Ross Girshick «Mask R-CNN» https://arxiv.org/abs/1703.06870
Vijay Badrinarayanan, Alex Kendall, Roberto Cipolla «SegNet: A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation» https://arxiv.org/abs/1511.00561
Jia, Yangqing and Shelhamer, Evan and Donahue, Jeff and Karayev, Sergey and Long, Jonathan and Girshick, Ross and Guadarrama, Sergio and Darrell, Trevor «Caffe: Convolutional Architecture for Fast Feature Embedding» https://arxiv.org/abs/1408.5093 http://caffe.berkeleyvision.org/
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, Raia Hadsell “Overcoming catastrophic forgetting in neural networks” https://arxiv.org/abs/1612.00796
Friedemann Zenke, Ben Poole, Surya Ganguli “Continual Learning Through Synaptic Intelligence” https://arxiv.org/abs/1703.04200
Andrei A. Rusu, Neil C. Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, Raia Hadsell “Progressive Neural Networks” https://arxiv.org/abs/1606.04671
Zhizhong Li, Derek Hoiem “Learning without Forgetting” https://arxiv.org/abs/1606.09282
Jiankang Deng, Jia Guo, Yuxiang Zhou, Jinke Yu, Irene Kotsia, Stefanos Zafeiriou “RetinaFace: Single-stage Dense Face Localisation in the Wild” https://arxiv.org/abs/1905.00641
Jiankang Deng, Jia Guo, Niannan Xue, Stefanos Zafeiriou “ArcFace: Additive Angular Margin Loss for Deep Face Recognition” https://arxiv.org/abs/1801.07698
Гудфеллоу Я., Бенджио И. «Глубокое обучение», ДМК Пресс, 2017
Ф. Шолле «Глубокое обучение на Python», Питер, 2018 г.
Емеличев В.А. и др. Лекции по теории графов. – М.: Наука, 1990.
Половников В.С. «Об оптимизации структурной реализации нейронных сетей» диссертация на соискание степени кандидата наук, 2007
O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. «Imagenet large scale visual recognition challenge», 2014 http://www.image-net.org/
Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, Piotr Dollár «Microsoft COCO: Common Objects in Context» https://arxiv.org/abs/1405.0312 http://cocodataset.org
Everingham, M., Eslami, S. M. A., Van Gool, L., Williams, C. K. I., Winn, J. and Zisserman, A. «The PASCAL Visual Object Classes Challenge: A Retrospective» International Journal of Computer Vision, 111(1), 98-136, 2015 http://host.robots.ox.ac.uk/pascal/VOC/
Lecun, Yann & Bottou, Leon & Bengio, Y & Haffner, Patrick. «Gradient-Based Learning Applied to Document Recognition», 1998. Proceedings of the IEEE. 86. 2278 - 2324. 10.1109/5.726791.
Alex Krizhevsky, Ilya Sutskever, Geoffrey Hinton «ImageNet Classification with Deep Convolutional Neural Networks», NIPS 2012
Karen Simonyan, Andrew Zisserman «Very deep convolutional networks for large scale image recognition», ICLR 2015 https://arxiv.org/abs/1409.1556
Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun «Deep Residual Learning for Image Recognition» https://arxiv.org/abs/1512.03385
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, Andrew Rabinovich «Going Deeper with Convolutions» Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1–9, 2015 https://arxiv.org/abs/1409.4842
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, Zbigniew Wojna «Rethinking the Inception Architecture for Computer Vision» https://arxiv.org/abs/1512.00567
Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, Alex Alemi «Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning» https://arxiv.org/abs/1602.07261
Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi «You Only Look Once: Unified, Real-Time Object Detection», ECCV 2016 https://arxiv.org/abs/1506.02640
Joseph Redmon, Ali Farhadi «YOLOv3: An Incremental Improvement»
Ross Girshick, Jeff Donahue, Trevor Darrell, Jitendra Malik «Rich feature hierarchies for accurate object detection and semantic segmentation» https://arxiv.org/abs/1311.2524
Ross Girshick «Fast R-CNN» https://arxiv.org/abs/1504.08083
Shaoqing Ren, Kaiming He, Ross Girshick, Jian Sun «Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks» https://arxiv.org/abs/1506.01497
Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, Piotr Dollár «Focal Loss for Dense Object Detection» https://arxiv.org/abs/1708.02002
Olaf Ronneberger, Philipp Fischer, Thomas Brox «U-Net: Convolutional Networks for Biomedical Image Segmentation» https://arxiv.org/abs/1505.04597
Kaiming He, Georgia Gkioxari, Piotr Dollár, Ross Girshick «Mask R-CNN» https://arxiv.org/abs/1703.06870
Vijay Badrinarayanan, Alex Kendall, Roberto Cipolla «SegNet: A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation» https://arxiv.org/abs/1511.00561
Jia, Yangqing and Shelhamer, Evan and Donahue, Jeff and Karayev, Sergey and Long, Jonathan and Girshick, Ross and Guadarrama, Sergio and Darrell, Trevor «Caffe: Convolutional Architecture for Fast Feature Embedding» https://arxiv.org/abs/1408.5093 http://caffe.berkeleyvision.org/
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, Raia Hadsell “Overcoming catastrophic forgetting in neural networks” https://arxiv.org/abs/1612.00796
Friedemann Zenke, Ben Poole, Surya Ganguli “Continual Learning Through Synaptic Intelligence” https://arxiv.org/abs/1703.04200
Andrei A. Rusu, Neil C. Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, Raia Hadsell “Progressive Neural Networks” https://arxiv.org/abs/1606.04671
Zhizhong Li, Derek Hoiem “Learning without Forgetting” https://arxiv.org/abs/1606.09282
Jiankang Deng, Jia Guo, Yuxiang Zhou, Jinke Yu, Irene Kotsia, Stefanos Zafeiriou “RetinaFace: Single-stage Dense Face Localisation in the Wild” https://arxiv.org/abs/1905.00641
Jiankang Deng, Jia Guo, Niannan Xue, Stefanos Zafeiriou “ArcFace: Additive Angular Margin Loss for Deep Face Recognition” https://arxiv.org/abs/1801.07698
Дополнительная информация
Канал в Telegram: https://t.me/+UJkSUkOE90D_RdXu
День недели
среда
Время
15:00-16:35
Аудитория
404
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Комбинаторные методы дискретной математики
Название спецкурса на английском языке
Combinatorial methods of discrete mathematics
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2026/27
Список тем
Модели вычислений, используемые для оценки сложности алгоритмов и вычислений
Меры сложности алгоритмов
Труднорешаемость задач
Классы P и NP и их свойства
NP-полные задачи
Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний
Полиномиальная сводимость задач
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения
Оптимизация алгоритмов перебора
Политика жадности
Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии
Матроиды
Характеризация случаев оптимальности жадных алгоритмов
Теорема Радо- Эдмонса.
Меры сложности алгоритмов
Труднорешаемость задач
Классы P и NP и их свойства
NP-полные задачи
Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний
Полиномиальная сводимость задач
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения
Оптимизация алгоритмов перебора
Политика жадности
Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии
Матроиды
Характеризация случаев оптимальности жадных алгоритмов
Теорема Радо- Эдмонса.
Список источников
Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. Москва, 1992. 140 стр.
Дополнительная информация
Для 5го курса МаТИС
Изучение классического раздела дискретной математики, разработанной в целях приложений к компьютерным наукам, касающимся вопросов обработки дискретной информации (Теории дискретных систем, Существования и перечисления комбинаторных конфигураций, Методов оптимизации комбинаторных алгоритмов). Изучение основных комбинаторных чисел и конфигураций, используемых при анализе дискретных систем и касающихся вопросов обработки и передачи информации.
День недели
среда
Время
15:00-16:35
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Алгебраические системы автоматов
Название спецкурса на английском языке
Algebraic automata systems
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2026/27
Список тем
Свободные группы
Группы Бернсайда
Матрицы
Группы Бернсайда
Матрицы
Список источников
книга С.В.Алешин Алгебраические системы автоматов, изд-во МГУ, 2016 г
Дополнительная информация
Занятия начинаются в 10-50
День недели
суббота
Время
10:45-12:20
Аудитория
1201
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Распознавание образов
Название спецкурса на английском языке
Image recognition
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2026/27
Список тем
Тесты
Короткие тесты
Разделяющие поверхности
Теорема Новикова
Комбинаторно-логический подход к распознаванию образов
Иерархическая распознающая система
Короткие тесты
Разделяющие поверхности
Теорема Новикова
Комбинаторно-логический подход к распознаванию образов
Иерархическая распознающая система
Список источников
Распознавание динамических образов, Алешин С.В., 1996, изд-во МГУ Москва
Теория интеллектуальных систем: в 4 кн. Книга первая. Распознавание образов, Кудрявцев В.Б., Гасанов Э.Э., Подколзин А.С. , 2018
Теория интеллектуальных систем: в 4 кн. Книга первая. Распознавание образов, Кудрявцев В.Б., Гасанов Э.Э., Подколзин А.С. , 2018
День недели
четверг
Время
18:30-20:05
Аудитория
414
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Алгоритмическая алгебра
Название спецкурса на английском языке
Algorithmic algebra
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2026/27
Список тем
Элементы теории рекурсивных функций и алгоритмов.
Частично рекурсивные функции как вариант формализации понятия алгоритма. Примитивно рекурсивные и общерекурсивные функции.
Перечислимые, разрешимые, примитивно рекурсивные предикаты, отношения,
множества.
Теорема Аккермана (о диагональной одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией).
Теоремы об устранимости кванторов в элементарных теориях (в теориях 1-го порядка) некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теоремы об устранимости кванторов в монадических теориях 2-го порядка некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования (без доказательства). Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования.
Применения теорем о разрешимости монадических теорий 2-го порядка к доказательству разрешимости некоторых теорий 1-го порядка.
Частично рекурсивные функции как вариант формализации понятия алгоритма. Примитивно рекурсивные и общерекурсивные функции.
Перечислимые, разрешимые, примитивно рекурсивные предикаты, отношения,
множества.
Теорема Аккермана (о диагональной одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией).
Теоремы об устранимости кванторов в элементарных теориях (в теориях 1-го порядка) некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теоремы об устранимости кванторов в монадических теориях 2-го порядка некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования (без доказательства). Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования.
Применения теорем о разрешимости монадических теорий 2-го порядка к доказательству разрешимости некоторых теорий 1-го порядка.
Список источников
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965
Панкратьев Е.В. Элементы компьютерной алгебры – М.: Интернет-университет информационных технологий
Рабин М. Разрешимые теории. Справочная книга по математической логике. Часть 3 Теория рекурсии. – Москва: Наука, 1982
Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980
Панкратьев Е.В. Элементы компьютерной алгебры – М.: Интернет-университет информационных технологий
Рабин М. Разрешимые теории. Справочная книга по математической логике. Часть 3 Теория рекурсии. – Москва: Наука, 1982
Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980
Дополнительная информация
В курсе освещаются следующие вопросы:
1) начальные сведения по теории алгоритмов и теории конечных автоматов,
2) уравнения в словах в свободном моноиде,
3) метод устранения кванторов,
4) алгоритмическая разрешимость теорий некоторых классов алгебраических систем.
Нужные для понимания спецкурса сведения по математической логике и алгебре будут кратко напоминаться по ходу лекций.
Курс переносится на весенний семестр
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.