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

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________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-й поток: математические методы обработки информации и принятия решений).

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

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

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

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

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

Знать:
1.	предпосылки вычислительного характера, приводящие к двум моделям абстрактных вычислительных устройств: машинам Тьюринга и конечным автоматам;
2.	основные способы задания языков, распознаваемых конечными автоматами, и методы перехода от одного типа задания к другому;
3.	основные способы задания конечно-автоматных преобразований и методы перехода от одного типа задания к другому;
4.	основные операции над машинами Тьюринга и понятие функции, вычислимой на машине Тьюринга;
5.	понятие моделирования машины Тьюринга и метод построения универсальной машины Тьюринга;
6.	операции суперпозиции, примитивной рекурсии и минимизации над частичными функциями;
7.	центральные идеи, лежащие в основе доказательства совпадения классов вычислимых и частично-рекурсивных функций;
8.	определения классов P, NP и понятие NP-полной задачи;
9.	центральные идеи, лежащие в основе доказательства NP-полноты задачи ВЫПОЛНИМОСТЬ;
10.	основные понятия, связанные с инвариантными классами;
11.	основы теории синтеза схем для функций из специальных классов;
12.	основы теории синтеза схем для не всюду определённых функций;
13.	методы получения индивидуальных нижних оценок сложности булевых функций из некоторых специальных классов;
14.	центральные идеи, лежащие в основе связи между схемной и алгоритмической сложностью функций;
15.	методологию построения и анализа основных моделей, возникающих в рамках теории алгоритмов и теории дискретных управляющих систем.

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

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

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

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

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

Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
Конечные автоматы	22	12	6	18	4	
Машины Тьюринга и вычислимые функции	30	16	8	24	6	
Сложность структурной реализации функций алгебры логики из некоторых классов	16	8	4	12	4	
Промежуточная аттестация: устный экзамен	4	0	0	0	4	
Итого	72	36	18	54	18	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)
7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.
Контрольная работа № 1	
Вариант 1	Вариант 2	

1. Дать определение провоинвариатного отношения эквивалентнос-ти. Что такое индекс отношения эквивалентности? Привести пример провоинвариатного отношения эквивалентности индекса 3.
2.  Построить диаграмму Мура для конечного автомата, который допускает множество всех слов четной длины и слово 110.
3.  С использованием правоинвариантного отношения эквивалент-ности конечного индекса доказать, что множество всех слов вида 1n001n+5 не является конечно-автоматным. 
4. Провести детерминизацию конечного автомата с входным алфа-витом {a,b,c}, множеством состояний {q1, q2, q3}, начальным состоянием q1, заключительным состоянием q3, если буквы a,b,c переводят состояние q1 соответственно в состояния q1,q2;  q1,q3 и q3,
состояние q2 – в состояния q1;  q2,q3 и q3, состояние q3 — в состояния 
q1,q2; q2 и q1.
5. Построить регулярное выражение в алфавите {0,1}, которое опре-деляет множество всех слов четной длины, содержащих подслово 011.
6. Что такое зависимость с запаздыванием? Описать, как с использо-ванием зависимости с запаздыванием вводится операция обратной связи для детерминированных функций. 
	
1. Дать определения регулярного выражения и регулярного множества. На основе каких утверждений доказывается конечная автоматность регулярных множеств?
2.  Построить диаграмму Мура для конечного автомата, который допускает множество всех слов нечетной длины и слово 01.
3.  С использованием правоинвариантного отношения эквивалент-ности конечного индекса доказать, что множество всех слов вида 1n+4001n не является конечно-автоматным. 
4. Провести детерминизацию конечного автомата с входным алфа-витом {a,b,c}, множеством состояний {q1, q2, q3}, начальным состоянием q1, заключительным состоянием q3, если буквы a,b,c переводят состояние q1 соответственно в состояния q3;  q2,q3 и q1,
состояние q2 – в состояния q1;  q1 и q2,q3 , состояние q3 — в состояния 
q2;  q1,q2 и q1.
5. Построить регулярное выражение в алфавите {0,1}, которое опре-деляет множество всех слов нечетной длины, содержащих подслово 101.
6. Дать определение детерминированной функции. Как детермини-рованная функция задается с помощью бесконечного дерева? Что такое вес дерева? 
	
Контрольная работа № 2	
Вариант 1	Вариант 2	

1. Дать определение функции, вычислимой на машине Тьюринга.
2. Построить машину Тьюринга в алфавите {0,1}, которая перераба-тывает любое слово вида 1m01n в слово 1m01n+n.
3. Построить машину Тьюринга в алфавите {0,1}, которая в основном коде вычисляет функцию x / (x – 1). 
	
1. Объяснить, что понимается под моделированием машины Тьюринга.
2. Построить машину Тьюринга в алфавите {0,1}, которая перераба-тывает любое слово вида 1m0k1n в слово 1m+n.
3. Построить машину Тьюринга в алфавите {0,1}, которая в основном коде вычисляет функцию 2 / (x – 1). 	
Контрольная работа № 3	
Вариант 1	Вариант 2	
 
1. Дать определение класса частично-рекурсивных функций. Являет-ся ли функция 1 – x частично-рекурсивной? 
2. Дать определение Р-сводимости. Верно ли, что любые две задачи из класса Р  Р-сводятся друг к другу? 
 3. Дать определение операции примитивной рекурсии. Как она при-меняется к частичным функциям?
 4. Доказать примитивную рекурсивность функции f(x), равной коли-честву чисел вида 2a + 5b на отрезке [0, x] (a, b — целые неотрица-тельные). 
 5. Применить операцию минимизации к функции log2(4 – x).
 6. Доказать частичную рекурсивность функции 2 / |x – 2|.
	 
1. Дать определение класса Р. Принадлежит ли функция [x / (y + 1)] классу Р (x, y задаются в двоичной записи)? 
 2. Дать определение операции примитивной рекурсии. Как она при-меняется к частичным функциям?
 3. Верно ли, что любая частичная функция, определенная ровно в 10 точках, частично-рекурсивна? 
 4. Доказать примитивную рекурсивность функции f(x), равной коли-честву чисел вида 2a + 3b на отрезке [0, x]  (a, b — целые неотрица-тельные). 
 5. Применить операцию минимизации к функции |x – 3| / 3.
 6. Доказать частичную рекурсивность функции log2(x + 1) + 1 / x.
	
Контрольная работа № 4	
Вариант 1	Вариант 2	

1. Определение инвариантного класса ФАЛ и его базового множества. Теорема о числе инвариантных классов с заданной мощностной константой σ (с указанием того, как эта константа определяется и какому множеству принадлежит). Доказательство данной теоремы для случая σ = 1 и идея доказательства для σ = 0.
2. Общее описание принципа локального кодирования О.Б. Лупанова с характеристикой его свойств и перечислением тех условий, которые обеспечивают асимптотическую оптимальность получаемых схем, а также указанием сложности и структуры этих схем. Пример применения принципа локального кодирования к классу самодвойственных ФАЛ.
3. Установить асимптотическое поведение функции Шеннона LC(Q(n)), n = 1,2,..., где Q(n) — множество всех тех ФАЛ из P2(n) , в столбце значений которых можно выделить [2n/3] непересекающихся подряд идущих подслов, принадлежащих множеству {(000), (001), (100), (010), (111)}.
	
1. Задача синтеза схем для ФАЛ или операторов из специального класса Q и связанные с ней понятия (последовательность Q(n), n = 1,2,..., функция LC(Q(n)) и др.). Определение невырожденного
класса Q и формулировка утверждения о нижней мощностной оценке его функции Шеннона.
2. Определение стандартного (относительно класса схем UC и функционала сложности L) класса ФАЛ. Развернутая формулировка утверждения о стандартности класса ФАЛ, обращающихся в ноль на
всех тех наборах значений переменных, номера которых больше заданного числа. Идея и основные этапы доказательства данного утверждения.
3. Установить асимптотическое поведение функции Шеннона LC(Q(n)), n = 1,2,..., где Q(n) — множество тех ФАЛ из P2(n), которые на любой паре противоположных наборов, за исключением, возможно, двух таких пар, принимают одинаковые значения.

Планы семинарских занятий 
Семинар 1
Множества, допускаемые конечными автоматами. Правоинвариантная эквивалентность. Теоретический материал [1, с. 27-31].
В классе и на дом. 
1.	Построить диаграмму Мура для автомата в алфавите {1,0}, который допускает следующее множество:
(a)	(1) Множество {0,1,Λ}; (2) Множество {0,1}* ∖ {0,1,Λ};
(b)	Все слова, начинающиеся на 01;
(c)	Все слова длины 3, кроме 110;
(d)	Все слова, содержащие 001;
(e)	Все слова, имеющие вхождения слов 000 и 111.
2.	Доказать конечную автоматность множеств:
(a)	Конечное множество X в алфавите {a1, ..., aт}; множество {a1, ..., aт}* ∖X;
(b)	Множество слов в алфавите {0,1}, содержащие неперекрывающиеся слова 000, 001, 011;
(c)	Множества вида 0n110n2…10nk, ni ≥ 1: (a) При каждом фиксированном k; (b) При произвольном k.
3.	Построить правоинвариантное отношение эквивалентности конечного индекса, объединением классов эквивалентности которого являются множества:
(a)	{Λ};
(b)	{Λ, 0,1};
(c)	{0n1, n ≥ 0};
(d)	Слова чётной длины и 1, 111.

4.	Для любого n ≥ 2 определить на {0,1} правоинвариантное отношение эквивалентности индекса n.
5.	Пользуясь правоинвариантным отношением эквивалентности доказать, что множества в алфавите {0,1} НЕ конечно-автоматны:

(a)	{0n102n, n ≥ 0};
(b)	Симметричные слова в любом не однобуквенном алфавите;
(c)	{0n21, n ≥ 1}.
Семинар 2
Теоретико-множественные операции над конечно-автоматными множествами. Недетерминированные автоматы. Операции произведения и итерации. Теоретический материал [1, с. 32-39].
В классе и на дом. 
1.	Ввести операцию прямого произведения автоматов. Доказать замкнутость конечно-автоматных множеств относительно операций объединения и пересечения.
2.	Сохраняют ли операции U, ∩, •, * класс не конечно-автоматных множеств?
3.	Построить диаграмму Мура и описать множество, допускаемое недетерминированным автоматом:
Q = {q1, q2, q3},
f(0, q1) = {q2},     f(1, q1) = {q1, q2},
f(0, q2) = {q3},     f(1, q2) = {q3},
f(0, q3) = {q3},     f(1, q3) = {q2, q3},
F = {q3}.
4.	Построить методом детерминизации эквивалентный данному детерминированный автомат:
Q = {q1, q2, q3},
f(0, q1) = {q1, q2},     f(1, q1) = {q1},
f(0, q2) = {q2},          f(1, q2) = {q2, q3},
f(0, q3) = {q1, q3},     f(1, q3) = {q1, q3},
F = {q3}.
5.	Пусть Ai = {A, Q, f, q1, Fi}, i = 1, 2, 3 (недетерминированные автоматы). Верно ли, что
(a)	При  F2 = Q ∖ F1  выполнено D(A2) = А* ∖ D(A1);
(b)	При  F3 = F1 ∩ F2  выполнено D(A3) = D(A1) ∩ D(A2).
6.	Построить недетерминированный автомат, который допускает произведение автоматных множеств D(A) • D(B):
A: Q = {q1, q2, q3},
f(0, q1) = q2,     f(1, q1) = q1,
f(0, q2) = q2,     f(1, q2) = q3,
f(0, q3) = q1,     f(1, q3) = q3,
F = {q1, q3};
B: Q = {q1, q2},
f(0, q1) = q1,     f(1, q1) = q2,
f(0, q2) = q1,     f(1, q2) = q2,
F = {q2}.

7.	Для автомата A из предыдущей задачи построить недетерминированный автомат, принимающий D(A)*.
8.	Построить из множеств {0}, {1} при помощи объединения, произведения и итерации множество всех слов, содержащих подслово 0001.
9.	А = {a1, ..., aт}. Сколько раз необходимо применить операцию итерации, чтобы получить множество А*∖{ā} при помощи объединения, произведения и итерации из множеств вида {ai}.
10.	 Пусть множество X состоит из п слов. Может ли множество X • X содержать больше п2 слов? Меньше п2 слов? В точности п2 слов?
Семинар 3
Регулярные выражения и регулярные множества. Теорема Клини. Теоретический материал [1, с. 40-42].
В классе и на дом. 
1.	Доказать регулярность множеств слов в алфавите {0,1}:
(a)	Любое конечное множество слов и дополнение к конечному множеству;
(b)	Множество слов, содержащих в качестве подслова одно из слов х1, ...,  хп;
(c)	Множество слов, не содержащих 01;

2.	Привести пример бесконечного регулярного множества, которое невозможно получить однократным использованием итерации.
3.	Пусть X — регулярное множество в алфавите {a1, ..., aт}; Y1, ..., Ym — регулярные множества в алфавите {b1, ..., bт}. Доказать, что множество слов, получаемых одновременной заменой букв a1, ..., aт в любом слове из X любыми словами из Y1, ..., Ym соответственно, является регулярным.
4.	Пусть X — регулярное множество, Rev(X) —множество обращений слов из X. Доказать, что оно тоже будет регулярным.
5.	Пусть X — конечно-автоматное множество в алфавите A, Y — конечно-автоматное множество в однобуквенном алфавите. Обозначим через X/Y множество тех слов из X, длины которых являются длинами слов из Y. Доказать, что множество X/Y конечно-автоматно.
Семинар 4
Детерминированные функции. Построение диаграмм Мура и канонических уравнений. Теоретический материал и примеры решения задач имеются в задачнике.
В классе. Из [7, глава IV]: 1.1 (1, 3, 8, 9), 1.2 (1), 2.1 (1, 6, 16), 2.4 (1, 3), 2.5 (3).
На дом.  Из [7, глава IV]: 1.1 (4, 6, 9, 13), 1.2 (2), 2.1 (3, 7), 2.4 (1, 3), 2.5 (3).
Семинар 5
Операции суперпозиции и обратной связи. Построение схем из автоматных элементов. Теоретический материал и примеры решения задач имеются в задачнике.
В классе. Из [7, глава IV]: 2.8 (3, 6), 2.9 (4), 2.13 (1, 4), 2.14 (1, 4), 2.17 (1, 4).
На дом. Из [7, глава IV]: 2.8 (5, 8), 2.9 (5), 2.13 (6, 11), 2.14 (2, 5), 2.17 (2, 5).
Семинар 6 
Консультационный семинар по разделу I.
Семинар 7
Машины Тьюринга. Функции, вычислимые на машинах Тьюринга. Теоретический материал и примеры решения задач имеются в задачнике.
В классе. Из [7, глава V]: 1.8 (1, 3), 1.4 (2); 1.14 (1, 2, 3, 4, 9, 10), 1.15 (2, 7).
На дом. Из [7, глава V]: 1.8 (2, 6), 1.4 (4), 1.14 (5, 6, 7, 12), 1.15 (4, 6).
Семинар 8
Примитивно-рекурсивные функции. Теоретический материал и примеры решения задач имеются в задачнике. См. также [1, с. 78].
В классе. Из [7, глава V]: 2.1 (9, 10, 12), 2.2 (1, 3); применить операцию примитивной рекурсии к частичным функциям g(х) = 2х и h(x,y,z) = z – 2; 2.3 (9, 10, 5), 2.4 (1, 2, 5, 7б).
На дом. Из [7, глава V]: 2.1 (2, 4), 2.4 (3, 7а), 2.3 (7, 8, 9).
Семинар 9
Операции ограниченного суммирования и мультиплицирования. Операция минимизации. Теоретический материал и примеры решения задач имеются в задачнике. См. также [1, с. 102-107].
В классе. Используя операции Πi ≤ x и Σi ≤ x доказать примитивную рекурсивность функций [х/у], [√x], [logax], «число делителей x», «число решений полиномиального уравнения в заданном промежутке».
Из [7, глава V]: 2.5 (1, 2, 3, 7, 11), 2.7 (2, 6).
На дом. Используя операции Πi ≤ x и Σi ≤ x доказать примитивную рекурсивность функций р(х), f1(x), f2(x), где
p(x) = 1, если x — простое число и p(x) = 0, иначе;
f1(x) — количество чисел вида уу на отрезке [0,х]; f2(x)  — количество чисел вида 2y∙3z на отрезке [0,х].
Из [7, глава V]: 2.5 (4, 10, 13), 2.7 (3, 5).
Семинар 10
Частично-рекурсивные функции. Теоретический материал и примеры решения задач имеются в задачнике. См. также [1, с. 108-113].
В классе. Из [7, глава V]: 2.8 (1, 2, 5).
Доказать частичную рекурсивность функций:
1.	f -1(x), где f — общерекурсивная перестановка (биективная функция) на N0.
2.	f(x) = x, если x принадлежит множеству {a1, ..., aт}; не определено в ином случае (a1, ..., aт — числа из N0).
3.	f(x) = x, если f1(x) ≥ f2(x); не определено в ином случае (f1(x), f2(x) — примитивно-рекурсивные функции).
4. x/y.
5. √x.
6.  f(x) = x, если в последовательности g есть две единицы на расстоянии x + 1; не определено в ином случае (g(x) — примитивно-рекурсивная функция, принимающая значения 0, 1 (двоичная последовательность)).
На дом. Из [7, глава V]: 2.8 (3).
Доказать частичную рекурсивность функций:
1.	f(x) = x, если x входит в пересечение областей значений частично-рекурсивных функций g1(z), g2(z); не определено в ином случае.
2.	f(x) = x, если x входит в область значений функции g; не определено в ином случае (g(z) — примитивно-рекурсивная функция, например z2, 2z).
3.	x – y.
4.	log2x.
5.	f(x) = x, если в последовательности g есть две единицы на расстоянии x + 1; не определено в ином случае (g(x) — примитивно-рекурсивная функция, принимающая значения 0, 1 (двоичная последовательность)).
Семинар 11
Класс P. Теоретический материал имеется в задачнике.
В классе. Из [8]: 2.3 (2, 4, 5, 7); доказать, что задача определения существенных переменных у функции, заданной таблицей значений, может быть выполнена на машине Тьюринга за полиномиальное время; 2.19 (7), 2.20 (1а, 2а, 2д, 3а, 4а).
На дом. Из [8]: 2.3 (6, 8, 9, 10), 2.19 (1), 2.20 (1г, 2г, 3г).
Семинар 12
P-сводимость и NP-полнота. Теоретический материал имеется в задачнике.
В классе и на дом. Из [8]: 2.5 (рис. 1, 3, 6), 2.17 (задача 5), 2.18 (1), 2.19 (4), 2.20 (1б, 1в, 2б, 3в).
Семинар 13
Консультационный семинар по разделу II.
Семинар 14
Постановка задачи синтеза схем для ФАЛ (операторов) из специальных классов, мощностные характеристики этих классов и соответствующие нижние оценки функций Шеннона для их сложности. Инвариантные и квазиинвариантные классы ФАЛ, их структурное описание и особенности, поведение мощностных последовательностей. Теоретический материал [4, §§1,11].
В классе.
1. Выяснить, какие из следующих классов ФАЛ (операторов) являются невырожденными, и получить нижние мощностные оценки (НМО) функций Шеннона для сложности реализации ФАЛ из данных классов СФЭ в стандартном базисе:
(a)	Q — класс ФАЛ, равных 1 при x1 = 0;
(b)	Q — класс ФАЛ, симметричных по БП x1, x2, x3;
(c)	Q — класс ФАЛ, монотонных по БП x1, x2;
(d)	Q — класс ФАЛ, равных 0 на наборах с чётном числом 1;
(e)	Q — класс линейных ФАЛ;
(f)	Q — класс самодвойственных ФАЛ;
(g)	Q — класс симметрических ФАЛ;
(h)	Q — класс операторов вида F = (f1, f2, f3) таких, что fi∙ fj = 0 при i  ≠  j и  f1 v f2 v f3 = 1.
2.	Выделить среди классов ФАЛ из п. 1 квазиинвариантные и инвариантные классы, для которых найти пределы соответствующих им мощностных последовательностей.
3.	Найти порождающее множество класса линейных ФАЛ.
На дом.
1.	Исследовать на невырожденность и, в случае невырожденности, установить асимптотику НМО функции Шеннона LC(Q(n)) для сложности реализации ФАЛ (операторов) от БП x1, ..., xn из класса Q, где:
(a)	Q — класс ФАЛ, равных 1 при x1 = x2 = 1;
(b)	Q — класс ФАЛ, монотонных по x1 и антимонотонных по x2;
(c)	Q — класс ФАЛ, у которых любая подфункция от БП x1, x2 принадлежит множеству { ¬x1, ¬x2, x1, x2, x1 v x2, x1 ~ x2 };
(d)	Q — класс ФАЛ, симметричных по своим n, n = 1,2,... существенным БП с рабочими числами вида a, a + 4, a + 8,  ...,  a + 4k, где a принадлежит множеству {0, 1, 2, 3} и k = [(n – a) / 4];
(e)	Q — класс операторов F = (f1, f2) таких, что f1(α1,…, αn) = ¬f2(β1,…, βn), где набор β имеет номер на единицу больше, чем набор α, если
α ≠ (1,...,1), и равен нулевому набору в противном случае.

2.	Выделить среди классов ФАЛ из п. 1 квазиинвариантные и инвариантные классы, для которых найти пределы соответствующих им мощностных последовательностей.
3.	Найти порождающее множество инвариантного класса ФАЛ, состоящего из констант и всех монотонных элементарных конъюнкций.
Семинар 15
Синтез схем для ФАЛ из специальных классов, установление асимптотики соответствующих функций Шеннона. Теоретический материал [4, §§2-5].
В классе. Установить асимптотическое поведение функции Шеннона LC(Q(n)) для сложности реализации ФАЛ (операторов) от БП x1, ..., xn из класса Q, где Q — один из невырожденных классов, указанных в классной задаче 1 семинара 12.
На дом. Установить асимптотическое поведение функции Шеннона LC(Q(n)) для сложности реализации ФАЛ (операторов) от БП x1, ..., xn из класса Q, где Q — один из невырожденных классов, указанных в домашней задаче 1 семинара 12.
Семинар 16
Сложность не всюду определённых функций, их использование при синтезе схем для ФАЛ из специальных классов. Теорема Храпченко. Теоретический материал [4, §§6-10].
В классе.
1.	Найти сложность не всюду определённой ФАЛ f от трёх переменных, для которой αf = (0001 1222).
2.	Найти асимптотику функции Шеннона LC(Q(n)) для сложности реализации ФАЛ от БП x1, ..., xn из класса Q(n), включающего в себя все те ФАЛ, которые обращаются в ноль на наборах куба Вп, имеющих не меньше п/2 единиц.
3.	Доказать, что 12 ≤ Lπ(s4{2}) ≤ 16, где snI — симметрическая ФАЛ от п БП, «рабочие» числа которой составляют подмножество I множества [0, n].
4.	Доказать, что Lπ((x1 +…+ xk)(xk+1 +…+ xn))  ≥  п2/2 (все сложения по модулю 2).
На дом.
1.	Найти сложность не всюду определённой ФАЛ f от трёх переменных, для которой αf = (0111 2221).
2.	Найти асимптотику функции Шеннона LC(Q(n)) для сложности реализации ФАЛ от БП x1, ..., xn из класса Q(n), включающего в себя все те ФАЛ, которые обращаются в ноль на наборах куба Вп, имеющих не равное i, 1 ≤  i ≤  п – 2 число единиц.
3.	Доказать, что 63 ≤ Lπ(s8{2,4,6}) ≤ 80.
4.	Доказать, что Lπ((x1 +…+ xk)(xk+1 +…+ xs)(xs+1 +…+ xn))  ≥  п2/3, где 1 ≤  k < s < п (все сложения по модулю 2). 
Семинар 17
Консультационный семинар по разделу III.
Семинар 18
Консультационный семинар по всем разделам.

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Экзамен проводится в устной форме. Для студентов, не сдавших экзамен, учебным планом предусматривается переэкзаменовка. 

Вопросы к экзамену.
I.	Конечные автоматы
1.	Конечный автомат-распознаватель, конечно-автоматное множество. [1, с. 27–28]
2.	Правоинвариантное отношение эквивалентности, связь с конечно-автоматными множествами. [1, с. 29–31]
3.	Замкнутость класса конечно-автоматных множеств относительно теоретико-множественных операций. [1, с. 32–33]
4.	Недетерминированные автоматы, процедура детерминизации. [1, с. 34–36]
5.	Операции произведение и итерации. Замкнутость конечно-автоматных множеств относительно операций произведения и итерации. [1, с. 37–39]
6.	Регулярные выражения и регулярные множества. [1, с. 40]
7.	Теорема Клини. [1, с. 40–42]
8.	Детерминированные функции. Задание детерминированных функций деревьями. Вес дерева. [2, с. 74–85]
9.	Канонические уравнения, векторная и скалярная формы канонических уравнений. [2, с. 88–91]
10.	Замкнутость класса конечно-автоматных функций относительно операции суперпозиции. [2, с. 92–94], [1, с. 57–59]
11.	Зависимость с запаздыванием. Операция введения обратной связи. [2, с. 94–96, 98–102]
12.	Существование конечных полных систем в классе конечно-автоматных функций. [2, с. 105–108], [1, с. 60–61]
II.	Машины Тьюринга и вычислимые функции
13.	Машины Тьюринга. Функции, вычислимые на машинах Тьюринга. [1, с. 65–68]
14.	Операции композиции и итерации над машинами Тьюринга. [1, с. 70–72]
15.	Моделирование машин Тьюринга. [1, с. 74–77]
16.	Универсальная машина Тьюринга. [1, с. 84–86]
17.	Операции суперпозиции, примитивной рекурсии и минимизации. [1, с. 77–79]
18.	Замкнутость класса функций, вычислимых на машинах Тьюринга, относительно операций суперпозиции, примитивной рекурсии и минимизации. [1, с. 80–83]
19.	Класс примитивно-рекурсивных функций. Простейшие примитивно-рекурсивные функции. [1, с. 102–105]
20.	Класс частично-рекурсивных функций. Примеры частично-рекурсивных функций. [1, с. 79, 108–109]
21.	Частичная рекурсивность вычислимых функций. Формула Клини. [1, с. 114–117]
22.	Классы P и NP. Примеры задач из класса NP. [1, с. 89–93]
23.	NP-полнота. Теорема Кука. [1, с. 95–99]
24.	NP-полнота задачи 3-ВЫП. [1, с. 99–100]
25.	Полиномиальная разрешимость задачи 2-ВЫП. [1, с. 101–102]
III. Сложность структурной реализации функций алгебры логики из некоторых классов
26.	Задача синтеза схем для функций (операторов) из специального класса, мощностные нижние оценки функции Шеннона для их сложности в случае невырожденного (ненулевого, квазиинвариантного) класса. [4, §1]
27.	Инвариантные классы функций С.В. Яблонского, их описание на языке базовых множеств и порождающих элементов. Теорема о числе инвариантных классов и фрагменты её доказательства. [4, §11]
28.	Синтез схем на основе модификации асимптотически наилучшего метода. Стандартные классы и стандартность класса функций, равных нулю на всех наборах значений переменных, номера которых больше заданного числа. [4, §2]
29.	Асимптотически наилучший метод синтеза схем для ненулевых квазиинвариантных классов, их стандартность. [4, §3]
30.	Общее описание принципа локального кодирования, его применение для доказательства стандартности класса самодвойственных функций. [4, §4]
31.	Применение принципа локального кодирования для доказательства стандартности невырожденных классов симметрических операторов, операторов, связанных с вычислением функции на нескольких последовательных наборах. [4, §5]
32.	Задача синтеза схем для не всюду определённых функций. Особенности получения нижней мощностной оценки соответствующей функции Шеннона, формулировка теоремы о её асимптотическом поведении. [4, §6]
33.	Асимптотически наилучший метод синтеза схем для не всюду определённых функций в случае их «сильной» определённости. [4, §7]
34.	Лемма о линейном разделяющем операторе. Асимптотически наилучший метод синтеза схем для не всюду определённых функций в случае их «средней» и «слабой» определённости. [4, §8]
35.	Лемма о цепях и сечениях π-схем. Верхние оценки сложности реализации линейных функций в классе π-схем. [4, §9]
36.	Теорема Храпченко, нижние оценки сложности линейной функции в классе π-схем. [4, §10]
37.	Схемная и алгоритмическая сложность функций, построение сложно реализуемых функций. Гипотеза С.В. Яблонского и теорема Дж. Сэвиджа. [6, с. 42–45]
Типовые задачи к экзамену.

I.	Задачи по конечным автоматам
1.	Построить диаграмму Мура конечного автомата, распознающего заданное множество.
2.	Используя правоинвариантное отношения эквивалентности, доказать, что заданное множество не является конечно-автоматным.
3.	Построить регулярное выражение, определяющее заданное множество.
4.	Построить диаграмму Мура конечного автомата, реализующего заданную функцию.
5.	По диаграмме Мура построить канонические уравнения и схему в стандартном автоматном базисе.
6.	По схеме в стандартном автоматном базисе построить канонические уравнения и диаграмму Мура.
II.	Задачи по машинам Тьюринга и рекурсивным функциям
7.	Построить машину Тьюринга, вычисляющую заданную функцию или выполняющую заданное преобразование.
8.	Доказать примитивную рекурсивность заданной функции.
9.	Применить операцию минимизации к заданной (частичной) функции.
10.	Доказать частичную рекурсивность заданной функции.
III.	Задачи на сложность реализации функций алгебры логики (ФАЛ)
11.	Выяснить, является ли заданный класс ФАЛ инвариантным классом, и, в случае инвариантности этого класса, найти его порождающее множество.
12.	Выяснить, является ли заданный класс ФАЛ (операторов) вырожденным, и, в случае его невырожденности, получить нижнюю мощностную оценку функции Шеннона для сложности реализации ФАЛ из этого класса схемами из функциональных элементов (СФЭ) в стандартном базисе.
13.	Получить верхнюю (асимптотически точную) оценку функции Шеннона для сложности реализации ФАЛ из заданного специального класса из определённых или не всюду определённых ФАЛ при их реализации СФЭ в стандартном базисе.
14.	Получить требуемую нижнюю оценку сложности реализации заданной ФАЛ в классе π-схем.
Экзаменационный билет состоит из двух вопросов и задачи, например:
1.	Операция композиции над машинами Тьюринга.
2.	Схемная и алгоритмическая сложность функций, гипотеза С.В. Яблонского и теорема Дж. Сэвиджа.
3.	Задача из раздела I (например: построить диаграмму Мура для автомата в алфавите {0,1}, который допускает множество всех слов четной длины и слово 001).

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

	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	
Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)
	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	предпосылки вычислительного характера, приводящие к двум моделям абстрактных вычислительных устройств: машинам Тьюринга и конечным автоматам;
2.	основные способы задания языков, распознаваемых конечными автоматами, и методы перехода от одного типа задания к другому;
3.	основные способы задания конечно-автоматных преобразований и методы перехода от одного типа задания к другому;
4.	основные операции над машинами Тьюринга и понятие функции, вычислимой на машине Тьюринга;
5.	понятие моделирования машины Тьюринга и метод построения универсальной машины Тьюринга;
6.	операции суперпозиции, примитивной рекурсии и минимизации над частичными функциями;
7.	центральные идеи, лежащие в основе доказательства совпадения классов вычислимых и частично-рекурсивных функций;
8.	определения классов P, NP и понятие NP-полной задачи;
9.	центральные идеи, лежащие в основе доказательства NP-полноты задачи ВЫПОЛНИМОСТЬ. 
Уметь:
1.	строить конечный автомат по неавтоматно заданному множеству слов или по неформализованному описанию детерминированной функции;
2.	переводить одно из основных определений конечно-автоматного множества или конечно-автоматной функции в другие;
3.	доказывать невхождение в классы конечно-автоматных множеств или конечно-автоматных функций конкретных множеств и функций;
4.	строить программы машин Тьюринга, вычисляющих простые словарные и числовые функции;
5.	доказывать примитивную рекурсивность или частичную рекурсивность простых арифметических функций;
6.	обосновывать принадлежность конкретных множеств классам P и NP;
7.	доказывать NP-полноту стандартных задач.
Владеть:  
1.	навыками оперирования с конечными автоматами-распознавателями и автоматами-преобразователями;
2.	навыками составления программ для машин Тьюринга;
3.	навыками построения выводов в формализмах примитивно-рекурсивных и частично-рекурсивных функций;
4.	навыками построения схем из функциональных элементов для булевых функций. 	

ОПК-1.Б	
Знать:
1.	основные понятия, связанные с инвариантными классами;
2.	основы теории синтеза схем для функций из специальных классов;
3.	основы теории синтеза схем для не всюду определённых функций;
4.	методы получения индивидуальных нижних оценок сложности булевых функций из некоторых специальных классов;
5.	центральные идеи, лежащие в основе связи между схемной и алгоритмической сложностью функций.
Уметь:
1.	получать схемные представления для булевых функций, находить оценки сложности их реализаций;
2.	получать нижние оценки для реализации булевых функций в классе π-схем;
3.	использовать не всюду определенные функции для синтеза схем для функций из специальных классов;
4.	применять на практике основные методы теории алгоритмов и теории дискретных управляющих систем. 
Владеть:  
1.	основными методами дискретной математики и теории управляющих систем для решения научных и прикладных задач;
2.	навыками решения практических задач методами теории алгоритмов и теории управляющих систем. 	

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

ПК-2.Б	

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

Основная литература:
1.	Марченков С.С. Избранные главы дискретной математики. –  М.: МАКС Пресс, 2016. (Электронный ресурс: http://mk.cs.msu.ru/images/2/25/ИзбрГлавыДискрМатем_2015.pdf)
2.	Яблонский С. В. Введение в дискретную математику. – М.: Высшая школа, 2003.
3.	Ложкин С.А. Лекции по основам кибернетики. – М.: МГУ, 2004.
4.	Ложкин С.А. Дополнительные главы кибернетики. – М.: МГУ, 2019. (Электронный ресурс: http://mk.cs.msu.ru/images/0/0b/Dgcyb-lect-190113.pdf)
5.	Яблонский С.В. Элементы математической кибернетики. – М.: Высшая школа, 2007.
6.	Сапоженко А.А. Некоторые вопросы сложности алгоритмов. – М.: МГУ, 2001. (Электронный ресурс: http://mk.cs.msu.ru/images/e/e8/Sapozhenko_alg.pdf)
7.	Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005.
8.	Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011. (Электронный ресурс: http://mk.cs.msu.ru/images/a/ab/Задачи_по_курсу_Основы_кибернетики_2011.pdf)

Информационные справочные системы:  http://www.mathnet.ru/

Материально-техническое обеспечение: аудитория с партами, компьютером, проектором, экраном и меловой доской.

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

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

11. Авторы программы:  профессора факультета ВМК МГУ С.С. Марченков, С.А. Ложкин.