Программа дисциплины Дискретная математика для направления 080500. 62 «Бизнес-информатика»

Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет бизнес-информатики

Программа дисциплины
Дискретная математика

для направления 080500.62 «Бизнес-информатика»

подготовки бакалавра

Автор программы:

Морозенко В.В., к.ф.-м.н., доцент, v.morozenko@mail.ru

Одобрена на заседании кафедры информационных технологий в бизнесе «___»____________ 20 г

Зав. кафедрой О.Л.Викентьева _______________________

Утверждена Учебно-методическим Советом НИУ ВШЭ - Пермь «___»_____________201 г.

Председатель Г.Е. Володина ________________________

Пермь, 2013

Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.

1Область применения и нормативные ссылки

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

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки «Бизнес-информатика»,изучающих дисциплину «Дискретная математика».

Программа разработана в соответствии с:

Образовательным стандартом НИУ ВШЭ для направления 080500.62 «Бизнес-информатика», (протокол от 02.07.2010 г. № 15);

Образовательной программой 080500.62 Бизнес-информатика.

Рабочим учебным планом университета по направлению подготовки 080500.62 Бизнес-информатика, утвержденным в 2012г.

2Цели освоения дисциплины

Целью освоения дисциплины «Дискретная математика»в области обучения является изучение дискретных структур, которые применяются при разработке математических моделей и алгоритмов для решения социально-экономических, информационно-технологических, оптимизационных и вычислительных задач. Аппарат дискретной математики необходим при создании и эксплуатации современных вычислительных систем, средств хранения, обработки и передачи информации, автоматизированных систем управления и проектирования. Содержание программы дисциплины «Дискретная математика» должно обеспечить базовую подготовку студентов в процессе формирования устойчивых теоретических знаний и практических навыков разработки и анализа алгоритмов для дальнейшей учебной, научной и профессиональной деятельности.

Для достижения поставленной цели при изучении дисциплины «Дискретная математика»решаются следующие задачи:

– познакомить студентов с основными дискретными структурами и дискретными математическими моделями;

– познакомить с эффективными алгоритмами для решения наиболее известных задач дискретной математики;

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

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

Курс призван повысить общую эрудицию студентов, дать им возможность ориентироваться в данной предметной области, подготовить к применению теоретических знаний при решении различных задач оптимизации и разработке средств автоматизированной поддержки принятия решений.

3Компетенции обучающегося, формируемые в результате освоения дисциплины

В результате освоения дисциплины студент должен:

Знать:

– основы теории графов;

– основы теории булевых функций;

– элементы комбинаторики;

– основы теории кодирования;

– основы теории конечных автоматов;

– основы логики высказываний и предикатов;

Уметь:

– исследовать графы, находить их основные характеристики и структурные особенности;

– применять основные алгоритмы теории графов;

– представлять булевы функции в виде формул заданного типа;

– проверять множество булевых функций на полноту;

– генерировать и подсчитывать число комбинаторных объектов с заданными свойствами;

– исследовать и строить схемы кодирования, отвечающие заданным требованиям;

– решать задачи анализа, синтеза и минимизации автоматов с заданными свойствами;

– проверять логичность рассуждений, основанных на предикатах.
Иметь навыки (приобрести опыт):

– применения аппарата теории графов для решения прикладных задач;

– применения булевых функций в логическом анализе;

– применения комбинаторных операций и комбинаторных принципов;

– применения методов теории кодирования в области информационных технологий;

– применения основных алгоритмов теории конечных автоматов для решения прикладных задач.

В результате освоения дисциплины студент осваивает следующие компетенции:

