Кафедра математической кибернетики - Вклад участника [ru]

Сложность алгоритмов

2024-12-16T09:23:37Z

AlekseevVB: /* Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418. */

Обязательный курс для студентов 418 группы. Читается в осеннем семестре.

Лектор - профессор [[Алексеев Валерий Борисович]].

== Программа курса ==
===Примеры задач с оценкой временной сложности по порядку.===
Сложность распознавания симметрии на машине Тьюринга.
Сложность распознавания полноты системы булевых функций на машине Тьюринга.

===Некоторые общие результаты о сложности алгоритмов.===
Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду.
Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между n и nlogn.

===Метод динамического пpогpаммиpования.===
Алгоpитм поиска кpатчайших путей между всеми паpами веpшин в гpафе. Алгоpитм для задачи об оптимальном поpядке умножения матpиц.

===Метод "pазделяй и властвуй" для построения быстрых алгоритмов.===
Алгоpитмы соpтиpовки вставкой и слиянием. Быстрые алгоpитмы для умножения чисел и матpиц.

===Метод pасшиpения модели для построения быстрых алгоритмов.===
Алгоpитмы обычного и булевского умножения матpиц с битовыми опеpациями. Алгоpитм тpанзитивного замыкания гpафа. Алгоpитмы для pаспознавания пpинадлежности булевых или многозначных функций, заданных векторно, некоторым замкнутым классам.

===Некоторые классы сложности.===
Определение классов DLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач. PSPACE-полные задачи.

==Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.==

[[Media:Вопросы_Сложность_алгоритмов_2024.doc|Вопросы к экзамену на январь 2025 года]]

== Литература ==
#[[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Изд. отдел ф-та ВМиК МГУ, 2002.
#Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
#Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
#Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
#Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.
#Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.

[[Категория:Лекционные_курсы_кафедры_МК]]

Файл:Вопросы Сложность алгоритмов 2024.doc

2024-12-16T09:22:10Z

AlekseevVB:

Сложность алгоритмов

2024-12-16T09:20:28Z

AlekseevVB: /* Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418. */

Обязательный курс для студентов 418 группы. Читается в осеннем семестре.

Лектор - профессор [[Алексеев Валерий Борисович]].

== Программа курса ==
===Примеры задач с оценкой временной сложности по порядку.===
Сложность распознавания симметрии на машине Тьюринга.
Сложность распознавания полноты системы булевых функций на машине Тьюринга.

===Некоторые общие результаты о сложности алгоритмов.===
Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду.
Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между n и nlogn.

===Метод динамического пpогpаммиpования.===
Алгоpитм поиска кpатчайших путей между всеми паpами веpшин в гpафе. Алгоpитм для задачи об оптимальном поpядке умножения матpиц.

===Метод "pазделяй и властвуй" для построения быстрых алгоритмов.===
Алгоpитмы соpтиpовки вставкой и слиянием. Быстрые алгоpитмы для умножения чисел и матpиц.

===Метод pасшиpения модели для построения быстрых алгоритмов.===
Алгоpитмы обычного и булевского умножения матpиц с битовыми опеpациями. Алгоpитм тpанзитивного замыкания гpафа. Алгоpитмы для pаспознавания пpинадлежности булевых или многозначных функций, заданных векторно, некоторым замкнутым классам.

===Некоторые классы сложности.===
Определение классов DLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач. PSPACE-полные задачи.

==Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.==

[[Media:Вопросы_Сложность_алгоритмов_2023.doc|Вопросы к экзамену на январь 2025 года]]

== Литература ==
#[[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Изд. отдел ф-та ВМиК МГУ, 2002.
#Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
#Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
#Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
#Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.
#Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.

[[Категория:Лекционные_курсы_кафедры_МК]]

Дискретная математика (1-й курс)

2024-05-29T09:35:48Z

AlekseevVB: /* Литература */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

== Экзамен 2024. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2024 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="20">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 2-6, 8-33, 35, 37-39)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 2-6, 8-33, 35, 37-39)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 2-5, 10-12, 20-28)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 1 (стр. 53-56) и вопрос 36 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 7)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 34 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2024-05-29T09:26:24Z

AlekseevVB: /* Часть В */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

== Экзамен 2024. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2024 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="20">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2024-05-29T09:25:23Z

AlekseevVB: /* Экзамен 2023. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2023 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

== Экзамен 2024. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2024 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Сложность алгоритмов

2023-12-18T10:28:57Z

AlekseevVB: /* Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418. */

Обязательный курс для студентов 418 группы. Читается в осеннем семестре.

Лектор - профессор [[Алексеев Валерий Борисович]].

== Программа курса ==
===Примеры задач с оценкой временной сложности по порядку.===
Сложность распознавания симметрии на машине Тьюринга.
Сложность распознавания полноты системы булевых функций на машине Тьюринга.

===Некоторые общие результаты о сложности алгоритмов.===
Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду.
Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между n и nlogn.

===Метод динамического пpогpаммиpования.===
Алгоpитм поиска кpатчайших путей между всеми паpами веpшин в гpафе. Алгоpитм для задачи об оптимальном поpядке умножения матpиц.

===Метод "pазделяй и властвуй" для построения быстрых алгоритмов.===
Алгоpитмы соpтиpовки вставкой и слиянием. Быстрые алгоpитмы для умножения чисел и матpиц.

===Метод pасшиpения модели для построения быстрых алгоритмов.===
Алгоpитмы обычного и булевского умножения матpиц с битовыми опеpациями. Алгоpитм тpанзитивного замыкания гpафа. Алгоpитмы для pаспознавания пpинадлежности булевых или многозначных функций, заданных векторно, некоторым замкнутым классам.

===Некоторые классы сложности.===
Определение классов DLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач. PSPACE-полные задачи.

==Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.==

[[Media:Вопросы_Сложность_алгоритмов_2023.doc|Вопросы к экзамену на январь 2024 года]]

== Литература ==
#[[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Изд. отдел ф-та ВМиК МГУ, 2002.
#Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
#Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
#Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
#Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.
#Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.

[[Категория:Лекционные_курсы_кафедры_МК]]

Файл:Вопросы Сложность алгоритмов 2023.doc

2023-12-18T10:27:52Z

AlekseevVB:

Файл:Вопросы ВКА 2023.pdf

2023-11-30T11:26:55Z

AlekseevVB:

Вероятностные и квантовые алгоритмы

