Программа (стр. 4 )

По предмету «Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках» семинары не предусмотрены

8. Примерная тематика курсовых проектов (работ)_______________________________

___Курсовые работы не предусмотрены___________________________________________

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

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

1.  , «Задачи и упражнения по курсу дискретной математики».// М.: "Наука", 2006

2.  , , «Лекции по дискретной математике. Часть I. Математическая логика». Учебное пособие. // М.: Изд-во РУДН, 2008.

3.  «Дискретная математика для программистов». Учебник. // Cпб.: Изд. дом «Питер», 2000.

4.  , «Задачи по теории множеств, математической логике и теории алгоритмов». Учебное пособие. 5-ое изд., // М:, Изд-во Физматлит, 2006

5.  , , . Лекции по дискретной математике. Часть II Комбинаторика. Теория конечных графов: Учебно-метод. пособие. – М.: Изд-во РУДН, 2008. – 60 с.: ил. -http://www. telesys. pfu. edu. ru/studies/book/kombinatorika-tkg. pdf

6.  Иванов математика. Издательство: ФИЗМАТЛИТ, 2007 г. 408 стр.

7.  Харари Фрэнк. Теория графов / Харари Фрэнк ; Пер. с англ. ; Под ред. . - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с.

8.  , , «Лекции по теории графов». Изд.2, испр., Изд-во Либроком, 2009.

9.  «Некоторые алгоритмы на графах». Учебное пособие, Белгород: Изд. БелГТАСМ, 2000.- 64 с.

б) дополнительная литература

1.  «Математическая логика и теория алгоритмов». 3-е изд. Учебное пособие для ВУЗов, // М:, Изд-во Физматлит, 2006

2.  «Дискретная математика: задачи и решения». Учебное пособие. //М. Изд-во «Бином. Лаборатория знаний», 2008.

3.  Зыков теории графов. — М.: «Вузовская книга», 2004. — С. 664

4.  «Графы в MAPLE» Пособие по дискретной математике для студентов университетов. М: Физматлит, 2007.

Сайт кафедры систем телекоммуникаций РУДН (информационный ресурс). Режим доступа: http://www. telesys. pfu. edu. ru – свободный. Учебный портал кафедры систем телекоммуникаций РУДН (информационный ресурс) Режим доступа: http://stud. sci. pfu. edu. ru – для зарегистрированных пользователей.

в) программное обеспечение Maple, MatLab, SciLab, MathCad, Mathematica

г) базы данных, информационно-справочные и поисковые системы___ не предусмотрено

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

лекционная аудитория, дисплейные классы

11. Методические рекомендации по организации изучения дисциплины:

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

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

Типовые задачи для промежуточного контроля знаний для первого семестра:

1.  Формулы сочетаний, перестановок, размещений элементов множества.

2.  Формулу числа перестановок мультимножества.

3.  Формулу включений и исключений.

4.  Доказательство тождеств с использованием формулы Бинома Ньютона.

5.  Разбиение множеств на всевозможные подмножества, разбиение множеств на определенное число подмножеств. Разбиение множеств на циклы.

6.  Полиномиальная теорема.

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

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

9.  Решение рекуррентных соотношений.

Типовые задачи для промежуточного контроля знаний для второго семестра:

1.  Построение СДНФ, СКНФ, нахождение существенных и фиктивных переменных, построение полинома Жегалкина.

2.  Представление функции булевой формулой.

3.  Нахождение двойственной функции по правилу двойственности, по принципу двойственности и по таблице.

4.  Проверка справедливости соотношения.

5.  Построить минимальное представление исходной функции с помощью алгоритма Куайна-МакКлоски и последующего выделения ядра.

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

7.  Найти предваренную и скулемовскую нормальные формы для формулы.

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

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

1.  Найти эксцентриситет, диаметр и радиус графа.

2.  Составить матрицу смежности и матрицу инцидентности для графа.

3.  Построить минимальное покрывающее дерево для графа по алгоритму Краскала.

4.  Задача на применение алгоритма Дейкстры.

5.  Задача на применение алгоритма Уоршалла-Флойда.

6.  Поиск эйлерова цикла в графе.

Типовые вопросы для итогового контроля знаний для первого семестра:

1.  Области применения комбинаторики. Определение множества, мощности множества, прямого произведения множеств. Правило суммы и правило произведения множеств.