Компетенция	Код по ФГОС/ НИУ	Дескрипторы – основные признаки освоения (показатели достижения результата)	Формы и методы обучения, способствующие формированию и развитию компетенции
Владение культурой мышления, способность к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения	ОНК3	Даёт четкие определения основных понятий информатики и программирования, видит их связь. Четко формулирует задачи, анализирует условия и обоснованно выбирает методы решения, уверенно интерпретирует результаты	Аудиторные занятия проводятся в форме, предполагающей активное участие студентов в работе, обсуждение проблем и анализ решений, предлагаемых студентами и преподавателем на лекциях и практических занятиях.
Способность логически верно, аргументировано и ясно строить устную и письменную речь	СЛК-1	Демонстрирует умение обосновывать предлагаемые решения (не только разрабатывать алгоритмы и программы, реализующие их, но и уметь доказывать правильность программ, анализировать и оценивать эффективность решений)	Самостоятельное изучение отдельных тем.
Способность к саморазвитию, повышению своей квалификации и мастерства	СЛК-4	Демонстрирует способность самостоятельно определять формирующиеся дефициты знаний, умений и навыков в ходе обучения. Показывает умение сформулировать проблемы, связанные с недостатком знаний и навыков, и выбрать подходы к их решению	Самостоятельное изучение отдельных тем при подготовке к контрольным мероприятиям
Готовность работать с информацией из различных источников/ Владение основными методами, способами и средствами получения, хранения, переработки информации	ИК- 4 / ИК-5	Показывает навыки уверенного владения средствами поиска информации в Internet, в различных источниках, рекомендованных для самостоятельного изучения. Демонстрирует умение оценивать и отбирать наиболее важную информацию, максимально полезную для решения поставленных задач при выполнении домашних заданий, при подготовке к контрольным мероприятиям	Выполнение заданий с постепенным наращиванием требований к сложности, используемым методам и средствам решения
Способность к организованному подходу к освоению и приобретению новых навыков и компетенций	СЛК -7	Демонстрирует способность применять полученные знания для решения новых задач в различных областях. Владеет навыками самостоятельного поиска, изучения и выбора методов и средств решения поставленных задач. Подготовлен к самостоятельному изучению новых технологий, инструментальных средств разработки программ.	Выполнение заданий с постепенным наращиванием требований к сложности, используемым методам и средствам решения
Использовать соответствующий математический аппарат и инструментальные средства для обработки, анализа и систематизации информации по теме исследования	ПК-22	Уверенно использует способы формального описания алгоритмов с применением математического аппарата. Знает и может использовать на практике математический аппарат, формальные средства, лежащие в основе различных методов разработки алгоритмов и программ. Может построить оценки и доказать свойства алгоритмов и программ с использованием формальных методов	Использование и сравнение формальных средств при изучении основных методов разработки программ и средств алгоритмических языков. Получение формальных оценок и сравнение их с результатами, полученными при практической реализации.

4Место дисциплины в структуре образовательной программы

Настоящая дисциплина относится к математическому и естественнонаучномублоку дисциплин, обеспечивающих базовую подготовку бакалавров.
Изучение данной дисциплины базируется на следующих дисциплинах:

Математический анализ;

Алгебра;

Программирование;

Информатика, математическая логика и теория алгоритмов.

Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями:

понимание основных концепций, принципов, теорий и фактов, связанных с информатикой и программированием;
умение применять основы алгебры, информатики и программирования к разработке алгоритмов;
навыки математического моделирования, анализа сложности и корректности математических моделей.

Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:

Введение в программную инженерию;

Научно-исследовательский семинар «Актуальные проблемы бизнес-информатики»

Компьютерная графика;

Программирование;

Управление данными;

Моделирование процессов и систем;

Оптимизация и математические методы решений;

Нечеткая логика и нейронные системы.

5Тематический план учебной дисциплины

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

6Формы контроля знаний студентов

Тип контроля	Форма контроля	1 год			Параметры
		1	2	3
Текущий (неделя)	Контрольная работа	8 неделя	8 неделя		Письменная работа (80 мин.)
	Домашнее задание			8 неделя	Письменная работа из 10 индивидуальных заданий
Итоговый	Экзамен	3 модуль			Письменный экзамен (90мин.)

6.1Критерии оценки знаний, навыков

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

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

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

6.2Порядок формирования оценок по дисциплине

Оценка за итоговый контроль основывается на результатах выполнения контрольных работ, домашнего задания и экзамена.

