Похожие работы
Название работы |
Кол-во страниц |
Размер |
Программа дисциплины для направления 010400. 62 «Прикладная математика...
|
1 |
247.67kb. |
Программа дисциплины Web-графы и поиск для направления 010400.
|
1 |
67.13kb. |
Программа дисциплины Прогнозирование временных рядов для направления...
|
1 |
142.57kb. |
Программа дисциплины Безопасность информационных сетей для направления...
|
1 |
208.14kb. |
Программа дисциплины Комплексный анализ для направления 010400.
|
1 |
141.49kb. |
Программа дисциплины Уравнения математической физики для направления...
|
1 |
196.95kb. |
Программа дисциплины Современная прикладная алгебра для направления...
|
1 |
189.55kb. |
Программа дисциплины и управление жизненным циклом для направления...
|
1 |
332.6kb. |
Рабочая программа учебной дисциплины Для подготовки бакалавров направления...
|
1 |
374.55kb. |
Программа дисциплины Алгоритмы и структуры данных для направления...
|
1 |
223.78kb. |
Программа дисциплины [Введите название дисциплины] для направления/...
|
1 |
319.25kb. |
Задача нерегулярного размещения геометрических объектов
|
1 |
85.13kb. |
Викторина для любознательных: «Занимательная биология»
|
1 |
9.92kb. |
|
Программа дисциплины Дискретная математика для направления 010400. 68 «Прикладная - страница №1/1
Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
«Национальный исследовательский университет
«Высшая школа экономики»
Факультет БИЗНЕС-ИНФОРМАТИКИ
Отделение ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
Программа дисциплины
Дискретная математика
для направления 010400.68 « Прикладная математика и информатика» подготовки магистров
Автор - Большакова Е.И. (eibolshakova@hse.ru)
Рекомендована секцией УМС
«Прикладная математика
и информатика»
Председатель
__________________ Кузнецов С.О.
«_____» __________________ 20___ г.
|
Одобрена на заседании кафедры
Анализа данных
и искусственного интеллекта
Зав. кафедрой
__________________ Кузнецов С.О.
«_____» __________________ 20___ г.
|
Утверждена УС факультета
бизнес-информатики
Ученый секретарь
__________________ Фомичев В.А.
« ____» ___________________20___ г.
|
|
Москва
I.Пояснительная записка
Автор программы
кандидат физико-математических наук, доцент Е.И. Большакова.
Требования к студентам
Специфические требования отсутствуют. Студенты должны быть готовы к восприятию сжатого систематизирующего блока, построенного на основе дисциплины «Дискретная математика» направления 010400.62 «Прикладная математика и информатика».
Аннотация
Адаптационный курс «Дискретная математика» предназначен для поддержки магистров первого года обучения по направлению 010400.68 «Прикладная математика и информатика», недостаточно знающих те разделы дискретной математики, которые являются базовыми для освоения дисциплин магистерской программы «Математическое моделирование».
В курсе излагаются базовые понятия теории множеств, алгебры логики и логических исчислений, теории графов и комбинаторики. Рассматриваются также отдельные вопросы сложности вычислений.
Учебные задачи курса
Данный адаптационный курс призван систематизировать знания по базовым разделам дискретной математики. В результате изучения дисциплины студенты должны:
-
Знать базовые понятия дискретной математики и связанные с ними основополагающие утверждения, знать основные подходы к оценке сложности вычислений;
-
Понимать особенности дискретных объектов и логических теорий, различать функции и отношения, графы и деревья;
-
Уметь математически корректно обозначать объекты дискретной математики и записывать логические формулы; определять общие свойства множеств, функций, отношений; вычислять число комбинаторных объектов, проводить доказательства методом математической индукции.
II.Тематический план дисциплины
«Дискретная математика»
№
|
Название темы
|
Всего часов по дисциплине
|
Аудиторные часы
|
Самосто-ятельная работа
|
Лекции
|
Сем. и практика занятия
|
1
|
Множества, отношения, функции
|
20
|
2
|
2
|
16
|
2
|
Булевы функции и алгебра логики
|
14
|
1
|
1
|
12
|
3
|
Комбинаторика
|
14
|
1
|
1
|
12
|
4
|
Логические исчисления
|
30
|
2
|
3
|
25
|
5
|
Графы и деревья
|
17
|
1
|
1
|
15
|
6
|
Сложность вычислений
|
13
|
1
|
0
|
12
|
|
Итого
|
108
|
8
|
8
|
92
|
III.Источники информации
Базовый учебник
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб: Питер, 2009. Главы 1, 3, 4, 5, 7, 9.
Основная литература
-
Кузнецов О.П. Дискретная математика для инженера. 6-е изд. – СПб: Издательство «Лань», 2009.
-
Кук В., Бейз Г. Компьютерная математика. – М: Наука, 1990.
-
Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. – 2-е изд. – М.: ФИЗМАТЛИТ, 2004.
Дополнительная литература
-
Абрамов С.А. Лекции о сложности алгоритмов. – М.: Изд-во МЦНМО, 2009.
-
Виленкин Н.Я. Популярная комбинаторика – М.: Наука, 1975.
-
Галушкина Ю.И.. Марьямов А.Н. Конспект лекций по дискретной математике. 2-е изд., испр. – М.: Айрис-пресс, 2008.
-
Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: пер. с нем. / Под ред. Б.Ф.Мельникова. – СПб.: БХВ-Петербург, 2010.
-
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
-
Зыков А.А. Основы теории графов. – М. : Вузовская книга, 2004. – 664 с.
-
Набебин А.А., Кораблин Ю.П. Математическая логика и теория алгоритмов. – Научный мир, 2008. – 343 с.
-
Липский В. Комбинаторика для программистов. – М. : Мир, 1988. – 213 с.
-
Спирина М.С., Спирин П.А. Дискретная математика – М.: Академия, 2009.
IV.Формы контроля и структура итоговой оценки
Текущий контроль в РУП не предусмотрен.
Итоговый контроль – зачёт в форме письменного теста (100 минут) в конце первого модуля.
Тест включает 15 заданий (вопросов и задач0, за решение каждого задания выставляются баллы в интервале от 0 до 4.
Итоговая оценка по курсу высчитывается по формуле:
Оитоговая = Сбаллов / Смаксимальная 10
и округляется до целого числа,
где Сбаллов – общая сумма баллов за решенные студентом задания,
Смаксимальная – максимально возможное число баллов за весь тест.
Таблица соответствия оценок по десятибалльной и системе зачет/незачет
Оценка по 10-балльной шкале
|
Оценка по 5-балльной шкале
|
1
|
незачет
|
2
|
3
|
4
|
зачет
|
5
|
6
|
7
|
8
|
9
|
10
|
Таблица соответствия оценок по десятибалльной и пятибалльной системе
По десятибалльной шкале
|
По пятибалльной системе
|
1 – неудовлетворительно
2 – очень плохо
3 – плохо
|
неудовлетворительно – 2
|
4 – удовлетворительно
5 – весьма удовлетворительно
|
удовлетворительно – 3
|
6 – хорошо
7 – очень хорошо
|
хорошо – 4
|
8 – почти отлично
9 – отлично
10 – блестяще
|
отлично – 5
|
V.Программа курса «Дискретная математика»
Тема 1. Множества, отношения, функции
1. Элементы и множества, задание множеств. Сравнение множеств, мощность множества. Операции над множествами, свойства операций. Алгебра множеств. Булеан. Разбиения и покрытия. Множества и кортежи. Декартово произведение множеств.
2. Бинарные и многоместные отношения. Обратное отношение, композиция отношений, степень отношения. Свойства отношений: рефлексивность, симметричность, антисимметричность, транзитивность, линейность. Отношение эквивалентности, классы эквивалентности, фактор-множество. Отношение порядка. Замыкание отношений.
3. Функциональные отношения. Свойства функций: инъективность, сюръективность, биективность. Монотонные функции. Обратная функция, суперпозиция функций.
Основная литература
-
Кузнецов О.П. Дискретная математика для инженера. 6-е изд. – СПб: Издательство «Лань», 2009.
-
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб: Питер, 2009.
Дополнительная литература
-
Кук В., Бейз Г., Компьютерная математика – М: Наука, 1990.
-
Спирина М.С., Спирин П.А. Дискретная математика – М.: Академия, 2009.
-
Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс матиематической логики. – 2-е изд. – М.: ФИЗМАТЛИТ, 2004
Тема 2. Булевы функции и алгебра логики
1. Таблицы истинности булевых функций. Существенные и несущественные переменные. Элементарные функции алгебры логики. Законы алгебры логики.
2. Реализация функций формулами, равносильные формулы. Равносильные преобразования формул, алгебра булевых функций. Булевы алгебры. Замыкание множества булевых функций, замкнутые и полные классы.
3. Дизъюнктивная и конъюнктивная нормальные формы. Совершенные нормальные формы и их построение.
Основная литература
-
Кузнецов О.П. Дискретная математика для инженера. 6-е изд. – СПб: Издательство «Лань», 2009.
-
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб: Питер, 2009.
Дополнительная литература
-
Галушкина Ю.И.. Марьямов А.Н. Конспект лекций по дискретной математике. 2-е изд., испр. – М.: Айрис-пресс, 2008.
-
Кук В., Бейз Г., Компьютерная математика – М: Наука, 1990.
-
Набебин А.А., Кораблин Ю.П. Математическая логика и теория алгоритмов. – Научный мир, 2008. – 343 с.
-
Спирина М.С., Спирин П.А. Дискретная математика – М.: Академия, 2009.
Тема 3. Комбинаторика
1. Комбинаторика множеств, кортежей, мультимножеств. Правило суммы и правило произведения для количества комбинаторных конфигураций. Формула включений и исключений.
2. Перестановки, перестановки с повторениями. Размещения и сочетания с повторениями и без повторений. Биномиальные коэффициенты. Разбиения, числа Стирлинга первого и второго рода. Число Белла.
Основная литература
-
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб: Питер, 2009.
Дополнительная литература
-
Виленкин Н.Я. Популярная комбинаторика – М.: Наука, 1975.
-
Липский В. Комбинаторика для программистов. – М. : Мир, 1988. – 213 с.
-
Спирина М.С., Спирин П.А. Дискретная математика – М.: Академия, 2009.
Тема 4. Логические исчисления
1. Формализация утверждений и рассуждений, аксиоматизация математических теорий. Понятие формальной теории: алфавит, правила построения формул, аксиомы, правила вывода. Выводимость формул, теоремы. Интерпретация формальной теории. Выполнимые и общезначимые формулы. Логическое следствие, логическая эквивалентность. Свойства теории: непротиворечивость, полнота, разрешимость.
2. Исчисление высказываний (ИВ): пропозициональные переменные, логические связки, формулы. Аксиомы и правила вывода классического исчисления высказываний. Теоремы ИВ и производные правила вывода. Свойства ИВ.
3. Исчисление предикатов первого порядка (ИП): функциональные и предикатные символы, предметные константы, логические связки и кванторы. Термы и формулы ИП. Свободные и связанные переменные. Аксиомы и правила вывода узкого ИП. Интерпретация ИП, свойства ИП. Логические законы. Формальная арифметика, теорема Геделя о неполноте.
4. Правила логического вывода и математические доказательства. Прямая, обратная теорема и теорема, противоположная обратной. Принцип математической индукции. Простая и строгая индукция для натуральных чисел. Обобщенная индукция для вполне упорядоченных множеств.
Основная литература
-
Кузнецов О.П. Дискретная математика для инженера. 6-е изд. – СПб: Издательство «Лань», 2009.
-
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб: Питер, 2009.
-
Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс матиематической логики. – 2-е изд. – М.: ФИЗМАТЛИТ, 2004
Дополнительная литература
-
Набебин А.А., Кораблин Ю.П. Математическая логика и теория алгоритмов. – Научный мир, 2008. – 343 с.
-
Галушкина Ю.И.. Марьямов А.Н. Конспект лекций по дискретной математике. 2-е изд., испр. – М.: Айрис-пресс, 2008.
-
Спирина М.С., Спирин П.А. Дискретная математика – М.: Академия, 2009.
Тема 5. Графы и деревья
1. Вершины и ребра графа, смежность и инцидентность. Изоморфизм графов. Маршруты, цепи, циклы. Подграфы. Связность графа, компоненты связности. Полные, ациклические и двудольные графы. Эйлеровы и Гамильтоновы циклы. Планарность графа.
2. Графы и бинарные отношения. Матрица смежности и матрица связности.
3. Деревья, их основные свойства. Свободные, ориентированные и упорядоченные деревья. Поддеревья. Бинарные деревья. Схемы обхода деревьев.
Основная литература
-
Кузнецов О.П. Дискретная математика для инженера. 6-е изд. – СПб: Издательство «Лань», 2009.
-
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб: Питер, 2009.
Дополнительная литература
-
Галушкина Ю.И.. Марьямов А.Н. Конспект лекций по дискретной математике. 2-е изд., испр. – М.: Айрис-пресс, 2008.
-
Зыков А.А. Основы теории графов. – М. : Вузовская книга, 2004. – 664 с.
-
Спирина М.С., Спирин П.А. Дискретная математика – М.: Академия, 2009.
Тема 6. Сложность вычислений
1. Временная сложность алгоритмов и сложность по памяти. Сложность вычислений в худшем случае, понятие о сложности в среднем. Асимптотические оценки сложности. Задачи распознавания языков.
2. Линейная и полиномиальная сводимость задач. Классы P и NP, их соотношение. NP-полнота, примеры NP-полных задач.
Основная литература
-
Кузнецов О.П. Дискретная математика для инженера. 6-е изд. – СПб: Издательство «Лань», 2009.
Дополнительная литература
-
Абрамов С.А. Лекции о сложности алгоритмов. – М.: Изд-во МЦНМО, 2009.
-
Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: пер. с нем. / Под ред. Б.Ф.Мельникова. – СПб.: БХВ-Петербург, 2010.
-
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
VI.Тематика заданий по итоговому контролю
Примеры задач, предлагаемых в письменном тесте
-
Определить свойства (рефлективность, симметричность, антисимметричность, транзитивность) отношения R:
R = { (x, y): x, y – натуральные числа, x = y2 };
-
Пусть R – множество вещественных чисел, и Q – отношение на R R, определенное следующим образом: (x,y) Q (v,w) тогда и только тогда, когда x < v и y <w . Является ли Q отношением порядка? Если да, то является ли этот порядок полным?
-
Для булевой функции, заданной формулой z (x y), построить таблицу истинности, а также эквивалентную совершенную дизъюнктивную нормальную форму.
-
Найти количество булевых функций от n переменных, среди которых k – фиктивных.
-
Последовательность высказываний {An} , n 1 определена рекуррентным соотношением:
An = An-1 (An-2 An-3) при n > 3; высказывания A1 и A3 истинны, а А2 – ложно.
Истинно или ложно высказывание An ? Выразить An через A1, A2 и A3 , доказать эту формулу математической индукцией, указав применяемую версию индукции.
-
При каких условиях запись c ( P( S(c, R(y, q), q)) f W(z, f) ) является формулой исчисления предикатов первого порядка (ИП)?
-
Последовательность {xn} называется ограниченной, если существует такое число C, что |xn| < C для всех n . Дайте определение неограниченной последовательности.
-
Отношение R из задачи 1 определено на множестве чисел {2, 3, 4, 6, 7, 8, 9}. Построить соответствующий граф отношения.
-
Сколько существует различных графов с n вершинами?
-
Приведите пример двух неизоморфных свободных деревьев с 5 узлами и двух неизоморфных ориентированных (корневых) деревьев с 7 узлами.
-
Сколько различных цепочек (последовательностей букв) можно составить из букв слова метаматематика? (Достаточно указать формулу подсчета).
-
70 студентов курса изучают английский язык, 50 – немецкий, 40 – французский. Известно, что 30 студентов изучают английский и немецкий языки, 20 студентов – английский и французский, 15 – немецкий и французский, а 10 студентов изучают все три языка. Определить число студентов, изучающих хотя бы один из указанных языков.
VII.Вопросы для оценки качества освоения дисциплины
Тема 1.
-
Что такое множество? Какими способами можно задать множество?
-
Укажите основные свойства операций над множествами.
-
Что такое разбиение множества?
-
Чем кортеж отличается от множества?
-
Что такое отношение? Степень отношения?
-
Чем асимметричность отличается от антисимметричности?
-
Какими свойствами обладает отношение эквивалентности?
-
Какими свойствами обладает отношение линейного порядка?
-
Что такое инъективная функция? Сюръективная функция? Биективная функция?
Тема 2.
-
Какие функции называют булевыми?
-
Укажите основные законы алгебры логики.
-
Какие формулы алгебры логики называются равносильными? Какие равносильные преобразования вы знаете?
-
Что такое дизъюнктивная и конъюнктивная нормальная форма?
-
Как привести формулу к совершенной нормальной форме?
-
Что такое замкнутый класс функций, полный класс? Приведите примеры.
Тема 3.
-
В чем состоит правило суммы и произведения в комбинаторике?
-
Приведите формулу включения/исключения. Объясните смысл применения.
-
Чему равно число различных перестановок из n элементов?
-
Как подсчитывается число различных перестановок с повторениями?
-
Укажите формулы для подсчета размещений без повторений и с повторениями.
-
Как подсчитывается число различных сочетаний с повторениями?
-
В чём смысл чисел Стирлинга?
-
Что такое число Белла?
Тема 4.
-
Как задается формальная теория (система)?
-
Что такое правильно построенная формула?
-
Чем аксиомы отличаются от правил вывода?
-
Укажите основные свойства формальных теорий.
-
Опишите язык исчисления высказываний.
-
Что такое выполнимая формула? тавтология?
-
Укажите основные свойства ИВ.
-
Сформулируйте правило modus ponens.
-
Опишите язык исчисления предикатов первого порядка.
-
Укажите основные свойства ИП.
-
Что такое интерпретация ИВ? Интерпретация ИП?
-
В чем смысл теоремы Геделя о неполноте.
-
Что такое обобщенная математическая индукция?
-
Приведите пример прямой и обратной теорем.
Тема 5.
-
Что такое отношение смежности и инцидентности?
-
Является ли отношение изоморфности графов отношением эквивалентности?
-
Приведите примеры полного графа.
-
Определите понятие связности графа.
-
Что такое компонента связности графа?
-
Какие способы представления графов вы знаете?
-
Определите понятие маршрута в графе.
-
Приведите пример Эйлерова цикла.
-
Что такое двудольный граф?
-
Приведите пример непланарного графа.
-
Что такое лес и дерево?
-
Какие виды деревьев вы знаете?
-
Приведите пример ориентированного дерева и ориентированного графа.
-
Опишите различные способы обхода деревьев.
Тема 6.
-
Что такое массовая задача?
-
Какие виды вычислительной сложности вы знаете?
-
Что такое задача распознавания языков (свойств)?
-
Что такое полиномиальная сводимость?
-
Объясните определение класса NP.
-
Какие задачи называются NP-полными?
-
Приведите примеры NP-полных задач.
-
Как доказать, что задача является NP-полной?
-
В чем состоит главная проблема теории вычислительной сложности?
VIII.Методические указания студентам
Из основной и дополнительной литературы для изучения тем курса следует выбирать те источники, которые по степени формальности изложения материала наиболее соответствуют уровню текущей подготовки студента.
Автор программы: _____________________________/ Большакова Е.И. /
|