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

Практикум по дискретным структурам

2024-03-27T05:49:58Z

Emergency User: /* Задание 2. Применение SAT решателей к задачам минимизации функций */

Практикум по дискретным структурам

2024-02-14T13:03:28Z

Emergency User:

Практикум по дискретным структурам

2024-02-14T12:11:32Z

Emergency User:

Практикум по дискретным структурам

2024-02-14T12:10:53Z

Emergency User: /* Задание 1. Регулярные выражения */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Переборные алгоритмы и их применения. ===

Использование переборных алгоритмов для задач комбинаторной оптимизации.
Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.

Распараллеливание программы.

=== Лекция 2. Оптимизация перебора. ===

Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра.

=== Лекция 3. Подходы к построению быстрых алгоритмов. ===

Градиентный метод. Динамическое программирование.

=== Лекция 4. Sat-решатели и их приложения - 1. ===

Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции.

=== Лекция 5. Sat-решатели и их приложения - 2. ===

Применение SAT решателей для поиска минимальных полиномиальных форм.

=== Лекция 6. Эвристические алгоритмы. ===

Моделирование отжига, генетические алгоритмы, роевые алгоритмы.

=== Лекция 7. Применение эвристических алгоритмов. ===

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Переборные алгоритмы ===

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

1. Из датасета на базе open_stt сформировать обучающую и тестовую выборки (по варинту).

2. Собрать модель на основе ctc_voxforge.py.

3. Обучить модели согласно заданию (по варианту, в котором 3 размера датасета + 2 варианта слоёв слоёв)

4. Провести эксперименты
размер датасета, время обучения, скорость inference, число эпох, число слоёв, cer/wer на тестовом и обучающем.

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Практикум по дискретным структурам

2024-02-14T12:10:26Z

Emergency User: /* Лекция 6. Эвристические алгоритмы. */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Переборные алгоритмы и их применения. ===

Использование переборных алгоритмов для задач комбинаторной оптимизации.
Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.

Распараллеливание программы.

=== Лекция 2. Оптимизация перебора. ===

Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра.

=== Лекция 3. Подходы к построению быстрых алгоритмов. ===

Градиентный метод. Динамическое программирование.

=== Лекция 4. Sat-решатели и их приложения - 1. ===

Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции.

=== Лекция 5. Sat-решатели и их приложения - 2. ===

Применение SAT решателей для поиска минимальных полиномиальных форм.

=== Лекция 6. Эвристические алгоритмы. ===

Моделирование отжига, генетические алгоритмы, роевые алгоритмы.

=== Лекция 7. Применение эвристических алгоритмов. ===

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

1. Из датасета на базе open_stt сформировать обучающую и тестовую выборки (по варинту).

2. Собрать модель на основе ctc_voxforge.py.

3. Обучить модели согласно заданию (по варианту, в котором 3 размера датасета + 2 варианта слоёв слоёв)

4. Провести эксперименты
размер датасета, время обучения, скорость inference, число эпох, число слоёв, cer/wer на тестовом и обучающем.

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Практикум по дискретным структурам

2024-02-14T12:10:13Z

Emergency User: /* Лекция 2. Оптимизация перебора. */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Переборные алгоритмы и их применения. ===

Использование переборных алгоритмов для задач комбинаторной оптимизации.
Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.

Распараллеливание программы.

=== Лекция 2. Оптимизация перебора. ===

Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра.

=== Лекция 3. Подходы к построению быстрых алгоритмов. ===

Градиентный метод. Динамическое программирование.

=== Лекция 4. Sat-решатели и их приложения - 1. ===

Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции.

=== Лекция 5. Sat-решатели и их приложения - 2. ===

Применение SAT решателей для поиска минимальных полиномиальных форм.

=== Лекция 6. Эвристические алгоритмы. ===

Моделирование отжига, генетические алгоритмы, роевые алгоритмы.

Лекция 7. Применение эвристических алгоритмов.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

1. Из датасета на базе open_stt сформировать обучающую и тестовую выборки (по варинту).

2. Собрать модель на основе ctc_voxforge.py.

3. Обучить модели согласно заданию (по варианту, в котором 3 размера датасета + 2 варианта слоёв слоёв)

4. Провести эксперименты
размер датасета, время обучения, скорость inference, число эпох, число слоёв, cer/wer на тестовом и обучающем.

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Практикум по дискретным структурам

2024-02-14T12:05:54Z

Emergency User: /* Лекция 1. Переборные алгоритмы и их применения. */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Переборные алгоритмы и их применения. ===

Использование переборных алгоритмов для задач комбинаторной оптимизации.
Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.

Распараллеливание программы.

=== Лекция 2. Оптимизация перебора. ===

Лекция 3. Подходы к построению быстрых алгоритмов.

Лекция 4. Sat-решатели и их приложения - 1.

Лекция 5. Sat-решатели и их приложения - 2.

Лекция 6. Эвристические алгоритмы.

Лекция 7. Применение эвристических алгоритмов.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

1. Из датасета на базе open_stt сформировать обучающую и тестовую выборки (по варинту).

2. Собрать модель на основе ctc_voxforge.py.

3. Обучить модели согласно заданию (по варианту, в котором 3 размера датасета + 2 варианта слоёв слоёв)

4. Провести эксперименты
размер датасета, время обучения, скорость inference, число эпох, число слоёв, cer/wer на тестовом и обучающем.

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Практикум по дискретным структурам

2024-02-14T12:01:56Z

Emergency User:

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Переборные алгоритмы и их применения. ===

=== Лекция 2. Оптимизация перебора. ===

Лекция 3. Подходы к построению быстрых алгоритмов.

Лекция 4. Sat-решатели и их приложения - 1.

Лекция 5. Sat-решатели и их приложения - 2.

Лекция 6. Эвристические алгоритмы.

Лекция 7. Применение эвристических алгоритмов.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

1. Из датасета на базе open_stt сформировать обучающую и тестовую выборки (по варинту).

2. Собрать модель на основе ctc_voxforge.py.

3. Обучить модели согласно заданию (по варианту, в котором 3 размера датасета + 2 варианта слоёв слоёв)

4. Провести эксперименты
размер датасета, время обучения, скорость inference, число эпох, число слоёв, cer/wer на тестовом и обучающем.

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Графы и их применения

2023-06-13T10:47:04Z

Emergency User: /* Список задач */

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров

Лектор: [[Бухман Антон Владимирович]]

== Программа курса Графы и их применения. ==

'''Занятие 1.
1. Введение. Обзор курса. - 20 минут
2. Семинар. Задачи на повторение курса по графам.

'''Занятие 2.
1. Семинар. Задачи на повторение -- продолжение.
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

'''Занятие 3.
1. Обходы графов.
2. Поиск компонент вершинной двусвязности.
3. Разбор задач на двусвязность.

'''Занятие 4.
1. Поиск множества фундаментальных циклов
2. Поиск компонент сильной связности.

'''Занятие 5.
1. Матроиды и жадные алгоритмы.
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

'''Занятие 6.
1. Переборные алгоритмы для построения всех остовных деревьев.
2. Коды Прюфера. Число остовных деревьев для полного графа

'''Занятие 7.
1. Числа Рамсея. Оценка чисел Рамсея.
2. Обобщение чисел Рамсея. Применение чисел Рамсея.

'''Занятие 8.
1. Паросочетания теорема Холла
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

'''Занятие 9.
1. Семинар по пройденным темам.

'''Занятие 10.
1. Алгоритм Куна для поиска максимальных паросочетаний
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
3. Венгерский алгоритм.

'''Занятие 11.
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
2. Задача коммивояжёра. ЗКНТ.
2. Эйлеров цикл. Задача китайского почтальона.

'''Занятие 12.
1. Последовательности деБрёйна.
2. Теорема о числе последовательностей.

'''Занятие 13.
1. Некоторые NP полные задачи на графах.
2. Обзор пройденного материала.

'''Занятие 14.
Семинар по пройденным темам.

'''Занятие 15.
Итоговая контрольная работа по курсу

== Вопросы к экзамену ==

1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности.
''В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99''

2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов.
''В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95''

3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности.
''Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477''

4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование.
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343''

5. Матроиды и жадные алгоритмы
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345''

6. Минимальные остовные деревья. Алгоритм Краскала и Прима.
''Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490''

7. Переборные алгоритмы для построения всех остовных деревьев.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158
''

8. Числа Рамсея
''Карпов. Теория графов. С. 477-479''

9. Оценки чисел Рамсея
''Карпов. Теория графов С. 479-481''

10. Обобщение чисел Рамсея
''Карпов. Теория графов С. 482-484''

11. Паросочетания, теорема Холла.
''А. Эвнин Вокруг теоремы Холла С.5-6''

12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
''А. Эвнин Вокруг теоремы Холла С. 7,18''

13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний
''Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 83-87''

14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами
''Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 887-91''

15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна.
''de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764''
16. Задача коммивояжёра и ЗКНТ.
''Гэри, Джонсон Вычислительные машины и труднорешаемые задачи
С 189-190''

17. Достаточные признаки гамильтоновости графа.

''R.Diestel Graph Theory. Springer 2000, C 213-216''

18. Эйлеровы графы и задача китайского почтальона.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239''

== Список литературы ==

В. Липский Комбинаторика для программистов. М.Мир, 1988

Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013

Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978

Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf

А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23

Гери Джонсон Вычислительные машины и труднорешаемые задачи

== Темы задач ==

1. Поиск компонент двусвязности

2. Множество фундаментальных циклов

3. Компоненты сильной связности

4. Коды Прюфера

5. Алгоритм Куна.

6. Венгерский алгоритм

7. Покрытие матрицы

8. Задача китайского почтальона

9. Задача коммивояжёра, МВГ

10. Задачи на теорему Холла

11. Гамильтоновость

12. Теория Рамсея

13. Задачи теории сложности на графах

14. Матроиды, жадные алгоритмы

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

Графы и их применения

2023-06-13T10:45:25Z

Emergency User: /* Список задач: */

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров

Лектор: [[Бухман Антон Владимирович]]

== Программа курса Графы и их применения. ==

'''Занятие 1.
1. Введение. Обзор курса. - 20 минут
2. Семинар. Задачи на повторение курса по графам.

'''Занятие 2.
1. Семинар. Задачи на повторение -- продолжение.
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

'''Занятие 3.
1. Обходы графов.
2. Поиск компонент вершинной двусвязности.
3. Разбор задач на двусвязность.

'''Занятие 4.
1. Поиск множества фундаментальных циклов
2. Поиск компонент сильной связности.

'''Занятие 5.
1. Матроиды и жадные алгоритмы.
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

'''Занятие 6.
1. Переборные алгоритмы для построения всех остовных деревьев.
2. Коды Прюфера. Число остовных деревьев для полного графа

'''Занятие 7.
1. Числа Рамсея. Оценка чисел Рамсея.
2. Обобщение чисел Рамсея. Применение чисел Рамсея.

'''Занятие 8.
1. Паросочетания теорема Холла
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

'''Занятие 9.
1. Семинар по пройденным темам.

'''Занятие 10.
1. Алгоритм Куна для поиска максимальных паросочетаний
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
3. Венгерский алгоритм.

'''Занятие 11.
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
2. Задача коммивояжёра. ЗКНТ.
2. Эйлеров цикл. Задача китайского почтальона.

'''Занятие 12.
1. Последовательности деБрёйна.
2. Теорема о числе последовательностей.

'''Занятие 13.
1. Некоторые NP полные задачи на графах.
2. Обзор пройденного материала.

'''Занятие 14.
Семинар по пройденным темам.

'''Занятие 15.
Итоговая контрольная работа по курсу

== Вопросы к экзамену ==

1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности.
''В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99''

2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов.
''В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95''

3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности.
''Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477''

4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование.
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343''

5. Матроиды и жадные алгоритмы
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345''

6. Минимальные остовные деревья. Алгоритм Краскала и Прима.
''Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490''

7. Переборные алгоритмы для построения всех остовных деревьев.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158
''

8. Числа Рамсея
''Карпов. Теория графов. С. 477-479''

9. Оценки чисел Рамсея
''Карпов. Теория графов С. 479-481''

10. Обобщение чисел Рамсея
''Карпов. Теория графов С. 482-484''

11. Паросочетания, теорема Холла.
''А. Эвнин Вокруг теоремы Холла С.5-6''

12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
''А. Эвнин Вокруг теоремы Холла С. 7,18''

13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний
''Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 83-87''

14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами
''Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 887-91''

15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна.
''de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764''
16. Задача коммивояжёра и ЗКНТ.
''Гэри, Джонсон Вычислительные машины и труднорешаемые задачи
С 189-190''

17. Достаточные признаки гамильтоновости графа.

''R.Diestel Graph Theory. Springer 2000, C 213-216''

18. Эйлеровы графы и задача китайского почтальона.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239''

== Список литературы ==

В. Липский Комбинаторика для программистов. М.Мир, 1988

Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013

Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978

Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf

А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23

Гери Джонсон Вычислительные машины и труднорешаемые задачи

== Список задач ==

1. Двусвязность

2. Множество фундаментальных циклов

3. КСС

4. Прюфер

5. Куна алгоритм

6. Венгерский алгоритм

7. Покрытие матрицы

8. Задача китайского почтальона

9. Задача коммивояжёра, МВГ

10. Задачи на теорему Холла

11. Гамильтоновость

12. Теория Рамсея

13. Задачи теории слодности на графах

14. Матроиды, жадные алгоритмы

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

Графы и их применения

2023-06-13T10:45:17Z

Emergency User: /* Список литературы: */

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров

Лектор: [[Бухман Антон Владимирович]]

== Программа курса Графы и их применения. ==

'''Занятие 1.
1. Введение. Обзор курса. - 20 минут
2. Семинар. Задачи на повторение курса по графам.

'''Занятие 2.
1. Семинар. Задачи на повторение -- продолжение.
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

'''Занятие 3.
1. Обходы графов.
2. Поиск компонент вершинной двусвязности.
3. Разбор задач на двусвязность.

'''Занятие 4.
1. Поиск множества фундаментальных циклов
2. Поиск компонент сильной связности.

'''Занятие 5.
1. Матроиды и жадные алгоритмы.
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

'''Занятие 6.
1. Переборные алгоритмы для построения всех остовных деревьев.
2. Коды Прюфера. Число остовных деревьев для полного графа

'''Занятие 7.
1. Числа Рамсея. Оценка чисел Рамсея.
2. Обобщение чисел Рамсея. Применение чисел Рамсея.

'''Занятие 8.
1. Паросочетания теорема Холла
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

'''Занятие 9.
1. Семинар по пройденным темам.

'''Занятие 10.
1. Алгоритм Куна для поиска максимальных паросочетаний
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
3. Венгерский алгоритм.

'''Занятие 11.
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
2. Задача коммивояжёра. ЗКНТ.
2. Эйлеров цикл. Задача китайского почтальона.

'''Занятие 12.
1. Последовательности деБрёйна.
2. Теорема о числе последовательностей.

'''Занятие 13.
1. Некоторые NP полные задачи на графах.
2. Обзор пройденного материала.

'''Занятие 14.
Семинар по пройденным темам.