Преподаватель оценивает работу студентов на семинарских и практических занятиях: на семинарских занятиях студенты работают по карточкам, на которых указаны практические задания. Работа каждого студента оценивается с учетом количества задач, решенных им во время занятия. Оценки за работу на семинарских и практических занятиях преподаватель выставляет в рабочую ведомость. Оценка по 10-ти балльной шкале за работу на семинарских и практических занятиях определяется перед промежуточным или итоговым контролем и называется - О_{аудиторная}.

Накопленная оценка за текущий контроль учитывает результаты студента по текущему контролю следующим образом:

О_{накопленная}= 2/3*О_{текущий} + 1/3* О_{аудиторная}

где О_{текущий}рассчитывается как взвешенная сумма всех форм текущего контроля, предусмотренных в РУП:

О_{текущий} = n₁·О_к/р + n₂·О_дз,

при этом n₁ = 0,7,n₂ = 0,3.

Способ округления накопленной оценки текущего контроля: арифметический.
Результирующая оценка за дисциплину рассчитывается следующим образом

О_{результирующая} = 0,6* О_{накопленная} + 0,4*·О_{экз/зач}

Способ округления накопленной оценки промежуточного (итогового) контроля в форме зачета: арифметический.

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

На экзамене студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл.

7Содержание дисциплины

Раздел 1.Теория графов

Тема 1. Основные понятия теории графов, способы задания.

Основные определения, понятия, обозначения теории графов: степень вершины, смежность вершин, инцидентность вершин и ребер, удаленность вершины, радиус, диаметр, центр графа. Основные способы задания графов: матрицы смежности и инциденций.

Количество часов аудиторной работы: 4.

Общий объем самостоятельной работы и распределение самостоятельной работы для разных видов подготовки студента: 6 часов.

Тема 2. Типы графов и обходы графов.

Основные типы графов: нулевой, полный, двудольный, связный, дополнительный граф. Основные операции над графами: добавление и удаление вершины, добавление и удаление ребра, отождествление вершин, стягивание графа. Эйлерова цепь, эйлеров цикл, критерии их существования, алгоритм Флери. Гамильтонова цепь, гамильтонов цикл, достаточные условия их существования.

Количество часов аудиторной работы: 4.

Тема 3. Экстремальные задачи на графах.

Критерий двудольности графа, правильная раскраска двудольного графа. Свойства деревьев, нахождение центра, радиуса и диаметра дерева, кодирование деревьев, остовное дерево графа. Задача о минимальном остовном дереве, алгоритмы Прима и Краскала. Задача коммивояжера, «жадный алгоритм». Задача о кратчайшем пути, алгоритм Дейкстры.

Количество часов аудиторной работы: 6.

Общий объем самостоятельной работы и распределение самостоятельной работы для разных видов подготовки студента: 8 часов.

Тема 4. Изоморфизм, планарность, правильная вершинная раскраска.

Изоморфизм, гомеоморфизм, планарность графов, методы установления изоморфизма или неизоморфизма, планарности или непланарности, формула Эйлера, критерий Понтрягина-Куратовского, необходимые признаки планарности. Правильная вершинная и реберная раскраска графов, хроматическое число, «жадный» алгоритм правильной раскраски, хроматический многочлен, его свойства.

Количество часов аудиторной работы: 4.

Литература по разделу:

Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2009, с. 189-290.

Морозенко В.В. Дискретная математика: Учеб.пособие. Пермь: Изд-во ПГУ, 2008, с. 3-45.
Для данного и всех последующих разделов: лекционные занятия проводятся в традиционной форме с изложением нового теоретического материала и примерами типовых задач, при решении которых используется данная теория. На семинарских занятиях студенты работают с карточками, содержащими типовые задачи, ранее рассмотренные на лекции. Каждый студент работает самостоятельно, в своем темпе, наиболее сложные задания разбираются на доске с участием преподавателя. Задачи, которые студенты не успели решить в аудитории, остаются им для самостоятельной работы дома.
Раздел 2. Булевы функции

Тема 5. Элементарные булевы функции, канонические способы задания.

