408,32 Kb.НазваниеПрограмма наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных наукахстраница3/3Дата конвертации03.10.2012Размер408,32 Kb.Тип 3 7. Практические занятия (семинары) По предмету «Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках» семинары не предусмотрены 8. Примерная тематика курсовых проектов (работ)_______________________________ ___Курсовые работы не предусмотрены___________________________________________ 9. Учебно-методическое и информационное обеспечение дисциплины: а) основная литература Гаврилов Г.П., Сапоженко А.А. «Задачи и упражнения по курсу дискретной математики».// М.: "Наука", 2006 Зарипова Э.Р., Кокотчикова М.Г., Севастьянов Л.А. «Лекции по дискретной математике. Часть I. Математическая логика». Учебное пособие. // М.: Изд-во РУДН, 2008. Новиков Ф.А. «Дискретная математика для программистов». Учебник. // Cпб.: Изд. дом «Питер», 2000. Лавров И.А., Максимова Л.Л. «Задачи по теории множеств, математической логике и теории алгоритмов». Учебное пособие. 5-ое изд., // М:, Изд-во Физматлит, 2006 Гайдамака Ю.В., Зарипова Э.Р., М.Г. Кокотчикова, Л.А. Севастьянов. Лекции по дискретной математике. Часть II Комбинаторика. Теория конечных графов: Учебно-метод. пособие. М.: Изд-во РУДН, 2008. 60 с.: ил. -http://www.telesys.pfu.edu.ru/studies/book/kombinatorika-tkg.pdf Иванов Б.Н. Дискретная математика. Издательство: ФИЗМАТЛИТ, 2007 г. 408 стр. Харари Фрэнк. Теория графов / Харари Фрэнк ; Пер. с англ. В.П.Козырева; Под ред. Г.П.Гаврилова. - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. «Лекции по теории графов». Изд.2, испр., Изд-во Либроком, 2009. Муромцев В.В. «Некоторые алгоритмы на графах». Учебное пособие, Белгород: Изд. БелГТАСМ, 2000.- 64 с. б) дополнительная литература Игошин В.И. «Математическая логика и теория алгоритмов». 3-е изд. Учебное пособие для ВУЗов, // М:, Изд-во Физматлит, 2006 Просветов Г.И. «Дискретная математика: задачи и решения». Учебное пособие. //М. Изд-во «Бином. Лаборатория знаний», 2008. Зыков А. А. Основы теории графов. М.: «Вузовская книга», 2004. С.P664 Кирсанов М.Н. «Графы в MAPLE» Пособие по дискретной математике для студентов университетов. М: Физматлит, 2007. Сайт кафедры систем телекоммуникаций РУДН (информационный ресурс). Режим доступа: свободный. Учебный портал кафедры систем телекоммуникаций РУДН (информационный ресурс) Режим доступа: для зарегистрированных пользователей. в) программное обеспечение Maple, MatLab, SciLab, MathCad, Mathematica г) базы данных, информационно-справочные и поисковые системы___ не предусмотрено 10. Материально-техническое обеспечение дисциплины: лекционная аудитория, дисплейные классы 11. Методические рекомендации по организации изучения дисциплины: На освоение дисциплины отводится три семестра. В качестве итогового контроля знаний в конце каждого семестра предусмотрен экзамен. Для текущего контроля успеваемости и промежуточной аттестации студентов рекомендуется использовать вопросы и задания подобные перечисленным ниже: Типовые задачи для промежуточного контроля знаний для первого семестра: Формулы сочетаний, перестановок, размещений элементов множества. Формулу числа перестановок мультимножества. Формулу включений и исключений. Доказательство тождеств с использованием формулы Бинома Ньютона. Разбиение множеств на всевозможные подмножества, разбиение множеств на определенное число подмножеств. Разбиение множеств на циклы. Полиномиальная теорема. Нахождение производящих функции для заданных последовательностей. Нахождение последовательностей по производящим функциям. Решение рекуррентных соотношений. Типовые задачи для промежуточного контроля знаний для второго семестра: Построение СДНФ, СКНФ, нахождение существенных и фиктивных переменных, построение полинома Жегалкина. Представление функции булевой формулой. Нахождение двойственной функции по правилу двойственности, по принципу двойственности и по таблице. Проверка справедливости соотношения. Построить минимальное представление исходной функции с помощью алгоритма Куайна-МакКлоски и последующего выделения ядра. Проверить является ли высказывание логическим следствием (двумя способами: любая из двух теорем и метод резолюций). Найти предваренную и скулемовскую нормальные формы для формулы. Проверить принадлежность функции классам монотонных функций, самодвойственных функций, линейных функций. Типовые задачи для промежуточного контроля знаний для третьего семестра: Найти эксцентриситет, диаметр и радиус графа. Составить матрицу смежности и матрицу инцидентности для графа. Построить минимальное покрывающее дерево для графа по алгоритму Краскала. Задача на применение алгоритма Дейкстры. Задача на применение алгоритма Уоршалла-Флойда. Поиск эйлерова цикла в графе. Типовые вопросы для итогового контроля знаний для первого семестра: Области применения комбинаторики. Определение множества, мощности множества, прямого произведения множеств. Правило суммы и правило произведения множеств. Выборка объема r из n элементов, типы выборок. Определение: размещение, размещение с повторением, сочетание, сочетание с повторением, перестановка, мультимножество. Формула для вычисления различных перестановок элементов мультимножества. Основные тождества, связанные с числом сочетаний (с доказательством). Бином Ньютона (2 способа доказательства). Свойства биномиальных коэффициентов (с доказательством). Треугольник Паскаля. Свойство шестиугольника треугольника Паскаля (с доказательством). Разбиение множества. Числа Стирлинга II рода. Свойства чисел Стирлинга II рода (с доказательством). Формула для вычисления чисел Стирлинга II рода через предыдущие (с доказательством). Формула для вычисления чисел Стирлинга II рода через сумму произведения сочетаний и предыдущих чисел Стирлинга II рода (с доказательством). Числа Белла. Рекуррентное соотношение для вычисления чисел Белла (с доказательством). Числа Стирлинга I рода. Формула для вычисления Стирлинга I рода (с доказательством). Беззнаковые числа Стирлинга I рода. Свойства беззнаковых чисел Стирлинга I рода (с доказательством). Формула для вычисления беззнаковых чисел Стирлинга I рода (с доказательством). Формула включений и исключений (с доказательством). Решение задачи о беспорядках. Формула для вычисления числа предметов, обладающих ровно n свойствами (с доказательством). Формула для вычисления числа предметов, обладающих не менее, чем k свойствами. Решение задачи о встречах. Полиномиальная теорема (с доказательством). Идея метода производящих функций. Вычисление производящих функций для последовательностей: , ,
7. Практические занятия (семинары) - Программа наименование дисциплины: Дискретная математика, математическая логика...
Комментариев нет:
Отправить комментарий