Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)

Курс для студентов 4 курса 2 потока, 2 ч лекций, 1 ч консультаций и 1 ч семинаров в неделю, отчетность — экзамен.

2024-2025 учебный год

Лекторы: Ложкин Сергей Андреевич, Савицкий Игорь Владимирович

Расписание с 08.11.24 по 20.12.24

ПТ 08.11.24 — лекция

ПН 11.11.24 — лекция

ПН 18.11.24 — лекция

ПТ 22.11.24 — консультация к контрольной работе 2 (машины Тьюринга и рекурсивные функции)

ПН 25.11.24 — контрольная работа 2 (машины Тьюринга и рекурсивные функции)

ПТ 29.11.24 — лекция

ПН 02.12.24 — лекция

ПН 09.12.24 — лекция

ПТ 13.12.24 — лекция (на этой лекции пройдёт семинар 8)

ПН 16.12.24 — консультация к контрольной работе 3 (синтез СФЭ)

ПТ 20.12.24 — контрольная работа 3 (синтез СФЭ)

Контрольные работы и экзамен

Контрольная работа 2

В понедельник 25.11.2024 планируется вторая контрольная работа по курсу ДГДМиК. Работа затрагивает часть курса, связанную с машинами Тьюринга, рекурсивными функциями и классами P, NP, и может требовать знания как лекционного, так и семинарского материала. Будет 6 заданий, в основном в виде задач.

Контрольная работа будет проходить в 12:15–13:50 в ауд. П-14 (по обычному расписанию лекции).

В пятницу 22.11.2024 планируется консультация к контрольной. Она пройдёт в 10:30–12:05 в ауд. П-14 (по обычному расписанию лекции/консультации).

Технические аспекты процедуры проведения контрольной:

1. Выключите звук на ваших электронных устройствах.

2. Оставьте все вещи (включая электронные устройства) в нижней части аудитории: у входа, либо у окна; на полу, скамейке или на столе.

3. Возьмите с собой только ручки и другие письменные принадлежности.

4. Получите лист бумаги и вариант у организатора.

5. На варианте указан номер вашего ряда (1–10). На рядах висят таблички с их номерами.

6. Проходите к вашему ряду и садитесь на самое дальнее от входа незанятое место (без пропусков).

7. Подпишите вариант: фамилия, имя, отчество и номер группы. На всех остальных листах подписывайте фамилию и номер группы.

8. Студентам Казахстанского филиала, которые посещают семинары не со своей группой, следует также указать группу, с которой они ходят на семинары, или фамилию преподавателя. 9. Можете сразу начинать работу.

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

11. Во время контрольной работы запрещается переговариваться или использовать любые материалы и электронные устройства. Наличие электронного устройства или материалов при себе приравнивается к их использованию.

Контрольная работа 1

В пятницу 25.10.2024 планируется первая контрольная работа по курсу ДГДМиК. Работа затрагивает часть курса, связанную с конечными автоматами (распознавателями и преобразователями) и может требовать знания как лекционного, так и семинарского материала. Будет 6 заданий, в основном в виде задач.

Контрольная работа будет проходить в 10:30–12:05 в ауд. П-14 (по обычному расписанию консультации). После контрольной работы маленький перерыв, поэтому работы будут собираться без задержек.

В понедельник 21.10.2024 планируется консультация к контрольной. Она пройдёт в 12:15–13:50 в ауд. П-14 (по обычному расписанию лекции).

Основные материалы

Программа курса 2024-2025 уч. года

Презентации к лекциям 1–12 (первая и вторая части курса; в файле присутствует электронное оглавление)

Программа семинарских занятий

Литература

1. Видео-лекции, прочитанные профессором С.С. Марченковым в 2020 г. (1-2 часть курса).
2. Видеозаписи и презентации лекций, прочитанных профессором С.А. Ложкиным в 2020 г. (3 часть курса).
3. Савицкий И.В. Презентации к лекциям по 1 и 2 частям курса (2023 г.)
4. Марченков С.С. Избранные главы дискретной математики М.: МАКС Пресс, 2015.
5. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
6. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002.
7. Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Изд-во МГУ, 2001.
8. Ложкин С.А. Дополнительные главы кибернетики. МГУ, 2019.
9. Ложкин С. А. Дополнительные главы кибернетики и теории управляющих систем. МГУ, 2008.
10. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
11. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу "Основы кибернетики", 2-е изд. М.: МАКС Пресс, 2011.

2023-2024 учебный год

Лекторы: Ложкин Сергей Андреевич, Савицкий Игорь Владимирович

Экзамен

Вопросы к экзамену и порядок проведения

Организационные вопросы проведения экзамена

Экзамен проводится 24 января 2024 года.

Обратите внимание! Личное присутствие студента обязательно даже в случае выставление оценки автоматом. Отсутствие студента будет приравнено к неявке, а на пересдачах предварительные оценки уже не будут учитываться.

Для экзамена зарезервированы аудитории 503–507. В аудиториях 503 и 504 будет приниматься экзамен, в аудитории 505 проставляются автоматы, а аудитории 506–507 будут использоваться для ожидания. Аудитории 524 и 527 использоваться не будут.

Студенты из групп 412, 413, 414, 415, 416 сдают в аудитории 503.

Студенты из групп 411, 417, 418, 419-1, 419-2 сдают в аудитории 504.

Приходить следует к следующему времени (независимо от наличия автомата):

Группы 412, 413, 418 и 419-1 — к 9:00.

Группы 411, 414, 415, 416, 417 и 419-2 — к 10:30.

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

Студентам, которые будут сдавать экзамен в какой-либо форме, следует централизованно (внутри группы) собрать зачётки и отнести в аудиторию экзамена своей группы (503 или 504). После этого преподаватели будут вызывать студентов по одному.

Студентам не со второго потока следует присоединиться к группе, с которой они посещали семинары.

Расписание консультаций и других мероприятий на 22 января 2024 года.

09:50, ауд. П-14. Написание пропущенной по уважительной причине контрольной.

• Каждый студент может написать не более одной пропущенной контрольной.
• Для допуска на написание пропущенной контрольной необходимо:

1. Заранее (до 18 января) записаться (сообщить И.В. Савицкому в Discord) с указанием номера контрольной (1, 2 или 3), которую студент будет писать.
2. Предъявить документ, подтверждающий уважительную причину отсутствия на контрольной с этим номером (справка по болезни).

11.30, ауд. П-14. Группы 413, 414, 416, 417: консультация по семинарам (Т.В. Андреева).

11.30, ауд. 505. Группы 411, 419/2: консультация по семинарам (А.В. Бухман).

11:30, ауд. 506. Группы 412,419/1: консультация по семинарам (Б.В. Чокаев).

11.30, ауд. 503. Группы 415, 418: консультация по семинарам (И.В. Савицкий).

13:00, ауд. П-14. Консультация по лекциям (С.А. Ложкин, И.В. Савицкий).

На семинарских консультациях студенты с других потоков присоединяются к группам, с которыми они посещали семинары.

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

Программа курса 2023-2024 уч. года

Лекции

Презентации к лекциям 1–12 (в файле присутствует электронное оглавление)

Семинары

Программа семинарских занятий 2023-2024 уч. года

Литература

1. Видео-лекции, прочитанные профессором С.С. Марченковым в 2020 г. (1-2 часть курса).
2. Видеозаписи и презентации лекций, прочитанных профессором С.А. Ложкиным в 2020 г. (3 часть курса).
3. Савицкий И.В. Презентации к лекциям по 1 и 2 частям курса (2023 г.)
4. Марченков С.С. Избранные главы дискретной математики М.: МАКС Пресс, 2015.
5. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
6. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002.
7. Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Изд-во МГУ, 2001.
8. Ложкин С.А. Дополнительные главы кибернетики. МГУ, 2019.
9. Ложкин С. А. Дополнительные главы кибернетики и теории управляющих систем. МГУ, 2008.
10. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
11. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу "Основы кибернетики", 2-е изд. М.: МАКС Пресс, 2011.

2022-2023 учебный год

Полная программа курса: Программа курса 2022-2023 уч. года

Экзамен

Вопросы к экзамену и порядок проведения

Организационные вопросы проведения экзамена

Экзамен проводится 24 января 2023 года.

Для экзамена зарезервированы аудитории 503–508. В аудиториях 503 и 504 будет приниматься экзамен, в аудитории 505 проставляются автоматы, а аудитории 506–508 будут использоваться для ожидания. Аудитории 524 и 527 использоваться не будут.

Студенты из групп 411, 412, 413, 414, 415, 416 сдают в аудитории 503.

Студенты из групп 417, 418, 419-1, 419-2 сдают в аудитории 504.

Приходить следует к следующему времени (независимо от наличия автомата):

Группы 413, 414, 416, 418 и 419-2 — к 9:00.

Группы 411, 412, 415, 417 и 419-1 — к 10:30.

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

Студентам, которые будут сдавать экзамен в какой-либо форме, следует централизованно (внутри группы) собрать зачётки и отнести в аудиторию экзамена своей группы (503 или 504). После этого преподаватели будут вызывать студентов по одному.

Студентам не со второго потока следует присоединиться к группе, с которой они посещали семинары.

Ведомости Казахстанского филиала (включая не второй поток) и иностранного отдела уже у нас.

Расписание консультаций и других мероприятий на 23 января 2023 года.

10:20, ауд. П-3. Проведение дополнительной контрольной работы для студентов, которые пропустили 3-ю контрольную работу по уважительной причине (имеющие справку о болезни).

11:15, ауд. П-3. Группы 412, 413, 417: показ работ по 3-й контрольной для студентов групп А.С. Нагорного.

