Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Дискретная математика
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Математические и компьютерные методы решения задач естествознания
Математические методы обработки информации и принятия решений
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к базовой части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по математическому анализу, линейной алгебре и алгоритмам и алгоритмическим языкам в объеме, соответствующем программе первого семестра обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики 
•	ОПК-2.Б Способность применять и модифицировать математические модели, а также интерпретировать полученные математические результаты при решении задач в области профессиональной деятельности 
•	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	применения, основные свойства и способы представления функций алгебры логики; 
2.	основы теории полноты, критерии полноты, основные подходы и методы распознавания полноты систем функций алгебры логики;
3.	применения и основные свойства графов, свойства деревьев и остовных деревьев в графах, критерии планарности и  свойства планарных графов, свойства раскрасок графов;
4.	основы теории сложности задач, примеры полиномиальных и труднорешаемых задач;
5.	применение и основные свойства схем из функциональных элементов, оценки сложности схемных сумматора, вычитателя и умножителя;
6.	применения, основные свойства и способы построения взаимно-однозначных и оптимальных кодов, а также кодов, исправляющих ошибки; 
7.	применения и основные свойства конечных автоматов-преобразователей.

Уметь: 
1.	обосновывать тождества алгебры логики, представлять функции алгебры логики формулами, дизъюнктивными и конъюнктивными нормальными формами, полиномами Жегалкина, схемами из функциональных элементов;
2.	выяснять полноту систем функций алгебры логики;
3.	проверять наличие у графа заданных свойств и оценивать число неизоморфных графов с заданными свойствами;
4.	находить остовное дерево или кратчайшее остовное дерево в связном графе;
5.	выяснять планарность графа или проверять возможность существования планарного графа с заданными свойствами;
6.	находить или оценивать хроматическое число или хроматический индекс графа;
7.	выяснять взаимную однозначность алфавитного кода, находить оптимальный код для заданного распределения частот;
8.	кодировать и декодировать сообщения в коде, исправляющем ошибки (в частности, одну ошибку);
9.	представлять отображение в виде конечного автомата-преобразователя (если это возможно);
10.	преобразовывать разные представления конечного автомата-преобразователя друг в друга, упрощать представления конечного автомата-преобразователя.

Владеть:  
1.	навыками понимания и применения подходов и методов современной дискретной математики при решении задач в профессиональной деятельности.

4. Формат обучения: лекции проводятся с применением слайдов, семинарские занятия проводятся с использованием меловой доски.