'''Занятие 15.
Итоговая контрольная работа по курсу

== Вопросы к экзамену ==

1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности.
''В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99''

2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов.
''В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95''

3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности.
''Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477''

4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование.
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343''

5. Матроиды и жадные алгоритмы
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345''

6. Минимальные остовные деревья. Алгоритм Краскала и Прима.
''Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490''

7. Переборные алгоритмы для построения всех остовных деревьев.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158
''

8. Числа Рамсея
''Карпов. Теория графов. С. 477-479''

9. Оценки чисел Рамсея
''Карпов. Теория графов С. 479-481''

10. Обобщение чисел Рамсея
''Карпов. Теория графов С. 482-484''

11. Паросочетания, теорема Холла.
''А. Эвнин Вокруг теоремы Холла С.5-6''

12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
''А. Эвнин Вокруг теоремы Холла С. 7,18''

13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний
''Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 83-87''

14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами
''Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 887-91''

15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна.
''de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764''
16. Задача коммивояжёра и ЗКНТ.
''Гэри, Джонсон Вычислительные машины и труднорешаемые задачи
С 189-190''

17. Достаточные признаки гамильтоновости графа.

''R.Diestel Graph Theory. Springer 2000, C 213-216''

18. Эйлеровы графы и задача китайского почтальона.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239''

== Список литературы ==

В. Липский Комбинаторика для программистов. М.Мир, 1988

Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013

Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978

Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf

А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23

Гери Джонсон Вычислительные машины и труднорешаемые задачи

== Список задач: ==

1. Двусвязность

2. Множество фундаментальных циклов

3. КСС

4. Прюфер

5. Куна алгоритм

6. Венгерский алгоритм

7. Покрытие матрицы

8. Задача китайского почтальона

9. Задача коммивояжёра, МВГ

10. Задачи на теорему Холла

11. Гамильтоновость

12. Теория Рамсея

13. Задачи теории слодности на графах

14. Матроиды, жадные алгоритмы

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

Графы и их применения

2023-06-13T10:45:08Z

Emergency User: /* Вопросы к экзамену: */

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров

Лектор: [[Бухман Антон Владимирович]]

== Программа курса Графы и их применения. ==

'''Занятие 1.
1. Введение. Обзор курса. - 20 минут
2. Семинар. Задачи на повторение курса по графам.

'''Занятие 2.
1. Семинар. Задачи на повторение -- продолжение.
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

'''Занятие 3.
1. Обходы графов.
2. Поиск компонент вершинной двусвязности.
3. Разбор задач на двусвязность.

'''Занятие 4.
1. Поиск множества фундаментальных циклов
2. Поиск компонент сильной связности.

'''Занятие 5.
1. Матроиды и жадные алгоритмы.
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

'''Занятие 6.
1. Переборные алгоритмы для построения всех остовных деревьев.
2. Коды Прюфера. Число остовных деревьев для полного графа

'''Занятие 7.
1. Числа Рамсея. Оценка чисел Рамсея.
2. Обобщение чисел Рамсея. Применение чисел Рамсея.

'''Занятие 8.
1. Паросочетания теорема Холла
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

'''Занятие 9.
1. Семинар по пройденным темам.

'''Занятие 10.
1. Алгоритм Куна для поиска максимальных паросочетаний
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
3. Венгерский алгоритм.

'''Занятие 11.
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
2. Задача коммивояжёра. ЗКНТ.
2. Эйлеров цикл. Задача китайского почтальона.

'''Занятие 12.
1. Последовательности деБрёйна.
2. Теорема о числе последовательностей.

'''Занятие 13.
1. Некоторые NP полные задачи на графах.
2. Обзор пройденного материала.

'''Занятие 14.
Семинар по пройденным темам.

'''Занятие 15.
Итоговая контрольная работа по курсу

== Вопросы к экзамену ==

1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности.
''В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99''

2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов.
''В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95''

3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности.
''Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477''

4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование.
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343''

5. Матроиды и жадные алгоритмы
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345''

6. Минимальные остовные деревья. Алгоритм Краскала и Прима.
''Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490''

7. Переборные алгоритмы для построения всех остовных деревьев.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158
''

8. Числа Рамсея
''Карпов. Теория графов. С. 477-479''

9. Оценки чисел Рамсея
''Карпов. Теория графов С. 479-481''

10. Обобщение чисел Рамсея
''Карпов. Теория графов С. 482-484''

11. Паросочетания, теорема Холла.
''А. Эвнин Вокруг теоремы Холла С.5-6''

12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
''А. Эвнин Вокруг теоремы Холла С. 7,18''

13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний
''Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 83-87''

14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами
''Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 887-91''

15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна.
''de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764''
16. Задача коммивояжёра и ЗКНТ.
''Гэри, Джонсон Вычислительные машины и труднорешаемые задачи
С 189-190''

17. Достаточные признаки гамильтоновости графа.

''R.Diestel Graph Theory. Springer 2000, C 213-216''

18. Эйлеровы графы и задача китайского почтальона.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239''

== Список литературы: ==

В. Липский Комбинаторика для программистов. М.Мир, 1988

Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013

Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978

Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf

А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23

Гери Джонсон Вычислительные машины и труднорешаемые задачи

== Список задач: ==

1. Двусвязность

2. Множество фундаментальных циклов

3. КСС

4. Прюфер

5. Куна алгоритм

6. Венгерский алгоритм

7. Покрытие матрицы

8. Задача китайского почтальона

9. Задача коммивояжёра, МВГ

10. Задачи на теорему Холла

11. Гамильтоновость

12. Теория Рамсея

13. Задачи теории слодности на графах

14. Матроиды, жадные алгоритмы

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

Графы и их применения

2023-06-13T10:44:07Z

Emergency User:

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров

Лектор: [[Бухман Антон Владимирович]]

== Программа курса Графы и их применения. ==

'''Занятие 1.
1. Введение. Обзор курса. - 20 минут
2. Семинар. Задачи на повторение курса по графам.

'''Занятие 2.
1. Семинар. Задачи на повторение -- продолжение.
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

'''Занятие 3.
1. Обходы графов.
2. Поиск компонент вершинной двусвязности.
3. Разбор задач на двусвязность.

'''Занятие 4.
1. Поиск множества фундаментальных циклов
2. Поиск компонент сильной связности.

'''Занятие 5.
1. Матроиды и жадные алгоритмы.
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

'''Занятие 6.
1. Переборные алгоритмы для построения всех остовных деревьев.
2. Коды Прюфера. Число остовных деревьев для полного графа

'''Занятие 7.
1. Числа Рамсея. Оценка чисел Рамсея.
2. Обобщение чисел Рамсея. Применение чисел Рамсея.

'''Занятие 8.
1. Паросочетания теорема Холла
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

'''Занятие 9.
1. Семинар по пройденным темам.

'''Занятие 10.
1. Алгоритм Куна для поиска максимальных паросочетаний
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
3. Венгерский алгоритм.

'''Занятие 11.
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
2. Задача коммивояжёра. ЗКНТ.
2. Эйлеров цикл. Задача китайского почтальона.

'''Занятие 12.
1. Последовательности деБрёйна.
2. Теорема о числе последовательностей.

'''Занятие 13.
1. Некоторые NP полные задачи на графах.
2. Обзор пройденного материала.

'''Занятие 14.
Семинар по пройденным темам.

'''Занятие 15.
Итоговая контрольная работа по курсу

== Вопросы к экзамену: ==

1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности.
''В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99''

2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов.
''В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95''

3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности.
''Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477''

4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование.
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343''

5. Матроиды и жадные алгоритмы
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345''

6. Минимальные остовные деревья. Алгоритм Краскала и Прима.
''Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490''

7. Переборные алгоритмы для построения всех остовных деревьев.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158
''

8. Числа Рамсея
''Карпов. Теория графов. С. 477-479''

9. Оценки чисел Рамсея
''Карпов. Теория графов С. 479-481''

10. Обобщение чисел Рамсея
''Карпов. Теория графов С. 482-484''

11. Паросочетания, теорема Холла.
''А. Эвнин Вокруг теоремы Холла С.5-6''

12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
''А. Эвнин Вокруг теоремы Холла С. 7,18''

13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний
''Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 83-87''

14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами
''Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 887-91''

15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна.
''de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764''
16. Задача коммивояжёра и ЗКНТ.
''Гэри, Джонсон Вычислительные машины и труднорешаемые задачи
С 189-190''

17. Достаточные признаки гамильтоновости графа.

''R.Diestel Graph Theory. Springer 2000, C 213-216''

18. Эйлеровы графы и задача китайского почтальона.
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239''

== Список литературы: ==

В. Липский Комбинаторика для программистов. М.Мир, 1988

Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013

Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978

Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf

А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23

Гери Джонсон Вычислительные машины и труднорешаемые задачи

== Список задач: ==

1. Двусвязность

2. Множество фундаментальных циклов

3. КСС

4. Прюфер

5. Куна алгоритм

6. Венгерский алгоритм

7. Покрытие матрицы

8. Задача китайского почтальона

9. Задача коммивояжёра, МВГ

10. Задачи на теорему Холла

11. Гамильтоновость

12. Теория Рамсея

13. Задачи теории слодности на графах

14. Матроиды, жадные алгоритмы

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

Графы и их применения

2023-06-13T10:40:18Z

Emergency User:

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров

Лектор: [[Бухман Антон Владимирович]]

== Программа курса Графы и их применения. ==

'''Занятие 1.
1. Введение. Обзор курса. - 20 минут
2. Семинар. Задачи на повторение курса по графам.

'''Занятие 2.
1. Семинар. Задачи на повторение -- продолжение.
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

'''Занятие 3.
1. Обходы графов.
2. Поиск компонент вершинной двусвязности.
3. Разбор задач на двусвязность.

'''Занятие 4.
1. Поиск множества фундаментальных циклов
2. Поиск компонент сильной связности.

'''Занятие 5.
1. Матроиды и жадные алгоритмы.
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

'''Занятие 6.
1. Переборные алгоритмы для построения всех остовных деревьев.
2. Коды Прюфера. Число остовных деревьев для полного графа

'''Занятие 7.
1. Числа Рамсея. Оценка чисел Рамсея.
2. Обобщение чисел Рамсея. Применение чисел Рамсея.

'''Занятие 8.
1. Паросочетания теорема Холла
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

'''Занятие 9.
1. Семинар по пройденным темам.

'''Занятие 10.
1. Алгоритм Куна для поиска максимальных паросочетаний
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
3. Венгерский алгоритм.

'''Занятие 11.
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
2. Задача коммивояжёра. ЗКНТ.
2. Эйлеров цикл. Задача китайского почтальона.

'''Занятие 12.
1. Последовательности деБрёйна.
2. Теорема о числе последовательностей.

'''Занятие 13.
1. Некоторые NP полные задачи на графах.
2. Обзор пройденного материала.

'''Занятие 14.
Семинар по пройденным темам.

'''Занятие 15.
Итоговая контрольная работа по курсу

Вопросы к экзамену:
1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности.
В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99
2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов.
В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95
3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности.
Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477
4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование.
Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343
5. Матроиды и жадные алгоритмы
Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345
6. Минимальные остовные деревья. Алгоритм Краскала и Прима.
Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490
7. Переборные алгоритмы для построения всех остовных деревьев.
Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158
8. Числа Рамсея
Карпов. Теория графов. С. 477-479
9. Оценки чисел Рамсея
Карпов. Теория графов С. 479-481
10. Обобщение чисел Рамсея
Карпов. Теория графов С. 482-484
11. Паросочетания, теорема Холла.
А. Эвнин Вокруг теоремы Холла С.5-6
12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
А. Эвнин Вокруг теоремы Холла С. 7,18
13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний
Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 83-87
14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
C 887-91
15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна.
de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764.

16. Задача коммивояжёра и ЗКНТ.
Гэри, Джонсон Вычислительные машины и труднорешаемые задачи
С 189-190,

17. Достаточные признаки гамильтоновости графа.
R.Diestel Graph Theory. Springer 2000, C 213-216

18. Эйлеровы графы и задача китайского почтальона.
Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239

== Список литературы: ==

В. Липский Комбинаторика для программистов. М.Мир, 1988

Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013

Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978

Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf

А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23

Гери Джонсон Вычислительные машины и труднорешаемые задачи

== Список задач: ==

1. Двусвязность

2. Множество фундаментальных циклов

3. КСС

4. Прюфер

5. Куна алгоритм

6. Венгерский алгоритм

7. Покрытие матрицы

8. Задача китайского почтальона

9. Задача коммивояжёра, МВГ

10. Задачи на теорему Холла

11. Гамильтоновость

12. Теория Рамсея

13. Задачи теории слодности на графах

14. Матроиды, жадные алгоритмы

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

Графы и их применения

2023-06-13T10:38:37Z

Emergency User:

Графы и их применения

2023-06-13T10:37:40Z

Emergency User: Добавлен апрограмма

Практикум по дискретным структурам

2021-05-26T08:08:10Z

Emergency User: /* Задание 5. Рекурентные нейронные сети */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

1. Из датасета на базе open_stt сформировать обучающую и тестовую выборки (по варинту).

2. Собрать модель на основе ctc_voxforge.py.

3. Обучить модели согласно заданию (по варианту, в котором 3 размера датасета + 2 варианта слоёв слоёв)

4. Провести эксперименты
размер датасета, время обучения, скорость inference, число эпох, число слоёв, cer/wer на тестовом и обучающем.

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Практикум по дискретным структурам

2021-05-26T08:06:05Z

Emergency User: /* Задание 2. Применение SAT решателей к задачам минимизации функций */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Практикум по дискретным структурам

2021-04-30T09:12:32Z

Emergency User: /* Практические задания */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

=== Задание 5. Рекурентные нейронные сети ===

=== Задание 6. Преобразование Фурье ===

=== Задание 7. Марковские модели ===

Практикум по дискретным структурам

2021-04-30T09:11:03Z

Emergency User: /* Практические задания */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. Регулярные выражения ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

Практикум по дискретным структурам

2021-04-30T09:10:36Z

Emergency User: /* Задание 1. */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. === Регулярные выражения

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

Практикум по дискретным структурам

2021-04-02T14:52:38Z

Emergency User: /* Задание 3. Классические модели машинного обучения */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику.

5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

Практикум по дискретным структурам

2021-04-02T14:50:41Z

Emergency User:

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. Применение SAT решателей к задачам минимизации функций ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список будет дан на лекции). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику. Для каждой модели.

5. Сравнить модели используя 5x2 кросс валидацию

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

Практикум по дискретным структурам

2021-04-02T14:49:34Z

Emergency User:

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Классические модели машинного обучения ===

1. Выбрать 3 модели машинного обучения (список будет дан на лекции). Рассказать о ней (презентация) кратко.

2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)

3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)

4. Провести тест посчитать acc/rec/F1 метрику. Для каждой модели.

5. Сравнить модели используя 5x2 кросс валидацию

=== Задание 4. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

Практикум по дискретным структурам

2021-02-24T14:19:49Z

Emergency User: /* Задание 2. */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

=== Задание 3. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

Практикум по дискретным структурам

2021-02-24T14:18:50Z

Emergency User: /* Задание 2. */

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

Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].

== Цель курса ==

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

== Лекции по курсу ==

=== Лекция 1. Регулярные выражения и обработка тескта. ===

=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===

Лекция 3. Sat-решатели и их приложения.

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

== Получение зачёта. ==

В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
Приём заданий происходит на семинарах во время выступления студента.

== Практические задания ==

=== Задание 1. ===

''Часть 1.''

Написать скрипт с использованием утилит bash, который выполняет следующие действия.
На вход подаётся путь к директории.
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp:
уникальный_id путь_к_файлу
...

utt2spk:
уникальный_id имя_спикера
...

text:
уникальный_id отекстовка
...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

''Часть 2.''

Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.

Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.

Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.

Пример входных данных:

wav.scp:
id1 /tmp/wavs/Name/1.wav

text:
id1 пример текста

utt2spk:
id1 Name

=== Задание 2. ===

Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

=== Задание 3. Обучение простейшей нейронной сети ===

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.

Практикум по дискретным структурам

2021-02-24T14:16:40Z

Emergency User: /* Задание 1. */

Практикум по дискретным структурам

2021-02-24T14:16:01Z

Emergency User: /* Задание 2. */

Практикум по дискретным структурам

2021-02-24T14:12:44Z

Emergency User: /* Задание 1. */

Практикум по дискретным структурам

2021-02-24T14:05:40Z

Emergency User: /* Задание 1. */

Практикум по дискретным структурам

2021-02-05T08:50:32Z

Emergency User: /* Задание 3. Обучение простейшей нейронной сети */

Практикум по дискретным структурам