10:20, ауд. 612. Группа 414: консультация по семинарам (Б.Р. Данилов).

12:00, ауд. П-3. Консультация по лекциям (С.Н. Селезнёва, И.В. Савицкий, С.А. Ложкин).

14:00, ауд. 612. Группы 411, 419-2, 412: консультация по семинарам (А.В. Бухман)

14:00, ауд. 506. Группы 415, 413: консультация по семинарам (Б.В. Чокаев)

14:00, ауд. П-3. Группы 416, 418, 419-1, 417: консультация по семинарам (И.В. Савицкий)

Студенты с других потоков присоединяются к группам, с которыми они посещали семинары.

Части 1-2. Дополнительные главы дискретной математики

Лекторы: Селезнева Светлана Николаевна, Савицкий Игорь Владимирович

• Лекции

Презентации к лекциям 1–9 (в файле присутствует электронное оглавление)

• Семинары

Программа семинарских занятий 2022-2023 уч. года

• Литература

1. Видео-лекции, прочитанные профессором С.С. Марченковым в 2020 г. (1-2 часть курса).
2. Марченков С.С. Избранные главы дискретной математики М.: МАКС Пресс, 2015.
3. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002.
4. Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Изд-во МГУ, 2001.
5. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
7. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу "Основы кибернетики", 2-е изд. М.: МАКС Пресс, 2011.

• Проверочные работы

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

Часть 3. Дополнительные главы кибернетики

• Материалы

1. Презентация к лекциям 2020-2021 учебного года.
2. С.А.Ложкин Дополнительные главы кибернетики и теории управляющих систем. МГУ, 2008.

Лектор: Ложкин Сергей Андреевич

2021-2022 учебный год

Подробное описание курса, программу курса, программу семинарских занятий, список литературы можно найти в: Программа курса 2021-2022 уч. года

Части 1-2. Дополнительные главы дискретной математики

Ведущие: Селезнева Светлана Николаевна, Савицкий Игорь Владимирович

• Лекции

Записи лекций 1–10 (автоматы, машины Тьюринга и рекурсивные функции)

Презентации к лекциям 1–10 (в файле присутствует электронное оглавление)

Ссылка на слайды и записи лекций 11-14 (сложностные классы), лектор - Селезнева С.Н.

• Семинары

Программа семинарских занятий 2021-2022 уч. года

Задачи к семинарам по конечным автоматам-распознавателям

Расписание проверочных работ 2021-2022 уч. года

• Литература

1. Видео-лекции, прочитанные профессором С.С. Марченковым в 2020 г. (1-2 часть курса).
2. Марченков С.С. Избранные главы дискретной математики М.: МАКС Пресс, 2015.
3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
5. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу "Основы кибернетики", 2-е изд. М.: МАКС Пресс, 2011.

• Схема оценивания 1-2 частей

Материал 1-2 частей разделен на 4 раздела. После изучения каждого из разделов проводится проверочная работа (на семинарском занятии). По итогам проверочных работ выводится предварительная оценка.

Часть 3. Дополнительные главы кибернетики

Ведущий: Ложкин Сергей Андреевич

Планы семинарских занятий 3 части курса и методические указания к ним на осенний семестр 2021–2022 уч. года.

График проведения лекций

• Лекция 1 (22.XI): вопрос 26 – запись лекции 1.
• Лекция 2 (23.XI): вопрос 27 – запись лекции 2.
• Лекция 3 (29.XI): а) вопросы 28 и 29 – запись лекции 3 (50 минут); б) консультация.
• Лекция 4 (30.XI): а) вопросы 30 и 31 – запись лекции 4.
• Лекция 5 (6.XII): вопрос 32 – запись лекции 5 (первые 40 минут); б) консультация.
• Лекция 6 (7.XII): а) вопрос 33 – запись лекции 5 (последние 37 минут); б) вопрос 34, формулировка теоремы Храпченко из вопроса 36, а также следствия из неё и комментарии к ней – запись лекции 6.
• Лекция 7 (13.XII): вопрос 35 и доказательство теоремы Храпченко из вопроса 36 – запись лекции 7.
• Лекция 8 (14.XII): а) вопрос 36 – запись лекции 8 (47 минут); б) консультация.

График проведения семинаров

• Семинар 1 (3.XII и 4.XII): семинар 12.
• Семинар 2 (10.XII и 11.XII): семинар 13.
• Семинар 3 (17.XII и 18.XII): семинар 14.

Контрольная работа

Контрольная работа по курсу запланирована на 17-18 декабря и будет проходить на втором часе семинара №3 третьего раздела курса.

Материалы

Видеозаписи лекций 2020-2021 уч. года по 3 разделу курса и презентация к ним

Ложкин С.А. Лекции по дополнительным главам кибернетики 2018-2019 (методические материалы)

Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики», 2-е изд. М.: МАКС Пресс, 2011.

Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики», М.: МАКС Пресс, 2002.