Алгебраические структуры в информатике
Название спецкурса на английском языке
Algebraic structures in computer science
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра теоретической информатики]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Неотрицательные матрицы. Перестановочная матрица. Неразложимая матрица. Критерии неразложимости. Сильно связный граф. Определение сильной связности графа через отсутствие собственных замкнутых подграфов. Примитивные матрицы. Связь с графами. Спектр, радиус матрицы. Теорема Перрона-Фробениуса.
Приложения неотрицательных матриц: числа Фибоначчи, популяция, модель Леонтьева, марковский процесс (разбор случая с двумя состояниями), PageRank.
Матрица смежности графа, её свойства. Характеристический многочлен, спектр графа. Быстрый подсчёт числа маршрутов.
Матрица Кирхгофа, её свойства. Кратность нуля спектра, алгебраические дополнения матрицы Кирхгофа.
Матрица инцидентности. Связь с матрицей Кирхгофа.
Число остовных деревьев связного графа. Число связных компонент графа.
Бинарные отношения. Лемма Бёрнсайда. Число неориентируемых графов без петель с заданным числом вершин.
Инварианты графов. Полный инвариант. Полиномиальные инварианты графов. Хроматические многочлен, многочлен Абеля.
Автоморфизмы и эндоморфизмы графов.
Свойства перманента. Теорема Фробениуса об определителе. Теорема Маркуса-Минка.
Алгебра над полем. Алгебра кватернионов: базис, ассоциативность, норма, сопряжение. Формула произведения кватернионов через скалярные и векторные части. Алгоритм вращения при помощи кватернионов.
Квазигруппы, лупы. Изотопность квазигрупп. Алгоритм Дамма. Квазигруппы в криптографии.
Тропическая алгебра. Идемпотентное полукольцо. Maxplus-алгебра: арифметика, матрицы. Построение регулярного расписания. Вычисление собственного значения для тропических неразложимых матриц. Heap-модель.
Некоммутативная криптография. Тропическая криптография. Криптосхема Месси-Омуры. Схема Эль-Гамаля над группой точек эллиптической кривой.
Разложение матрицы в произведение двух симметричных (эрмитовых). Действительнозначная жорданова клетка. Приложения LU-разложения и разложения Холецкого. Псевдообратная матрица. Сингулярное разложение и его приложения.
Приложения неотрицательных матриц: числа Фибоначчи, популяция, модель Леонтьева, марковский процесс (разбор случая с двумя состояниями), PageRank.
Матрица смежности графа, её свойства. Характеристический многочлен, спектр графа. Быстрый подсчёт числа маршрутов.
Матрица Кирхгофа, её свойства. Кратность нуля спектра, алгебраические дополнения матрицы Кирхгофа.
Матрица инцидентности. Связь с матрицей Кирхгофа.
Число остовных деревьев связного графа. Число связных компонент графа.
Бинарные отношения. Лемма Бёрнсайда. Число неориентируемых графов без петель с заданным числом вершин.
Инварианты графов. Полный инвариант. Полиномиальные инварианты графов. Хроматические многочлен, многочлен Абеля.
Автоморфизмы и эндоморфизмы графов.
Свойства перманента. Теорема Фробениуса об определителе. Теорема Маркуса-Минка.
Алгебра над полем. Алгебра кватернионов: базис, ассоциативность, норма, сопряжение. Формула произведения кватернионов через скалярные и векторные части. Алгоритм вращения при помощи кватернионов.
Квазигруппы, лупы. Изотопность квазигрупп. Алгоритм Дамма. Квазигруппы в криптографии.
Тропическая алгебра. Идемпотентное полукольцо. Maxplus-алгебра: арифметика, матрицы. Построение регулярного расписания. Вычисление собственного значения для тропических неразложимых матриц. Heap-модель.
Некоммутативная криптография. Тропическая криптография. Криптосхема Месси-Омуры. Схема Эль-Гамаля над группой точек эллиптической кривой.
Разложение матрицы в произведение двух симметричных (эрмитовых). Действительнозначная жорданова клетка. Приложения LU-разложения и разложения Холецкого. Псевдообратная матрица. Сингулярное разложение и его приложения.
Список источников
Хорн Р., Джонсон Ч., "Матричный анализ", М.: Мир, 1989
Гантмахер Ф.Р., "Теория матриц", М.: Наука, 1967
Асанов М. О., Баранский В. А., "Графы, матроиды, алгоритмы", Расин В. В.: Дискретная математика: — НИЦ РХД, 2001. — 288 с.
Гроссман И., Магнус В., "Группы и их графы", 1971
В. И. Арнольд, "Геометрия комплексных чисел, кватернионов и спинов", М.: МЦНМО, 2002, 40 с
Прасолов В.В. "Задачи и теоремы линейной алгебры", МЦНМО, 2015, 579 с
Bernd Heidergott, Geert Jan Olsder, and Jacob van der Woude, "Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications", Princeton Series in Applied Mathematics, 2005
Кривулин Н.К., "Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем", СПб.: Изд-во С.-Петерб. ун-та, 2009, 256 с.
Лидл Р., Нидеррайтер Г., "Конечные поля" в 2-х томах, 1988
Куракин В.Л., Нечаев А.А., "Линейные коды и полилинейные рекурренты"
Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А., "Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы", М.: КомКнига, 2006, 328 с.
А. С. Кузьмин, В. Т. Марков, А. А. Михалёв, А. В. Михалёв, А. А. Нечаев,
"Криптографические алгоритмы на группах и алгебрах", Фундамент. и прикл.
матем., 2015, том 20, выпуск 1, 205–222
Белоусов В. Д. «Основы теории квазигрупп и луп» — М.: Наука, 1967. — 224с.
Минк Х., "Перманенты", Мир, 1982, 216 с.
М. Э. Казарян, "Тропическая геометрия", М.: МЦНМО, 2012. — 43 с.
Харари Ф., "Теория графов", 2003.
Зыков А.А., "Основы теории графов", М.: Наука, 1987. — 381 с.
Гантмахер Ф.Р., "Теория матриц", М.: Наука, 1967
Асанов М. О., Баранский В. А., "Графы, матроиды, алгоритмы", Расин В. В.: Дискретная математика: — НИЦ РХД, 2001. — 288 с.
Гроссман И., Магнус В., "Группы и их графы", 1971
В. И. Арнольд, "Геометрия комплексных чисел, кватернионов и спинов", М.: МЦНМО, 2002, 40 с
Прасолов В.В. "Задачи и теоремы линейной алгебры", МЦНМО, 2015, 579 с
Bernd Heidergott, Geert Jan Olsder, and Jacob van der Woude, "Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications", Princeton Series in Applied Mathematics, 2005
Кривулин Н.К., "Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем", СПб.: Изд-во С.-Петерб. ун-та, 2009, 256 с.
Лидл Р., Нидеррайтер Г., "Конечные поля" в 2-х томах, 1988
Куракин В.Л., Нечаев А.А., "Линейные коды и полилинейные рекурренты"
Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А., "Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы", М.: КомКнига, 2006, 328 с.
А. С. Кузьмин, В. Т. Марков, А. А. Михалёв, А. В. Михалёв, А. А. Нечаев,
"Криптографические алгоритмы на группах и алгебрах", Фундамент. и прикл.
матем., 2015, том 20, выпуск 1, 205–222
Белоусов В. Д. «Основы теории квазигрупп и луп» — М.: Наука, 1967. — 224с.
Минк Х., "Перманенты", Мир, 1982, 216 с.
М. Э. Казарян, "Тропическая геометрия", М.: МЦНМО, 2012. — 43 с.
Харари Ф., "Теория графов", 2003.
Зыков А.А., "Основы теории графов", М.: Наука, 1987. — 381 с.
Дополнительная информация
Для понимания достаточно алгебры первых трёх семестров специалитета или годового курса алгебры для магистров.
Запись по почте viktoria.tenzina@math.msu.ru
День недели
четверг
Время
16:45-18:20
Аудитория
407
Дата первого занятия
Аудитория первого занятия
407
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.