2023-11-30T11:26:12Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:Вопросы_ВКА_2023.pdf|Вопросы к экзамену в январе 2024 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки.

*Лекция 5. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 6. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью.

*Лекция 7. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 8. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 9. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 10. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 11. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 12. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 13. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 272-280, 285-288.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-235, 239-242.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Вероятностные и квантовые алгоритмы

2023-11-30T11:03:21Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:ВКА_2023.zip|Вопросы к экзамену в январе 2024 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки.

*Лекция 5. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 6. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью.

*Лекция 7. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 8. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 9. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 10. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 11. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 12. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 13. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 272-280, 285-288.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-235, 239-242.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Файл:ВКА 2023.zip

2023-11-30T11:01:57Z

AlekseevVB:

Вероятностные и квантовые алгоритмы

2023-11-30T10:47:15Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:ВКА_2023.docx|Вопросы к экзамену в январе 2024 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки.

*Лекция 5. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 6. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью.

*Лекция 7. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 8. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 9. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 10. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 11. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 12. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 13. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 272-280, 285-288.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-235, 239-242.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Вероятностные и квантовые алгоритмы

2023-11-30T10:46:18Z

AlekseevVB: /* Программа курса */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:ВКА_2022.docx|Вопросы к экзамену в январе 2023 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки.

*Лекция 5. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 6. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью.

*Лекция 7. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 8. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 9. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 10. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 11. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 12. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 13. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 272-280, 285-288.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-235, 239-242.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Дискретная математика (1-й курс)

2023-05-25T14:58:29Z

AlekseevVB: /* Экзамен 2022. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

== Экзамен 2023. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2023 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2023-05-25T14:55:59Z

AlekseevVB: /* Экзамен 2021 г. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

== Экзамен 2022. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Просеминар для 2-го курса

2023-03-13T06:19:13Z

AlekseevVB: /* Программа просеминара */

{{DISPLAYTITLE:Просеминар для 2-го курса "Избранные вопросы дискретной математики и математической кибернетики"}}

'''Информация о просеминаре 2022-2023 учебного года.'''

= Общая информация =

Просеминар предназначен для знакомства студентов 2 курса с основными направлениями и наиболее интересными результатами проводимых на кафедре и в лаборатории исследований в области дискретной математики, теории графов, сложности алгоритмов, теории синтеза, надёжности и контроля дискретных управляющих систем, а также с применением этих результатов при решении некоторых задач проектирования СБИС и программирования.

Просеминар начинает свою работу с <span style="background:#FFDDDD">28</span>.02.2023 и проводится в форме независимых лекций-семинаров, на которые приглашаются все заинтересованные студенты 1 и 2 курсов. Предварительных знаний не требуется.

Занятия проходят '''по вторникам с 16:20 до 17:55 в ауд. <span style="background:#FFDDDD">503</span>'''. На первых семинарах 28 февраля и 7 марта с общей информацией о научной тематике кафедры, а также с интересными примерами решаемых задач выступят зав. кафедрой профессор [[Ложкин Сергей Андреевич|С.А.Ложкин]] и профессор [[Алексеев Валерий Борисович|В.Б.Алексеев]].

[[Информация для 2 курса|Общая информация о кафедре для студентов 2 курса бакалавриата.]]

= Программа просеминара =

'''Сложность алгебраических вычислений - примеры быстрых алгоритмов и нерешенные задачи.'''

* Докладчик: [[Алексеев Валерий Борисович|Алексеев В.Б.]]
* Дата: 28 февраля.
* Аннотация: Будет рассказано про нерешенную до конца («зависшую») проблему быстрого умножения матриц, про неожиданный алгоритм Штрассена для этой задачи и его обобщения, про следствия для быстрых алгоритмов на графах и в целом про сложность алгебраических вычислений.

'''Оптимальная реализация некоторых монотонных симметрических функций формулами на основе двоичных кодов.'''

* Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]]
* Дата: 7 марта.
* [[Media: Proseminar 2023.03.07 annotation.pdf|Аннотация]].

'''Сложность алгоритмов на графах.'''

* Докладчик: [[Алексеев Валерий Борисович|Алексеев В.Б.]]
* Дата: 14 марта.
* Аннотация: быстрый алгоритм транзитивного замыкания графа, быстрый приближенный алгоритм для поиска минимального вершинного покрытия, эйлеровы и гамильтоновы циклы, задача коммивояжера.

'''Проблемы сложности, надежности и контроля на примере реализации линейной и некоторых других булевых функций в модели контактных схем и BDD.'''

* Докладчик: [[Ложкин Сергей Андреевич|Ложкин С.А.]]
* Дата: 21 марта.
* Аннотация: Решение основных проблем и задач теории дискретных управляющих систем, указанных в теме семинара, будет рассмотрено на примере счетчика четности, то есть суммы по модулю 2 заданного числа булевых переменных, при его реализации в классах контактных схем, являющихся моделью транзисторного уровня современных сверхбольших интегральных схем, и BDD. Для счетчика четности будут построены: минимальная контактная схема и близкий к минимальному тест, диагностирующий обрыв одного из ее контактов; минимальная схема, корректирующая обрыв одного контакта.

= Материалы докладов прошлых лет =

[[Media:2016_Proseminar_FPGA.pdf|Программируемые логические интегральные схемы.]] (2016, [[Шуплецов Михаил Сергеевич|Шуплецов М.С.]])

[[Media:Proseminar_2016_Marchenko.pdf| Математические методы проектирования топологии СБИС.]] (2016, бывш. сотр. Марченко А.М.)

[[Media:Prosem_2016_Podymov_Zakharov.pdf| Дискретные модели и задачи управления компьютерными сетями.]] (2016, [[Захаров Владимир Анатольевич|Захаров В.А.]] и [[Подымов Владислав Васильевич|Подымов В.В.]])

Вероятностные и квантовые алгоритмы

2022-12-26T12:23:02Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:ВКА_2022.docx|Вопросы к экзамену в январе 2023 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 5. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Файл:ВКА 2022.docx

2022-12-26T12:22:19Z

AlekseevVB:

Вероятностные и квантовые алгоритмы

2022-12-26T10:41:31Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:Вопросы по курсу ВКА 2022.docx|Вопросы к экзамену в январе 2023 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 5. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Файл:Вопросы по курсу ВКА 2022.docx

2022-12-26T10:40:09Z

AlekseevVB:

Вероятностные и квантовые алгоритмы

2022-12-26T10:39:05Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:Вопросы по курсу ВКА 2022.docx|Вопросы к экзамену на январь 2023 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 5. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Вероятностные и квантовые алгоритмы

2022-12-26T10:31:50Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:Вопросы к экзамену по курсу ВКА 2022.docx|Вопросы к экзамену на январь 2023 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 5. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Вероятностные и квантовые алгоритмы

2022-12-26T10:26:00Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:ВКА_2022.docx|Вопросы к экзамену на январь 2023 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 5. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Файл:Вопросы к экзамену по курсу ВКА 2022.docx

2022-12-26T10:25:06Z

AlekseevVB:

Сложность алгоритмов

2022-12-21T09:24:44Z

AlekseevVB: /* Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418. */

Обязательный курс для студентов 418 группы. Читается в осеннем семестре.

Лектор - профессор [[Алексеев Валерий Борисович]].

== Программа курса ==
===Примеры задач с оценкой временной сложности по порядку.===
Сложность распознавания симметрии на машине Тьюринга.
Сложность распознавания полноты системы булевых функций на машине Тьюринга.

===Некоторые общие результаты о сложности алгоритмов.===
Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду.
Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между n и nlogn.

===Метод динамического пpогpаммиpования.===
Алгоpитм поиска кpатчайших путей между всеми паpами веpшин в гpафе. Алгоpитм для задачи об оптимальном поpядке умножения матpиц.

===Метод "pазделяй и властвуй" для построения быстрых алгоритмов.===
Алгоpитмы соpтиpовки вставкой и слиянием. Быстрые алгоpитмы для умножения чисел и матpиц.

===Метод pасшиpения модели для построения быстрых алгоритмов.===
Алгоpитмы обычного и булевского умножения матpиц с битовыми опеpациями. Алгоpитм тpанзитивного замыкания гpафа. Алгоpитмы для pаспознавания пpинадлежности булевых или многозначных функций, заданных векторно, некоторым замкнутым классам.

===Некоторые классы сложности.===
Определение классов DLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач. PSPACE-полные задачи.

==Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.==

[[Media:Вопросы_Сложность_алгоритмов_2022.doc|Вопросы к экзамену на январь 2023 года]]

== Литература ==
#[[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Изд. отдел ф-та ВМиК МГУ, 2002.
#Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
#Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
#Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
#Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.
#Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.

[[Категория:Лекционные_курсы_кафедры_МК]]

Файл:Вопросы Сложность алгоритмов 2022.doc

2022-12-21T09:23:14Z

AlekseevVB:

Дискретная математика (1-й курс)

2022-05-22T10:49:50Z

AlekseevVB: /* Экзамен (2021 г.) */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен 2021 г.==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Экзамен 2022. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:49:19Z

AlekseevVB: /* Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Экзамен 2022. Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:47:33Z

AlekseevVB: /* Часть В */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и других материалов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:45:42Z

AlekseevVB: /* Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

Экзамен планируется устный. В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:42:14Z

AlekseevVB: /* Литература */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Лекции (онлайн) Алексеева В.Б. по дискретной математике: https://www.youtube.com/watch?v=SAhzEOVDNEI&list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
<li> Весь материал имеется также в книге: Алексеев В.Б. Дискретная математика : учебник. М.: Инфра-М, 2021 (доступна в электронной библиотечной системе (ЭБС) Znanium.com).
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:38:35Z

AlekseevVB: /* Часть В */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>
Третьим пунктом в билете стоит задача по одной из 4 тем: алгебра логики, графы, коды, автоматы.
Задачи решаются без конспектов и любых других материалов.

После ответа на билет возможна прогонка по всему материалу без конспекта (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы.

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:37:52Z

AlekseevVB: /* Часть В */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:33:29Z

AlekseevVB: /* Часть А */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием).
<li> Теорема Маркова.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:28:58Z

AlekseevVB: /* Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
<li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:28:22Z

AlekseevVB: /* Часть А */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.).
Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами.
Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»).
Определения и формулировки – без конспектов.

===Часть А===
Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами. Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
<li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:27:47Z

AlekseevVB: /* Часть В */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.).
Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами.
Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»).
Определения и формулировки – без конспектов.

===Часть А===
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
<li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
Часть В – ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:24:17Z

AlekseevVB: /* Вопросы к экзамену по курсу «Дискретная математика», 2022 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика» для 2 и 3 потоков, 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.).
Можно смотреть текст на ноутбуке, но нельзя пользоваться мобильными телефонами.
Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»).
Определения и формулировки – без конспектов.

===Часть А===
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
<li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:21:32Z

AlekseevVB: /* Вопросы к экзамену по курсу «Дискретная математика», 2022 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика», 2022 год.==

В билете 2 вопроса (один из части А и один из части В) и задача.

Часть А – ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определения и формулировки – без конспектов.

===Часть А===
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
<li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Дискретная математика (1-й курс)

2022-05-22T10:18:53Z

AlekseevVB: /* Вопросы к экзамену по курсу «Дискретная математика», 2021 год. */

== Лекторы ==
*проф. [[Алексеев Валерий Борисович| Алексеев Валерий Борисович]]
*проф. [[Марченков Сергей Серафимович| Марченков Сергей Серафимович]]
*проф. [[Селезнева Светлана Николаевна| Селезнева Светлана Николаевна]]

==Экзамен (2021 г.)==

'''Вторая пересдача экзамена состоится 18 сентября (в субботу) очно в ауд. 609. Начало в 12 ч'''.

Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами, они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи, они оцениваются в 4 балла каждое.

Продолжительность написания работы - 2 ч (120 мин).

[[Media: example-dm1-exam.pdf | Примерный вариант экзаменационной работы]]

Экзамен проводится очно в аудитории 609. Работу нужно написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются экзаменаторам. Но предварительно выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png нужно отослать по эл. почте dm1@cs.msu.ru, в теме письма нужно написать фамилию, инициалы и номер группы студента, выполнившего работу.

Оценки за экзамен станут известны 20 сентября (в понедельник) в 14 ч. После этого по эл. почте dm1@cs.msu.ru будут приниматься апелляции. Во вторник, 21 сентября, в 12 ч апелляции будут рассматриваться очно. После обсуждения всех апелляций оценки будут поставлены в ведомости.