Элементарные булевы функции, способы задания булевых функций, существенные и фиктивные переменные, карты Карно. Разложение булевых функций в полиномы Жегалкина, совершенные дизъюнктивные и совершенные конъюнктивные нормальные формы (СДНФ и СКНФ). Минимизация дизъюнктивных и конъюнктивных нормальных форм с помощью карт Карно.

Количество часов аудиторной работы: 4.

Тема 6. Замкнутые классы булевых функций.

Замкнутые классы самодвойственных, монотонных, линейных функций и функций, сохраняющих 0 и 1. Леммы о функциях, не принадлежащих замкнутым классам.

Количество часов аудиторной работы: 4.

Тема 7.Полные системы булевых функций, базисы.

Примеры полных систем булевых функций и базисов, теорема о двух системах, критерий Поста функциональной полноты, алгоритм проверки системы на полноту.

Количество часов аудиторной работы: 4.

Литература по разделу:

Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2009, с. 79-100.

Морозенко В.В. Дискретная математика: Учеб.пособие. Пермь: Изд-во ПГУ, 2008, с. 45-86.
Раздел 3. Логика высказываний и предикатов

Тема 8. Высказывания, методы проверки логического следования.

Интерпретация составного высказывания, тавтология, противоречие, нейтральное, выполнимое, опровержимое высказывание. Логическое следование, логическая эквивалентность составных высказываний, методы проверки логического следования и логической эквивалентности, сведение к противоречию, сведение к тавтологии.

Количество часов аудиторной работы: 4.

Тема 9. Предикаты, предикатные формулы.

Предметная область, предметные переменные, область истинности предиката, логические операции над предикатами, кванторы. Предикатная формула, интерпретация, модель, общезначимые, противоречивые, выполнимые, опровержимые формулы. Список основных эквивалентностей, методы проверки логического следования и логической эквивалентности для некоторых классов предикатных формул, геометрический смысл кванторов.

Количество часов аудиторной работы: 4.

Тема 10. Метод резолюций в логике предикатов.

Предваренный и нормальный вид предикатной формулы, элиминация кванторов, сколемовские константы и функции. Процедура унификации, унификаторы, метод резолюций, основное правило метода резолюций, резольвента.

Количество часов аудиторной работы: 6.

Литература по разделу:

Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2009, с. 100-134.

Пентус А.Е., Пентус М.Р. Математическая теория формальных языков: Учеб.пособие. – М.: БИНОМ. Лаборатория знаний: Интернет-Университет информационных технологий, 2006.
Раздел 4. Комбинаторика

Тема 11.Основные комбинаторные операции

Основные комбинаторные операции: выборки с возвращением и без возвращения элементов, выборки с упорядочением и без упорядочения элементов, сочетания и размещения, числа сочетаний и размещений.

Количество часов аудиторной работы: 4.

Тема 12.Комбинаторные принципы

Основные комбинаторные принципы: принцип сложения, принцип умножения, принцип дополнения, принцип включения-исключения, принцип кодирования.

Количество часов аудиторной работы: 4.

Тема 13.Биномиальная и полиномиальная формулы

Треугольник Паскаля, бином Ньютона, биномиальные коэффициенты, их основные свойства. Полиномиальная формула.

Количество часов аудиторной работы: 4.

Тема 14.Рекуррентные соотношения

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

Количество часов аудиторной работы: 4.

Литература по разделу:

Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2009, с. 134-159.

Морозенко В.В. Дискретная математика: Учеб.пособие. Пермь: Изд-во ПГУ, 2008, с. 86-127.
Раздел 5. Кодирование

Тема 15.Однозначно декодируемые схемы алфавитного кодирования.

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

Количество часов аудиторной работы: 4.

Тема 16.Экономное кодирование, коды с минимальной избыточностью.

Избыточность схемы кодирования, частотные характеристики алфавита, схемы с минимальной избыточностью, коды Хаффмана.

Количество часов аудиторной работы: 4.

Тема 17.Помехоустойчивое кодирование, самокорректирующиеся коды.

Двоичные равномерные коды, расстояние Хэмминга, кодовое расстояние, линейные коды, способы их задания, свойства, двойственные коды. Проблема защиты каналов связи, помехоустойчивые схемы кодирования, коды Хэмминга. Методы сжатия информации, алгоритм Лемпеля-Зива.

Количество часов аудиторной работы: 6.

Литература по разделу:

Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2002, с. 159-189.

Морозенко В.В. Дискретная математика: Учеб.пособие. Пермь: Изд-во ПГУ, 2008, с. 127-154.
Раздел 6. Теория автоматов

Тема 18.Конечные детерминированные автоматы, способы задания.

Схема абстрактного конечного автомата, принципы его функционирования, способы задания: таблицей и диаграммой Мура. Автоматы-распознаватели и автоматы-преобразователи, автоматы Мура, автоматы Мили, автоматы-генераторы.

Количество часов аудиторной работы: 4.

Тема 19.Регулярные выражения, распознавание регулярных языков.

Слова и языки, операции над ними: сложение, умножение, итерация, дополнение. Регулярные выражения и регулярные языки, теорема Клини.

Количество часов аудиторной работы: 4.

Тема 20.Задачи анализа, синтеза и минимизации автоматов.

Задача анализа автомата-распознавателя, алгоритм для решения задачи анализа, представление распознаваемого языка в виде регулярного выражения. Задача синтеза автомата-распознавателя по заданному регулярному выражению, детерминированные двухполюсные источники, замкнутые множества состояний источника, преобразование источника в автомат. Эквивалентные автоматы, эквивалентные состояния автомата, задача минимизации автоматов-распознавателей и автоматов-преобразователей, алгоритм Мили для решения задачи минимизации.

Количество часов аудиторной работы: 4.

Тема 21.Логические автоматы.

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

Количество часов аудиторной работы: 4.

Литература по разделу:

Морозенко В.В. Дискретная математика: Учеб.пособие. Пермь: Изд-во ПГУ, 2008, с. 154-204.

8Образовательные технологии

8.1Методические рекомендации преподавателю

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

8.2Методические указания студентам

На семинарских занятиях рекомендуется работа по индивидуальным карточкам, содержащим задания по соответствующим разделам учебного курса. Задания, которые не были решены на семинаре, должны быть решены самостоятельно дома.

9Оценочные средства для текущего контроля и аттестации студента

9.1Тематика заданий текущего контроля

Примерные задания для контрольной работы:

Контрольная работа №1. Графы

Работа состоит из 6 заданий:

для графа, заданного изображением на плоскости, требуется найти центр, радиус и диаметр, а также построить эйлерову цепь или эйлеров цикл (указание: использовать алгоритм Флери);
для графа, заданного матрицей расстояний, требуется построить минимальное остовное дерево, а также найти кратчайшие пути от фиксированной вершины до всех остальных вершин графа (указание: использовать алгоритмы Прима/Краскала и Дейкстры);
для дерева, заданного двоичным кодом, требуется найти центр, радиус и диаметр (указание: использовать помечивающий алгоритм для деревьев);
требуется выяснить – изоморфны ли графы, заданные изображениями на плоскости (указание: в случае неизоморфности графов найти инвариант, подтверждающий различие графов, в случае изоморфности указать хотя бы одно соответствие между множествами вершин, сохраняющее их смежность);
для графа, заданного матрицей инциденций, построить дополнительный граф, доказать его планарность, найти его число граней и хроматическое число (указание: для доказательства планарности достаточно нарисовать граф на плоскости без пересечения ребер; число граней можно найти по формуле Эйлера; для поиска хроматического числа сначала применить «жадный» алгоритм, а затем выделить в графе максимальный полный подграф);
для заданного комплекса работ требуется составить график выполнения работ в кратчайшие сроки и список критических работ (указание: представить комплекс работ в виде взвешенного орграфа, применить к нему алгоритм Демукрона, а затем заполнить таблицу, содержащую наиболее ранние и наиболее поздние сроки начала и окончания работ).

Контрольная работа №2. Комбинаторика. Кодирование

