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




Скачать 78.12 Kb.
НазваниеПрограмма дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика»
Дата17.02.2013
Размер78.12 Kb.
ТипПрограмма дисциплины
Министерство экономического развития и торговли

Российской Федерации


Государственный университет - Высшая школа экономики
Факультет БИЗНЕС-ИНФОРМАТИКИ


Программа дисциплины


Дискретная математика – 2

для направления 010500.62 «Прикладная математика и информатика» подготовки бакалавра

Автор Объедков С.А. (sergei.obj@gmail.com)

Рекомендована секцией УМС Одобрена на заседании кафедры


«Бизнес-информатика» кафедры анализа данных и

искусственного интеллекта

Председатель Зав. кафедрой

_______________ __________________С.О. Кузнецов

«_____» __________________ 200 г. «____»_____________________ 200 г


Утверждена УС факультета

бизнес-информатики

Ученый секретарь

_______________В.А. Фомичев

« ____» ___________________200 г.

Москва


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





Название темы

Всего часов по дисциплине

Аудиторные часы

Самостоятельная работа










Лекции

Сем. и практ. занятия




1

Сложность вычислений по времени

49

10

10

29

2

Сложность вычислений по памяти

10

2

2

6

3

Сложность вероятностных алгоритмов

10

2

2

6

4

Введение в модальную логику

39

8

8

23




Итого:

108

22

22

64


---------------------------------------------------------------------------------------------------------------------------------------------------------

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

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.


---------------------------------------------------------------------------------------------------------------------------------------------------------

Формы контроля:


  • текущий контроль – контрольная работа

  • итоговый контроль – зачет


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

Работа на практических занятиях (решение задач) – 10%

Письменная аудиторная контрольная работа (60 мин.) - 25%

Письменный зачет (120 мин.) - 65%

---------------------------------------------------------------------------------------------------------------------------------------------------------


Содержание программы


Тема 1. Сложность вычислений по времени.

Измерение сложности, O-обозначения, Θ-обозначения. Детерминированная и недетерминированная машины Тьюринга. Класс P. Класс NP. Сведение за полиномиальное время. NP-полнота. Теорема Кука – Левина. NP-полные задачи. Теорема об иерархии классов сложности по времени. Машина Тьюринга с оракулом и определяемые на ее основе классы сложности.


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

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. (Главы 1 – 3).

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

Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Вильямс, 2007. С. Г. Полный справочник по Java. М.: Вильямс, 2007. С. 88 – 97, 1085 – 1150.

Sipser, Michael (2006), Introduction to the Theory of Computation. – Boston, Mass.: Thomson Course Technology, p. 245 – 301, 340 – 343, 348 – 351.


Тема 2. Сложность вычислений по памяти.

Классы языков, распознаваемых детерминированными и недетерминированными машинами Тьюринга с использованием памяти логарифмического размера относительно размера входа (L и NL). NL-полнота задачи о нахождении пути между двумя заданными вершинами в ориентированном графе. Теорема о совпадении классов NL и coNL.


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

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. (Раздел 7.5).

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

Sipser, Michael (2006), Introduction to the Theory of Computation. – Boston, Mass.: Thomson Course Technology, p. 320 – 328.


Тема 3. Сложность вероятностных алгоритмов.

Вероятностные алгоритмы. Класс BPP языков, распознаваемых вероятностными машинами Тьюринга с полиномиальным временем работы. Примеры языков из класса BPP.


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

Крупский В.Н. Введение в сложность вычислений. М.: Факториал Пресс, 2006. С. 75 – 83.

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

Sipser, Michael (2006), Introduction to the Theory of Computation. – Boston, Mass.: Thomson Course Technology, p. 368 – 380.


Тема 4. Введение в модальную логику.

Реляционные структуры. Модальные языки. Модели, фреймы и общие фреймы.


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

Garson, James (2008), Modal Logic, in: Stanford Encyclopedia of Philosophy.

http://plato.stanford.edu/entries/logic-modal/

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

Фейс Р. Модальная логика. М.: Наука, 1974.