'''Стандартные задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
*Записать заданную k-значную функцию в 1-й или 2-й форме.
*Найти полином по модулю k заданной k-значной функции при заданном простом числе k или проверить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном числе k.
*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, в которой любые два различные состояния отличимы, для заданной автоматной функции.

== Вопросы к экзамену по курсу «Дискретная математика», 2022 год.==

===Часть А===
<ol>
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона) (вопрос № 1 только для студентов 2-3 потоков).
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
<li> Лемма о нелинейной функции.
<li> Теорема Поста о полноте системы функций алгебры логики.
<li> Теорема о предполных классах.
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.
<li> Деревья. Свойства деревьев.
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
<li> Теорема о раскраске планарных графов в 5 цветов.
<li> Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием).
<li> Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
<li> Неравенство Макмиллана.
<li> Существование префиксного кода с заданными длинами кодовых слов.
<li> Теорема редукции.
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
<li> Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
</ol>

=== Часть В ===
<ol start="22">
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
<li> Полные системы. Примеры полных систем (с доказательством полноты).
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
<li> Понятие замкнутого класса. Замкнутость классов T0, T1, L.
<li> Класс монотонных функций, его замкнутость.
<li> Лемма о несамодвойственной функции.
<li> Лемма о немонотонной функции.
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
<li> k-значные функции. Теорема о представлении k-значных функций 1-й формой.
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
<li> Корневые деревья. Верхняя оценка их числа.
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
<li> Планарные (плоские) графы. Формула Эйлера.
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Оптимальные коды, их свойства.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
</ol>

===Литература===
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс. (Вопросы 3-6, 8, 10-36, 38, 40-42)
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. (Вопросы 1, 3-7, 12-14, 22-31)
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. (Вопрос 2 (стр. 53-56) и вопрос 39 (задача 4.9 из главы 7))
<li> [[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Издательский отдел факультета ВМК МГУ, 2002 (Вопрос 9)
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990 (Вопрос 37 (стр. 36-37 и 237))
</ol>

[[Категория:Лекционные курсы кафедры МК]]

Участник:AlekseevVB

2021-12-14T09:52:34Z

AlekseevVB: /* Избранные публикации */

{{DISPLAYTITLE:Алексеев Валерий Борисович}}
[[Image:Alekseev.jpg|thumb|right|Алексеев Валерий Борисович]]'''Алексеев Валерий Борисович''' — доктор физико-математических наук, профессор.

== [[Области научных интересов]] ==

=== Сложность алгоритмов, квантовые алгоритмы ===

Разрабатываются методы ускорения алгоритмов на различных дискретных структурах, рассматриваются квантовые алгоритмы. Изучается проблема установления сложности алгоритмов умножения матриц. Устанавливаются связи между существованием быстрых алгоритмов для различных задач и существованием алгебр специальной структуры. Строятся быстрые полиномиальные алгоритмы для распознавания свойств дискретных (булевых, k-значных) функций.

=== Теория функциональных систем ===

Изучается структура решетки замкнутых классов в множестве частичных k-значных функций. Изучаются специальные базисы в k-значных логиках.

=== Оценки количества дискретных функций ===

Разрабатываются методы оценки числа дискретных функций с заданными свойствами. Устанавливается асимптотика логарифма числа функций от n переменных в различных классах.

== Лекционные курсы ==

* [[Дискретная математика (1й курс)]]
* [[Сложность алгоритмов]]
* [[Вероятностные и квантовые алгоритмы]]

== Спецсеминары ==
* [[Дискретная математика и математическая кибернетика]]
* [[Дискретные функции и сложность алгоритмов]]

== Аспиранты и студенты ==

== Избранные публикации ==

# О простых базисах k-значной логики // Математические заметки, 1969, т. 5, вып.4, с.471-482.
# Простые базисы и простые функции в k-значной логике // Кибернетика, 1971, N5, с.137-141.
# О числе простых базисов в k-значной логике // Сб. "Дискретный анализ". Вып.19. Новосибирск, 1971. С.3-10.
# О числе k-значных монотонных функций // ДАН СССР, 1973, т.208, N3, с.505-508.
# О числе монотонных k-значных функций // Сб. "Проблемы кибернетики". Вып.28. М.: Наука. 1974. С.5-24.
# Использование симметрии при нахождении ширины частично упорядоченного множества // Дискретн. анализ, 1974, вып.26, из-во СО АН СССР, с. 20-35.
# О расшифровке некоторых классов монотонных многозначных функций // Журнал вычислит. математики и мат. физики, 1976, т.16, N.1, с.189-198.
# Толщина произвольного полного графа // Математический сборник, 1976, т. 101(143), вып.2(10) (совм. с Гончаковым В. С.)
# Теорема Абеля в задачах и решениях // М.: Наука, 1976.
# О разложении полного графа на подграфы, вложимые в плоскую целочисленную решетку // Сб."Методы дискретного анализа в синтезе управляющих систем", 1978, вып.32, из-во СО АН СССР, с.3-20. (совм. с Мартиновой М. К.)
# О полупростых базисах k-значной логики // Математические заметки, 1980, т.28, вып.3, с.407-422.
# О числе функций в классах, задаваемых центральными предикатами // Математические заметки. - 1985. Т. 37, вып.6 - С.880-886.
# On the complexity of some algorithms of matrix multiplication // Journal of algorithms, 1985, т.6, с.71-85.
# Метод построения быстрых алгоритмов в k-значной логике // Матем. заметки. 1985. 38, вып. 1. С. 148-156. (совм. с Емельяновым Н. Р.)
# Recognition of properties in k-valued logic and approximate algorithms // Lecture Notes in Computer Science. Springer-Verlag, 1987. Т.278. С. 10-13.
# Ступенчатые билинейные алгоритмы и распознавание полноты в k-значных логиках // Известия ВУЗов. Математика. 1988, N.7. С.19-27.
# Сложность умножения матриц. Обзор. // Кибернетический сб. М.:Мир, 1988, вып. 25, с. 189-236.
# О числе функций в некоторых замкнутых классах частичной k-значной логики // Дискретная математика. 1989. Т.1, вып.1. С.32-42.
# О числе семейств подмножеств, замкнутых относительно пересечения // Дискретная математика. Т. 1, вып. 2 (1989). С. 129-136.
# Вложения графов в поверхности и теория графов тока // Дискретная математика, 1990, т.2, вып.4, с.97-115. (совм. с Коржиком В. П.)
# Элементы теории графов и схем. // М.: Изд-во МГУ, 1991. 40 с. (совм. с [[Ложкин Сергей Андреевич|Ложкиным С. А.]])
# О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика, 1994, т.6, вып.4, с.58-79.(совм. с [[Вороненко Андрей Анатольевич|Вороненко А. А.]])
# О некоторых алгебрах, связанных с быстрыми алгоритмами // Дискретная математика. 1996, т.8, N 1, с. 52-64.
# Логические полукольца и их использование для построения быстрых алгоритмов // Вестн. Моск. ун-та. Матем. механ. 1997, N 1. С. 22-29.
# Минимальные расширения с простым умножением для алгебры матриц второго порядка // Дискретная математика. 1997, т.9, N 1, с. 71-82.
# О сложности распознавания полноты систем функций в классе P_3^* // Вестн. Моск. ун-та. Матем. механ. 1997, N 3. (совм. с Кривенко М. М.)
# От метода А.А.Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Труды МИРАН, 1997, т. 218. С.22-27.
# Метод искусственных ограничений для оценки числа дискретных функций // Сб. "Математические вопросы кибернетики". Вып. 8 (1999). М.: Наука. С. 123-134.
# Элементы теории графов, схем и автоматов. // М.: Издательский отдел ф-та ВМиК МГУ, 2000. 58 с. (совм. с [[Ложкин Сергей Андреевич|Ложкиным С. А.]])
# Теорема Абеля в задачах и решениях // М.: МЦНМО, 2001 (новое издание, [http://www.mccme.ru/free-books/pdf/alekseev.pdf PDF]).
# Введение в теорию сложности алгоритмов // М.: Издательский отдел ф-та ВМиК МГУ, 2002.
# О числе отображений типа замыкания // Дискретная математика, 2004, т.16, вып.2, с.85-97.
# Abel's theorem in problems and solutions // Kluwer Academic Publishers, 2004.
# On the voltage-current transferring in topological graph theory // Ars Combinatoria, 2005 (January), v.74, p. 331-349. (совм. с Коржиком В. П.)
# Сложность умножения в некоторых групповых алгебрах // Дискретная математика, 2005, т.17, вып.1, с.3-17. (совм. с Поспеловым А.Д.)
# О некоторых замкнутых классах самодвойственных частичных многозначных функций // Ученые записки Казанского государственного университета. Серия «Физико-математические науки», т.151, книга 2, 2009, с. 16-24.
# Лекции по дискретной математике // М.: ИНФРА-М, 2012.
# О приближении максимально-нелинейных булевых функций почти линейными функциями // Дискретная математика, т. 24, вып. 3, 2012, с. 73-81. (совм. с Омаровым Р.Р.)
# On the Exact and Approximate Bilinear Complexities of Multiplication of 4 × 2 and 2 × 2 Matrices // Proceedings of the Steklov Institute of Mathematics, 2013, Vol. 282, Suppl. 1, pp. S123-S139. (совместно со Смирновым А.В.)
# О билинейной сложности умножения матриц размеров mх2 и 2х2 // Чебышевский сборник, т. 16, вып. 4, 2015, Тула, Изд-во Тул. гос. пед. ун-та им. Л.Н. Толстого, с. 11-27.
# О замкнутых классах в частичной k-значной логике, содержащих класс монотонных функций // Дискретная математика, т. 30, № 2, 2018, с. 3-13.
# О билинейной сложности умножения матриц размеров 2х2 и 2хm над конечным полем // Вестн. Моск. ун-та. Выч. матем. и киберн. 2019, N 4, с. 5-10.
# О замкнутых классах в частичной k-значной логике, содержащих все полиномы // Дискретная математика, т. 33, № 2, 2021, с. 6-19.
# Дискретная математика. Учебник. // М.: ИНФРА-М, 2021, 133 с.

Участник:AlekseevVB

2021-12-14T09:50:21Z

AlekseevVB: /* Избранные публикации */

Файл:Вопросы Сложность алгоритмов 2021.doc

2021-12-14T09:40:37Z

AlekseevVB:

Сложность алгоритмов

2021-12-14T09:39:14Z

AlekseevVB: /* Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418. */

Обязательный курс для студентов 418 группы. Читается в осеннем семестре.

Лектор - профессор [[Алексеев Валерий Борисович]].

== Программа курса ==
===Примеры задач с оценкой временной сложности по порядку.===
Сложность распознавания симметрии на машине Тьюринга.
Сложность распознавания полноты системы булевых функций на машине Тьюринга.

===Некоторые общие результаты о сложности алгоритмов.===
Вычислимые функции, их нумерация. Теоремы о существовании общерекурсивной функции, трудно вычислимой хотя бы в одной точке, в бесконечном числе точек и почти всюду.
Регулярные языки и автоматы. Теорема о регулярности языка, распознаваемого со следом константной или слаборастущей длины. Несуществование задач с временной сложностью на машине Тьюринга по порядку между n и nlogn.

===Метод динамического пpогpаммиpования.===
Алгоpитм поиска кpатчайших путей между всеми паpами веpшин в гpафе. Алгоpитм для задачи об оптимальном поpядке умножения матpиц.

===Метод "pазделяй и властвуй" для построения быстрых алгоритмов.===
Алгоpитмы соpтиpовки вставкой и слиянием. Быстрые алгоpитмы для умножения чисел и матpиц.

===Метод pасшиpения модели для построения быстрых алгоритмов.===
Алгоpитмы обычного и булевского умножения матpиц с битовыми опеpациями. Алгоpитм тpанзитивного замыкания гpафа. Алгоpитмы для pаспознавания пpинадлежности булевых или многозначных функций, заданных векторно, некоторым замкнутым классам.

===Некоторые классы сложности.===
Определение классов DLOG, P, NP, PSPACE, соотношение между ними. Теорема Кука об NP-полноте задачи о выполнимости конъюнктивной нормальной формы. Доказательство NP-полноты других задач. PSPACE-полные задачи.

==Вопросы к экзамену по курсу «Сложность алгоритмов» для гр. 418.==

[[Media:Вопросы_Сложность_алгоритмов_2021.doc|Вопросы к экзамену на январь 2022 года]]

== Литература ==
#[[Media:KNIGA1.pdf|Алексеев В.Б. Введение в теорию сложности алгоритмов.]] М.: Изд. отдел ф-та ВМиК МГУ, 2002.
#Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ вычислительных алгоpитмов. М.: Мир, 1979.
#Барздинь Я.М. Сложность распознавания симметрии на машинах Тьюринга. Сб. "Проблемы кибернетики", вып. 15 (1965), с. 245-248.
#Гэpи М., Джонсон Д. Вычислительные машины и тpудноpешаемые задачи. М.: Мир, 1982.
#Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М., «Мир», 1985.
#Проблемы математической логики. Сложность алгоритмов и вычислимых функций. (Сб. переводов), М.: Мир, 1970.

[[Категория:Лекционные_курсы_кафедры_МК]]

Вероятностные и квантовые алгоритмы

2021-11-24T12:49:13Z

AlekseevVB: /* Программа курса */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:ВКА_2021.docx|Вопросы к экзамену на январь 2022 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 5. Вероятностные методы в перечислительных задачах. Метод Монте-Карло, связь между числом испытаний и точностью. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Вероятностные и квантовые алгоритмы

2021-11-24T12:45:38Z

AlekseevVB: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]

Лектор - профессор [[Алексеев Валерий Борисович]].

Курс читается для студентов магистерской программы «Дискретные структуры и алгоритмы» (группа 618/1) в осеннем семестре. Лекции - 3 ч в неделю. Форма отчетности - экзамен.

[[Категория:Лекционные_курсы_кафедры_МК]]

==Объявления==

[[Media:ВКА_2021.docx|Вопросы к экзамену на январь 2022 года]]

==Программа курса==

*Лекция 1. Вероятностный анализ алгоритмов. Алгоритм динамического программирования для задачи упаковки подмножеств. Его полиномиальность «в среднем».

*Лекция 2. Алгоритм динамического программирования для задачи «Выполнимость КНФ». Его полиномиальность «в среднем».

*Лекция 3. Жадный алгоритм для задачи о покрытии. Его точность для почти всех входов.

*Лекция 4. Вероятностные алгоритмы и их анализ. Вероятностный алгоритм Фрейвалда для проверки матричного тождества с оценкой вероятности ошибки. Вероятностный алгоритм проверки тождеств для многочлена. Оценка вероятности ошибки.

*Лекция 5. Вероятностные методы в перечислительных задачах. Полностью полиномиальная рандомизированная аппроксимационная схема с двумя параметрами для задачи о мощности объединения множеств. Следствие для задачи о числе выполняющих наборов для ДНФ.

*Лекция 6. Вероятностные методы в параллельных вычислениях. Параллельный алгоритм для поиска максимального по включению независимого множества в графе. Оценка времени его работы.

*Лекция 7. Вероятностные методы в распределенных вычислениях. Вероятностный протокол византийского соглашения. Оценка числа раундов.

*Лекция 8. Вероятностное округление. Приближенный вероятностный алгоритм для задачи «Максимальная выполнимость» на основе линейной релаксации. Оценка его точности в среднем.

*Лекция 9. Метод условных вероятностей для дерандомизации алгоритмов. Детерминированный алгоритм для задачи «Максимальная выполнимость», построенный путем дерандомизации. Его сложность.

*Лекция 10. Вероятностные вычисления. Односторонние ошибки. Классы сложности RP, coRP, RPweak, RPstrong. Их соотношение с классами NP, coNP и между собой.

*Лекция 11. Двухсторонние ошибки. Классы сложности BPP, BPPweak, BPPstrong. Соотношение между ними.

*Лекция 12. Классы сложности PP, PPweak. Их соотношение между собой и с классами NP, PSPACE.

*Лекция 13. Класс сложности ZPP. Его соотношение с классами RP, coRP.

*Лекция 14. Алгебраические основы квантовых вычислений. Тензорное произведение линейных пространств, теорема о его согласованности со скалярным произведением (для унитарных пространств).

*Лекция 15. Тензорное произведение линейных операторов, его свойства: дистрибутивность при действии на разложимый вектор; связь с произведением операторов.

*Лекция 16. Обратимые классические схемы. Теорема о связи вычислений булевыми схемами и обратимыми схемами.

*Лекция 17. Квантовые компьютеры и квантовые схемы. Квантовые схемы для двух операторов отражения относительно гиперплоскости, их сложность.

*Лекция 18. Квантовые вычисления. Квантовый алгоритм Гровера для задачи поиска, его сложность и точность.

'''Литература'''

1. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений (авторское электронное издание), стр. 122-147, 161-195, 207-212, 273-291.
discopal.ispras.ru/img_auth.php/f/f4/Book-advanced-algorithms.pdf

или

2. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. – М.: МФТИ, 2007, стр. 99-120, 129-160, 169-173, 227-244.

3. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. – М.: МЦМНО, ЧеРо, 1999, стр. 48-58, 66-71.

Файл:ВКА 2021.docx

2021-11-24T12:43:56Z

AlekseevVB:

Шаблон:Current Seminars

2021-03-24T08:12:52Z

AlekseevVB: /* Доклады на спецсеминарах */

== Доклады на спецсеминарах ==
{|
|colspan="3"|'''[[Дискретная математика и математическая кибернетика]]'''
{{announce Seminar | 6 ноября 2020
| '''О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов'''.
Аннотация. Исследованы задачи реализации булевых функций контактными схемами и схемами из функциональных элементов, допускающими короткие проверяющие либо диагностические тесты относительно неисправностей заранее оговоренного вида, которые могут происходить в схемах. Указанные задачи были впервые предложены (применительно к контактным схемам) С.В. Яблонским
и И.А. Чегис в середине 1950-х годов и изучались многими авторами. Рассмотрены следующие виды неисправностей: обрывы и/или замыкания контактов, константные (однотипные или произвольные) либо инверсные неисправности на входах и/или выходах функциональных элементов. Число допустимых неисправностей в схемах может быть ограничено сверху единицей или заданным натуральным числом либо никак не ограничено. Получен ряд верхних и/или нижних оценок длин минимальных тестов для схем, реализующих заданные, все или почти все булевы функции, при различных исходных условиях. Во многих случаях найдены точные значения этих длин и/или улучшены известные ранее результаты.
| '''Попков К.А.''' (Институт прикладной математики им. М.В. Келдыша РАН)}}

|-
|colspan="3"|'''[[Дискретные функции и сложность алгоритмов]]'''
{{announce Seminar | 26 марта 2021
|Продолжение доклада "О пороговых булевых функциях" (в 16.20 в Skype, группа СПСЁ)
| Алексеев В.Б. (профессор кафедры МК)}}

{{announce Seminar | 2 октября 2020
| "Условное тестирование схем Кардо" (Вороненко А.А.)
| Пенкин В.А. (студент группы 418)}}
{{announce Seminar | 9 октября 2020
| "Универсальные функции для классов линейных функций двух переменных" (Вороненко А.А., Окунева А.С.)
| Журавлева С.А. (студент группы 318)}}
{{announce Seminar | 16 октября 2020
| "Универсальные функции для классов линейных функций трех переменных" (Вороненко А.А., Окунева А.С.)
| Фаерштейн И.С. (студент группы 518мк_дс)}}
{{announce Seminar | 23 октября 2020
| "О сложности pаспознавания монотонности" (Вороненко А.А.)
| Китаев С.Н. (асп. 1 г.о.)}}

|-
|colspan="3"|'''[[Теория управляющих систем и математические модели СБИС]]'''
{{announce Seminar|
|
| }}

|-
|colspan="3"|'''[[Сложность решения дискретных задач]]'''
{{announce Seminar|
|
| }}

|-
|colspan="3"|'''[[Теоретические проблемы программирования]]'''
{{announce Seminar| 8 октября 2020
| "Modelling and Verification of Timed Interaction and Migration" (G. Ciobanu, M. Coutny)
| Евгений Винарский (студент группы 618мк_дус)}}
{{announce Seminar| 15 октября 2020
| Проверка эквивалентности в одном классе многоленточных автоматов
| Шынар Жайлауова (асп.)}}
{{announce Seminar| 22 октября 2020
| Принципы устройства протокола блокчейна Ethereum и языка описания смарт-контрактов Solidity
| Сергей Портнов (студент группы 418)}}
{{announce Seminar| 29 октября 2020
| "Minimizing GFG Transition-Based Automata" (O. Kupferman, B. Abu Radi)
| Артур Хашаев (асп.)}}
{{announce Seminar| 12 ноября 2020
| "A hierarchy of temporal logics with past" (F. Laroussinie, Ph. Schnoebelen)
| Нина Куцак (студент группы 618мк_дус)}}
{{announce Seminar| 19 ноября 2020
| "Deterministic 1-counter automata" (M. Paterson, L. Valiant)
| Нурлан Рахимжанов (студент группы 418)}}
{{announce Seminar| 26 ноября 2020
| "2-Way Finite Automata" (Serena Rietbergen)
| Диана Оспанова (студент группы 418)}}
{{announce Seminar| 3 декабря 2020
| "TCTL-preserving translations from timed-arc Petri nets to networks of timed automata" (J. Byg, M. Jacobsen, L. Jacobsen, K.Y. Jørgensen, M.H. Møller, J. Srba)
| Георгий Попков (студент группы 518мк_дус)}}
{{announce Seminar| 10 декабря 2020
| "The mu-calculus and model checking" (I. Walukievicz, J. Bradfield)
| Антон Гнатенко (ВШЭ)}}
{{announce Seminar| 17 декабря 2020
| "Model Checking with Multi-Valued Logics" (G. Bruns, P. Godefroid)
| Илья Мушкин (студент группы 418)}}


|}

Шаблон:Current Seminars

2021-03-17T10:32:33Z

AlekseevVB: /* Доклады на спецсеминарах */

== Доклады на спецсеминарах ==
{|
|colspan="3"|'''[[Дискретная математика и математическая кибернетика]]'''
{{announce Seminar | 6 ноября 2020
| '''О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов'''.
Аннотация. Исследованы задачи реализации булевых функций контактными схемами и схемами из функциональных элементов, допускающими короткие проверяющие либо диагностические тесты относительно неисправностей заранее оговоренного вида, которые могут происходить в схемах. Указанные задачи были впервые предложены (применительно к контактным схемам) С.В. Яблонским
и И.А. Чегис в середине 1950-х годов и изучались многими авторами. Рассмотрены следующие виды неисправностей: обрывы и/или замыкания контактов, константные (однотипные или произвольные) либо инверсные неисправности на входах и/или выходах функциональных элементов. Число допустимых неисправностей в схемах может быть ограничено сверху единицей или заданным натуральным числом либо никак не ограничено. Получен ряд верхних и/или нижних оценок длин минимальных тестов для схем, реализующих заданные, все или почти все булевы функции, при различных исходных условиях. Во многих случаях найдены точные значения этих длин и/или улучшены известные ранее результаты.
| '''Попков К.А.''' (Институт прикладной математики им. М.В. Келдыша РАН)}}

|-
|colspan="3"|'''[[Дискретные функции и сложность алгоритмов]]'''
{{announce Seminar | 19 марта 2021
| "О пороговых булевых функциях" (в 16.20 в Skype, группа СПСЁ)
| Алексеев В.Б. (профессор кафедры МК)}}

{{announce Seminar | 2 октября 2020
| "Условное тестирование схем Кардо" (Вороненко А.А.)
| Пенкин В.А. (студент группы 418)}}
{{announce Seminar | 9 октября 2020
| "Универсальные функции для классов линейных функций двух переменных" (Вороненко А.А., Окунева А.С.)
| Журавлева С.А. (студент группы 318)}}
{{announce Seminar | 16 октября 2020
| "Универсальные функции для классов линейных функций трех переменных" (Вороненко А.А., Окунева А.С.)
| Фаерштейн И.С. (студент группы 518мк_дс)}}
{{announce Seminar | 23 октября 2020
| "О сложности pаспознавания монотонности" (Вороненко А.А.)
| Китаев С.Н. (асп. 1 г.о.)}}

|-
|colspan="3"|'''[[Теория управляющих систем и математические модели СБИС]]'''
{{announce Seminar|
|
| }}

|-
|colspan="3"|'''[[Сложность решения дискретных задач]]'''
{{announce Seminar|
|
| }}

|-
|colspan="3"|'''[[Теоретические проблемы программирования]]'''
{{announce Seminar| 8 октября 2020
| "Modelling and Verification of Timed Interaction and Migration" (G. Ciobanu, M. Coutny)
| Евгений Винарский (студент группы 618мк_дус)}}
{{announce Seminar| 15 октября 2020
| Проверка эквивалентности в одном классе многоленточных автоматов
| Шынар Жайлауова (асп.)}}
{{announce Seminar| 22 октября 2020
| Принципы устройства протокола блокчейна Ethereum и языка описания смарт-контрактов Solidity
| Сергей Портнов (студент группы 418)}}
{{announce Seminar| 29 октября 2020
| "Minimizing GFG Transition-Based Automata" (O. Kupferman, B. Abu Radi)
| Артур Хашаев (асп.)}}
{{announce Seminar| 12 ноября 2020
| "A hierarchy of temporal logics with past" (F. Laroussinie, Ph. Schnoebelen)
| Нина Куцак (студент группы 618мк_дус)}}
{{announce Seminar| 19 ноября 2020
| "Deterministic 1-counter automata" (M. Paterson, L. Valiant)
| Нурлан Рахимжанов (студент группы 418)}}
{{announce Seminar| 26 ноября 2020
| "2-Way Finite Automata" (Serena Rietbergen)
| Диана Оспанова (студент группы 418)}}
{{announce Seminar| 3 декабря 2020
| "TCTL-preserving translations from timed-arc Petri nets to networks of timed automata" (J. Byg, M. Jacobsen, L. Jacobsen, K.Y. Jørgensen, M.H. Møller, J. Srba)
| Георгий Попков (студент группы 518мк_дус)}}
{{announce Seminar| 10 декабря 2020
| "The mu-calculus and model checking" (I. Walukievicz, J. Bradfield)
| Антон Гнатенко (ВШЭ)}}
{{announce Seminar| 17 декабря 2020
| "Model Checking with Multi-Valued Logics" (G. Bruns, P. Godefroid)
| Илья Мушкин (студент группы 418)}}


|}

Шаблон:Current Seminars

2021-03-17T10:28:36Z

AlekseevVB: /* Доклады на спецсеминарах */

== Доклады на спецсеминарах ==
{|
|colspan="3"|'''[[Дискретная математика и математическая кибернетика]]'''
{{announce Seminar | 6 ноября 2020
| '''О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов'''.
Аннотация. Исследованы задачи реализации булевых функций контактными схемами и схемами из функциональных элементов, допускающими короткие проверяющие либо диагностические тесты относительно неисправностей заранее оговоренного вида, которые могут происходить в схемах. Указанные задачи были впервые предложены (применительно к контактным схемам) С.В. Яблонским
и И.А. Чегис в середине 1950-х годов и изучались многими авторами. Рассмотрены следующие виды неисправностей: обрывы и/или замыкания контактов, константные (однотипные или произвольные) либо инверсные неисправности на входах и/или выходах функциональных элементов. Число допустимых неисправностей в схемах может быть ограничено сверху единицей или заданным натуральным числом либо никак не ограничено. Получен ряд верхних и/или нижних оценок длин минимальных тестов для схем, реализующих заданные, все или почти все булевы функции, при различных исходных условиях. Во многих случаях найдены точные значения этих длин и/или улучшены известные ранее результаты.
| '''Попков К.А.''' (Институт прикладной математики им. М.В. Келдыша РАН)}}

|-
|colspan="3"|'''[[Дискретные функции и сложность алгоритмов]]'''
{{announce Seminar | 19 марта 2021
| "О пороговых булевых функциях"
| Алексеев В.Б. (профессор кафедры МК)}}

{{announce Seminar | 2 октября 2020
| "Условное тестирование схем Кардо" (Вороненко А.А.)
| Пенкин В.А. (студент группы 418)}}
{{announce Seminar | 9 октября 2020
| "Универсальные функции для классов линейных функций двух переменных" (Вороненко А.А., Окунева А.С.)
| Журавлева С.А. (студент группы 318)}}
{{announce Seminar | 16 октября 2020
| "Универсальные функции для классов линейных функций трех переменных" (Вороненко А.А., Окунева А.С.)
| Фаерштейн И.С. (студент группы 518мк_дс)}}
{{announce Seminar | 23 октября 2020
| "О сложности pаспознавания монотонности" (Вороненко А.А.)
| Китаев С.Н. (асп. 1 г.о.)}}

|-
|colspan="3"|'''[[Теория управляющих систем и математические модели СБИС]]'''
{{announce Seminar|
|
| }}

|-
|colspan="3"|'''[[Сложность решения дискретных задач]]'''
{{announce Seminar|
|
| }}

|-
|colspan="3"|'''[[Теоретические проблемы программирования]]'''
{{announce Seminar| 8 октября 2020
| "Modelling and Verification of Timed Interaction and Migration" (G. Ciobanu, M. Coutny)
| Евгений Винарский (студент группы 618мк_дус)}}
{{announce Seminar| 15 октября 2020
| Проверка эквивалентности в одном классе многоленточных автоматов
| Шынар Жайлауова (асп.)}}
{{announce Seminar| 22 октября 2020
| Принципы устройства протокола блокчейна Ethereum и языка описания смарт-контрактов Solidity
| Сергей Портнов (студент группы 418)}}
{{announce Seminar| 29 октября 2020
| "Minimizing GFG Transition-Based Automata" (O. Kupferman, B. Abu Radi)
| Артур Хашаев (асп.)}}
{{announce Seminar| 12 ноября 2020
| "A hierarchy of temporal logics with past" (F. Laroussinie, Ph. Schnoebelen)
| Нина Куцак (студент группы 618мк_дус)}}
{{announce Seminar| 19 ноября 2020
| "Deterministic 1-counter automata" (M. Paterson, L. Valiant)
| Нурлан Рахимжанов (студент группы 418)}}
{{announce Seminar| 26 ноября 2020
| "2-Way Finite Automata" (Serena Rietbergen)
| Диана Оспанова (студент группы 418)}}
{{announce Seminar| 3 декабря 2020
| "TCTL-preserving translations from timed-arc Petri nets to networks of timed automata" (J. Byg, M. Jacobsen, L. Jacobsen, K.Y. Jørgensen, M.H. Møller, J. Srba)
| Георгий Попков (студент группы 518мк_дус)}}
{{announce Seminar| 10 декабря 2020
| "The mu-calculus and model checking" (I. Walukievicz, J. Bradfield)
| Антон Гнатенко (ВШЭ)}}
{{announce Seminar| 17 декабря 2020
| "Model Checking with Multi-Valued Logics" (G. Bruns, P. Godefroid)
| Илья Мушкин (студент группы 418)}}


|}