Дискретная математика (КФ) — различия между версиями
Материал из Кафедра математической кибернетики
(→Экзамен) |
|||
| (не показаны 22 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| + | __NOTOC__ | ||
| + | <div style="max-width:940px"> | ||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] | ||
| − | Курс для студентов | + | Курс для студентов 2-го курса Казахстанского филиала МГУ, читается в 1-м семестре, 2 ч лекций и 2 ч семинаров в неделю, отчетность — экзамен. |
| + | |||
| + | ==2025-2026 учебный год== | ||
| + | |||
| + | Лектор - [[Савицкий Игорь Владимирович]] | ||
| + | |||
| + | ===Экзамен=== | ||
| + | |||
| + | [[Media:Дискретная математика_(2_часа)_-_программа.pdf|'''Программа курса''']] | ||
| + | |||
| + | ===Основные материалы=== | ||
| + | |||
| + | [[Media:ДМ_2h_Презентация.pdf|'''Презентации к лекциям''']] (в файле присутствует электронное оглавление) | ||
| + | |||
| + | ===Литература=== | ||
| + | |||
| + | #[https://www.youtube.com/playlist?list=PLcsjsqLLSfNAY-pm5c4XZQhSl1U_20itT Видео-лекции], прочитанные профессором [[Алексеев Валерий Борисович | В.Б. Алексеевым]] в 2020 г. (расширенный вариант курса на 3 ч в неделю). | ||
| + | #[[Media:ДМ_2h_Презентация.pdf|Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.]] | ||
| + | #[[Media:Алексеев_-_2004_-_Лекции_по_дискретной_математике.pdf|Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004.]] | ||
| + | #Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с. | ||
| + | #Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с. | ||
| + | |||
| + | |||
| + | <!--- | ||
| + | ==2021-2022 учебный год== | ||
Лектор - [[Селезнева Светлана Николаевна]] | Лектор - [[Селезнева Светлана Николаевна]] | ||
| − | ==Экзамен== | + | ===Экзамен=== |
'''Экзамен состоится 14 июня очно'''. | '''Экзамен состоится 14 июня очно'''. | ||
| Строка 16: | Строка 42: | ||
Экзамен проводится очно в аудитории. Работу следует написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются принимающему экзамен. | Экзамен проводится очно в аудитории. Работу следует написать разборчиво от руки на светлых листах контрастной ручкой. Каждый лист работы нужно подписать: фамилию, инициалы и номер группы. После окончания экзамена выполненные работы сдаются принимающему экзамен. | ||
| − | |||
| − | |||
'''Вопросы к экзамену''' | '''Вопросы к экзамену''' | ||
| Строка 30: | Строка 54: | ||
*Базис в P_2. Теореме о числе функций в базисе P_2. | *Базис в P_2. Теореме о числе функций в базисе P_2. | ||
*Предполные классы. Теорема о предполных классах в P_2. | *Предполные классы. Теорема о предполных классах в P_2. | ||
| − | * | + | *Графы. Пути и цепи. Циклы и связность. Леммы об удалении и добавлении ребер в связных графах. Теорема о числе вершин, числе ребер и числе компонент связности в графе. |
*Деревья. Теорема о равносильных определениях дерева. | *Деревья. Теорема о равносильных определениях дерева. | ||
*Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами. | *Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами. | ||
| Строка 48: | Строка 72: | ||
*Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов. | *Отличимость состояний конечного автомата. Теорема Мура. Упрощение автоматов. | ||
| − | + | '''Литература''' | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | ''' | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
<ol> | <ol> | ||
<li> Слайды к лекциям. | <li> Слайды к лекциям. | ||
| Строка 102: | Строка 82: | ||
</ol> | </ol> | ||
| − | + | '''Задачи к экзамену''' | |
| − | + | ||
| − | + | ||
| − | + | *Найти существенные и фиктивные переменные заданной функции алгебры логики. | |
| + | *Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики. | ||
| + | *Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве. | ||
| + | *Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной). | ||
| + | *Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы. | ||
| + | *Найти число неизоморфных графов с заданными свойствами и изобразить эти графы. | ||
| + | *Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду. | ||
| + | *Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3. | ||
| + | *Проверить, является ли заданный граф планарным. | ||
| + | *Проверить, найдется ли планарный граф с заданными свойствами. | ||
| + | *Найти хроматическое число или хроматический индекс заданного графа. | ||
| + | *Проверить разделимость заданного алфавитного кода (по алгоритму). | ||
| + | *Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов. | ||
| + | *Найти оптимальный алфавитный двоичный код по заданному набору частот. | ||
| + | *Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код. | ||
| + | *Кодировать или исправить ошибку и декодировать сообщение в коде Хэмминга. | ||
| + | *Найти диаграмму Мура автоматной функции, заданной описанием. | ||
| + | *Найти диаграмму Мура, каноническую таблицу или канонические уравнения автоматной функции, заданной одним из перечисленных способов. | ||
| + | *Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции. | ||
| + | ---> | ||
Текущая версия на 10:19, 27 ноября 2025
Курс для студентов 2-го курса Казахстанского филиала МГУ, читается в 1-м семестре, 2 ч лекций и 2 ч семинаров в неделю, отчетность — экзамен.
2025-2026 учебный год
Лектор - Савицкий Игорь Владимирович
Экзамен
Основные материалы
Презентации к лекциям (в файле присутствует электронное оглавление)
Литература
- Видео-лекции, прочитанные профессором В.Б. Алексеевым в 2020 г. (расширенный вариант курса на 3 ч в неделю).
- Савицкий И.В. Презентации к лекциям по дискретной математике для 2 часов в неделю. 2023.
- Алексеев В.Б. Лекции по дискретной математике. М.: ВМК МГУ, 2004.
- Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. 416 с.
