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

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________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.	основы теории NP-полных алгоритмов;
6.	методологию построения и анализа основных моделей, возникающих в рамках теории дискретных управляющих систем и теории алгоритмов;
7.	методы получения оценок и характер роста функций Шеннона сложности и длины ДНФ и функций Шеннона сложности схем (в том числе для некоторых специальных классов функций и для схем с некоторыми связанными с требованиями самокорректирования ограничениями).

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

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

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

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

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

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
Единичный куб и функции алгебры логики (ФАЛ), представление ФАЛ с помощью ДНФ. Сокращенная ДНФ и тупиковые ДНФ, их «геометрический» смысл. Способы построения однозначно получаемых ДНФ (сокращённой, пересечения тупиковых, Квайна, суммы тупиковых). Особенности ДНФ для ФАЛ из некоторых классов. Функция покрытия и алгоритм построения всех тупиковых ДНФ, оценка длины градиентного покрытия. Алгоритмические трудности минимизации ДНФ, оценки максимальных и типичных значений некоторых параметров ДНФ.	25	10	10	20	5	
Основные классы УС – формулы и схемы из функциональных элементов (СФЭ), контактные схемы (КС), – их структура, меры сложности, функционирование, полнота. Некоторые частные случаи и обобщения основных классов, оценка числа схем различных типов. Эквивалентность схем. Понятие подсхемы и принцип эквивалентной замены. Тождества и связанные с ними эквивалентные преобразования УС. Построение полных систем тождеств для формул, СФЭ и КС. Отсутствие конечной полной системы тождеств для КС. Некоторые модификации основных классов схем. Автоматные функции, их реализация схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями.	27	10	12	22	5	
Задача синтеза УС, сложность ФАЛ и функция Шеннона. Простейшие методы синтеза схем, реализация некоторых ФАЛ и оценка их сложности. Метод каскадов для КС и СФЭ, метод Шеннона. Мощностные методы получения нижних оценок для функций Шеннона. Асимптотически наилучшие методы синтеза формул, СФЭ и КС. Синтез схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Схемы на КМОП-транзисторах, задача логического и «физического» синтеза СБИС, основные этапы её решения.	25	10	10	20	5	
Самокорректирующиеся КС и простейшие методы их синтеза. Асимптотически наилучшие методы синтеза КС, корректирующих один обрыв или одно замыкание. Задача контроля УС, тесты для таблиц. Алгоритм построения всех тупиковых тестов, оценки максимального и типичного значений длины диагностического теста.	10	4	4	8	2	
Полиномиальная сводимость языков, классы Р и NP, теорема Кука.	5	2	0	2	3	
Промежуточная аттестация: устный экзамен	16	0	0	0	16	
Итого	108	36	36	72	36	

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

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

ВАРИАНТ КОНТРОЛЬНОЙ РАБОТЫ №1
1.	Определение элементарной конъюнкции и элементарной дизъюнкции, ДНФ и КНФ, их «геометрическая» интерпретация. Критерий единственности ДНФ.
2.	Определение пучка, регулярной точки и регулярной грани ФАЛ; ДНФ  и критерий вхождения в неё простых импликант.
3.	Определение монотонной ФАЛ и её «нижних» единиц. Утверждение о сокращённой ДНФ монотонной ФАЛ, особенности её тупиковых ДНФ.
4.	Определение кратчайшей ДНФ и её связь с тупиковыми ДНФ, определение функции Шеннона  для длины кратчайших ДНФ, реализующих ФАЛ от  БП. Поведение функции Шеннона  (идея получения верхней оценки и пример ФАЛ, на которой достигается нижняя оценка).
5.	Определение функции Шеннона  для числа минимальных ДНФ у ФАЛ от  БП, её нижняя оценка и пример ФАЛ, на которой эта оценка достигается.
6.	Построить сокращённую ДНФ ФАЛ , столбец значений которой имеет вид .
7.	На основе ФАЛ покрытия для редуцированной таблицы Квайна построить ядро, ДНФ Квайна, ДНФ сумма тупиковых и все тупиковые ДНФ функции , заданной сокращённой ДНФ:
.

ВАРИАНТ КОНТРОЛЬНОЙ РАБОТЫ №2
1.	Определение структуры СФЭ в базисе  как помеченного графа специального вида, определение ФАЛ, реализуемой в вершине СФЭ, и системы ФАЛ, реализуемой этой СФЭ. Определение приведённой СФЭ, утверждение о соотношениях между рангом, сложностью и глубиной приведённой СФЭ с 1 выходом в стандартном базисе.
2.	Определение эквивалентных формул. Верхняя оценка числа попарно не эквивалентных формул от БП , имеющих сложность не больше, чем , в стандартном базисе, а также в базисе .
3.	Определение подсхемы заданной КС из неориентированных контактов с неразделёнными полюсами, принцип эквивалентной замены. Определение тождества для КС из неориентированных контактов с неразделёнными полюсами и его подстановки; описание указанной подстановки одного из основных тождеств, результатом которой является тождество для -схем, моделирующее формульное тождество .
4.	Суммарное цикломатическое число КС и его изменение при ЭП КС на базе различных основных тождеств. Идея и основные этапы доказательства утверждения об отсутствии КПСТ в классе всех КС.
5.	Тождества перехода от одного базиса к другому; утверждение о моделировании ЭП формул в различных базисах и идея его доказательства.
6.	С помощью расширенной системы основных тождеств построить ЭП для формул  и :
, 
7.	С помощью системы основных тождеств  построить ЭП для КС  и , указав без каких тождеств вида  при этом нельзя обойтись. Упрощённый вариант задачи: преобразовать КС  описанным способом в КС, все контакты которой лежат на цепях, соединяющих различные полюса и не имеющих общих внутренних вершин.

ВАРИАНТ КОНТРОЛЬНОЙ РАБОТЫ №3
1.	Определение сложности  системы ФАЛ  в классе СФЭ над базисом  и формулировка утверждения о простейшей нижней оценке этой сложности. Универсальная система ФАЛ  порядка  и оценка указанного вида для её сложности.
2.	Определение функции Шеннона  и её верхняя оценка, получаемая методом Шеннона, с описанием структуры и указанием сложности схемы, построенной для произвольной ФАЛ .
3.	Операция присоединения одной вершины СФЭ к другой вершине этой схемы и её свойства, определение строго приведённой СФЭ. Формулировка утверждения о верхней оценке сложности  и идея его доказательства.
4.	Определение ‑регулярного множества наборов куба , , от БП , его свойства и задание с помощью системы ФАЛ от БП . Построить 2-регулярное подмножество куба  от БП , на котором ФАЛ ,  и  совпадают с одной из ФАЛ .
5.	С помощью моделирования совершенной ДНФ на основе контактного дерева построить –КС, реализующую ФАЛ , где , а затем получить из этой ККС инверсную схему.
6.	Построить минимальную –КС для ФАЛ : 
.
7.	С помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по , построить –КС ∑ для системы ФАЛ  и СФЭ  для ФАЛ , где , .

Планы семинарских занятий 
Семинар 1. Комбинаторика граней единичного булева куба. Представление функций алгебры логики (ФАЛ) с помощью ДНФ и его «геометрическая» интерпретация, совершенная ДНФ. Сокращённая ДНФ и «геометрические» методы её построения, карта Карно. Теоретический материал [1: с. 19-32], [5: с. 290-292, 296-298]. В классе. Из [5]: гл. IX — 1.2(1-6); гл.I — 2.3(3). Найти число тех ФАЛ от п БП, совершенная ДНФ которых является их единственной ДНФ и имеет длину 2; доказать, что длина совершенной ДНФ от БП х1,... ,хп, являющейся единственной ДНФ реализуемой ею ФАЛ, не больше, чем 2п-1. Из [5]: гл. IX — 2.1 (1,2), 2.5 (1,5), 2.6 (1,5). На дом. Из [5]: гл. IX — 1.2 (7,9); гл. I — 2.3 (4). Найти число тех ФАЛ от БП х1,... ,хп, совершенная ДНФ которых является их единственной ДНФ длины 2п-1 и длины 3. Из [5]: гл. IX — 2.1 (3), 2.5 (2,6), 2.6 (2,6).
Семинар 2. Алгебраические методы построения сокращённой ДНФ. Тупиковые ДНФ, ядро и ДНФ пересечение тупиковых. Теоретический материал [1: с. 32-36, 38-41], [5: с. 296-298, 301-303]. В классе. Из [5]: гл.IX — 2.3(1,2), 2.2(1,2), 2.9(3), 2.14(1,2), 3.3(1,2) — построить ядро и ДНФ пересечения тупиковых, 2.12 (3). На дом. Из [5]: гл. IX — 2.3(3,4), 2.2(3,4), 2.9(5), 3.3(3,4) — построить ядро и ДНФ пересечения тупиковых, 2.12 (6), 2.13.
Семинар 3. ДНФ Квайна и ДНФ сумма тупиковых. Таблица Квайна, методы построения всех тупиковых (минимальных, кратчайших) ДНФ. Теоретический материал [1: с. 41-44, 51-55], [5: с. 301-303]. В классе. Из [5]: гл.IX — 3.1 (1,5), 3.3(1,2) — построить ДНФ Квайна и ДНФ суммы тупиковых, 3.4(3), 3.6 (1,4,7). На дом. Из [5]: гл. IX — 3.1 (4,6), 3.3(3,4) — построить ДНФ Квайна и ДНФ суммы тупиковых, 3.4(4), 3.6 (3,6,8).
Семинар 4. Особенности ДНФ для некоторых типов ФАЛ, оценки числа тупиковых (минимальных) ДНФ. Разбор задач к контрольной №1. Теоретический материал [1: с. 44-50, 59-65], [5: с. 301-303]. В классе. Построить совершенную и сокращённую ДНФ ФАЛ f(х1,х2,х3), если известно, что она линейно зависит от БП х1 и Nf ⊇ {(000), (101)}, Nf1 ⊇ {(110), (011)}. Из [5]: гл. IX — 2.9(2). Построить сокращённую ДНФ монотонной ФАЛ 4 переменных, нижними единицами которой являются наборы (0101), (1011), (1100), (0110). Из [5]: гл. IX — 2.12(2), 3.7(2). На дом. Построить совершенную и сокращённую ДНФ ФАЛ 4 переменных, если известно, что она линейно зависит от первых двух БП и Nf ⊇ {(0100), (1001)}, Nf1 ⊇ {(1010), (1111)}. Построить сокращённую ДНФ монотонной ФАЛ 4 переменных, нижними единицами которой являются наборы (1010), (0100), (0011), (1001). Из [5]: гл. IX — 2.9(8), 2.12(8), 3.7(4).
Семинар 5. Контрольная работа №1.
Семинар 6. Эквивалентные преобразования (ЭП) формул. Теоретический материал [1: с. 86-90, 146-161], [4: с. 19]. В классе. Из [4]: 3.1(1), 3.3(1,4), 3.8(1-3). На дом. Из [4]: 3.1(2), 3.3(3,6), 3.8(5-9).
Семинар 7. Задание формул деревьями и СФЭ, оптимизация подобных формул по глубине. Контактные схемы и π-схемы, моделирование формул и π -схем. Теоретический материал [1: гл.2, §§2,5]. В классе.
1.	Для формулы  построить соответствующее ей дерево и квазидерево, а затем перейти от него к более «компактной» СФЭ, применяя операцию «отождествления» максимальных по включению изоморфных квазиподдеревьев до тех пор, пока это возможно
2.	Построить в Б0 формулу минимальной глубины, подобную формуле 
3.	С помощью различных приёмов (просмотр всех наборов, нахождение всех простых проводящих цепей, а также всех тупиковых неединичных сечений) построить таблицу истинности ФАЛ, реализуемых КС, показанными на рис. 10 и 12 из [4].
4.	Построить π-схемы, моделирующие: а) конкретные ДНФ и КНФ; б) «естественную» ДНФ мультиплексорной ФАЛ, полученную разложением Шеннона этой ФАЛ по её адресным переменным (на базе КД); в) совершенную ДНФ ФАЛ f(х1,х2,х3), столбец значений которой имеет вид (01101100) (на базе КД).
На дом. В соответствии с приведёнными выше пунктами 1-4:
1.	
2.	
3.	Рис. 13, 14, 17 из [4].
4.	в) (11011001 01111001).
Семинар 8. Эквивалентные преобразования КС. Теоретический материал [1: с. 169-185]. В классе. Из [4]: 4.1(2,4,6-8). На дом. Из [4]: 4.1 (9-12).
Семинар 9. Эквивалентные преобразования КС (окончание). Теоретический материал [1: с. 169-185]. В классе. Из [4]: 4.3(1).
1. Для заданных эквивалентных КС S', S" от БП Х(п) и m, n построить их ЭП на основе тождеств τm, а затем доказать, что не существует их ЭП основе тождеств τm–1.
а)	m = п = 3, а S' и S'' — КС из задачи 4.1 (9) домашнего задания семианара 7;
б)	m = п = 3, а S' и S'' — π-схемы, моделирующие левую и правую части тождества дистрибутивности дизъюнкции относительно конъюнкции;
в)	m = 2, n = 3, S' — первая (левая) КС из задачи 4.1 (10) домашнего задания семинара 7, а КС S'' получается из второй (правой) КС этой задачи перестановкой контактов х, z и проведением цепи из контактов у, z, соединяющей неполюсные вершины;
г)	m = п = 2, а S' — первая (левая) КС из задачи 4.1 (11) домашнего задания семинара 7, а КС S'' получается из второй (правой) КС этой задачи проведением цепи из контактов х, у, соединяющей полюса 1 и 2.
На дом. Из [4]: 4.3(3). В соответствии с приведённым выше пунктом 1:
1.   а) m = п = 3, а S' и S'' — π-схемы, моделирующие две части формульного тождества
	
б) m = n = 3, а S' и S'' — КС от БП Х(3) с полюсами 1, 2, 3 такие, что в КС S' полюс с номером i, i = 1,2,3, соединён с её единственной внутренней вершиной контактом xi, а в КС S'' он соединён с полюсом j, 0 < i < j < 4, цепочкой контактов xixj.
Семинар 10. Теорема перехода. Эквивалентные преобразования (ЭП) СФЭ с помощью основных тождеств путём моделирования ЭП соответствующих формул. Подготовка к контрольной по второму разделу (контрольная работа №2). В классе. Из [4]: 3.9(1)
1. Вывести формульное тождество t из системы тождеств τ, а затем промоделировать этот вывод в классе СФЭ: 
	
На дом. Из [4]: 3.9(2). В соответствии с приведённым выше пунктом 1:
1. t — тождество обобщённого склеивания, τ — расширенная система основных тождеств.
Семинар 11. Контрольная работа №2.
Семинар 12. Сложность ФАЛ и методы синтеза схем на основе ДНФ. Теоретический материал [1: с. 186-210]. В классе. Из [5]: гл.X — 1.1 (2-4, а также ФАЛ  в классе КС), 2.4(1); доказать минимальность некоторых из построенных в предыдущих задачах схем. На дом. Из [5]: гл.X — 1.1 (5-7), 2.4(2); доказать минимальность некоторых из построенных в предыдущих задачах схем.
Семинар 13. Каскадные КС и инверсные КС, метод каскадов для КС. Метод Шеннона. Теоретический материал [1: с. 186-210]. В классе. Для заданной на рис. 1а каскадной КС построить инверсную к ней КС (К1). Из [5]: гл.X — 2.13(1, 4, 7), 2.14(1), 2.14(2 — с оптимизацией сложности за счёт выбора порядка БП разложения), 2.14(5). Разлагая ФАЛ от 3 или 4 БП по всем БП, кроме последней, построить для неё КС (К2) и СФЭ (КЗ) по методу Шеннона. На дом. Для заданной на рис. 1б каскадной КС построить инверсную к ней КС (Д1). Из [5]: гл.X — 2.13(2, 5, 6), 2.14(3 — с оптимизацией сложности за счёт выбора порядка БП разложения), 2.14(6). Разлагая ФАЛ от 3 или 4 БП по всем БП, кроме последней, построить для неё КС (Д2) и СФЭ (ДЗ) по методу Шеннона.
Семинар 14. Моделирование каскадных КС в классе СФЭ. Метод каскадов и метод Шеннона для СФЭ. Теоретический материал [1: с. 186-210]. В классе. Показанную на рис. 1а каскадную КС промоделировать в классе СФЭ (К1). С помощью метода каскадов построить СФЭ для ФАЛ и систем ФАЛ из [5]: гл.X — 2.13(1, 4, 7), 2.14(1), 2.14(2), 2.14(5). Используя метод Шеннона доказать, что LC(4)  18. На дом. Показанную на рис. 1б каскадную КС промоделировать в классе СФЭ (Д1). С помощью метода каскадов построить СФЭ для ФАЛ и систем ФАЛ из [5]: гл.X — 2.13(2, 5, 6), 2.14(3), 2.14(6). Используя метод Шеннона доказать, что LC(5)  34.
Семинар 15. Асимптотически наилучшие методы синтеза и связанные с ними конструкции. Синтез схем для некоторых ФАЛ. Подготовка к контрольной по третьему разделу курса. Теоретический материал [1, с. 215-240]. В классе.
1.	Выписать таблицу значений ФАЛ стандартного ДУМ порядка 3 и высоты 3 (К1). Построить 2-регулярное разбиение куба В4, на каждой компоненте которого каждая из ФАЛ   моделируется либо БП, либо её отрицанием.
2.	Построить минимальные реализации для ФАЛ  как в классе СФЭ, так и в классе КС.
3.	Повторение материала семинарских занятий:
а)	семинар 10 — построить минимальную (1,1)-КС для ФАЛ 
б)	семинары 12 и 11 (метод каскадов для КС и СФЭ) — с помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по х1, х2, х3, х4, построить (1,2)-КС для системы ФАЛ F = (f1,f2) и СФЭ для ФАЛ f1, где f1 = (0110100010000101),

На дом.
1.	Выписать таблицу значений ФАЛ ДУМ порядка 3, связанного с разбиением куба В3 на 3 подмножества: . Построить 2-регулярное разбиение куба В7, на каждой компоненте которого любая отличная от константы ФАЛ от БП х1, х2 моделируется либо БП, либо её отрицанием.
2.	Построить минимальные реализации для ФАЛ  как в классе СФЭ, так и в классе КС, а также системы ФАЛ  в классе КС.
3.	Повторение материала предыдущих семинарских занятий:
а) построить минимальную (1,1)-КС для ФАЛ 

б)	с помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по х1, х2, х3, х4, построить (1,2)-КС для системы ФАЛ F = (f1,f2) и СФЭ для ФАЛ f1, где f1 = (1001 0110 1001 0111), 
в)	установить асимптотику сложности реализации схемами из функциональных элементов ФАЛ 
Семинар 16. Контрольная работа №3.
Семинар 17. Синтез самокорректирующихся КС. Тесты для таблиц, тесты для контактных схем.  Теоретический материал [4: с. 49-50], [1: с. 65-72, 51-55], [4: с. 32-34, 37-38]. В классе. Из [4]: 7.9(б), 7.10(1), 7.13, 5.1 (1, 2 — все тупиковые диагностические тесты), 5.1 (3 — все тупиковые проверяющие тесты), 6.2, 6.4, 6.11 (если хватит времени). На дом. Из [4]: 7.9(в), 7.10(2), 7.11 (а), 5.1 (5 — все тупиковые диагностические тесты, 6 — все тупиковые проверяющие тесты), 6.3, 6.5, 6.14.
Семинар 18. Контрольная работа №4.

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

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

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

1.	Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальными формами (ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ и критерий единственности ДНФ.
2.	Сокращённая ДНФ и способы её построения.
3.	Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых. ДНФ Квайна, критерий вхождения простых импликант в тупиковые ДНФ и его локальность.
4.	Особенности ДНФ линейных и монотонных ФАЛ. Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ.
5.	Градиентный алгоритм и оценка длины градиентного покрытия, лемма о «протыкающих» наборах. Использование градиентного алгоритма для построения ДНФ.
6.	Задача минимизации ДНФ. Поведение функции Шеннона и оценки типичных значений для ранга и длины ДНФ.
7.	Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с ней параметров. Теорема Ю.И. Журавлёва о ДНФ сумма минимальных.
8.	Формулы, способы их задания и эквивалентные преобразования. Оптимизация подобных формул по глубине.
9.	Эквивалентные преобразования формул с помощью тождеств. Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б0.
10.	Задание формул графами, схемы из функциональных элементов (СФЭ). Оценка числа формул и СФЭ в базисе Б0={&,, }.
11.	Эквивалентные преобразования СФЭ и моделирование с их помощью формульных преобразований. Моделирование эквивалентных преобразований формул и схем в различных базисах, теорема перехода.
12.	Контактные схемы (КС) и π-схемы, оценка их числа. Особенности функционирования многополюсных КС.
13.	Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщённых тождеств.
14.	Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС.
15.	Некоторые модификации и частные случаи основных классов схем (каскадные КС и BDD, КМОП-схемы, вычисляющие программы и др.)
16.	Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями.
17.	Задача синтеза. Методы синтеза схем на основе ДНФ и связанные с ними верхние оценки сложности функций.
18.	Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторых схем.
19.	Разделительные КС и лемма Шеннона. Метод каскадов для КС и СФЭ, примеры его применения. Метод Шеннона.
20.	Нижние мощностные оценки функций Шеннона.
21.	Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б0.
22.	Регулярные разбиения единичного куба и моделирование ФАЛ переменными. Методы синтеза формул в базисе Б0, поведение функции Шеннона для глубины ФАЛ.
23.	Асимптотически наилучший метод синтеза КС. Синтез схем для некоторых дешифраторов и мультиплексоров.
24.	Задача синтеза схем для ФАЛ из специальных классов. Асимптотически оптимальные методы синтеза СФЭ и КС для ФАЛ из некоторых классов.
25.	Схемы на КМОП-транзисторах и реализация ими простейших функций. Задачи логического и топологического синтеза СБИС, основные этапы и методы их решения.
26.	Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание).
27.	Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста.
28.	Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировка теоремы Кука. Примеры NP-полных проблем.
29.	Доказательство теоремы Кука.
 
Типовые задачи к экзамену.

Задачи на ДНФ
1.	По заданной ФАЛ построить её сокращённую ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.
Задачи на эквивалентные преобразования и структурное моделирование
1.	По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств.
2.	По заданной формуле построить подобную ей формулу минимальной глубины.
3.	По заданной формуле с поднятыми отрицаниями построить моделирующую её π схему и обратно.
4.	По данной каскадной КС построить инверсную каскадную КС.
Задачи на синтез схем
1.	По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую её СФЭ или КС.
2.	Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.
Задачи на самокоррекцию и тесты
1.	По заданной КС построить эквивалентную ей самокорректирующуюся КС.
2.	По заданной таблице или КС и списку её неисправностей построить все тупиковые проверяющие (диагностические) тесты.
Задачи на сложность алгоритмов
1.	Построить полиномиальное сведение одного языка к другому.

По результатам тестов и контрольных работ с учетом посещаемости студентов, их работы на лекциях и семинарах, а также самостоятельной работы выставляется предварительная оценка.
Для студентов, имеющих предварительную оценку «5», экзамен проводится в форме собеседования по программе курса на определения, формулировки утверждений и идеи их доказательства, методы решения задач. Для студентов, имеющих предварительную оценку «2», экзамен представляет собой письменный тест-контрольную.
Все остальные студенты (с предварительной оценкой «3-», «3» и «4») получают билет с двумя вопросами и одной задачей и после 15-20 минут подготовки отвечают на него сначала на уровне определений, формулировок утверждений и идей их доказательства, а также методов решения задач. Затем студент, по усмотрению экзаменатора, должен раскрыть те или иные детали доказательства утверждений из вопросов билета по конспектам или иным источникам, а также полностью или частично решить задачу билета в течение выделенного специально для этого времени. Студенты, набравшие не менее 80% от суммы баллов по задачам тестов-контрольных соответствующего раздела, от решения билетной задачи данного типа освобождаются. Последний этап экзамена представляет собой описанное выше собеседование по другим вопросам или задачам программы.
В соответствии с общими правилами итоговая экзаменационная оценка не может превосходить предварительную оценку больше, чем на один балл. Студент, который имеет предварительную оценку «3» или «4» и не претендует на более высокую итоговую оценку, сдаёт экзамен, как правило, по упрощённой процедуре (в форме собеседования по билету и программе без предварительной подготовки) с целью подтверждения этой оценки.

Экзаменационный билет состоит из двух вопросов и задачи, например

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

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

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

ОПК-1.Б	
Знать:
1.	методологию построения и анализа основных моделей, возникающих в рамках теории дискретных управляющих систем и теории алгоритмов;
2.	методы получения оценок и характер роста функций Шеннона сложности и длины ДНФ и функций Шеннона сложности схем (в том числе для некоторых специальных классов функций и для схем с некоторыми связанными с требованиями самокорректирования ограничениями);

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

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

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

ПК-2.Б	

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

Основная литература:

1.	Ложкин С.А. Лекции по основам кибернетики. – М.: МГУ, 2004. (Электронные версии лекций можно найти по адресу http://mk.cs.msu.ru/index.php/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%BA%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8_(2-%D0%B9_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA,_3_%D0%BA%D1%83%D1%80%D1%81)).
2.	Яблонский С.В. Элементы математической кибернетики. – М.: Высшая школа, 2007.
3.	Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2010.
4.	Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011.
5.	Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2004.
6.	Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС. (http://mk.cs.msu.ru/images/8/87/Lozhkin-Marchenko-VSLI-models.pdf)
7.	Алексеев В.Б. Введение в теорию сложности алгоритмов. – М.: Изд-во МГУ, 2002.

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

8.	Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. – М.: МГУ, 2000.
9.	Дискретная математика и математические вопросы кибернетики. – М.: Наука, 1974.
10.	Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – М.: МГУ, 1984.
11.	Нигматуллин Р.Г. Сложность булевых функций. – М.: Наука, 1991.

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

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

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

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

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