5. Объем дисциплины (модуля) составляет 3 з.е., в том числе 90 академических часа, отведенных на контактную работу обучающихся с преподавателем, 54 академических часа на самостоятельную работу обучающихся. 

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

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Алгебра логики. Функции алгебры логики. Тождества в алгебре логики. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Полиномы Жегалкина. Схемы из функциональных элементов (СФЭ). Полные системы, примеры полных систем. Замкнутые классы. Классы функций, сохраняющих константу, линейных, самодвойственных и монотонных функций, их замкнутость.  Теорема Поста о полноте в P2. Базис P2, теорема о наибольшем числе функций в базисе P2. Предполные классы. Теорема о предполных классах в P2. Сведения об описании Постом всех замкнутых классов в P2. Многозначные логики. Представление функций k-значных логик в 1-й и 2-й формах и полиномами по модулю k. 	30	12	14	26	4	
2.	Труднорешаемые задачи. Задачи распознавания. Класс P полиномиально решаемых задач распознавания. Класс NP полиномиально проверяемых задач распознавания. NP-трудные и NP-полные задачи. Теорема об NP-полноте задачи выполнимости КНФ (только формулировка). Теорема об NP-полноте задачи выполнимости 3-КНФ. Теорема о полиномиальности задачи выполнимости 2-КНФ.	5	4	0	4	1	
3.	Текущий контроль успеваемости: проверочная работа № 1 по теме «Алгебра логики».	2	0	1	1	1	
4.	Графы.  Основные определения и простейшие свойства графов. Связность, двусвязность и k-связность графов. Деревья, свойства деревьев. Остовные деревья, кратчайшие остовные деревья в связных графах. Планарность графов. Теорема Эйлера для планарных графов. Непланарность графов K5 и K3,3. Критерий Понтрягина-Куратовского планарности графа. Раскраски графов, хроматическое число и хроматический индекс графа. Теорема об оценке хроматического числа планарного графа.	21	12	6	18	3	
5.	Коды. Алфавитные коды, однозначность алфавитного кода. Алгоритм проверки однозначности алфавитного кода. Теорема Маркова. Неравенство Макмиллана. Теорема о существовании алфавитного кода с заданными длинами кодовых слов. Оптимальные коды (коды с минимальной избыточностью), свойства оптимальных кодов. Алгоритм построения оптимального кода для заданного распределения частот (метод Хаффмана) и его обоснование. Коды, обнаруживающие и исправляющие ошибки замещения. Коды, исправляющие одну ошибку, код Хэмминга. Линейные коды.	21	12	6	18	3	
6.	Текущий контроль успеваемости: проверочная работа № 2 по темам «Графы. Коды». 	4	0	2	2	2	
7.	Конечные автоматы.  Конечный автомат-преобразователь, канонические уравнения, каноническая таблица и диаграмма Мура конечного автомата-преобразователя. Автоматные функции. Функция единичной задержки, ее автоматность. Схемы из функциональных элементов с элементами задержки (СФЭЗ), автоматность осуществляемых ими отображений. Представление конечных автоматов-преобразователей СФЭЗ. Эксперименты с автоматами. Теорема Мура о длине эксперимента, обнаруживающего неэквивалентность состояний конечного автомата-распознавателя. Упрощение автоматов.	18	10	6	16	2	
8.	Схемы из функциональных элементов. Схемные n-разрядные сумматор и вычитатель, их сложность. Схемный n-разрядный умножитель. Теорема Карацубы о сложности n-разрядного умножителя.	5	4	0	4	1	
9.	Текущий контроль успеваемости: проверочная работа № 3 по теме «Конечные автоматы».	2	0	1	1	1	
Промежуточная аттестация: устный экзамен	36	0	0	0	36	
Итого	144	54	36	90	54	

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

Занятие 1. Функции алгебры логики. Формулы. Существенность переменных. [4] гл. 1 1.17(1, 2), 1.19(1, 2), 1.20(4-6), 1.28(1, 2), 1.31(1, 2), 1.33(1, 2), 1.34(5),  1.35. На дом: [4] гл. 1 1.17(3, 4), 1.19(3, 4), 1.20(7-9), 1.28(3, 4), 1.31(3), 1.33(3, 4), 1.34(6).

Занятие 2. ДНФ, КНФ, полиномы Жегалкина и СФЭ. [4] Гл. 1 2.3(1, 3, 5), 2.4(3, 5), 2.18(1), 2.22(5), 2.23(3, 5, 7), 2.28, 2.29, гл. 10 1.1(1, 3, 5). На дом: [4] Гл. 1 2.3(4, 8), 2.4(4, 6), 2.18(7), 2.23(4, 6, 8), 2.25, 2.27(1, 2), гл. 10 1.1(2, 4, 6).

Занятия 3-4. Замкнутые классы. Классы T0, T1, L, S, M. [4] Гл. 2 1.9(1, 2, 5, 6), 4.1(1), 4.2(1), 3.2(3, 4), 3.3(3, 4), 3.7, 2.2(3, 5, 7), 2.3(5), 2.7, 2.8(1), 5.1(3, 4), 5.4(5), 5.5(4). На дом: [4] Гл. 2 1.9(3, 4, 7, 8), 4.1(2), 4.2(3), 3.2(5, 6), 3.3(5, 6), 3.6, 2.2(4, 6, 8), 2.3(6), 2.8(2), 5.1(5, 6), 5.4(6), 5.5(5).

Занятия 5-6. Подсчет числа функций. Полнота. Базисы. [4] Гл. 2 5.21(1-3), 4.3(1-4, 7), 6.1(2, 4), 6.2(1, 3), 6.4(1, 2), 6.5(1), 6.3(1, 2), 6.11, 6.13, 6.16, 6.10(1, 4). На дом: [4] Гл. 2 5.21(4, 5), 4.3(8-11), 6.1(1, 3), 6.2(2, 4), 6.4(3), 6.5(2), 6.3(3, 4), 6.12, 6.17, 6.10(2).

Занятие 7. Многозначные функции. [4] гл. 3 1.11(2, 5, 8), 2.7(1, 3), 2.12(1, 3). На дом: [4] гл. 3 1.11(4, 7, 10), 2.7(2, 4), 2.12(2, 5). 

Проверочная работа № 1 (1 ч).

Занятия 8-9. Графы. Деревья. [4] гл 6 1.34(р. 6.2, 6.3),1.3, 1.21(1), 1.29(1, 2), 1.10, 1.12, 1.13, 1.26, 1.27, 1.54, 1.60, 3.1(а, в), 3.2(1, 3), 3.3, 3.10(1). На дом:  [4] гл 6 1.34(р. 6.4, 6.5),1.4, 1.21(2), 1.29(3, 4), 1.18, 1.22, 3.1(б, г), 3.2(2, 4), 3.10(2).

Занятие 10. Планарность. Раскраски. [4] гл. 6 2.1(р. 6.5), 2.2, 2.3, 2.8, 2.10, 2.13, 2.17(1), 2.18(р. 6.2, 6.6в), 2.19(1, 3). На дом:  [4] гл. 6 2.1(р. 6.6), 2.4, 2.9, 2.17(2), 2.18(р. 6.5, 6.6а,б), 2.19(2).

Занятия 11-12. Алфавитные коды. Оптимальные коды. [4] гл 7 1.2(1-3), 1.7(1, 3), 1.6(1-3), 1.8, 2.1(2-4), 2.10(1, 4, 5). На дом: [4] гл 7 1.2(4-6), 1.7(4, 5), 1.6(4-6), 2.1(1, 5), 2.10(2, 3, 6), 2.14.

Занятие 13. Коды, исправляющие ошибки. Линейные коды. [4] гл. 7 3.18(1, 2), 3.19(1, 2), 3.20(1, 2), 3.21(1, 3, 5), 3.22(1, 5, 8),4.7(1в, г). На дом: [4] гл. 7 3.21(2, 4, 6), 3.22(2, 6, 9),3.24(1, 2), 4.7(1б, д). 

Проверочная работа № 2 (2 ч).

Занятия 14-15. Конечные автоматы.  [4] гл. 4 2.1(1, 4, 12, 15, 24, 27), 2.5(1, 2), 2.13(1, 7), 2.14(1, 3), 2.2(3, 4). На дом: [4] гл. 4 2.1(3, 5, 14, 16, 25, 28), 2.5(3), 2.13(2, 8), 2.14(2, 4), 2.2(5, 6).

Занятие 16. Повторение (по задачам всего семестра).

Проверочная работа № 3 (1 ч).

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Проверочная работа № 1

1.	Построить совершенную КНФ, сокращенную ДНФ и полином Жегалкина функции алгебры логики f(x, y, z) = (x \to y) \sim z. 
2.	Найти число функций алгебры логики, зависящих от переменных x1, …, xn, в множестве A = (T_0 \cup S) \cap L. 
3.	Выяснить, принадлежит ли функция алгебры логики f(x, y, z) = \bar x \bar y \bar z замыканию системы A = {\bar x, x \oplus y \oplus z, x(y \sim z) \oplus yz}. 
4.	Выяснить, можно ли найти такую функцию f \in P2, что система B = {xy \lor xz \lor yz, f} является базисом P2. Ответ обосновать. 
5.	Выяснить, представима ли полиномом по модулю 4 функция f(x) = 3 j0(x) + j_2(x) \in P4.  
Проверочная работа № 2
1.	Выяснить, сколько найдется неизоморфных непланарных графов (без петель и кратных ребер) с 6 вершинами и 13 ребрами. Изобразить все эти графы. 
2.	Найти все наборы вида (0,0,0,0,-,-,-,-,-,-) (вместо прочерка может быть либо 0, либо 1), которые являются кодами упорядоченных корневых деревьев с 5 ребрами. Изобразить все эти деревья. 
3.	В графе без циклов (без петель и кратных ребер) две компоненты связности, 144 вершины степени 4, остальные вершины – степени 2 или 1. Найти число вершин степени 1 в этом графе. 
4.	В связном графе G = (V, E) (без петель и кратных ребер) 116 вершин и 116 ребер. Какие значения может принимать хроматическое число  графа G? Ответ обосновать.
5.	Выяснить, какое наименьшее число ребер нужно удалить из полного графа K7, чтобы получить планарный граф. Ответ обосновать. Изобразить этот полученный планарный граф. 
6.	Проверить, является ли однозначным алфавитный код С = {ab, cab, bbc, bcc, abbc} в кодирующем алфавите B = {a, b, c}. При отрицательном ответе указать слово в алфавите B, допускающее не менее двух декодирований. 
7.	Выяснить, существует ли однозначный двоичный алфавитный код с длинами кодовых слов 1, 2, 4, 4, 4, 5? При положительном ответе построить префиксный двоичный код с такими длинами кодовых слов.
8.	Построить оптимальный двоичный алфавитный код для распределения частот P = (0,5; 0,11; 0,09; 0,08; 0,08; 0,08; 0,06). 
9.	Выяснить, сколько ошибок замещения может обнаружить и может исправить код с характеристической функцией f(x1, …, xn) = x1 \oplus … \oplus xn. Ответ обосновать.
10.	Принадлежит ли слово 1010110000 коду Хэмминга длины 10? Ответ обосновать.

Проверочная работа № 3
1.	Построить диаграмму Мура автоматной функции f, преобразующей бесконечные двоичные последовательности x(1)x(2)… x(t)… в бесконечные двоичные последовательности y(1)y(2)… y(t)… по правилу y(t) = 1, если t – четно и в конечной последовательности x(1)x(2)… x(t) встретились хотя бы две единицы подряд, и y(t) = x(t) иначе.
2.	Построить диаграмму Мура автоматной функции, заданной каноническими уравнениями: y(t) = q1(t-1) \oplus q2(t-1), q1(t) = q2(t-1), q2(t) = x(t), q1(0) = 0, q2(0) = 1. Указать слово, которое отличает состояния 01 и 10, или обосновать, что эти состояния неотличимы. 
3.	В базисе из конъюнкции, дизъюнкции, отрицания и задержки построить СФЭ с задержками для автоматной функции f, преобразующей бесконечные двоичные последовательности x(1)x(2)… x(t)… в бесконечные двоичные последовательности y(1)y(2)… y(t)… по правилу y(1) = 1, y(t) = x(t) \lor x(t-1) при t \ge 2. 
4.	Для автоматной функции из предыдущей задачи построить диаграмму Мура, в которой отсутствуют пары неотличимых состояний. Обосновать, что построенная диаграмма Мура обладает этим свойством. 
5.	Построить канонические уравнения для автоматной функции, заданной СФЭ с задержками (предложена СФЭЗ).
7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

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

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

Часть А – ответ без подготовки по любым бумажным материалам (конспектам, книгам, распечаткам лекций и т.д.); проверяется понимание доказательств;  определения и теоремы формулируются без конспектов. Электронными средствами (компьютерами, телефонами и т.д.) на экзамене пользоваться не разрешается.

1.	Алгоритм построения вектора коэффициентов полинома Жегалкина функции алгебры логики (с обоснованием). 
2.	Двойственность. Класс самодвойственных функций, его замкнутость. 
3.	Лемма о нелинейной функции. 
4.	Теорема Поста о полноте системы функций алгебры логики. 
5.	Теорема о предполных классах. 
6.	Теоремы о представлении k-значных функций 2-й формой и полиномами. 
7.	Деревья. Теорема о равносильных определенияих дерева. Свойства деревьев. 
8.	Точки сочленения и мосты в графе. Двусвязность и k-связность графов.  Теорема о равносильных определениях двусвязных графов.  
9.	Дерево блоков и точек сочленения связного графа.  
10.	Алгоритм построения кратчайшего остовного дерева (с обоснованием). 
11.	Теорема о раскраске планарных графов в 5 цветов. 
12.	Алгоритм распознавания взаимной однозначности (разделимости) алфавитного кодирования (с обоснованием). 
13.	Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования. 
14.	Неравенство Макмиллана. 
15.	Теорема о существование префиксного кода с заданными длинами кодовых слов. 
16.	Теорема редукции. 
17.	Коды с исправлением r ошибок. Оценка функции Mr(n). 
18.	Коды Хэмминга. Оценка функции M1(n). 
19.	Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений. 
20.	Моделирование автоматной функции схемой из функциональных элементов и элементов задержки. 
21.	Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура. 
22.	Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
23.	NP-полнота задачи выполнимости 3-КНФ (с обоснованием).

Часть Б – ответ без конспектов и без подготовки.

1.	Функции алгебры логики. Равенство функций. Тождества для элементарных функций. 
2.	Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме. 
3.	Полные системы. Примеры полных систем (с доказательством полноты). 
4.	Теорема Жегалкина о представлении функции алгебры логики полиномом. 
5.	Понятие замкнутого класса. Замкнутость классов T0, T1, L. 
6.	Класс монотонных функций, его замкнутость. 
7.	Лемма о несамодвойственной функции. 
8.	Лемма о немонотонной функции. 
9.	Теорема о максимальном числе функций в базисе в алгебре логики. 
10.	Функции k-значной логики. Теорема о существовании конечной полной системы в Pk. 
11.	Основные понятия теории графов. Изоморфизм графов. Связность графов, леммы о связных графах. Теорема об оценке числа компонент связности в графе. 
12.	Корневые деревья. Верхняя оценка их числа. 
13.	Обходы графов, поиск в глубину и поиск в ширину в графе. Критерий точки сочленения в графе.
14.	Геометрическое представление графов. Теорема о представлении графов в трехмерном пространстве. 
15.	Планарные (плоские) графы. Формула Эйлера для планарных графов. 
16.	Теоремы о непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону). 
17.	Теорема о раскраске вершин графа в 2 цвета (теорема Кенига). 
18.	Оптимальные коды, их свойства. 
19.	Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов. 
20.	Схемы из функциональных элементов (СФЭ). Реализация функций алгебры логики схемами. 
21.	Сумматор. Верхняя оценка сложности n-разрядного сумматора. Вычитатель. Верхняя оценка сложности n-разрядного вычитателя. 
22.	Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
23.	Понятие задачи распознавания, классы P и NP. NP-трудные и  NP-полные задачи. Задача выполнимости КНФ, ее NP-полнота (без доказательства).
24.	Полиномиальный алгоритм проверки выполнимости 2-КНФ (с обоснованием).

Задачи на экзамене

В билете кроме двух теоретических вопросов указана тема задачи. Всего тем четыре: алгебра логики, графы, коды, автоматы. По итогам проверочных работ каждый студент по каждой из этих четырех тем получает одну из трех оценок - 1; 0,5 или 0. Оценка 1 по определенной теме означает освобождение от задачи по этой теме, если она попадается в билете. Оценка 0 означает дополнительную задачу по этой теме на экзамене. Все дополнительные задачи (по одной задаче по каждой теме, за которую 0) решаются студентом до выбора билета. Если студент не решил достаточного числа дополнительных задач, то ему может быть поставлена оценка неуд (без возможности выбрать билет). Если студент решил не все дополнительные задачи и тянет билет, то ему снижается оценка с учетом числа нерешенных дополнительных задач. Задачи решаются без конспектов. После ответа на билет экзаменатор может опрашивать студента по всему материалу (определения, формулировки теорем, идеи доказательств). Кроме того, экзаменатор может предлагать студенту решить задачи по любым темам из курса (в том числе, по которым у студента 1). На пересдаче нет освобождения от задач и дополнительных задач: студент отвечает на два теоретических вопроса в билете и решает задачу из билета.

Типовые задачи для экзамена.

1.	Доказать заданное тождество алгебры логики.
2.	Представить заданную функцию алгебры логики совершенной ДНФ или КНФ, полиномом Жегалкина или СФЭ.
3.	Подсчитать число функций алгебры логики n переменных в заданном множестве.
4.	Исследовать заданную систему функций алгебры логики на полноту.
5.	Выяснить, является ли заданная система функций алгебры логики базисом.
6.	Представить заданную k-значную функцию в 1-й или во 2-й форме.
7.	Представить заданную k-значную функцию полиномом по модулю k (при простом k).
8.	Выяснить, можно ли представить заданную k-значную функцию полиномом по модулю k (при составном k).
9.	Найти число неизоморфных графов с заданными свойствами (при заданном малом числе вершин).
10.	Найти кратчайшее остовное дерево заданного графа.
11.	Найти код заданного упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по заданному коду.
12.	Выяснить, является ли заданный граф планарным.
13.	Найти хроматическое число или хроматический индекс заданного графа.
14.	Выяснить, является ли заданный алфавитный код однозначным.
15.	Построить префиксный код с заданными длинами кодовых слов.
16.	Построить оптимальный двоичный код для заданного распределения частот.
17.	Закодировать или декодировать сообщение в коде Хэмминга. 
18.	Обосновать автоматность заданного отображения.
19.	Преобразовать заданное представление конечного автомата в предложенное другое его представление (представления: диаграмма Мура, канонические уравнения, СФЭЗ).
20.	Построить диаграмму Мура без неотличимых состояний для заданной автоматной функции.
		
Экзаменационный билет состоит из двух вопросов (из части А и из части Б) и задачи, например

1.	Теорема Поста о полноте системы функций алгебры логики.
2.	Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
3.	Найти число неизоморфных графов (без петель и кратных ребер) с 6 вершинами и 12 ребрами. Изобразить эти неизоморфные графы. 
ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  
	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Коллоквиум,
Экзамен	Отсутствие знаний	Отдельные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Контрольная работа, зачет
	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципи-ального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен
	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие частичного опыта)	В целом, сформированные навыки (владения), но недостаточно используемые 	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)
	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	применения, основные свойства и способы представления функций алгебры логики; 
2.	основы теории полноты, критерии полноты, основные подходы и методы распознавания полноты систем функций алгебры логики;
3.	применения и основные свойства графов, свойства деревьев и остовных деревьев в графах, критерии планарности и  свойства планарных графов, свойства раскрасок графов;
4.	основы теории сложности задач, примеры полиномиальных и труднорешаемых задач;
5.	применение и основные свойства схем из функциональных элементов, оценки сложности схемных сумматора, вычитателя и умножителя;
6.	применения, основные свойства и способы построения взаимно-однозначных и оптимальных кодов, а также кодов, исправляющих ошибки; 
7.	применения и основные свойства конечных автоматов-преобразователей.

Уметь: 
1.	обосновывать тождества алгебры логики, представлять функции алгебры логики формулами, дизъюнктивными и конъюнктивными нормальными формами, полиномами Жегалкина, схемами из функциональных элементов;
2.	выяснять полноту систем функций алгебры логики;
3.	проверять наличие у графа заданных свойств и оценивать число неизоморфных графов с заданными свойствами;
4.	находить остовное дерево или кратчайшее остовное дерево в связном графе;
5.	выяснять планарность графа или проверять возможность существования планарного графа с заданными свойствами;
6.	находить или оценивать хроматическое число или хроматический индекс графа;
7.	выяснять взаимную однозначность алфавитного кода, находить оптимальный код для заданного распределения частот;
8.	кодировать и декодировать сообщения в коде, исправляющем ошибки (в частности, одну ошибку);
9.	представлять отображение в виде конечного автомата-преобразователя (если это возможно);
10.	преобразовывать разные представления конечного автомата-преобразователя друг в друга, упрощать представления конечного автомата-преобразователя.

Владеть: 
1.	навыками понимания и применения подходов и методов современной дискретной математики при решении задач в профессиональной деятельности.

ОПК-1.Б, ОПК-2.Б, 
ПК-2.Б	

8. Ресурсное обеспечение:

Основная литература:
  
1.	Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
2.	Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002.
3.	Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
4.	Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Дополнительная литература:

1.	Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986. 
2.	Марченков С.С. Основы теории булевых функций. М.: Физматлит, 2014.
3.	Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
4.	Липский В. Комбинаторика для программистов. М.: Мир, 1988.
5.	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982..
6.	Марченков С.С. Конечные автоматы. М.: Физматлит, 2008.

Информационные справочные системы:

http://mk.cs.msu.ru/index.php/Дискретная_математика_(1й_курс)  -  основная страница курса со всеми материалами

http://mk.cs.msu.ru/index.php/Дискретная_математика_(1-й_поток)  - страница курса 1-го потока со всеми материалами

Материально-техническое обеспечение:

аудитория с партами, проектором, экраном и меловой доской для лекций; аудитория с партами и меловой доской для семинарских занятий.

9. Язык преподавания - русский.

10. Преподаватели:

Лектор – профессор факультета ВМК МГУ С.Н. Селезнева.
Преподаватели семинарских занятий – профессора факультета ВМК В.Б. Алексеев, С.С. Марченков, С.Н. Селезнева, старший преподаватель факультета ВМК А.С. Нагорный
.
11. Авторы программы:  профессора факультета ВМК МГУ В.Б. Алексеев, С.Н. Селезнева.