---------------------------------------------------------------------------------------------------------------------------------------------------------


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


  1. Анализ сложности алгоритмов.

  2. Влияние выбора вычислительной модели на оценку сложности алгоритмов.

  3. Класс задач, разрешимых за полиномиальное время на детерминированной машине Тьюринга.

  4. Доказательство принадлежности языков классу P.

  5. Класс задач, разрешимых за полиномиальное время на недетерминированной машине Тьюринга.

  6. Доказательство принадлежности языков классу NP.

  7. Соотношение классов P и NP.

  8. Сводимость за полиномиальное время.

  9. Доказательство NP-полноты.

  10. Принадлежность языков классам L и NL.

  11. Доказательство NL-полноты.

  12. Соотношение между классом BPP и классами сложности по памяти.

  13. Язык пропозициональной динамической логики.

  14. Нормальные модальные логики.

  15. Аксиомы деонтической логики.



---------------------------------------------------------------------------------------------------------------------------------------------------------

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


  1. Верно ли, что массив из n чисел, каждое из которых равно -1, 0 или 1, можно отсортировать за время O(n) в худшем случае? Объясните ответ.

  2. В некоторой программе осуществляется n последовательных вызовов операции f. Известно, что эта последовательность вызовов занимает время Θ(n log n) в худшем случае. Каким может быть максимальное время выполнения (в терминах Θ) одной операции f из этой последовательности?

  3. Пусть задано конечное множество S и конечный набор его подмножеств S1, S2, ..., Sk. Для каждого множества Si заданы два числа lowi и highi. Требуется выяснить, существует ли подмножество T S, такое что для каждого i выполняется lowi ≤ |T Si| ≤ highi. Докажите, что эта задача является NP-трудной, сведя к ней задачу о выполнимости 3-КНФ (3-CNF_SAT).

  4. Задача по определению того, содержит ли граф простой (без повторяющихся вершин) путь с числом ребер не менее m является NP-полной. Почему из этого следует, что существование алгоритма, вычисляющего самый длинный простой цикл в графе за полиномиальное время от длины входа, маловероятно?

  5. Верно ли, что SAT ∈ co-NP?

  6. Верно ли, что CLIQUE ≤P VERTEX_COVER?

  7. Верно ли, что CLIQUE ≤P 3-CNF_SAT?

  8. Верно ли, что «Путь» ≤P {2008}, где «Путь» – язык, соответствующий задаче о существовании пути между двумя врешинами в графе.

  9. Покажите, что язык, слова которого являются последовательностями правильно вложенных скобок, принадлежит классу L.

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

  11. Опишите класс фреймов, в котором данное высказывание, записанное на базовом темпоральном языке, является общезначимым: PFφ → Fpφ.

  12. Что такое модель в модальной логике?

  13. Что такое фрейм в модальной логике?

  14. Что такое обощенный фрейм в модальной логике?

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

  16. Является ли следующая формула теоремой логики K: ◇(φ & ψ) → ◇φ?

  17. Приведите пример модальной логики, не являющейся нормальной.

  18. Приведите пример формулы, тождественно ложной в К.

  19. Опишите класс фреймов, в котором данное высказвание, записанное на базовом темпоральном языке, является общезначимым: PFφ → FPφ.


---------------------------------------------------------------------------------------------------------------------------------------------------------


Автор программы: _____________________________/ Объедков С.А./

Подпись обязательна.





Похожие:

Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины: Моделирование Бизнес-процессов  для направления 010500. 62 «Прикладная математика и информатика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010500....
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Дискретная математика для направления Прикладная математика и информатика 010500
Автор программы: Доктор технических наук, профессор, академик Российской Академии естественных наук О. П. Кузнецов
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины иностранный язык (английский) для направления 010500. 62 "Прикладная математика и информатика"
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010500. 62 "Прикладная...
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины иностранный язык (английский) для направления 010500. 62 "Прикладная математика и информатика"
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010500. 62 "Прикладная...
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика»
Программа дисциплины «Упорядоченные множества для анализа данных» для подготовки магистров по направлению 010500. 68 (магистерская...
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика»
Программа дисциплины «Упорядоченные множества для анализа данных» для подготовки магистров по направлению 010500. 68 (магистерская...
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины «Дискретная математика» для направления 010400. 62 «Прикладная математика и информатика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины «Дискретная математика» для направления 010400. 62 «Прикладная математика и информатика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Обучение машин и восстановление зависимостей для направления 010500. 68- прикладная математика и информатика подготовки магистров Автор Михальский А. И. () Рекомендована секцией умс «Прикладная математика и информатика»
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. Москва, Наука 1979
Программа дисциплины Дискретная математика 2 для направления 010500. 62 «Прикладная математика и информатика» iconПрограмма дисциплины иностранный язык (английский) для направления 010500. 62 "Математика"
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010500. 62 «Прикладная...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница