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

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________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.	методы синтеза схем для функций из некоторых специальных классов;
8.	методы получения индивидуальных нижних оценок сложности булевых функций из некоторых специальных классов;
9.	методы получения оценок функций Шеннона длин полных тестов для КС.
Уметь:
1.	получать схемные и формульные представления для булевых функций, находить оценки сложности их реализаций;
2.	строить близкие к оптимальным тесты для схем, получать оценки длины миимальных тестов;
3.	применять на практике основные методы теории дискретных управляющих систем;
4.	находить, анализировать и обрабатывать научно-техническую информацию в областях, примыкающих к математической кибернетике.
Владеть: 
1.	основными методами теории управляющих систем для решения научных и прикладных задач;
2.	навыками решения практических задач методами теории управляющих систем;
3.	современной методологией теории управляющих систем для установления новых научных фактов в области математической кибернетики.

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

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

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

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
Асимптотически наилучшие методы синтеза формул, схем из функциональных элементов (СФЭ) и схем проводящего типа в произвольном базисе.	14	14	7	21	14	
Синтез схем для некоторых специальных ФАЛ и оценки их сложности.	16	16	8	24	16	
Некоторые вопросы контроля контактных схем.	6	6	3	9	6	
Промежуточная аттестация: устный экзамен	18	0	0	0	18	
Итого	108	36	18	54	54	

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

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

Контрольные работы по курсу не проводятся.

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

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

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

1.	Формулы и СФЭ в произвольном базисе, функционалы их сложности и основные соотношения между этими функционалами. Верхняя оценка числа формул и СФЭ. См. [1:гл.2,§4], [2:гл.1,§2].
2.	Некоторые модификации контактных схем (КС), итеративные КС (ИКС). Верхние оценки числа схем контактного типа. См. [1:гл.2,§7], [2:гл.1,§1].
3.	Нижние мощностные оценки функции Шеннона для сложности схем контактного типа, для сложности и задержки формул и СФЭ в произвольном базисе. См. [1:гл.4,§4], [2:гл.1,§§1,2].
4.	Универсальные множества ФАЛ и их построение. Асимптотически наилучшие методы синтеза СФЭ в произвольном базисе и ИКС. См. [1:гл.4,§8], [2:гл.1,§§3-5].
5.	Асимптотически наилучший метод синтеза КС и формул в произвольном базисе. См. [1:гл.4,§8], [2:гл.1,§6].
6.	Поведение функции Шеннона для задержки ФАЛ в произвольном базисе. Построение СФЭ асимптотически оптимальных как по сложности, так и по задержке. См. [2:гл.1,§7], [10:§21].
7.	Синтез схем для некоторых дешифраторов и мультиплексоров, оценки их сложности. См. [1:гл.4,§7].
8.	Реализация «больших» систем ФАЛ в классе КС и нижние оценки её сложности. Асимптотика сложности универсального контактного многополюсника. См. [2:гл.2,§1].
9.	Метод забивающих констант и незабиваемые множества переменных ФАЛ. Асимптотика сложности мультиплексора в некоторых классах схем. См. [2:гл.2,§2].
10.	Теорема Храпченко. Сложность реализации линейной и некоторых других ФАЛ в классе π-схем. См. [3:часть I, разд. 2,§1; разд. 3,§2], [2:гл.2,§5].
11.	Сферические ФАЛ. Сложность линейной и других ФАЛ в классе КС и самокорректирующихся КС. См. [3:часть III, разд. 3,§1], [2:гл.2,§4].
12.	Сложность реализации линейной ФАЛ в классе СФЭ. См [2:гл.II,§2], [11:гл.8,§2].
13.	Полный диагностический тест для контактных схем. См. [7:с.132-134].
14.	Верхняя оценка длины полного проверяющего теста для контактных схем. См. [7:с.135-142].
15.	Верхняя константная оценка функции Шеннона длины единичного проверяющего теста при моделировании булевой функции двухполюсными контактными схемами с фиксированной входной избыточностью. См. [12:лемма 1 и теорема 4].
 
Типовые задачи к экзамену.

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

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

1.	Некоторые модификации контактных схем (КС), итеративные КС (ИКС). Верхние оценки числа схем контактного типа.
2.	Полный диагностический тест для контактных схем.
3.	Получить методом Храпченко нижнюю оценку сложности реализации ФАЛ (0110100101101000) в классе π-схем.

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

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

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

ПК-2.Б	

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

Основная литература:
1.	Ложкин С.А. Лекции по основам кибернетики. – М.: МГУ, 2004.
2.	Ложкин С.А. Дополнительные главы кибернетики и теории управляющих систем. (Электронные версии последних лет можно найти по адресу http://
mk.cs.msu.ru/index.php/Дополнительные_главы_кибернетики_и_теории_управляющих_систем )
3.	Яблонский С.В. Элементы математической кибернетики. – М.: Высшая школа, 2007.
4.	Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2010.
5.	Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011.
6.	Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2009.
7.	Редькин Н.П. Надежность и диагностика схем. – М: МГУ, 1992. 192 с.

Дополнительная литература:
8.	Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. – М.: МГУ, 2000.
9.	Дискретная математика и математические вопросы кибернетики. – М.: Наука, 1974.
10.	Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – М.: МГУ, 1984.
11.	Нигматулин Р.Г. Сложность булевых функций. – М.: Наука, 1991.
12.	Романов Д.С., Романова Е.Ю. О единичных проверяющих тестах для схем переключательного типа // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2015, №1. С. 5-23.

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

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

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

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

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