2.  Выборка объема r из n элементов, типы выборок. Определение: размещение, размещение с повторением, сочетание, сочетание с повторением, перестановка, мультимножество. Формула для вычисления различных перестановок элементов мультимножества.

3.  Основные тождества, связанные с числом сочетаний (с доказательством).

4.  Бином Ньютона (2 способа доказательства).

5.  Свойства биномиальных коэффициентов (с доказательством).

6.  Треугольник Паскаля. Свойство шестиугольника треугольника Паскаля (с доказательством).

7.  Разбиение множества. Числа Стирлинга II рода. Свойства чисел Стирлинга II рода (с доказательством). Формула для вычисления чисел Стирлинга II рода через предыдущие (с доказательством). Формула для вычисления чисел Стирлинга II рода через сумму произведения сочетаний и предыдущих чисел Стирлинга II рода (с доказательством).

8.  Числа Белла. Рекуррентное соотношение для вычисления чисел Белла (с доказательством).

9.  Числа Стирлинга I рода. Формула для вычисления Стирлинга I рода (с доказательством).

10.  Беззнаковые числа Стирлинга I рода. Свойства беззнаковых чисел Стирлинга I рода (с доказательством). Формула для вычисления беззнаковых чисел Стирлинга I рода (с доказательством).

11.  Формула включений и исключений (с доказательством).

12.  Решение задачи о беспорядках.

13.  Формула для вычисления числа предметов, обладающих ровно n свойствами (с доказательством). Формула для вычисления числа предметов, обладающих не менее, чем k свойствами.

14.  Решение задачи о встречах.

15.  Полиномиальная теорема (с доказательством).

16.  Идея метода производящих функций.

17.  Вычисление производящих функций для последовательностей:

18.  ,

19.  ,

20.  ,

21. 

22.  Производящие функции (ПФ). Виды ПФ. Определение суммы последовательности и суммы ПФ. Определение произведения (свертки) последовательностей и ПФ. Умножение ПФ на действительное число.

23.  Свойства класса ПФ.

24.  Операции с ПФ (с доказательством): Линейные операции, сдвиг начала вправо, сдвиг начала влево, частичные суммы, дополнительные частичные суммы, изменение масштаба, свертка.

25.  ПФ для (n, r) сочетаний с ограниченным числом повторений.

26.  ПФ для (n, r) сочетаний с неограниченным числом повторений.

27.  Экспоненциальная ПФ.

28.  Метод решения однородных линейных рекуррентных соотношений. Доказательство 4-х положений для нахождения общих решений рекуррентных соотношений. Решение неоднородных линейных рекуррентных соотношений. Как пример найти решение НЛРС: .

29.  Поиск с возвращением. Использование исчерпывающего поиска. Задача прохождения лабиринта. Общий алгоритм поиска с возвращением. Дерево полного прохода алгоритма. Процедура поиска с возвращением. Оценка сложности алгоритма.

30.  Генерация перестановок.

31.  Порождение сочетаний

Типовые вопросы для итогового контроля знаний для второго семестра:

7.  Основные понятия теории множеств.

8.  Понятие прямого произведения множеств.

9.  Определение алгебры и подалгебры. Функции алгебры логики.

10.  Соответствия и функции в теории множеств.

11.  Булева алгебра и свойства булевых операций.

12.  Принцип двойственности и свойство двойственности.

13.  Совершенная дизъюнктивная нормальная форма.

14.  Построение СДНФ для функции, заданной таблицей.

15.  Совершенная конъюнктивная нормальная форма.

16.  Основные эквивалентные преобразования и их доказательства.

17.  Полином Жегалкина.

18.  Алгоритм Куайна-МакКлоски.

19.  Определение фиктивных и существенных переменных.

20.  Понятие двойственности и примеры двойственных и самодвойственных функций.

21.  Определение минимальной, кратчайшей и неизбыточной ДНФ.

22.  Теорема о функциональной полноте.

23.  Определение и свойства функциональной полноты и замкнутости. Замыкание.

24.  Общие принципы построения формальной в теории исчисления высказываний.

25.  Алгоритм преобразования формул в предваренную нормальную форму.

26.  Метод резолюций для исчисления высказываний.

27.  Алгоритм унификации.

28.  Класс функций T0. Определение и доказательство замкнутости.

29.  Класс функций T1. Определение и доказательство замкнутости.

30.  Класс функций S. Определение и лемма о несамодвойственной функции.

31.  Класс функций M. Определение и лемма о немонотонной функции.

32.  Класс функций L. Определение и лемма о нелинейной функции.

33.  Понятие предиката, квантора, алфавита и формулы.

34.  Интерпретация формул при исчислении предикатов.

35.  Понятие скулемовской стандартной формы.

36.  Предваренная нормальная форма.

37.  Метод резолюций для исчисления высказываний.

38.  Сравнительный анализ предикатов и высказываний. Примеры.

39.  Понятие унификатора, склейки и резольвенты в исчислении предикатов.

40.  Теоремы о логическом следствии.

41.  Алгоритм преобразования формул в предваренную нормальную форму.

42.  Теорема о функциональной полноте.

Типовые вопросы для итогового контроля знаний для третьего семестра:

1.  Неориентированный граф. Определение. Смежность ребер и вершин. Инцидентность. Изоморфизм.

2.  Теорема о четности вершин в конечном графе. Определения полного графа и подграфа.

3.  Определение маошрута, замкнутого маршрута. Определение цепи и простой цепи. Определение дерева. Теорема о количестве ребер в дереве с n вершинами.

4.  Связный неориентированный граф. Теорема о связности графа.

5.  Определение орграфа. Смежность в орграфе. Положительная и отрицательная инцидентность в орграфе. Положительная и отрицательная степени вершин в орграфе.

6.  Определение пустого графа. Определение изолированной вершины. Определение ормаршрута и замкнутого ормаршрута. Определение пути и простого пути. Определение контура.

7.  Определение сильносвязного графа. Определение орграфа. Определение симметричного и смешанного графов.

8.  Определение эксцентриситета, диаметра и радиуса в графе. Центр графа.

9.  Матрица смежности и инцидентности для неорграфа. Список смежности. Матрица весов.

10.  Матрица смежности и инцидентности для орграфа.

11.  Теорема о числе ормаршрутов длины n между двумя вершинами орграфа.

12.  Построение минимального покрывающего дерева по алгоритму Краскала. Алгоритм.

13.  Построение максимального покрывающего дерева по алгоритму Краскала. Алгоритм.

14.  Определение псевдографа и мультиграфа. Определение плоского графа.

15.  Построение минимального покрывающего дерева по алгоритму Прима. Алгоритм.

16.  Построение максимального покрывающего дерева по алгоритму Прима. Алгоритм

17.  Поиск маршрута и наименьшей длины по алгоритму Дейкстры. Алгоритм.

18.  Задача о кенигсбергских мостах. Определение эйлерова цикла и эйлерова графа. Определение эйлерова пути и способ получения эйлерова пути из эйлерова цикла.

19.  Теорема о четности степеней в эйлеровом графе.

20.  Поиск эйлерова цикла в графе. Алгоритм.

21.  Поиск минимальных расстояний между всеми парами вершин по алгоритму Уоршалла-Флойда. Алгоритм.

22.  Сравнение алгоритмов Дейкстры и Уоршалла-Флойда. Сходства и различия алгоритмов.

23.  Задача построения транзитивного замыкания бинарного отношения. Определение бинарного отношения. Определение транзитивного замыкания. Матрица достижимости (связности).

24.  Построение транзитивного замыкания для графа. Алгоритм.

25.  Особенности i-той строки и i-столбца для Алгоритма Уоршалла-Флойда. Доказательство.

26.  Особенности i-той строки и i-столбца для Алгоритма поиска транзитивного замыкания. Доказательство.

27.  Определение потока в графе. Условия существования потока в графе. Правила расскрашивания дуг графа для поиска увеличивающей цепи. Определение прямых и обратных дуг.

28.  Увеличение потока в графе по увеличивающей цепи. Алгоритм.

29.  Поиск максимального потока в графе. Алгоритм.

30.  Поиск потока минимальной стоимости. Алгоритм.

31.  Поиск оптимального маршрута почтальона для орграфа. Алгоритм.

32.  Определение гамильтонова цикла и гамильтоновой цепи.

33.  Гамильтоновы и эйлеровы графы. Сходства и различия гамильтонова и эйлерова циклов.

34.  Три достаточных критерия существования гамильтоновых циклов в неорграфе.

35.  Поиск гамильтонова цикла в орграфе. Алгоритм с упрощением

Разработчик:

Ст. преподаватель каф. систем телекоммуникаций

Должность, название кафедры, инициалы, фамилия)

Заведующий кафедрой систем телекоммуникаций

название кафедры, инициалы, фамилия