2021-02-05T08:47:14Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:46:18Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:45:40Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:44:47Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:44:11Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:36:41Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:35:36Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:34:06Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:28:48Z

Emergency User:

Практикум по дискретным структурам

2021-02-05T08:28:32Z

Emergency User:

Шаблон:Important Announcements

2020-12-18T16:12:30Z

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

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

{|width = 90%
{{announce News|01 ноября 2020 г.|
Уважаемые студенты 411-419 групп!

Контрольная работа по курсу "'''Дополнительные главы дискретной математики'''" (ДГДМ) состоится в субботу 19 декабря 2020 года утром c 10:00 до 12:00.
Для участия в ней Вам необходимо пройти в 9:50 по следующей ссылке в Google Classroom:

https://classroom.google.com/c/MjQ0ODg5MjQ4MTA4?cjc=prst32i

Там же имеется файл 4к_2п_ДГДМ_вар-ты.xlsx, в котором напротив Вашей фамилии Вы можете найти номер Вашего варианта. В 10:00 откроется доступ к вариантам, и начнётся контрольная работа.

Выполнять задания необходимо тёмной ручкой на белой бумаге. В 12:00 контрольная работа закончится, и Вам будет выделено дополнительное время (5-10 минут) для того, чтобы Вы смогли отсканировать/сфотографировать Ваши решения и прикрепить полученные сканы/фото в Google Classroom. Имя прикрепляемого файла должно содержать Вашу фамилию (в латинской транскрипции), инициалы, номер группы и номер варианта.

Например, "IvanovSP_417_2var.PDF". Настоятельно рекомендуем загружать работу одним PDF-файлом. Если это Вам не удобно, можно загружать несколько файлов, нумеруя их по порядку.
Кроме формата PDF, можно использовать формат JPG.

По любым вопросам, которые у Вас могут возникнуть, Вы можете обращаться в период с 10:00 до 10:30 к лекторам. Для этого Вам нужно будет подключиться к конференции zoom:

https://us02web.zoom.us/j/88969881240?pwd=cnY2L2lheE5POFd5aWQvakFCV1FrZz09
Код доступа к конференции был передан старостам групп.

С наилучшими пожеланиями,
преподаватели курса ДГДМ.}}

{|width = 90%
{{announce News|01 ноября 2020 г.|
Уважаемые студенты 411-419 групп!
Контрольная работа по курсу "'''Дополнительные главы дискретной математики'''" (ДГДМ) состоится в субботу 19 декабря 2020 года утром c 10:00 до 12:00.
Для участия в ней Вам необходимо пройти в 9:50 по следующей ссылке в Google Classroom:
https://classroom.google.com/c/MjQ0ODg5MjQ4MTA4?cjc=prst32i
Там же имеется файл 4к_2п_ДГДМ_вар-ты.xlsx, в котором напротив Вашей фамилии Вы можете найти номер Вашего варианта. В 10:00 откроется доступ к вариантам, и начнётся контрольная работа.
Выполнять задания необходимо тёмной ручкой на белой бумаге. В 12:00 контрольная работа закончится, и Вам будет выделено дополнительное время (5-10 минут) для того, чтобы Вы смогли отсканировать/сфотографировать Ваши решения и прикрепить полученные сканы/фото в Google Classroom. Имя прикрепляемого файла должно содержать Вашу фамилию (в латинской транскрипции), инициалы, номер группы и номер варианта.
Например, "IvanovSP_417_2var.PDF". Настоятельно рекомендуем загружать работу одним PDF-файлом. Если это Вам не удобно, можно загружать несколько файлов, нумеруя их по порядку.
Кроме формата PDF, можно использовать формат JPG.
По любым вопросам, которые у Вас могут возникнуть, Вы можете обращаться в период с 10:00 до 10:30 к лекторам. Для этого Вам нужно будет подключиться к конференции zoom:
https://us02web.zoom.us/j/88969881240?pwd=cnY2L2lheE5POFd5aWQvakFCV1FrZz09
Код доступа к конференции был передан старостам групп.
С наилучшими пожеланиями,
преподаватели курса ДГДМ.}}

<includeonly>|- class="announce"
| valign="top" nowrap="true" align="right" style="font-style:italic" |
| valign="top" style="padding-left:0.5cm;" align="right"|[[Template:Important Announcements|архив объявлений]]
</includeonly><noinclude>|}
__NOEDITSECTION__
=== Архив объявлений ===
----
{|width = 90%
{{announce News|01 ноября 2020 г.| Спецсеминар "'''Дискретная математика и математическая кибернетика'''". В пятницу, '''6 ноября''', в '''16-20''' состоится доклад '''Попкова Кирилла Андреевича''' (Институт прикладной математики им. М.В. Келдыша РАН) "'''О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов'''". Спецсеминар состоится '''онлайн''' с помощью zoom. Узнать коды доступа можно по эл. почте у [[Селезнева Светлана Николаевна | преподавателя]].}}
{|width = 90%
{{announce News|28 апреля 2020 г.| '''Вниманию студентов 418 группы и 618/1 и 618/2 групп!''' Предзащита выпускных работ пройдет 6-го и 7-го мая по специальному графику и с использованием системы Zoom. Время предзащиты определяется научным руководителем, поэтому каждый студент обязан связаться со своим научным руководителем для назначения времени защиты. Для допуска к предзащите студент или научный руководитель должен на адрес mk@cs.msu.ru прислать: электронную версию выпускной работы в формате pdf, скан-копию отзыва научного руководителя, компьютерная презентация доклада в формате ppt или pdf и информацию о рецензенте.}}
{{announce News|19 апреля 2020 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: vkr418_2020.pdf| требования к оформлению ВКР]]. Текст положения о ВКР и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках и формате проведения предзащиты будет сообщена позднее.}}
{{announce News|19 апреля 2020 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: md618_2020.pdf| требования к оформлению магистерской диссертации]]. Текст положения о магистерской диссертации и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках и формате проведения предзащиты будет сообщена позднее.}}
{{announce News|02 марта 2020 г.| Продолжает работу научный семинар кафедры математической кибернетики '''«Дискретная математика и математическая кибернетика»''' (руководители семинара – д.ф.-м.н., зав. каф. С.А.Ложкин, д.ф.-м.н., проф. В.Б.Алексеев). Заседание семинара состоится '''6 марта 2020 г., 16:30, ауд. 523'''. Докладчик: к.ф.-м.н. Сергеев Игорь Сергеевич (ФГУП «Научно-исследовательский институт «Квант», механико-математический факультет МГУ имени М.В. Ломоносова). Название доклада: «Некоторые вопросы синтеза параллельных схем».}}
{{announce News|28 февраля 2020 г.| Начинает работу '''просеминар кафедры''', на который приглашаются '''студенты 1 и 2 курсов'''. Занятия проходят по '''пятницам с 16:20 до 17:55 в ауд. 507''', первое занятие 28 февраля. Форма проведения: независимые лекции-семинары. [[Media:prosem20_schedule.pdf|План лекций-семинаров.]] }}
{{announce News|07 января 2020 г.| Вниманию студентов группы 618/1! Экзамен пр курсу [[Вероятностные и квантовые алгоритмы]] начнется 17 января (пятница) в 10 ч в ауд. 507. Консультация к экзамену по курсу [[Вероятностные и квантовые алгоритмы]] назначена 16 января (четверг) в 15.00 в ауд. 507.}}
{{announce News|29 декабря 2019 г.| Вниманию студентов 318-й группы! Консультация к экзамену по курсу [[Избранные вопросы дискретной математики]] состоится 8 января (в среду) в 11 ч в ауд. 504.}}
{{announce News|25 декабря 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Второй заход отчета по преддипломной практике (418 группа) и отчета по НИР (группы 618/1 и 618/2) пройдет ''' в понедельник 30 декабря 2019 в 11:00, в аудитории 503'''.}}
{{announce News|18 декабря 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Отчет по преддипломной практике (418 группа) и отчет по НИР (группы 618/1 и 618/2) пройдут ''' в среду 25 декабря 2019 в 11:00, в аудитории 524'''.}}
{{announce News|2 декабря 2019 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: otchet618-2019.pdf| требования к оформлению отчета по научно-исследовательской работе (НИР)]] и [[Media: otchet_pattern618-2019.zip| шаблоны отчета по НИР]].}}
{{announce News|2 декабря 2019 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: otchet418-2019.pdf| требования к оформлению отчета по преддипломной практике]] и [[Media: otchet_pattern418-2019.zip| шаблоны отчета по преддипломной практике]].}}
{{announce News|13 ноября 2019 г.| Традиционный '''[[Вечер кафедр 2019|вечер кафедр]]''' математической кибернетики и информационной безопасности состоится '''7 декабря''' (в субботу), ориентировочное время начала: '''17:30'''.}}
{{announce News|30 сентября 2019 г.| Начинает работу научный семинар кафедры математической кибернетики '''«Дискретная математика и математическая кибернетика»''' (руководители семинара – д.ф.-м.н., зав. каф. С.А.Ложкин, д.ф.-м.н., проф. В.Б.Алексеев). Первое заседание семинара состоится ''4 октября 2019 г., 16:30, ауд. 612''. Докладчик: д.ф.-м.н., профессор В.Б. Алексеев. Название доклада: «Что такое квантовые вычисления?». [[Media:dmseminar_191004.pdf|Аннотация доклада]].
}}
{{announce News|2 сентября 2019 г.| Вниманию студентов 518/2 группы! Первое занятие по курсу [[Проектирование_больших_систем_С%2B%2B|Проектирование больших систем на C++]] состоится '''11 сентября'''.}}
{{announce News|29 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Последняя итерация защит курсовых работ пройдет '''31 мая (пятница) 2019 г. в 11:00, ауд. 503'''.}}
{{announce News|27 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Вторая итерация защит курсовых работ пройдет '''29 мая (среда) 2019 г. в 11:00, ауд. 612'''.}}
{{announce News|22 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Защита курсовых работ пройдет '''27 мая (понедельник) 2019 г. в 11:00, ауд. 612'''.}}
{{announce News|22 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Появились [[Media:kursovaja_2019.zip |требования к оформлению курсовой работы]]. Информация о сроках проведения защит курсовых работ будет сообщена позднее.}}
{{announce News|24 апреля 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Финальный заход предзащиты ВКР и магистерских диссертаций пройдет '''8 мая (среда) 2019 г. в 16:00, ауд. 582'''.}}
{{announce News|24 апреля 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Второй заход предзащиты ВКР и магистерских диссертаций пройдет '''26 апреля (пятница) 2019 г. в 16:20, ауд. 504'''.}}
{{announce News|9 апреля 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Предзащита ВКР и магистерских диссертаций пройдет '''24 апреля (среда) 2019 г. в 15:15, ауд. 582'''.}}
{{announce News|1 апреля 2019 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: vkr418.pdf| требования к оформлению ВКР]]. Текст положения о ВКР и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках проведения предзащиты будет сообщена позднее.}}
{{announce News|1 апреля 2019 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: md618.pdf| требования к оформлению магистерской диссертации]]. Текст положения о магистерской диссертации и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках проведения предзащиты будет сообщена позднее.}}
{{announce News|1 января 2019 г.| Вниманию студентов 418 группы! Экзамен по курсу '''[[Сложность алгоритмов]]''' состоится 11 января в 10.00 (а не в 9.00) в ауд. 508.}}
{{announce News|1 января 2019 г.| Вниманию студентов 418 группы! Консультация по курсу '''[[Сложность алгоритмов]]''' состоится 10 января с 13 ч в ауд. 507.}}
{{announce News|1 января 2019 г.| Вниманию студентов группы 618/1! Экзамен по курсу '''[[Вероятностные и квантовые алгоритмы]]''' состоится 10 января в 10.00 (а не в 9.00) в ауд. 507.}}
{{announce News|1 января 2019 г.| Вниманию студентов группы 618/1! Консультация по курсу '''[[Вероятностные и квантовые алгоритмы]]''' состоится 9 января с 15 ч в ауд. 505.}}
{{announce News|30 декабря 2018 г.| Вниманию студентов 318 группы! Консультация по курсу '''[[Избранные вопросы дискретной математики]]''' состоится 9 января с 11 ч в ауд. 503.}}
{{announce News|20 декабря 2018 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Второй заход отчета по преддипломной практике (418 группа) и отчета по НИР (группы 618/1 и 618/2) пройдет '''26 декабря 2018 в 15:00, в аудитории 609'''.}}
{{announce News|20 декабря 2018 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Отчет по преддипломной практике (418 группа) и отчет по НИР (группы 618/1 и 618/2) пройдут '''24 декабря 2018 в 15:00, в аудитории 612'''.}}
{{announce News|10 декабря 2018 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: otchet618-2018.pdf| требования к оформлению отчета по научно-исследовательской работе (НИР)]] и [[Media: otchet_pattern618-2018.zip| шаблоны отчета по НИР]].}}
{{announce News|10 декабря 2018 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: otchet418-2018.pdf| требования к оформлению отчета по преддипломной практике]] и [[Media: otchet_pattern418-2018.zip| шаблоны отчета по преддипломной практике]].}}
{{announce News|7 ноября 2018 г.| Традиционный '''[[Вечер кафедр 2018|вечер кафедр]]''' математической кибернетики и информационной безопасности [[Media:Traditional meeting 2018 announcement.pdf|состоится]] '''8 декабря''' (в субботу), ориентировочное время начала: '''18:00'''.}}
{{announce News|17 октября 2018 г.| Спецкурс для аспирантов "'''Графы и их приложения'''" читается по пятницам с 8-45 до 9-20 в ауд. 503. Первая лекция - 19 октября.}}
{{announce News|11 октября 2018 г.| Начинает работу Межфакультетский научный семинар «[[Актуальные математические задачи, связанные с проектированием СБИС]]» Руководители семинара – профессор кафедры математической кибернетики (МК) факультета ВМК Ложкин С.А. и профессор кафедры математической теории интеллектуальных систем (МАТИС) механико-математического факультета Гасанов Э.Э. На заседаниях семинара предполагается рассматривать научные результаты последних лет, полученные при решении математических задач, связанных с теми или иными этапами проектирования различных типов современных СБИС. Планируется также проведение докладов, посвященных текущему состоянию производства и проектирования СБИС, анализу возникающих в этих областях математических проблем. Первое заседание семинара состоится '''12 октября 2018 г. в 16 30 в ауд. 508''' (совместно с семинаром «[[Теория управляющих систем и математические модели СБИС]]»). На нём будет представлен доклад аспиранта кафедры МАТИС '''Ефимова Алексея Андреевича''' на тему: '''«Нижняя оценка энергопотребления для одного класса объёмных схем»'''.}}
{{announce News|5 октября 2018 г.| Вниманию студентов 518/2 группы! Занятия по курсу [[Проектирование_больших_систем_С%2B%2B|Проектирование больших систем на C++]] с 5 октября будут проходить в ауд. '''612'''.}}
{{announce News|6 июня 2018 г. | Студенты, писавшие письменный тест по курсу [[Основы кибернетики (3-й поток)]], должны ознакомиться с результатами экзамена с 15:00 до 15:30 – в аудитории П-9 или с 16:00 до 16:30 – в аудитории 632.}}
{{announce News|28 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Вторая итерация защит курсовых работ состоится 30 мая (в среду). Для всех групп начало в '''11:00''', в ауд. 503.}}
{{announce News|22 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Защита курсовых работ состоится 28 мая (в понедельник). Начало в '''11:00''' для 318 группы, ауд. 503. Начало в '''12:00''' для студентов 518/1 и 518/2 групп, ауд. 503,504. [[Media:kursovaja_2018.zip |Требования к оформлению курсовой работы]] вывешены на доске объявлений кафедры.}}
{{announce News|8 мая 2018 г.| '''Вниманию студентов 418, 618/1 и 618/2 групп!''' Последняя итерация предзащиты выпускных курсов (4 и 6 курс) кафедры пройдет 11-го мая в аудитории 505, начало в 10:00.}}
{{announce News|7 мая 2018 г.| '''Вниманию аспирантов 1 г/о кафедр ИО, МК и ММП!''' Экзамен по курсу [[Дискретные модели управляющих систем]] состоится 16 мая (в среду) в ауд. 582. Выдача вопросов в 16 ч. Начало опроса в 17 ч.}}
{{announce News|13 апреля 2018 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: vkr418-2018.pdf| требования к оформлению ВКР]]. Текст положения о ВКР и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Предзащита ВКР состоится 27 апреля (в пятницу) с 16:20 до 18:00 в ауд. 504 .}}
{{announce News|13 апреля 2018 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: md618-2018.pdf| требования к оформлению магистерской диссертации]]. Текст положения о магистерской диссертации и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Предзащита магистерских диссертаций состоится 27 апреля (в пятницу) с 18:00 в ауд. 504 (группа 618/1) и ауд. 505 (группа 618/2).}}
{{announce News|9 февраля 2018 г.| '''Вниманию участников семинара "[[Сложность решения дискретных задач]]"!''' Первое (организационное) заседание семинара в весеннем семестре состоится '''16 февраля''' (в пятницу) в '''16-20''' в ауд. '''503'''. На нем будет рассказано о работе семинара в семестре и будут выданы статьи для докладов участникам.}}
{{announce News|1 января 2018 г.| '''Вниманию студентов группы 518/2!''' конcультация к экзамену по курсу [[Математические модели и методы логического синтеза сверхбольших интегральных схем]] пройдет 8-го января 2018 г. в ауд. 506, начало в 12:00.}}
{{announce News|26 декабря 2017 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' вторая попытка сдачи отчета по преддипломной практике и по научно-исследовательской работе пройдет 29 декабря (в пятницу) с 12 ч в ауд. 503.}}
{{announce News|26 декабря 2017 г.| '''Вниманию аспирантов кафедры МК!''' Аттестация аспирантов кафедры МК состоится в среду 17 января в 14 ч 00 мин, ауд. 612. На аттестацию необходимо прийти со всеми необходимыми для аттестации бумагами, полностью оформленными. О необходимых бумагах и их оформлении узнавайте в отделе аспирантуры.}}
{{announce News|22 декабря 2017 г.| '''Вниманию студентов группы 618/1!''' Консультация по курсу [[Вероятностные и квантовые алгоритмы]] состоится 9 января (во вторник) с 15 ч 00 мин в ауд. 504. Экзамен - 10 января (в среду) с 9 ч 00 мин в ауд. 507.}}
{{announce News|22 декабря 2017 г.| '''Вниманию студентов 418 группы!''' Консультация по курсу [[Сложность алгоритмов]] состоится 17 января (в среду) с 15 ч 00 мин в ауд. 504. Экзамен - 18 января (в четверг) с 9 ч 00 мин в ауд. 508.}}
{{announce News|22 декабря 2017 г.| '''Вниманию студентов 318 группы!''' Консультация по курсу [[Избранные вопросы дискретной математики]] состоится 13 января (в субботу) с 12 ч 30 мин в ауд. 507.}}
{{announce News|12 декабря 2017 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: otchet618-2017.pdf| требования к оформлению отчета по научно-исследовательской работе (НИР)]] и [[Media: otchet_pattern618-2017.zip| шаблоны отчета по НИР]]. Отчет по НИР состоится 25 декабря (в понедельник) с 11 ч в ауд. 503 (группа 618/1) и ауд. 504 (группа 618/2).}}
{{announce News|12 декабря 2017 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: otchet418-2017.pdf| требования к оформлению отчета по преддипломной практике]] и [[Media: otchet_pattern418-2017.zip| шаблоны отчета по преддипломной практике]]. Отчет по преддипломной практике состоится 25 декабря (в понедельник) с 12 ч в ауд. 503 и в ауд. 504.}}
{{announce News|10 ноября 2017 г.| Традиционный '''[[Вечер кафедр 2017|вечер кафедр]]''' математической кибернетики и информационной безопасности состоится '''25 ноября''' (в субботу), ориентировочное время начала: '''16:00'''.}}
{{announce News|6 октября 2017 г.| Вниманию студентов групп 518/1 и 618/1! На странице "Магистерские программы" появился список курсов, которые можно выбрать в качестве элективных в этом семестре. Для того, чтобы в конце семестра зачесть курс не из списка как элективный, необходимо '''срочно (!)''' обратиться к ответственному исполнителю магистерской программы "Дискретные структуры и алгоритмы".}}
{{announce News|5 октября 2017 г.| Вниманию студентов групп 518/2 и 618/2! На странице "Магистерские программы" появился список курсов, которые можно выбрать в качестве элективных в этом семестре. Чтобы была возможность в конце семестра зачесть курс не из списка как элективный, необходимо '''срочно (!)''' обратиться к руководству кафедры.}}
{{announce News|14 сентября 2017 г.| Вниманию студентов 518/2 группы! Занятия по курсу [[Проектирование_больших_систем_С%2B%2B|Проектирование больших систем на C++]] с 15 сентября будут проходить в ауд. '''609'''.}}
{{announce News|1 сентября 2017 г.| Вниманию студентов 318 группы! Нагрузка по курсу [[Избранные вопросы дискретной математики]] (ИВДМ): лекции - каждую неделю, семинары - раз в две недели. В понедельник, 4 сентября, состоится только лекция по ИВДМ на 3-й паре.}}
{{announce News|1 сентября 2017 г.| Поздравляем с началом нового учебного года! Успехов и новых свершений!}}
{{announce News|18 мая 2017 г.| Вниманию студентов 318, 518/1, 518/2 групп! Защита курсовых работ состоится 26 мая (в пятницу) начало в '''11:30''', ауд. 504,505. Требования к оформлению работы вывешены на доске объявлений кафедры. [[Media: title-kursovaja.zip |Образец титульного листа дипломной работы]].}}
{{announce News|5 мая 2017 г.| Вниманию студентов 618/1 и 618/2 групп! Пересдача предзащиты (отчете по преддипломной практике) состоится 10 мая (в пятницу) с 15 ч 00 мин до 16 ч 30 мин, ауд. 504.}}
{{announce News|3 мая 2017 г.| Вниманию студентов 418, 618/1 и 618/2 групп! Пересдача предзащиты (отчете по преддипломной практике) состоится 5 мая (в пятницу) с 16 ч 30 мин до 19 ч, ауд. 504. Первыми будут выступать студенты 418 группы.}}
{{announce News|21 апреля 2017 г.| Вниманию студентов 618/1 и 618/2 групп! Появились [[Media: mvkr618-2017.doc |сведения]] о предзащите (отчете по преддипломной практике). Предзащита состоится 3 мая (в среду) с 16 ч 30 мин до 18 ч: 618/1 группа - в ауд. 503; 618/2 группа - в ауд. 504.}}
{{announce News|21 апреля 2017 г.| Вниманию студентов 418 группы! Появились [[Media: vkr418-2017.doc |сведения]] о предзащите (отчете по преддипломной практике). Предзащита состоится 3 мая (в среду) с 15 ч до 16 ч 20 мин в ауд. 505.}}
{{announce News|12 апреля 2017 г.| В среду, 12 апреля в 17-00 (обратите внимание на время начала семинара!)
состоится доклад

Vijay Ganesh (University of Waterloo)
"On The Unreasonable Effectiveness of Boolean SAT Solvers".

Abstract:

Modern conflict-driven clause-learning (CDCL) Boolean SAT solvers routinely
solve very large industrial SAT instances in relatively short periods of
time. This phenomenon has stumped both theoreticians and practitioners
since Boolean satisfiability is an NP-complete problem widely believed to
be intractable. It is clear that these solvers somehow exploit the
structure of real-world instances. However, to-date there have been few
results that precisely characterize this structure or shed any light on why
these SAT solvers are so efficient.

In this talk, I will present results that provide a deeper empirical
understanding of why CDCL SAT solvers are so efficient, which may
eventually lead to a complexity-theoretic result. Our results can be
divided into two parts. First, I will talk about structural parameters that
can characterize industrial instances and shed light on why they are easier
to solve even though they may contain millions of variables compared to
small crafted instances with hundreds of variables. Second, I will talk
about internals of CDCL SAT solvers, and describe why they are particularly
suited to solve industrial instances.
}}
{{announce News|3 января 2017 г.| Вниманию студентов 418 группы! Консультация по курсу «Сложность алгоритмов» - во вторник 17 января в 12.00 в ауд. 504.}}
{{announce News|3 января 2017 г.| Вниманию студентов группы 618/1. Консультация по курсу «Вероятностные и квантовые алгоритмы» - в воскресенье 15 января в 12.00 в ауд. 506.}}
{{announce News|30 декабря 2016 г.| С НОВЫМ ГОДОМ! ЗДОРОВЬЯ, УСПЕХОВ, УДАЧИ В НОВОМ ГОДУ.}}
{{announce News|16 декабря 2016 г.| Вывешены [[Media: Вопросы_к_экзамену_по_курсу_ВКА.docx| вопросы к экзамену по курсу "Вероятностные и квантовые алгоритмы"]] для гр. 618/1, лектор - профессор [[Алексеев Валерий Борисович]].}}
{{announce News|16 декабря 2016 г.| На странице курса [[Сложность алгоритмов]] вывешены Вопросы к экзамену по курсу "Сложность алгоритмов" для гр. 418 2016 года, лектор - профессор [[Алексеев Валерий Борисович]].}}
{{announce News|14 декабря 2016 г.| Появилась [[Media: Программа курса ДА.doc| программа курса "Дискретный анализ"]], лектор - профессор [[Сапоженко Александр Антонович]].}}
{{announce News|2 декабря 2016 г.| Вниманию студентов 618/1 и 618/2 групп! Появились [[Media: otchet618-2016.doc| требования к оформлению отчета по научно-исследовательской работе (НИР)]]. Отчет по НИР состоится 23 декабря (в пятницу) с 10 ч в ауд. 503.}}
{{announce News|2 декабря 2016 г.| Вниманию студентов 418 группы! Появились [[Media: otchet418-2016.doc| требования к оформлению отчета по преддипломной практике]]. Отчет по преддипломной практике состоится 23 декабря (в пятницу) с 14 ч 30 мин в ауд. 503.}}
{{announce News|7 ноября 2016 г.| Традиционный '''[[Вечер кафедр 2016|вечер кафедр]]''' математической кибернетики и информационной безопасности состоится '''26 ноября''' (в субботу), ориентировочное время начала: '''16:00'''.}}
{{announce News|18 октября 2016 г.| 24 октября в МГУ будет проходить семинар по программе MIPSfpga. На семинаре вас познакомят с современными направлениями и архитектурными решениями при разработке систем на кристалле, а также предоставят возможность поработать с реализацией процессора MIPS в ПЛИС на примере образовательных плат компаний Altera и Xilinx. [[Семинар_MIPSfpga_(24.10.2016)|Подробности здесь.]]}}
{{announce News|13 сентября 2016 г.| На странице курса [[Основы кибернетики (3-й поток)]] вывешены результаты пересдачи по этому курсу, прошедшей 09.09.2016. Показ работ состоится 14.09 в 14:30 в ауд. 504.}}
{{announce News|20 мая 2016 г.| Вниманию студентов 318 группы! Защита курсовых работ состоится в пятницу, 27 мая, с 14 ч (аудитория будет объявлена дополнительно). Требования к оформлению работы вывешены на доске объявлений кафедры.}}
{{announce News|20 мая 2016 г.| Вниманию студентов 518/1 и 518/2 групп! Защита курсовых работ состоится в среду, 25 мая, с 11 ч 30 мин (аудитория будет объявлена дополнительно). Требования к оформлению работы вывешены на доске объявлений кафедры.}}
{{announce News|16 апреля 2016 г.| Вниманию студентов 2 курса! 25 апреля в ауд. 504 пройдет общая встреча студентов с преподавателями кафедры математической кибернетики, начало в 16:20.}}
{{announce News|8 апреля 2016 г.| Вниманию студентов 418 группы! Появилась информация о [[Media:2016-418.doc|предзащите в 418 группе]] и образец [[Media:titul-vkr.doc|титульного листа ВКР]]}}.
{{announce News|04 апреля 2016 г.| Вниманию студентов магистратуры! Начинается чтение спецкурса на английском языке [[Boolean SAT/SMT Solvers for Software Engineering]]. Лекции первой части курса пройдут 4-го, 5-го, 7-го и 8-го арпеля в аудитории 526б, начало лекций в 18:00.}}
{{announce News|04 марта 2016 г.| Вниманию студентов 1 и 2 курсов! Начинает свою работу просеминар кафедры математической кибернетики и лаборатории дискретных управляющих систем и их приложений для студентов 2 курса. Первое заседание просеминара пройдет 14 марта с 16:20 до 17:55 в ауд. 504. Информацию о докладах можно будет найти в ближайшее время на [[Просеминар для 2-го курса|странице просеминара]].}}
{{announce News|26 февраля 2016 г.| На семинаре кафедры математической кибернетики состоится представление [[Media:Thesis_Novikova.pdf|диссертации]] Татьяны Анатольевной Новиковой (Казахстанский филиал МГУ в г. Астана).}}
{{announce News|20 января 2016 г.| Вывешены [[Media:Ok_fall2015.pdf|вопросы к экзамену]] по курсу [[Основы кибернетики (2-й поток)|«Основы кибернетики» (2-й поток)]].}}
{{announce News|12 января 2016 г.| Вниманию студентов группы 518/2! Консультация к экзамену по курсу «Элементы теории синтеза, надёжности и контроля дискретных управляющих систем» состоится 16.01.2016 в 11:00 в ауд. 506. На ней будут объявлены результаты контрольной и выданы проверенные работы.}}
{{announce News|29 декабря 2015 г.| Вывешен [[Media:Вопросы_ЭТДУС_418.pdf|список]] вопросов и типовых задач к экзамену по курсу «Элементы теории дискретных управляющих систем», который состоится 12.01.2016 в 9:00 в ауд. 505. Консультация к этому экзамену пройдёт 11.01.2016 в 14:00 в ауд. 503.}}
{{announce News|14 декабря 2015 г.| Вывешены [[Media:Курс_ЭТСНКДУС_518-2.pdf|вопросы, типовые задачи и литература]] к экзамену по курсу «Элементы теории синтеза, надёжности и контроля дискретных управляющих систем». Контрольная по вопросам и задачам разделов I, II состоится 19 декабря в 13:00 в ауд. 507, а консультация к ней пройдёт 18 декабря в 16:30 в ауд. 505. }}
{{announce News|13 декабря 2015 г.| Вывешены [[Media:Курс_ОК_318,_418_Осень.pdf| вопросы, типовые задачи и литература]] к экзамену по курсу «Основы кибернетики». См. дополнительную информацию на [[Основы кибернетики (318, 418 группы)|странице курса]]. }}
{{announce News|24 ноября 2015 г.| Поздравляем команду факультета ВМК с победой в соревновании [http://cad-contest.el.cycu.edu.tw/CAD-contest-at-ICCAD2015/ 2015 CAD Contest]! Подробности [[Команда факультета ВМК - победитель соревнования 2015 CAD Contest | здесь]]. }}
{{announce News|24 ноября 2015 г.| Вниманию участников вечера кафедр! Мероприятие состоится в аудитории '''П-7''' 2-го учебного корпуса. }}
{{announce News|19 ноября 2015 г.| 19 ноября 2015 года исполняется 80 лет со дня рождения доктора физико-математических наук профессора Гария Петровича Гаврилова (19.11.1935 – 05.12.1999), одного из первых двух штатных сотрудников кафедры математической кибернетики (в момент открытия она называлась кафедрой математической логики и теории автоматов). Гарий Петрович внес огромный вклад в организацию образования на факультете ВМК МГУ, в разработку новых курсов. Он получил много глубоких интересных результатов в математике, подготовил 6 кандидатов наук. Благодаря его переводам широкий круг людей в нашей стране познакомился с теорией графов. С краткой биографией и научными достижениями Гария Петровича Гаврилова можно ознакомиться [https://cs.msu.ru/persons/287 здесь]. }}
{{announce News|8 ноября 2015 г.| Традиционный '''вечер кафедр''' математической кибернетики и информационной безопасности (ранее - вечер кафедры математической кибернетики) состоится '''28 ноября''' (в субботу). Начало в '''16:00'''. Место проведения - 2-й учебный корпус, факультет ВМК. Аудитория будет объявлена позднее. По всем вопросам (в том числе выписыванию пропуска для прохода в корпус) можно обратиться сюда: [mailto:valdus@yandex.ru valdus@yandex.ru]. }}
{{announce News|5 ноября 2015 г.| Вниманию студентов! 10 ноября (16:00-20:00) представителем компании Imagination Technologies [http://panchul.com/about_ru/ Юрием Панчулом] совместно с кафедрой математической кибернетики будет проведен семинар, посвященный проекту [http://community.imgtec.com/university/ MIPSfpga]. На семинаре вас познакомят с основами работы с ПЛИС на примере образовательных плат компаний Altera и Xilinx. Подробности [[Media:Mipsfpga_announcement.pdf| здесь]]. }}
{{announce News|20 октября 2015 г.| Вниманию студентов 4-5 курсов! Спецсеминар [[Теория управляющих систем и математические модели СБИС]] 23 октября пройдет совместно со спецсеминаром [[Дискретная математика и математическая кибернетика]] в 16:20, ауд. 612. }}
{{announce News|17 октября 2015 г.| Вниманию студентов 318 группы! Выложено первое домашнее задание по [[Практикум (3 курс, осенний семестр 2015 года)| практикуму]]. }}
{{announce News|9 октября 2015 г.| Вниманию студентов спецсеминаров [[Некоторые вопросы теории управляющих систем]] и [[Теория управляющих систем и математические модели СБИС]] 9 октября пройдет совместное заседание спесеминаров в ауд. 704. }}
{{announce News|29 сентября 2015 г.| Вниманию студентов 418 группы! 30 сентября и 7 октября вместо лекций по курсу [[Элементы теории дискретных управляющих систем|"Элементы теории дискретных управляющих систем"]] пройдут занятия по "Практикуму на ЭВМ". }}
{{announce News|1 сентября 2015 г.| Первая и вторая лекции по курсу [[Математические модели и методы логического синтеза сверхбольших интегральных схем|Математические модели и методы логического синтеза СБИС]] для студентов группы 518(2) переносятся с 2 сентября и 9 сентября на 3-ю и 4-ую пару (с 12:50 до 16:10) 10 сентября в аудиторию 506.}}
{{announce News|31 августа 2015 г.| Вниманию студентов 518(2) группы! 2 сентября в 10-00 в ауд. 696 состоится собрание студентов магистерской программы [[:Категория:Магистерская программа Дискретные управляющие системы и их приложения|Дискретные управляющие системы и их приложения]]. Магистрантам указанной программы (особенно тем, кто не заканчивал кафедру математической кибернетики) рекомендуется прослушать первую часть курса [[Элементы теории дискретных управляющих систем]], который читается для студентов 418 группы (см. расписание и следующее объявление).}}
{{announce News|31 августа 2015 г.| Вниманию студентов 418 группы! Вместо занятий по практикуму 2 сентября и 9 сентября в 10-30 в ауд. 696 для студентов 418 группы состоятся лекции С.А.Ложкина по курсу [[Элементы теории дискретных управляющих систем]].}}
{{announce News|28 августа 2015 г.| Собрание коллектива факультета ВМК состоится в понедельник, 31 августа, в 12-30 в ауд. П_13.}}
{{announce News|26 мая 2015 г.| Защита курсовых работ студентов 318 группы состоится в среду, 27 мая, в ауд. 504. Начало в 11 ч. Информация об оформлении курсовых работ [[Media:kurs-318-2015.doc |здесь]]. Образец оформления титульного листа курсовой работы [[Media:titul-kurs-318-2015.doc | здесь]].}}
{{announce News|26 апреля 2015 г.| Выложены [[Media:OK_add_3.2_2015.pdf | дополнительные теоретические задачи]] к разделу "синтез и сложность управляющих систем" по курсам [[Основы кибернетики (3-й поток)]] , [[Основы кибернетики (318, 418 группы)]].}}
{{announce News|14 апреля 2015 г.| '''Обновление''' [[Media:diplom-518-2015.doc | информации для 518 группы]] об оформлении дипломной работы, сроках сдачи текста работы на кафедру и предзащитах, [[Media:titul-diplom-518-2015.doc | образец оформления титульного листа дипломной работы]].}}
{{announce News|14 апреля 2015 г.| '''Обновление''' [[Media:diplom-418-2015.doc | информации для 418 группы]] об оформлении выпускной квалификационной работы, сроках сдачи текста работы на кафедру и предзащитах, [[Media:titul-diplom-418-2015.doc | образец оформления титульного листа выпускной квалификационной работы]].}}
{{announce News|22 марта 2015 г.| Выложена [[Media:OK_add_2_2015.pdf | дополнительная задача]] к разделу "Эквивалентные преобразования управляющих систем" по курсам [[Основы кибернетики (3-й поток)]] , [[Основы кибернетики (318, 418 группы)]]. Задачи 1 и 3 к разделу "Минимизация ДНФ" больше не принимаются.}}
{{announce News|5 марта 2015 г.| Выложены [[Media:OK_add_1_2015.pdf | дополнительные задачи]] к разделу "Минимизация ДНФ" по курсам [[Основы кибернетики (3-й поток)]] , [[Основы кибернетики (318, 418 группы)]]}}
{{announce News|6 февраля 2015 г.| Доступно ''предварительное'' '''[[Расписание |расписание занятий]]''' на весенний семестр.}}
{{announce News|18 января 2015 г.| Консультация к экзамену по курсу [[Дискретная математика 1 (группа 141)]] для состоится 23 января, в пятницу, в ауд. 505. Консультация лектора - в 16 ч, консультация по решению задач - в 14 ч.}}
{{announce News|15 января 2015 г.| Консультация к экзамену по курсу [[Избранные вопросы дискретной математики]] для 318 группы состоится 20 января, во вторник, в 12-00 в аудитории 504. Информация о результатах коллоквиумов [[Media: ivdm-318-2015.doc|здесь]].}}
{{announce News|10 января 2015 г.| Консультация к экзамену по курсу "Сложность алгоритмов" для 418 группы пройдет 16 января в 16:00 в аудитории 505. Материалы для подготовки к экзамену можно найти на [[Сложность алгоритмов|странице курса]].}}
{{announce News|6 января 2015 г.| Консультация к экзамену по курсу "Избранные вопросы математической теории вычислений" для 518 группы пройдет 9 января в 16:00 в аудитории 504. Материалы для подготовки к экзамену можно найти на [[Модели вычислений|странице курса]].}}
{{announce News|5 января 2015 г.| Консультация к экзамену по курсу "Математические модели и методы синтеза СБИС" пройдет 9 января в 12:00 в аудитории 504. Материалы для подготовки к экзамену можно найти на [[Математические модели и методы синтеза СБИС|странице курса]].}}
{{announce News|25 ноября 2014 г.| Традиционный [[вечер кафедры]] математической кибернетики состоится '''6 декабря''' (в субботу) в ауд. '''П-7'''. Начало в '''16:00'''.}}
{{announce News|8 октября 2014 г.| Спецсеминар [[Некоторые вопросы теории управляющих систем]] начинает работу 10 октября. Спецсеминар будет проходить по пятницам в аудитории '''704''' в '''16:20'''.}}
{{announce News|30 сентября 2014 г.| Спецсеминар [[Теория управляющих систем и математические модели СБИС]] начинает работу 3 октября. Спецсеминар будет проходить по пятницам в аудитории '''612''' в '''16:20'''.}}
{{announce News|30 сентября 2014 г.| Совместный спецсеминар [[Дискретный анализ]] (рук. А.А. Сапоженко) и [[Сложность решения дискретных задач]] (рук. С.Н. Селезнева) начинает работу 3 октября. Спецсеминар будет проходить по пятницам в аудитории '''504''' с '''16:20''' до '''17:55'''.}}
{{announce News|29 сентября 2014 г.| Совместный спецсеминар [[Теоретические проблемы программирования]] (рук. Р.И. Подловченко, В.А. Захаров) и [[Математическая криптография]] (рук. М.И. Анохин, Н.П. Варновский) начинает работу 3 октября. Спецсеминар будет проходить по пятницам в аудитории '''508''' в '''16:20'''.}}
{{announce News|29 сентября 2014 г.| Вниманию слушателей спецкурса [[C++ 11/14 и современные аспекты построения компиляторов]]. Спецкурс будет проходить по четвергам в аудитории '''685''' в '''16:20'''.}}
{{announce News|22 сентября 2014 г.| Начинается чтение спецкурса Вычисления на машинах Минского. Лектор — проф. [[Марченков Сергей Серафимович]]. Первое занятие — 29 сентября в 10:30 аудитории 526-Б.}}
{{announce News|19 сентября 2014 г.| Начинается чтение спецкурса [[C++ 11/14 и современные аспекты построения компиляторов]]. Первое занятие — 25 сентября в аудитории 705.}}
{{announce News|11 июня 2014 г.| На страницах курсов [[Основы кибернетики (3-й поток)]] и [[Элементы теории дискретных управляющих систем]] (318 гр.) появилась информация о проведении экзаменов по этим курсам.}}
{{announce News|10 июня 2014 г.| [[Media:exam-vmb.doc|Вопросы к экзамену по курсу "Введение в математическую биологию"]] для студентов 418 группы.}}
{{announce News|06 июня 2014 г.| Для студентов 318 группы на странице курса [[Основы кибернетики (318, 418 группы)]], а также для студентов 320-328 групп на странице курса [[Основы кибернетики (3-й поток)]] появилась информация по поводу проведения консультаций.}}
{{announce News|03 июня 2014 г.| Для студентов 320-328 групп на странице курса [[Основы кибернетики (3-й поток)]] появилась информация по поводу проведения переписывания контрольных работ.}}
{{announce News|14 апреля 2014 г.| Для студентов 518 группы: [[Media: inf-518-2014.doc|информация о требованиях к дипломной работе]] и [[Media:title-diplom.doc|образец титульного листа дипломной работы]].}}
{{announce News|24 марта 2014 г.| Объявляется набор студентов и аспирантов в команду для решения [http://cad_contest.ee.ncu.edu.tw/CAD-Contest-at-ICCAD2014/problem_a/default.html одной из задач] соревнования [http://cad_contest.ee.ncu.edu.tw/CAD-Contest-at-ICCAD2014/ 2014 CAD Contest at ICCAD]. Записаться в команду и задать вопросы можно по адресу mikle.shupletsov@gmail.com. Краткое введение в проблематику задачи пройдет в рамках спецсеминара "Некоторые вопросы теории управляющих систем" 26 марта в 14-35 в ауд. 507. Кроме того, более подробную информацию по соревнованию можно будет получить 28 марта в 16-10 в ауд. П-13 (после лекции по курсу "Основы кибернетики").}}
{{announce News|24 марта 2014 г.| Выложена [[Media:OK_problems3.pdf | дополнительная задача]] к разделу "Синтез и сложность управляющих систем" по курсу [[Основы кибернетики (3-й поток)]].}}
{{announce News|18 февраля 2014 г.| Начинает работу спецсеминар [[Сложность решения дискретных задач]]. Первое заседание семинара состоится 21 февраля 2014 г. в 16-20 в ауд. 503.}}
{{announce News|17 февраля 2014 г.| Начинает работу спецсеминар [[Теория управляющих систем и математические модели СБИС]]. Первое заседание состоится 21 февраля в 16.20 в ауд. '''609'''.}}
{{announce News|17 февраля 2014 г.| Начинает работу спецсеминар [[Некоторые вопросы теории управляющих систем]]. Первое заседание состоится 19 февраля в 14.35 в ауд. '''507'''.}}
{{announce News|12 февраля 2014 г.| Начинается чтение спецкурса [[Архитектурные особенности современных вычислительных систем]]. Информация обновлена на странице курса.}}
{{announce News|10 февраля 2014 г.| Появилось объявление о докладе на спецсеминаре [[Дискретная математика и математическая кибернетика]] 14 февраля 2014 г.}}
{{announce News|15 января 2014 г.| Появилось объявление о докладе на спецсеминаре [[Дискретная математика и математическая кибернетика]] 7 февраля 2014 г.}}
{{announce News|1 января 2014 г.| С НОВЫМ 2014 ГОДОМ!}}
{{announce News|30 декабря 2013 г.| Для студентов 4-го курса появилось [[Media:kons-4-2013.docx| расписание консультаций]] по курсам "[[Основы кибернетики (2-й поток)]]" и "[[Математическая логика и логическое программирование]]" (для 3-го потока + 418-419 группы)}}
{{announce News|30 декабря 2013 г.| Для студентов 318, 418, 419, 518 групп появилось [[Media:kons-mk-2013.docx| расписание консультаций]] кафедральных курсов}}
{{announce News|24 декабря 2013 г.| Для студентов 418-419 групп появились [[Media:sa2013.doc|вопросы к экзамену]] и [[Media:konssa2013.docx|объявление о консультации]] по курсу "[[Сложность алгоритмов]]"}}
{{announce News|19 декабря 2013 г.| Для студентов 318 группы появилась информация к зачету на странице курса "[[Дополнительные главы дискретной математики (2-й поток III курса)|Дополнительные главы дискретной математики]]"}}
{{announce News|15 декабря 2013 г.| Для студентов 3-го курса 2-го потока появились [[Media:dgdm2013.pdf|вопросы к зачету]] по курсу "[[Дополнительные главы дискретной математики (2-й поток III курса)|Дополнительные главы дискретной математики]]" }}
{{announce News|13 декабря 2013 г.| Для студентов 518 группы появилась информация об [[Media:pract2013.pdf| отчете по производственной практике]] и об [[Media:dipl2013.pdf| отчете по дипломной работе]]}}
{{announce News|11 декабря 2013 г.| Традиционный ВЕЧЕР КАФЕДРЫ МАТЕМАТИЧЕСКОЙ КИБЕРНЕТИКИ факультета ВМК состоится в субботу 14 декабря в аудитории П7. Гостей ждем к 16 часам, официальное начало мероприятия -- в 16:30. Отметим, что в этом году фактически проводится совместный вечер двух кафедр -- математической кибернетики и информационной безопасности. Приходите -- будет интересно и весело!}}
{{announce News|3 октября 2013 г.| Начинает работу спецсеминар [[Некоторые вопросы теории управляющих систем]]. Первое заседание состоится 7 октября в 14.35 в ауд. '''506'''.}}
{{announce News|19 сентября 2013 г.| Начинает работу спецсеминар [[Теория управляющих систем и математические модели СБИС]]. Первое заседание состоится 20 сентября в 16.20 в ауд. '''612'''.}}
</noinclude>|}

Шаблон:Important Announcements

2020-12-18T16:08:07Z

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

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

{|width = 90%
{{announce News|01 ноября 2020 г.|
Уважаемые студенты 411-419 групп!

Контрольная работа по курсу "'''Дополнительные главы дискретной математики'''" (ДГДМ) состоится в субботу 19 декабря 2020 года утром c 10:00 до 12:00.
Для участия в ней Вам необходимо пройти в 9:50 по следующей ссылке в Google Classroom:

https://classroom.google.com/c/MjQ0ODg5MjQ4MTA4?cjc=prst32i

Там же имеется файл 4к_2п_ДГДМ_вар-ты.xlsx, в котором напротив Вашей фамилии Вы можете найти номер Вашего варианта. В 10:00 откроется доступ к вариантам, и начнётся контрольная работа.

Выполнять задания необходимо тёмной ручкой на белой бумаге. В 12:00 контрольная работа закончится, и Вам будет выделено дополнительное время (5-10 минут) для того, чтобы Вы смогли отсканировать/сфотографировать Ваши решения и прикрепить полученные сканы/фото в Google Classroom. Имя прикрепляемого файла должно содержать Вашу фамилию (в латинской транскрипции), инициалы, номер группы и номер варианта.

Например, "IvanovSP_417_2var.PDF". Настоятельно рекомендуем загружать работу одним PDF-файлом. Если это Вам не удобно, можно загружать несколько файлов, нумеруя их по порядку.
Кроме формата PDF, можно использовать формат JPG.

По любым вопросам, которые у Вас могут возникнуть, Вы можете обращаться в период с 10:00 до 10:30 к лекторам. Для этого Вам нужно будет подключиться к конференции zoom:

https://us02web.zoom.us/j/88969881240?pwd=cnY2L2lheE5POFd5aWQvakFCV1FrZz09
Код доступа к конференции был передан старостам групп.

С наилучшими пожеланиями,
преподаватели курса ДГДМ.}}

{|width = 90%
{{announce News|01 ноября 2020 г.| Спецсеминар "'''Дискретная математика и математическая кибернетика'''". В пятницу, '''6 ноября''', в '''16-20''' состоится доклад '''Попкова Кирилла Андреевича''' (Институт прикладной математики им. М.В. Келдыша РАН) "'''О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов'''". Спецсеминар состоится '''онлайн''' с помощью zoom. Узнать коды доступа можно по эл. почте у [[Селезнева Светлана Николаевна | преподавателя]].}}

<includeonly>|- class="announce"
| valign="top" nowrap="true" align="right" style="font-style:italic" |
| valign="top" style="padding-left:0.5cm;" align="right"|[[Template:Important Announcements|архив объявлений]]
</includeonly><noinclude>|}
__NOEDITSECTION__
=== Архив объявлений ===
----
{|width = 90%
{{announce News|28 апреля 2020 г.| '''Вниманию студентов 418 группы и 618/1 и 618/2 групп!''' Предзащита выпускных работ пройдет 6-го и 7-го мая по специальному графику и с использованием системы Zoom. Время предзащиты определяется научным руководителем, поэтому каждый студент обязан связаться со своим научным руководителем для назначения времени защиты. Для допуска к предзащите студент или научный руководитель должен на адрес mk@cs.msu.ru прислать: электронную версию выпускной работы в формате pdf, скан-копию отзыва научного руководителя, компьютерная презентация доклада в формате ppt или pdf и информацию о рецензенте.}}
{{announce News|19 апреля 2020 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: vkr418_2020.pdf| требования к оформлению ВКР]]. Текст положения о ВКР и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках и формате проведения предзащиты будет сообщена позднее.}}
{{announce News|19 апреля 2020 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: md618_2020.pdf| требования к оформлению магистерской диссертации]]. Текст положения о магистерской диссертации и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках и формате проведения предзащиты будет сообщена позднее.}}
{{announce News|02 марта 2020 г.| Продолжает работу научный семинар кафедры математической кибернетики '''«Дискретная математика и математическая кибернетика»''' (руководители семинара – д.ф.-м.н., зав. каф. С.А.Ложкин, д.ф.-м.н., проф. В.Б.Алексеев). Заседание семинара состоится '''6 марта 2020 г., 16:30, ауд. 523'''. Докладчик: к.ф.-м.н. Сергеев Игорь Сергеевич (ФГУП «Научно-исследовательский институт «Квант», механико-математический факультет МГУ имени М.В. Ломоносова). Название доклада: «Некоторые вопросы синтеза параллельных схем».}}
{{announce News|28 февраля 2020 г.| Начинает работу '''просеминар кафедры''', на который приглашаются '''студенты 1 и 2 курсов'''. Занятия проходят по '''пятницам с 16:20 до 17:55 в ауд. 507''', первое занятие 28 февраля. Форма проведения: независимые лекции-семинары. [[Media:prosem20_schedule.pdf|План лекций-семинаров.]] }}
{{announce News|07 января 2020 г.| Вниманию студентов группы 618/1! Экзамен пр курсу [[Вероятностные и квантовые алгоритмы]] начнется 17 января (пятница) в 10 ч в ауд. 507. Консультация к экзамену по курсу [[Вероятностные и квантовые алгоритмы]] назначена 16 января (четверг) в 15.00 в ауд. 507.}}
{{announce News|29 декабря 2019 г.| Вниманию студентов 318-й группы! Консультация к экзамену по курсу [[Избранные вопросы дискретной математики]] состоится 8 января (в среду) в 11 ч в ауд. 504.}}
{{announce News|25 декабря 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Второй заход отчета по преддипломной практике (418 группа) и отчета по НИР (группы 618/1 и 618/2) пройдет ''' в понедельник 30 декабря 2019 в 11:00, в аудитории 503'''.}}
{{announce News|18 декабря 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Отчет по преддипломной практике (418 группа) и отчет по НИР (группы 618/1 и 618/2) пройдут ''' в среду 25 декабря 2019 в 11:00, в аудитории 524'''.}}
{{announce News|2 декабря 2019 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: otchet618-2019.pdf| требования к оформлению отчета по научно-исследовательской работе (НИР)]] и [[Media: otchet_pattern618-2019.zip| шаблоны отчета по НИР]].}}
{{announce News|2 декабря 2019 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: otchet418-2019.pdf| требования к оформлению отчета по преддипломной практике]] и [[Media: otchet_pattern418-2019.zip| шаблоны отчета по преддипломной практике]].}}
{{announce News|13 ноября 2019 г.| Традиционный '''[[Вечер кафедр 2019|вечер кафедр]]''' математической кибернетики и информационной безопасности состоится '''7 декабря''' (в субботу), ориентировочное время начала: '''17:30'''.}}
{{announce News|30 сентября 2019 г.| Начинает работу научный семинар кафедры математической кибернетики '''«Дискретная математика и математическая кибернетика»''' (руководители семинара – д.ф.-м.н., зав. каф. С.А.Ложкин, д.ф.-м.н., проф. В.Б.Алексеев). Первое заседание семинара состоится ''4 октября 2019 г., 16:30, ауд. 612''. Докладчик: д.ф.-м.н., профессор В.Б. Алексеев. Название доклада: «Что такое квантовые вычисления?». [[Media:dmseminar_191004.pdf|Аннотация доклада]].
}}
{{announce News|2 сентября 2019 г.| Вниманию студентов 518/2 группы! Первое занятие по курсу [[Проектирование_больших_систем_С%2B%2B|Проектирование больших систем на C++]] состоится '''11 сентября'''.}}
{{announce News|29 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Последняя итерация защит курсовых работ пройдет '''31 мая (пятница) 2019 г. в 11:00, ауд. 503'''.}}
{{announce News|27 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Вторая итерация защит курсовых работ пройдет '''29 мая (среда) 2019 г. в 11:00, ауд. 612'''.}}
{{announce News|22 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Защита курсовых работ пройдет '''27 мая (понедельник) 2019 г. в 11:00, ауд. 612'''.}}
{{announce News|22 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Появились [[Media:kursovaja_2019.zip |требования к оформлению курсовой работы]]. Информация о сроках проведения защит курсовых работ будет сообщена позднее.}}
{{announce News|24 апреля 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Финальный заход предзащиты ВКР и магистерских диссертаций пройдет '''8 мая (среда) 2019 г. в 16:00, ауд. 582'''.}}
{{announce News|24 апреля 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Второй заход предзащиты ВКР и магистерских диссертаций пройдет '''26 апреля (пятница) 2019 г. в 16:20, ауд. 504'''.}}
{{announce News|9 апреля 2019 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Предзащита ВКР и магистерских диссертаций пройдет '''24 апреля (среда) 2019 г. в 15:15, ауд. 582'''.}}
{{announce News|1 апреля 2019 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: vkr418.pdf| требования к оформлению ВКР]]. Текст положения о ВКР и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках проведения предзащиты будет сообщена позднее.}}
{{announce News|1 апреля 2019 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: md618.pdf| требования к оформлению магистерской диссертации]]. Текст положения о магистерской диссертации и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Информация о сроках проведения предзащиты будет сообщена позднее.}}
{{announce News|1 января 2019 г.| Вниманию студентов 418 группы! Экзамен по курсу '''[[Сложность алгоритмов]]''' состоится 11 января в 10.00 (а не в 9.00) в ауд. 508.}}
{{announce News|1 января 2019 г.| Вниманию студентов 418 группы! Консультация по курсу '''[[Сложность алгоритмов]]''' состоится 10 января с 13 ч в ауд. 507.}}
{{announce News|1 января 2019 г.| Вниманию студентов группы 618/1! Экзамен по курсу '''[[Вероятностные и квантовые алгоритмы]]''' состоится 10 января в 10.00 (а не в 9.00) в ауд. 507.}}
{{announce News|1 января 2019 г.| Вниманию студентов группы 618/1! Консультация по курсу '''[[Вероятностные и квантовые алгоритмы]]''' состоится 9 января с 15 ч в ауд. 505.}}
{{announce News|30 декабря 2018 г.| Вниманию студентов 318 группы! Консультация по курсу '''[[Избранные вопросы дискретной математики]]''' состоится 9 января с 11 ч в ауд. 503.}}
{{announce News|20 декабря 2018 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Второй заход отчета по преддипломной практике (418 группа) и отчета по НИР (группы 618/1 и 618/2) пройдет '''26 декабря 2018 в 15:00, в аудитории 609'''.}}
{{announce News|20 декабря 2018 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' Отчет по преддипломной практике (418 группа) и отчет по НИР (группы 618/1 и 618/2) пройдут '''24 декабря 2018 в 15:00, в аудитории 612'''.}}
{{announce News|10 декабря 2018 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: otchet618-2018.pdf| требования к оформлению отчета по научно-исследовательской работе (НИР)]] и [[Media: otchet_pattern618-2018.zip| шаблоны отчета по НИР]].}}
{{announce News|10 декабря 2018 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: otchet418-2018.pdf| требования к оформлению отчета по преддипломной практике]] и [[Media: otchet_pattern418-2018.zip| шаблоны отчета по преддипломной практике]].}}
{{announce News|7 ноября 2018 г.| Традиционный '''[[Вечер кафедр 2018|вечер кафедр]]''' математической кибернетики и информационной безопасности [[Media:Traditional meeting 2018 announcement.pdf|состоится]] '''8 декабря''' (в субботу), ориентировочное время начала: '''18:00'''.}}
{{announce News|17 октября 2018 г.| Спецкурс для аспирантов "'''Графы и их приложения'''" читается по пятницам с 8-45 до 9-20 в ауд. 503. Первая лекция - 19 октября.}}
{{announce News|11 октября 2018 г.| Начинает работу Межфакультетский научный семинар «[[Актуальные математические задачи, связанные с проектированием СБИС]]» Руководители семинара – профессор кафедры математической кибернетики (МК) факультета ВМК Ложкин С.А. и профессор кафедры математической теории интеллектуальных систем (МАТИС) механико-математического факультета Гасанов Э.Э. На заседаниях семинара предполагается рассматривать научные результаты последних лет, полученные при решении математических задач, связанных с теми или иными этапами проектирования различных типов современных СБИС. Планируется также проведение докладов, посвященных текущему состоянию производства и проектирования СБИС, анализу возникающих в этих областях математических проблем. Первое заседание семинара состоится '''12 октября 2018 г. в 16 30 в ауд. 508''' (совместно с семинаром «[[Теория управляющих систем и математические модели СБИС]]»). На нём будет представлен доклад аспиранта кафедры МАТИС '''Ефимова Алексея Андреевича''' на тему: '''«Нижняя оценка энергопотребления для одного класса объёмных схем»'''.}}
{{announce News|5 октября 2018 г.| Вниманию студентов 518/2 группы! Занятия по курсу [[Проектирование_больших_систем_С%2B%2B|Проектирование больших систем на C++]] с 5 октября будут проходить в ауд. '''612'''.}}
{{announce News|6 июня 2018 г. | Студенты, писавшие письменный тест по курсу [[Основы кибернетики (3-й поток)]], должны ознакомиться с результатами экзамена с 15:00 до 15:30 – в аудитории П-9 или с 16:00 до 16:30 – в аудитории 632.}}
{{announce News|28 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Вторая итерация защит курсовых работ состоится 30 мая (в среду). Для всех групп начало в '''11:00''', в ауд. 503.}}
{{announce News|22 мая 2018 г.| '''Вниманию студентов 318, 518/1, 518/2 групп!''' Защита курсовых работ состоится 28 мая (в понедельник). Начало в '''11:00''' для 318 группы, ауд. 503. Начало в '''12:00''' для студентов 518/1 и 518/2 групп, ауд. 503,504. [[Media:kursovaja_2018.zip |Требования к оформлению курсовой работы]] вывешены на доске объявлений кафедры.}}
{{announce News|8 мая 2018 г.| '''Вниманию студентов 418, 618/1 и 618/2 групп!''' Последняя итерация предзащиты выпускных курсов (4 и 6 курс) кафедры пройдет 11-го мая в аудитории 505, начало в 10:00.}}
{{announce News|7 мая 2018 г.| '''Вниманию аспирантов 1 г/о кафедр ИО, МК и ММП!''' Экзамен по курсу [[Дискретные модели управляющих систем]] состоится 16 мая (в среду) в ауд. 582. Выдача вопросов в 16 ч. Начало опроса в 17 ч.}}
{{announce News|13 апреля 2018 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: vkr418-2018.pdf| требования к оформлению ВКР]]. Текст положения о ВКР и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Предзащита ВКР состоится 27 апреля (в пятницу) с 16:20 до 18:00 в ауд. 504 .}}
{{announce News|13 апреля 2018 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: md618-2018.pdf| требования к оформлению магистерской диссертации]]. Текст положения о магистерской диссертации и шаблоны оформления титульной страницы, отзыва научного руководителя и рецензии рецензента можно найти на [https://cs.msu.ru/studies/finalexams сайте факультета]. Предзащита магистерских диссертаций состоится 27 апреля (в пятницу) с 18:00 в ауд. 504 (группа 618/1) и ауд. 505 (группа 618/2).}}
{{announce News|9 февраля 2018 г.| '''Вниманию участников семинара "[[Сложность решения дискретных задач]]"!''' Первое (организационное) заседание семинара в весеннем семестре состоится '''16 февраля''' (в пятницу) в '''16-20''' в ауд. '''503'''. На нем будет рассказано о работе семинара в семестре и будут выданы статьи для докладов участникам.}}
{{announce News|1 января 2018 г.| '''Вниманию студентов группы 518/2!''' конcультация к экзамену по курсу [[Математические модели и методы логического синтеза сверхбольших интегральных схем]] пройдет 8-го января 2018 г. в ауд. 506, начало в 12:00.}}
{{announce News|26 декабря 2017 г.| '''Вниманию студентов групп 418, 618/1 и 618/2!''' вторая попытка сдачи отчета по преддипломной практике и по научно-исследовательской работе пройдет 29 декабря (в пятницу) с 12 ч в ауд. 503.}}
{{announce News|26 декабря 2017 г.| '''Вниманию аспирантов кафедры МК!''' Аттестация аспирантов кафедры МК состоится в среду 17 января в 14 ч 00 мин, ауд. 612. На аттестацию необходимо прийти со всеми необходимыми для аттестации бумагами, полностью оформленными. О необходимых бумагах и их оформлении узнавайте в отделе аспирантуры.}}
{{announce News|22 декабря 2017 г.| '''Вниманию студентов группы 618/1!''' Консультация по курсу [[Вероятностные и квантовые алгоритмы]] состоится 9 января (во вторник) с 15 ч 00 мин в ауд. 504. Экзамен - 10 января (в среду) с 9 ч 00 мин в ауд. 507.}}
{{announce News|22 декабря 2017 г.| '''Вниманию студентов 418 группы!''' Консультация по курсу [[Сложность алгоритмов]] состоится 17 января (в среду) с 15 ч 00 мин в ауд. 504. Экзамен - 18 января (в четверг) с 9 ч 00 мин в ауд. 508.}}
{{announce News|22 декабря 2017 г.| '''Вниманию студентов 318 группы!''' Консультация по курсу [[Избранные вопросы дискретной математики]] состоится 13 января (в субботу) с 12 ч 30 мин в ауд. 507.}}
{{announce News|12 декабря 2017 г.| '''Вниманию студентов 618/1 и 618/2 групп!''' Появились [[Media: otchet618-2017.pdf| требования к оформлению отчета по научно-исследовательской работе (НИР)]] и [[Media: otchet_pattern618-2017.zip| шаблоны отчета по НИР]]. Отчет по НИР состоится 25 декабря (в понедельник) с 11 ч в ауд. 503 (группа 618/1) и ауд. 504 (группа 618/2).}}
{{announce News|12 декабря 2017 г.| '''Вниманию студентов 418 группы!''' Появились [[Media: otchet418-2017.pdf| требования к оформлению отчета по преддипломной практике]] и [[Media: otchet_pattern418-2017.zip| шаблоны отчета по преддипломной практике]]. Отчет по преддипломной практике состоится 25 декабря (в понедельник) с 12 ч в ауд. 503 и в ауд. 504.}}
{{announce News|10 ноября 2017 г.| Традиционный '''[[Вечер кафедр 2017|вечер кафедр]]''' математической кибернетики и информационной безопасности состоится '''25 ноября''' (в субботу), ориентировочное время начала: '''16:00'''.}}
{{announce News|6 октября 2017 г.| Вниманию студентов групп 518/1 и 618/1! На странице "Магистерские программы" появился список курсов, которые можно выбрать в качестве элективных в этом семестре. Для того, чтобы в конце семестра зачесть курс не из списка как элективный, необходимо '''срочно (!)''' обратиться к ответственному исполнителю магистерской программы "Дискретные структуры и алгоритмы".}}
{{announce News|5 октября 2017 г.| Вниманию студентов групп 518/2 и 618/2! На странице "Магистерские программы" появился список курсов, которые можно выбрать в качестве элективных в этом семестре. Чтобы была возможность в конце семестра зачесть курс не из списка как элективный, необходимо '''срочно (!)''' обратиться к руководству кафедры.}}
{{announce News|14 сентября 2017 г.| Вниманию студентов 518/2 группы! Занятия по курсу [[Проектирование_больших_систем_С%2B%2B|Проектирование больших систем на C++]] с 15 сентября будут проходить в ауд. '''609'''.}}
{{announce News|1 сентября 2017 г.| Вниманию студентов 318 группы! Нагрузка по курсу [[Избранные вопросы дискретной математики]] (ИВДМ): лекции - каждую неделю, семинары - раз в две недели. В понедельник, 4 сентября, состоится только лекция по ИВДМ на 3-й паре.}}
{{announce News|1 сентября 2017 г.| Поздравляем с началом нового учебного года! Успехов и новых свершений!}}
{{announce News|18 мая 2017 г.| Вниманию студентов 318, 518/1, 518/2 групп! Защита курсовых работ состоится 26 мая (в пятницу) начало в '''11:30''', ауд. 504,505. Требования к оформлению работы вывешены на доске объявлений кафедры. [[Media: title-kursovaja.zip |Образец титульного листа дипломной работы]].}}
{{announce News|5 мая 2017 г.| Вниманию студентов 618/1 и 618/2 групп! Пересдача предзащиты (отчете по преддипломной практике) состоится 10 мая (в пятницу) с 15 ч 00 мин до 16 ч 30 мин, ауд. 504.}}
{{announce News|3 мая 2017 г.| Вниманию студентов 418, 618/1 и 618/2 групп! Пересдача предзащиты (отчете по преддипломной практике) состоится 5 мая (в пятницу) с 16 ч 30 мин до 19 ч, ауд. 504. Первыми будут выступать студенты 418 группы.}}
{{announce News|21 апреля 2017 г.| Вниманию студентов 618/1 и 618/2 групп! Появились [[Media: mvkr618-2017.doc |сведения]] о предзащите (отчете по преддипломной практике). Предзащита состоится 3 мая (в среду) с 16 ч 30 мин до 18 ч: 618/1 группа - в ауд. 503; 618/2 группа - в ауд. 504.}}
{{announce News|21 апреля 2017 г.| Вниманию студентов 418 группы! Появились [[Media: vkr418-2017.doc |сведения]] о предзащите (отчете по преддипломной практике). Предзащита состоится 3 мая (в среду) с 15 ч до 16 ч 20 мин в ауд. 505.}}
{{announce News|12 апреля 2017 г.| В среду, 12 апреля в 17-00 (обратите внимание на время начала семинара!)
состоится доклад

Vijay Ganesh (University of Waterloo)
"On The Unreasonable Effectiveness of Boolean SAT Solvers".

Abstract:

Modern conflict-driven clause-learning (CDCL) Boolean SAT solvers routinely
solve very large industrial SAT instances in relatively short periods of
time. This phenomenon has stumped both theoreticians and practitioners
since Boolean satisfiability is an NP-complete problem widely believed to
be intractable. It is clear that these solvers somehow exploit the
structure of real-world instances. However, to-date there have been few
results that precisely characterize this structure or shed any light on why
these SAT solvers are so efficient.

In this talk, I will present results that provide a deeper empirical
understanding of why CDCL SAT solvers are so efficient, which may
eventually lead to a complexity-theoretic result. Our results can be
divided into two parts. First, I will talk about structural parameters that
can characterize industrial instances and shed light on why they are easier
to solve even though they may contain millions of variables compared to
small crafted instances with hundreds of variables. Second, I will talk
about internals of CDCL SAT solvers, and describe why they are particularly
suited to solve industrial instances.
}}
{{announce News|3 января 2017 г.| Вниманию студентов 418 группы! Консультация по курсу «Сложность алгоритмов» - во вторник 17 января в 12.00 в ауд. 504.}}
{{announce News|3 января 2017 г.| Вниманию студентов группы 618/1. Консультация по курсу «Вероятностные и квантовые алгоритмы» - в воскресенье 15 января в 12.00 в ауд. 506.}}
{{announce News|30 декабря 2016 г.| С НОВЫМ ГОДОМ! ЗДОРОВЬЯ, УСПЕХОВ, УДАЧИ В НОВОМ ГОДУ.}}
{{announce News|16 декабря 2016 г.| Вывешены [[Media: Вопросы_к_экзамену_по_курсу_ВКА.docx| вопросы к экзамену по курсу "Вероятностные и квантовые алгоритмы"]] для гр. 618/1, лектор - профессор [[Алексеев Валерий Борисович]].}}
{{announce News|16 декабря 2016 г.| На странице курса [[Сложность алгоритмов]] вывешены Вопросы к экзамену по курсу "Сложность алгоритмов" для гр. 418 2016 года, лектор - профессор [[Алексеев Валерий Борисович]].}}
{{announce News|14 декабря 2016 г.| Появилась [[Media: Программа курса ДА.doc| программа курса "Дискретный анализ"]], лектор - профессор [[Сапоженко Александр Антонович]].}}
{{announce News|2 декабря 2016 г.| Вниманию студентов 618/1 и 618/2 групп! Появились [[Media: otchet618-2016.doc| требования к оформлению отчета по научно-исследовательской работе (НИР)]]. Отчет по НИР состоится 23 декабря (в пятницу) с 10 ч в ауд. 503.}}
{{announce News|2 декабря 2016 г.| Вниманию студентов 418 группы! Появились [[Media: otchet418-2016.doc| требования к оформлению отчета по преддипломной практике]]. Отчет по преддипломной практике состоится 23 декабря (в пятницу) с 14 ч 30 мин в ауд. 503.}}
{{announce News|7 ноября 2016 г.| Традиционный '''[[Вечер кафедр 2016|вечер кафедр]]''' математической кибернетики и информационной безопасности состоится '''26 ноября''' (в субботу), ориентировочное время начала: '''16:00'''.}}
{{announce News|18 октября 2016 г.| 24 октября в МГУ будет проходить семинар по программе MIPSfpga. На семинаре вас познакомят с современными направлениями и архитектурными решениями при разработке систем на кристалле, а также предоставят возможность поработать с реализацией процессора MIPS в ПЛИС на примере образовательных плат компаний Altera и Xilinx. [[Семинар_MIPSfpga_(24.10.2016)|Подробности здесь.]]}}
{{announce News|13 сентября 2016 г.| На странице курса [[Основы кибернетики (3-й поток)]] вывешены результаты пересдачи по этому курсу, прошедшей 09.09.2016. Показ работ состоится 14.09 в 14:30 в ауд. 504.}}
{{announce News|20 мая 2016 г.| Вниманию студентов 318 группы! Защита курсовых работ состоится в пятницу, 27 мая, с 14 ч (аудитория будет объявлена дополнительно). Требования к оформлению работы вывешены на доске объявлений кафедры.}}
{{announce News|20 мая 2016 г.| Вниманию студентов 518/1 и 518/2 групп! Защита курсовых работ состоится в среду, 25 мая, с 11 ч 30 мин (аудитория будет объявлена дополнительно). Требования к оформлению работы вывешены на доске объявлений кафедры.}}
{{announce News|16 апреля 2016 г.| Вниманию студентов 2 курса! 25 апреля в ауд. 504 пройдет общая встреча студентов с преподавателями кафедры математической кибернетики, начало в 16:20.}}
{{announce News|8 апреля 2016 г.| Вниманию студентов 418 группы! Появилась информация о [[Media:2016-418.doc|предзащите в 418 группе]] и образец [[Media:titul-vkr.doc|титульного листа ВКР]]}}.
{{announce News|04 апреля 2016 г.| Вниманию студентов магистратуры! Начинается чтение спецкурса на английском языке [[Boolean SAT/SMT Solvers for Software Engineering]]. Лекции первой части курса пройдут 4-го, 5-го, 7-го и 8-го арпеля в аудитории 526б, начало лекций в 18:00.}}
{{announce News|04 марта 2016 г.| Вниманию студентов 1 и 2 курсов! Начинает свою работу просеминар кафедры математической кибернетики и лаборатории дискретных управляющих систем и их приложений для студентов 2 курса. Первое заседание просеминара пройдет 14 марта с 16:20 до 17:55 в ауд. 504. Информацию о докладах можно будет найти в ближайшее время на [[Просеминар для 2-го курса|странице просеминара]].}}
{{announce News|26 февраля 2016 г.| На семинаре кафедры математической кибернетики состоится представление [[Media:Thesis_Novikova.pdf|диссертации]] Татьяны Анатольевной Новиковой (Казахстанский филиал МГУ в г. Астана).}}
{{announce News|20 января 2016 г.| Вывешены [[Media:Ok_fall2015.pdf|вопросы к экзамену]] по курсу [[Основы кибернетики (2-й поток)|«Основы кибернетики» (2-й поток)]].}}
{{announce News|12 января 2016 г.| Вниманию студентов группы 518/2! Консультация к экзамену по курсу «Элементы теории синтеза, надёжности и контроля дискретных управляющих систем» состоится 16.01.2016 в 11:00 в ауд. 506. На ней будут объявлены результаты контрольной и выданы проверенные работы.}}
{{announce News|29 декабря 2015 г.| Вывешен [[Media:Вопросы_ЭТДУС_418.pdf|список]] вопросов и типовых задач к экзамену по курсу «Элементы теории дискретных управляющих систем», который состоится 12.01.2016 в 9:00 в ауд. 505. Консультация к этому экзамену пройдёт 11.01.2016 в 14:00 в ауд. 503.}}
{{announce News|14 декабря 2015 г.| Вывешены [[Media:Курс_ЭТСНКДУС_518-2.pdf|вопросы, типовые задачи и литература]] к экзамену по курсу «Элементы теории синтеза, надёжности и контроля дискретных управляющих систем». Контрольная по вопросам и задачам разделов I, II состоится 19 декабря в 13:00 в ауд. 507, а консультация к ней пройдёт 18 декабря в 16:30 в ауд. 505. }}
{{announce News|13 декабря 2015 г.| Вывешены [[Media:Курс_ОК_318,_418_Осень.pdf| вопросы, типовые задачи и литература]] к экзамену по курсу «Основы кибернетики». См. дополнительную информацию на [[Основы кибернетики (318, 418 группы)|странице курса]]. }}
{{announce News|24 ноября 2015 г.| Поздравляем команду факультета ВМК с победой в соревновании [http://cad-contest.el.cycu.edu.tw/CAD-contest-at-ICCAD2015/ 2015 CAD Contest]! Подробности [[Команда факультета ВМК - победитель соревнования 2015 CAD Contest | здесь]]. }}
{{announce News|24 ноября 2015 г.| Вниманию участников вечера кафедр! Мероприятие состоится в аудитории '''П-7''' 2-го учебного корпуса. }}
{{announce News|19 ноября 2015 г.| 19 ноября 2015 года исполняется 80 лет со дня рождения доктора физико-математических наук профессора Гария Петровича Гаврилова (19.11.1935 – 05.12.1999), одного из первых двух штатных сотрудников кафедры математической кибернетики (в момент открытия она называлась кафедрой математической логики и теории автоматов). Гарий Петрович внес огромный вклад в организацию образования на факультете ВМК МГУ, в разработку новых курсов. Он получил много глубоких интересных результатов в математике, подготовил 6 кандидатов наук. Благодаря его переводам широкий круг людей в нашей стране познакомился с теорией графов. С краткой биографией и научными достижениями Гария Петровича Гаврилова можно ознакомиться [https://cs.msu.ru/persons/287 здесь]. }}
{{announce News|8 ноября 2015 г.| Традиционный '''вечер кафедр''' математической кибернетики и информационной безопасности (ранее - вечер кафедры математической кибернетики) состоится '''28 ноября''' (в субботу). Начало в '''16:00'''. Место проведения - 2-й учебный корпус, факультет ВМК. Аудитория будет объявлена позднее. По всем вопросам (в том числе выписыванию пропуска для прохода в корпус) можно обратиться сюда: [mailto:valdus@yandex.ru valdus@yandex.ru]. }}
{{announce News|5 ноября 2015 г.| Вниманию студентов! 10 ноября (16:00-20:00) представителем компании Imagination Technologies [http://panchul.com/about_ru/ Юрием Панчулом] совместно с кафедрой математической кибернетики будет проведен семинар, посвященный проекту [http://community.imgtec.com/university/ MIPSfpga]. На семинаре вас познакомят с основами работы с ПЛИС на примере образовательных плат компаний Altera и Xilinx. Подробности [[Media:Mipsfpga_announcement.pdf| здесь]]. }}
{{announce News|20 октября 2015 г.| Вниманию студентов 4-5 курсов! Спецсеминар [[Теория управляющих систем и математические модели СБИС]] 23 октября пройдет совместно со спецсеминаром [[Дискретная математика и математическая кибернетика]] в 16:20, ауд. 612. }}
{{announce News|17 октября 2015 г.| Вниманию студентов 318 группы! Выложено первое домашнее задание по [[Практикум (3 курс, осенний семестр 2015 года)| практикуму]]. }}
{{announce News|9 октября 2015 г.| Вниманию студентов спецсеминаров [[Некоторые вопросы теории управляющих систем]] и [[Теория управляющих систем и математические модели СБИС]] 9 октября пройдет совместное заседание спесеминаров в ауд. 704. }}
{{announce News|29 сентября 2015 г.| Вниманию студентов 418 группы! 30 сентября и 7 октября вместо лекций по курсу [[Элементы теории дискретных управляющих систем|"Элементы теории дискретных управляющих систем"]] пройдут занятия по "Практикуму на ЭВМ". }}
{{announce News|1 сентября 2015 г.| Первая и вторая лекции по курсу [[Математические модели и методы логического синтеза сверхбольших интегральных схем|Математические модели и методы логического синтеза СБИС]] для студентов группы 518(2) переносятся с 2 сентября и 9 сентября на 3-ю и 4-ую пару (с 12:50 до 16:10) 10 сентября в аудиторию 506.}}
{{announce News|31 августа 2015 г.| Вниманию студентов 518(2) группы! 2 сентября в 10-00 в ауд. 696 состоится собрание студентов магистерской программы [[:Категория:Магистерская программа Дискретные управляющие системы и их приложения|Дискретные управляющие системы и их приложения]]. Магистрантам указанной программы (особенно тем, кто не заканчивал кафедру математической кибернетики) рекомендуется прослушать первую часть курса [[Элементы теории дискретных управляющих систем]], который читается для студентов 418 группы (см. расписание и следующее объявление).}}
{{announce News|31 августа 2015 г.| Вниманию студентов 418 группы! Вместо занятий по практикуму 2 сентября и 9 сентября в 10-30 в ауд. 696 для студентов 418 группы состоятся лекции С.А.Ложкина по курсу [[Элементы теории дискретных управляющих систем]].}}
{{announce News|28 августа 2015 г.| Собрание коллектива факультета ВМК состоится в понедельник, 31 августа, в 12-30 в ауд. П_13.}}
{{announce News|26 мая 2015 г.| Защита курсовых работ студентов 318 группы состоится в среду, 27 мая, в ауд. 504. Начало в 11 ч. Информация об оформлении курсовых работ [[Media:kurs-318-2015.doc |здесь]]. Образец оформления титульного листа курсовой работы [[Media:titul-kurs-318-2015.doc | здесь]].}}
{{announce News|26 апреля 2015 г.| Выложены [[Media:OK_add_3.2_2015.pdf | дополнительные теоретические задачи]] к разделу "синтез и сложность управляющих систем" по курсам [[Основы кибернетики (3-й поток)]] , [[Основы кибернетики (318, 418 группы)]].}}
{{announce News|14 апреля 2015 г.| '''Обновление''' [[Media:diplom-518-2015.doc | информации для 518 группы]] об оформлении дипломной работы, сроках сдачи текста работы на кафедру и предзащитах, [[Media:titul-diplom-518-2015.doc | образец оформления титульного листа дипломной работы]].}}
{{announce News|14 апреля 2015 г.| '''Обновление''' [[Media:diplom-418-2015.doc | информации для 418 группы]] об оформлении выпускной квалификационной работы, сроках сдачи текста работы на кафедру и предзащитах, [[Media:titul-diplom-418-2015.doc | образец оформления титульного листа выпускной квалификационной работы]].}}
{{announce News|22 марта 2015 г.| Выложена [[Media:OK_add_2_2015.pdf | дополнительная задача]] к разделу "Эквивалентные преобразования управляющих систем" по курсам [[Основы кибернетики (3-й поток)]] , [[Основы кибернетики (318, 418 группы)]]. Задачи 1 и 3 к разделу "Минимизация ДНФ" больше не принимаются.}}
{{announce News|5 марта 2015 г.| Выложены [[Media:OK_add_1_2015.pdf | дополнительные задачи]] к разделу "Минимизация ДНФ" по курсам [[Основы кибернетики (3-й поток)]] , [[Основы кибернетики (318, 418 группы)]]}}
{{announce News|6 февраля 2015 г.| Доступно ''предварительное'' '''[[Расписание |расписание занятий]]''' на весенний семестр.}}
{{announce News|18 января 2015 г.| Консультация к экзамену по курсу [[Дискретная математика 1 (группа 141)]] для состоится 23 января, в пятницу, в ауд. 505. Консультация лектора - в 16 ч, консультация по решению задач - в 14 ч.}}
{{announce News|15 января 2015 г.| Консультация к экзамену по курсу [[Избранные вопросы дискретной математики]] для 318 группы состоится 20 января, во вторник, в 12-00 в аудитории 504. Информация о результатах коллоквиумов [[Media: ivdm-318-2015.doc|здесь]].}}
{{announce News|10 января 2015 г.| Консультация к экзамену по курсу "Сложность алгоритмов" для 418 группы пройдет 16 января в 16:00 в аудитории 505. Материалы для подготовки к экзамену можно найти на [[Сложность алгоритмов|странице курса]].}}
{{announce News|6 января 2015 г.| Консультация к экзамену по курсу "Избранные вопросы математической теории вычислений" для 518 группы пройдет 9 января в 16:00 в аудитории 504. Материалы для подготовки к экзамену можно найти на [[Модели вычислений|странице курса]].}}
{{announce News|5 января 2015 г.| Консультация к экзамену по курсу "Математические модели и методы синтеза СБИС" пройдет 9 января в 12:00 в аудитории 504. Материалы для подготовки к экзамену можно найти на [[Математические модели и методы синтеза СБИС|странице курса]].}}
{{announce News|25 ноября 2014 г.| Традиционный [[вечер кафедры]] математической кибернетики состоится '''6 декабря''' (в субботу) в ауд. '''П-7'''. Начало в '''16:00'''.}}
{{announce News|8 октября 2014 г.| Спецсеминар [[Некоторые вопросы теории управляющих систем]] начинает работу 10 октября. Спецсеминар будет проходить по пятницам в аудитории '''704''' в '''16:20'''.}}
{{announce News|30 сентября 2014 г.| Спецсеминар [[Теория управляющих систем и математические модели СБИС]] начинает работу 3 октября. Спецсеминар будет проходить по пятницам в аудитории '''612''' в '''16:20'''.}}
{{announce News|30 сентября 2014 г.| Совместный спецсеминар [[Дискретный анализ]] (рук. А.А. Сапоженко) и [[Сложность решения дискретных задач]] (рук. С.Н. Селезнева) начинает работу 3 октября. Спецсеминар будет проходить по пятницам в аудитории '''504''' с '''16:20''' до '''17:55'''.}}
{{announce News|29 сентября 2014 г.| Совместный спецсеминар [[Теоретические проблемы программирования]] (рук. Р.И. Подловченко, В.А. Захаров) и [[Математическая криптография]] (рук. М.И. Анохин, Н.П. Варновский) начинает работу 3 октября. Спецсеминар будет проходить по пятницам в аудитории '''508''' в '''16:20'''.}}
{{announce News|29 сентября 2014 г.| Вниманию слушателей спецкурса [[C++ 11/14 и современные аспекты построения компиляторов]]. Спецкурс будет проходить по четвергам в аудитории '''685''' в '''16:20'''.}}
{{announce News|22 сентября 2014 г.| Начинается чтение спецкурса Вычисления на машинах Минского. Лектор — проф. [[Марченков Сергей Серафимович]]. Первое занятие — 29 сентября в 10:30 аудитории 526-Б.}}
{{announce News|19 сентября 2014 г.| Начинается чтение спецкурса [[C++ 11/14 и современные аспекты построения компиляторов]]. Первое занятие — 25 сентября в аудитории 705.}}
{{announce News|11 июня 2014 г.| На страницах курсов [[Основы кибернетики (3-й поток)]] и [[Элементы теории дискретных управляющих систем]] (318 гр.) появилась информация о проведении экзаменов по этим курсам.}}
{{announce News|10 июня 2014 г.| [[Media:exam-vmb.doc|Вопросы к экзамену по курсу "Введение в математическую биологию"]] для студентов 418 группы.}}
{{announce News|06 июня 2014 г.| Для студентов 318 группы на странице курса [[Основы кибернетики (318, 418 группы)]], а также для студентов 320-328 групп на странице курса [[Основы кибернетики (3-й поток)]] появилась информация по поводу проведения консультаций.}}
{{announce News|03 июня 2014 г.| Для студентов 320-328 групп на странице курса [[Основы кибернетики (3-й поток)]] появилась информация по поводу проведения переписывания контрольных работ.}}
{{announce News|14 апреля 2014 г.| Для студентов 518 группы: [[Media: inf-518-2014.doc|информация о требованиях к дипломной работе]] и [[Media:title-diplom.doc|образец титульного листа дипломной работы]].}}
{{announce News|24 марта 2014 г.| Объявляется набор студентов и аспирантов в команду для решения [http://cad_contest.ee.ncu.edu.tw/CAD-Contest-at-ICCAD2014/problem_a/default.html одной из задач] соревнования [http://cad_contest.ee.ncu.edu.tw/CAD-Contest-at-ICCAD2014/ 2014 CAD Contest at ICCAD]. Записаться в команду и задать вопросы можно по адресу mikle.shupletsov@gmail.com. Краткое введение в проблематику задачи пройдет в рамках спецсеминара "Некоторые вопросы теории управляющих систем" 26 марта в 14-35 в ауд. 507. Кроме того, более подробную информацию по соревнованию можно будет получить 28 марта в 16-10 в ауд. П-13 (после лекции по курсу "Основы кибернетики").}}
{{announce News|24 марта 2014 г.| Выложена [[Media:OK_problems3.pdf | дополнительная задача]] к разделу "Синтез и сложность управляющих систем" по курсу [[Основы кибернетики (3-й поток)]].}}
{{announce News|18 февраля 2014 г.| Начинает работу спецсеминар [[Сложность решения дискретных задач]]. Первое заседание семинара состоится 21 февраля 2014 г. в 16-20 в ауд. 503.}}
{{announce News|17 февраля 2014 г.| Начинает работу спецсеминар [[Теория управляющих систем и математические модели СБИС]]. Первое заседание состоится 21 февраля в 16.20 в ауд. '''609'''.}}
{{announce News|17 февраля 2014 г.| Начинает работу спецсеминар [[Некоторые вопросы теории управляющих систем]]. Первое заседание состоится 19 февраля в 14.35 в ауд. '''507'''.}}
{{announce News|12 февраля 2014 г.| Начинается чтение спецкурса [[Архитектурные особенности современных вычислительных систем]]. Информация обновлена на странице курса.}}
{{announce News|10 февраля 2014 г.| Появилось объявление о докладе на спецсеминаре [[Дискретная математика и математическая кибернетика]] 14 февраля 2014 г.}}
{{announce News|15 января 2014 г.| Появилось объявление о докладе на спецсеминаре [[Дискретная математика и математическая кибернетика]] 7 февраля 2014 г.}}
{{announce News|1 января 2014 г.| С НОВЫМ 2014 ГОДОМ!}}
{{announce News|30 декабря 2013 г.| Для студентов 4-го курса появилось [[Media:kons-4-2013.docx| расписание консультаций]] по курсам "[[Основы кибернетики (2-й поток)]]" и "[[Математическая логика и логическое программирование]]" (для 3-го потока + 418-419 группы)}}
{{announce News|30 декабря 2013 г.| Для студентов 318, 418, 419, 518 групп появилось [[Media:kons-mk-2013.docx| расписание консультаций]] кафедральных курсов}}
{{announce News|24 декабря 2013 г.| Для студентов 418-419 групп появились [[Media:sa2013.doc|вопросы к экзамену]] и [[Media:konssa2013.docx|объявление о консультации]] по курсу "[[Сложность алгоритмов]]"}}
{{announce News|19 декабря 2013 г.| Для студентов 318 группы появилась информация к зачету на странице курса "[[Дополнительные главы дискретной математики (2-й поток III курса)|Дополнительные главы дискретной математики]]"}}
{{announce News|15 декабря 2013 г.| Для студентов 3-го курса 2-го потока появились [[Media:dgdm2013.pdf|вопросы к зачету]] по курсу "[[Дополнительные главы дискретной математики (2-й поток III курса)|Дополнительные главы дискретной математики]]" }}
{{announce News|13 декабря 2013 г.| Для студентов 518 группы появилась информация об [[Media:pract2013.pdf| отчете по производственной практике]] и об [[Media:dipl2013.pdf| отчете по дипломной работе]]}}
{{announce News|11 декабря 2013 г.| Традиционный ВЕЧЕР КАФЕДРЫ МАТЕМАТИЧЕСКОЙ КИБЕРНЕТИКИ факультета ВМК состоится в субботу 14 декабря в аудитории П7. Гостей ждем к 16 часам, официальное начало мероприятия -- в 16:30. Отметим, что в этом году фактически проводится совместный вечер двух кафедр -- математической кибернетики и информационной безопасности. Приходите -- будет интересно и весело!}}
{{announce News|3 октября 2013 г.| Начинает работу спецсеминар [[Некоторые вопросы теории управляющих систем]]. Первое заседание состоится 7 октября в 14.35 в ауд. '''506'''.}}
{{announce News|19 сентября 2013 г.| Начинает работу спецсеминар [[Теория управляющих систем и математические модели СБИС]]. Первое заседание состоится 20 сентября в 16.20 в ауд. '''612'''.}}
</noinclude>|}

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

2020-09-13T10:21:16Z

Emergency User:

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

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

'''Оценки пересдачи экзамена по "Дискретной математике" (от 11.09.2020 г.) появятся в воскресенье, 13 сентября, в 10 ч (по московскому времени)'''. В это же время станет возможно загрузить проверенные работы. Ссылки, по которым можно будет загрузить проверенные работы, будут разосланы старостам групп.

'''Пересдача экзамена по дискретной математике''' (11 сентября 2020 г.) будет проходить удаленно в той же форме, что и основной экзамен летом 2020 г. Схема экзамена описана ниже.

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

Работу нужно написать от руки на светлых листах контрастной ручкой. После выполнения работы ее нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png отправить на проверку (загрузить по определенной ссылке, ссылка будет разослана старостам групп). На сканирование или фотографирование работы и ее отправку отводится 15 мин. Если работа студента не получена через 2 ч 15 мин после начала экзамена, то считается, что студент работу не сдал.

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

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

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

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

===Часть А===
<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-й курс)

2020-09-13T07:02:10Z

Emergency User:

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

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

'''Оценки пересдачи экзамена по "Дискретной математике" (от 11.09.2020 г.) появятся в воскресенье, 13 сентября, в 10 ч (по московскому времени)'''. В это же время станет возможно загрузить проверенные работы. Ссылки, по которым можно будет загрузить проверенные работы, будут разосланы старостам групп.

Ссылка на проверенные работы: https://m.cs.msu.ru/s/SSR8tY6eZss3pxL

там же лежит файл с общими результатами называется "ДМ пересдача ..."

'''Пересдача экзамена по дискретной математике''' (11 сентября 2020 г.) будет проходить удаленно в той же форме, что и основной экзамен летом 2020 г. Схема экзамена описана ниже.

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

Работу нужно написать от руки на светлых листах контрастной ручкой. После выполнения работы ее нужно отсканировать или сфотографировать. Затем сканы или фотографии работы в формате pdf, jpg или png отправить на проверку (загрузить по определенной ссылке, ссылка будет разослана старостам групп). На сканирование или фотографирование работы и ее отправку отводится 15 мин. Если работа студента не получена через 2 ч 15 мин после начала экзамена, то считается, что студент работу не сдал.

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

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

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

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

===Часть А===
<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>

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

Файл:Dm2v3.pdf

2020-09-11T14:05:20Z

Emergency User: Emergency User загружена новая версия «Файл:Dm2v3.pdf»

Файл:Dm2v2.pdf

2020-09-11T14:05:09Z

Emergency User: Emergency User загружена новая версия «Файл:Dm2v2.pdf»

Файл:Dm2v1.pdf

2020-09-11T14:04:00Z

Emergency User: Emergency User загружена новая версия «Файл:Dm2v1.pdf»

Файл:Dm2v3.pdf

2020-09-11T13:40:20Z

Emergency User: Emergency User загружена новая версия «Файл:Dm2v3.pdf»

Файл:Dm2v3.pdf

2020-09-11T13:39:43Z

Emergency User: Emergency User загружена новая версия «Файл:Dm2v3.pdf»

Файл:Dm2v3.pdf

2020-09-11T13:16:46Z

Emergency User: Emergency User загружена новая версия «Файл:Dm2v3.pdf»