Работа состоит из 8 заданий:

для заданной схемы алфавитного кодирования требуется найти слово, допускающее неоднозначное декодирование (указание: применить алгоритм Маркова);
для заданного набора частот встречаемости букв исходного алфавита требуется построить префиксный или суффиксный код с минимальной избыточностью в двухбуквенном кодирующем алфавите (указание: применить метод Хаффмана);
для слова кода Хэмминга, полученного на выходе канала связи, требуется найти разряд, в котором произошла одиночная ошибка (указание: по известным формулам вычислить контрольные суммы, а затем сложить номера нечетных сумм);
для линейного кода, заданного порождающей матрицей, требуется найти кодовое расстояние, порождающую матрицу и характеристическую функцию двойственного кода (указание: составить и решить систему булевых уравнений);
текстовая задача на вычисление числа комбинаторных объектов (указание: применить комбинаторный принцип умножения и формулу для числа сочетаний или размещений);
текстовая задача на вычисление числа комбинаторных объектов (указание: применить комбинаторный принцип сложения и формулу для числа сочетаний или размещений);
текстовая задача на вычисление числа комбинаторных объектов (указание: применить комбинаторный принцип включения-исключения);
требуется найти слагаемое с определенными свойствами, получающееся после возведения в высокую степень заданного трехчлена (указание: применить полиномиальную формулу).

Примерные задания для домашнего задания:

Привести текстовый пример составного высказывания, состоящего из двух простых высказываний, которое:

а) является тавтологией;

б) является противоречием;

в) является нейтральным высказыванием.

Составное высказывание задано формулой.

а) составить таблицу истинности;

б) нарисовать карту Карно;

в) написать СДНФ;

г) нарисовать диаграмму Эйлера-Венна.

Является ли высказывание P, заданное формулой, логическим следствием высказывания Q?

а) проверить сведением к тавтологии;

б) проверить сведением к противоречию;

в) проверить, используя диаграмму Эйлера-Венна.

Является ли составное высказывание В логическим следствием из высказыванияА?
Является ли противоречием данное составное высказывание?
Решить логическую задачу.
Привести текстовые примеры одноместного и двуместного предикатов, которые

а) общезначимы;

б) противоречивы;

в) нейтральны.

Нарисовать область истинности заданного

а) одноместного предиката Р(х);

б) двуместного предиката Q(x,y).

Является ли предикатное высказывание истинным?
Является ли предикатная формула В с квантором логическим следствием из предикатной формулыА?

9.2Вопросы для оценки качества освоения дисциплины

Примерный перечень вопросов к экзамену:

Основные понятия теории графов, удаленность вершины, центр, радиус и диаметр графа.
Способы задания графов, свойства матриц смежности и инциденций, теорема о рукопожатиях.
Основные операции над графами, неравенства для числа вершин, ребер и компонент связности графа.
Типы графов, дополнительные графы, двудольные графы, критерий двудольности.
Обходы графов: эйлеровы цепи и циклы, необходимые и достаточные условия их существования, алгоритм Флери.
Обходы графов: гамильтоновы цепи и циклы, достаточные условия их существования.
Деревья, их свойства, кодирование деревьев, остовные деревья.
Экстремальные задачи теории графов: минимальное остовное дерево, алгоритмы Прима и Краскала.
Экстремальные задачи теории графов: задача коммивояжера, «жадный» алгоритм
Экстремальные задачи теории графов: задача о кратчайшем пути, алгоритм Дейкстры.
Изоморфизм и гомеоморфизм графов, методы доказательства изоморфности и неизоморфности графов.
Плоские укладки графов, планарные графы, критерий Понтрягина-Куратовского.
Необходимые условия планарности, формула Эйлера для планарных графов.
Правильные вершинные раскраски графов, хроматическое число, неравенства для хроматического числа.
Теорема о пяти красках, гипотеза четырех красок, «жадный» алгоритм.
Хроматический многочлен, его нахождение и свойства.
Задача о поиске выхода из лабиринта, реберная раскраска графа.
Ориентированные графы, источники и стоки, топологическая сортировка, алгоритм Демукрона.
Составление расписания выполнения комплекса работ в кратчайшие сроки методами теории графов.
Элементарные булевы функции и способы их задания (табличный, векторный, формульный, графический, карта Карно).
Существенные и фиктивные переменные булевых функций, основные тождества, эквивалентные преобразования формул.
Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом неопределенных коэффициентов.
Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом эквивалентных преобразований.
Разложение булевых функций в СДНФ и СКНФ.
Минимизация ДНФ и КНФ методом эквивалентных преобразований.
Минимизация ДНФ и КНФ с помощью карт Карно.
Замкнутые классы булевых функций Т₀, Т₁, L, лемма о нелинейной функции.
Замкнутые классы булевых функций S и М, леммы о несамодвойственной и немонотонной функции.
Полная система функций, теорема о двух системах булевых функций.
Теорема Поста о полноте системы булевых функций, алгоритм проверки системы на полноту, базис.
Схемы из функциональных элементов, правила построения и функционирования, метод синтеза СФЭ, основанный на СДНФ и СКНФ.
Метод синтеза СФЭ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника, сложность получаемых схем.
Основные комбинаторные операции, сочетания и размещения (с возвращением и без возвращения элементов).
Комбинаторные принципы сложения, умножения, дополнения, включения-исключения.
Биномиальные коэффициенты, их свойства, бином Ньютона.
Треугольник Паскаля, полиномиальная формула.
Однородные линейные рекуррентные соотношения, примеры, методы решения.
Неоднородные линейные рекуррентные соотношения, примеры, методы решения.
Алфавитное кодирование: необходимое и достаточные условия однозначности декодирования.
Алфавитное кодирование: теорема Маркова, алгоритм Маркова.
Коды с минимальной избыточностью (коды Хаффмана), метод построения.
Линейные коды, порождающая матрица, двойственный код.
Самокорректирующиеся коды (коды Хэмминга), метод построения.
Определение, схема и функционирование абстрактного автомата, способы задания автоматов.
Типы конечных автоматов, автоматы Мили и Мура, автоматы-генераторы.
Слова и языки, операции над ними, их свойства.
Регулярные выражения и регулярные языки, теорема Клини.
Задача анализа автоматов-распознавателей.
Задача синтеза автоматов-распознавателей.
Эквивалентные состояния автомата-распознавателя, эквивалентные автоматы-распознаватели, минимизация автоматов-распознавателей, алгоритм Мили.
Эквивалентные состояния автомата-преобразователя, эквивалентные автоматы- преобразователи, минимизация автоматов- преобразователей, алгоритм Мили.
Детерминированные и недетерминированные функции, примеры, способы задания.
Ограниченно-детерминированные (автоматные) функции, способы их задания.
Логические автоматы, способы их задания, синтез двоичного сумматора.
Операции над логическими автоматами: суперпозиция и введение обратной связи.
Простые и составные высказывания.
Методы проверки логического следования в логике высказываний: сведение к тавтологии или к противоречию, метод резолюций.
Предикаты и предикатные формулы.
Кванторы, их геометрическаяинтрепретация.
Метод резолюций проверки логического следования в логике предикатов.

9.3Примеры заданий итогового контроля

Примеры задач итогового контроля:

Какие переменные являются существенными, а какие – фиктивными для функции ?
Разложить в совершенную ДНФ и КНФ функцию
Найти минимальную ДНФ и КНФ булевой функции .
Решить систему булевых уравнений

Каким из 5 замкнутых классов T₀, T₁, L, S и M принадлежит функция ?
Функцию доопределить так, чтобы она сохраняла 0 и была самодвойственной.
Написать полином Жегалкина для булевой функции .
Полна ли система функций . Является ли она базисом?
Сколько булевых функций от n аргументов содержится во множестве ?
Найти центр и диаметр корневого дерева, заданного кодом: (001 011 000 110 101 101).
Является ли планарным граф, заданный своей матрицей смежности? Ответ обосновать.
Изоморфны ли графы:
Найти кратчайшие пути от вершины 1 до остальных вершин, графа, заданного матрицей расстояний.
Вычислить хроматическое число и найти хроматический многочлен графа, заданного своей матрицей инциденций:
Построить минимальное остовное дерево графа, заданного матрицей расстояний:
Найти кратчайшие пути от вершины 1 до остальных вершин, графа, заданного матрицей расстояний.
Связь между работами, входящими в состав проекта, задана таблицей. Требуется:

а) нарисовать сетевой график проекта;

б) составить список «критических» работ.

Наименование работы	Предшествующие работы	Длительность работы
A	С, E	3
B	F	4
C	F	5
D	A, G	2
E	F	4
F	––	3
G	B, C, E	6

Используя алгоритм Маркова, для схемы кодирования ={01, 10, 103, 1033, 31001} найти слово, допускающее неоднозначное декодирование.
Построить префиксный код с длинами кодовых слов 1,1,2,2,2,2,2 в алфавите, содержащем минимальное количество букв.
Построить суффиксный код Хаффмана в алфавите {0,1} для набора частот {0.08, 0.12, 0.1, 0.25, 0.15, 0.3}. Вычислить избыточность полученной схемы. Какова была бы минимальная избыточность равномерной схемы в том же алфавите для заданного набора частот?
Слово (010 111 010) требуется отправить по каналу связи, используя код Хэмминга. Сколько контрольных разрядов надо добавить и что нужно в них записать?
На выходе канала связи получено кодовое слово Хэмминга (100 110 100 111). Какое сообщение было отправлено?
Найти коэффициент при x6 в выражении (3+5x-2x3)10.
Сколько существует семизначных чисел, делящихся на 5, в которых все цифры различны?
В течение 5 дней нужно провести 11 матчей. Сколько существует различных расписаний, согласно которым каждый день должен состояться хотя бы один матч?
Каждый из 20 спортсменов выстрелил по одному разу в крупную, среднюю и мелкую мишень. Известно, что в мелкую мишень попали 6 человек, в среднюю – 10 человек, в крупную – 16 человек, в мелкую и среднюю – 2 человека, в мелкую и крупную – 5 человек, в среднюю и крупную – 8 человек, а во все три мишени – 1 человек. Сколько человек не попало ни в одну из мишеней? Сколько человек попало только в среднюю мишень?
Сколько существует трехзначных автомобильных номеров, в которых ровно 2 цифры совпадают?
Выписать все слова длины 3, принадлежащие языку, заданному регулярным выражением .
Построить конечный автомат, распознающий все слова в алфавите {a,b,c}, кроме слов ac и bac.
Нарисовать диаграмму Мура функции, заданной системой уравнений:
В автомате ввели обратную связь по переменным .

Написать каноническую таблицу полученного автомата.

10Учебно-методическое и информационное обеспечение дисциплины

10.1Базовый учебник

Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2009.

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

Морозенко В.В. Дискретная математика: Учеб.пособие. Пермь: Изд-во ПГУ, 2008.
Пентус А.Е., Пентус М.Р. Математическая теория формальных языков: Учеб.пособие. – М.: БИНОМ. Лаборатория знаний: Интернет-Университет информационных технологий, 2006.
Шапорев С.Д. Дискретная математика: Курс лекций и практических занятий : учеб.пособие для вузов. – СПб.: BVH-Санкт-Петербург, 2006.

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

Акимов О.Е. Дискретная математика: логика, группы, графы. 2-е изд., дополн. М.: Лаборатория Базовых Знаний, 2001.
Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2000.
Горбатов В.А. Фундаментальные основы дискретной математики. М.: Физматлит, 2000.

10.4Справочники, словари, энциклопедии

Справочная книга по математической логике: В 4-х частях/ Под ред. Барвайса Дж.- Ч.III. Теория рекурсии. М.: Наука, 1982.

10.5Программные средства

Не предусмотрены.

10.6Дистанционная поддержка дисциплины

Использование системы LMS

11Материально-техническое обеспечение дисциплины

Не требуется.