Учебно-методический комплекс   Специальность  010400 Информационные технологии icon

Учебно-методический комплекс   Специальность  010400 Информационные технологии


Смотрите также:
Учебно-методический комплекс для студентов специальности «Реклама» Санкт-Петербург...
Учебно-методический комплекс для студентов специальностей 080801 «Прикладная информатика в...
Учебно-методический комплекс по дисциплине теория вероятностей...
Учебно-методический комплекс по дисциплине «Информационные технологии в управлении»...
Учебно-методический комплекс для студентов очной формы обучения направления: 230201...
Учебно-методический комплекс для студентов специальности 080507 «Менеджмент организаций» очной и...
Учебно-методический комплекс (специальность: 021100 «юриспруденция») Москва 2004...
Учебно-методический комплекс по дисциплине «Технологии полиграфии» Специальность: 070601. 65...
Учебно-методический комплекс по дисциплине...
Учебно-методический комплекс по дисциплине информационные технологии в образовании...
Учебно-методический комплекс по поддержке курса «информационные технологии в математике» 2...
Учебно-методический комплекс по дисциплине «информационные технологии в математике» для дневного...



Загрузка...
скачать
ТВЕРСКОЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

 



 

ФАКУЛЬТЕТ

Прикладной математики и кибернетики

 



 

Кафедра 

 

информатики

 

 

 

Учебно-методический комплекс

 

Специальность 

010400 - Информационные технологии

Дисциплина 

Математическая логика и теория алгоритмов

 

Общая дисциплина

 

 

Зав.кафедрой

М.А.Тайцлин




№ протокола

9




Дата

14.06.2006

   

Авторы

 

  • М.А.Тайцлин

 

 



 

 

^ Выписка из государственного стандарта

 

Исчисления высказываний и предикатов. Теории первого порядка. Формальная арифметика. Введение в теорию алгебраических систем. Вычислимые и рекурсивные функции. Машины Тьюринга. Тезис Черча. Меры сложности алгоритмов. Классы задач P и NP. NP-полные задачи. Клаузальная логика, семантика дизъюнктов, секвенциальная нотация, семантические сети, хорновские дизъюнкты и их интерпретация, метод резолюций.

 

^ Цели и задачи изучения дисциплины

 

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

 

 

^ Предварительные знания и навыки, требуемые для изучения дисциплины

 

Курсы информатики и дискретной математики

 

Знания и навыки, получаемые студентами при изучении дисциплины

 

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

 



 

^ Общий бюджет времени

 

Специальность

010400 - Информационные технологии

 

Курс

Семестр

Всего

Ауд.

Лекций

Прак.

Лаб.

Отчетность

2

3

170

75

45

30

0

Экзамен

2

4

128

110

66

44

0

Экзамен

 



 

^ Содержание учебной программы

 

Семестр 3





Модуль 1 





Название темы Исчисление высказываний

  1. Исчисление высказываний. Алфавит, формулы, секвенции. Схемы аксиом и правил вывода. Доказательство. Примеры доказуемых секвенций. Эквивалентность линейного доказательства и доказательства в виде дерева.

  2. Эквивалентность формул. Булевы эквивалентности.

  3. Теорема о замене. Нормальные формы.

  4. Полнота и непротиворечивость.


Распределение времени



Лекций (часов)

10

Практики (часов)

6

Лабораторных (часов)

0

Самостоятельной работы (часов)

20



Содержание самостоятельной работы


Доказательство секвенций в исчислении высказываний. Изучение доказательства теорем.


Методические материалы и ссылки по теме

 

^ Вид материала

Описание материала

Файл материала

Учебное пособие

А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 1. Тверь, 1998.

ch3.ps


Отчетность



Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

октябрь

10

ch3.ps






Модуль 2 





Название темы Язык логики предикатов. Реляционные базы данных

  1. Алгебраические системы. Язык логики предикатов. Формулы и термы. Истинность формулы в системе на состоянии.

  2. Базы данных. Описание свойств баз данных на языке логики предикатов.


Распределение времени



Лекций (часов)

8

Практики (часов)

6

Лабораторных (часов)

0

Самостоятельной работы (часов)

15



Содержание самостоятельной работы


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


Методические материалы и ссылки по теме

 

^ Вид материала

Описание материала

Файл материала

Учебное пособие

А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 1. Тверь, 1998.

ch3.ps


Отчетность

Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

октябрь

30

ch3.ps






Модуль 3 





Название темы Частичная рекурсивность функций, вычислимых на машинах Тьюринга

  1. Частичная рекурсивность функций, вычислимых на машинах Тьюринга.

  2. Универсальные функции.

  3. Неразрешимость проблемы остановки для машин Тьюринга.

  4. Существование частично рекурсивной функции с нерекурсивной областью определения.


Распределение времени



Лекций (часов)

10

Практики (часов)

6

Лабораторных (часов)

0

Самостоятельной работы (часов)

1



Содержание самостоятельной работы


Изучение теоретического материала.


Методические материалы и ссылки по теме

 

^ Вид материала

Описание материала

Файл материала

Учебное пособие

А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 2. Тверь, 1998.

ch4.ps





Название темы Неразрешимость проблемы равенства в теории полугрупп

  1. Полусистемы Туэ. Построение полусистемы Туэ по машине Тьюринга.

  2. Ассоциативные исчисления. Построение ассоциативного исчисления по машине Тьюринга.

  3. Неразрешимость проблемы равенства в теории полугрупп.


Распределение времени



Лекций (часов)

8

Практики (часов)

4

Лабораторных (часов)

0

Самостоятельной работы (часов)

1


Содержание самостоятельной работы


Изучение теоретического материала.


Методические материалы и ссылки по теме

 

^ Вид материала

Описание материала

Файл материала

Учебное пособие

А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 2. Тверь, 1998.

ch4.ps


Отчетность

Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

декабрь

20








Семестр 4 





Модуль 1 





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

  1. Машины Тьюринга с входом. Коды алгебраических систем. Алгоритмические проблемы. Классификация машин Тьюринга и алгоритмических проблем.

  2. Зависимость сложности алгоритмической проблемы от числа входных лент, числа символов на рабочих лентах и от числа рабочих лент.

  3. Полиномиальная сводимость.

  4. NP-полные проблемы.

  5. NP-полнота SAT.

  6. Другие NP-полные проблемы.

  7. Машины Тьюринга со стеком.

  8. Теоремы Кука о связи временной и емкостной сигнализирующих.


Распределение времени



Лекций (часов)

10

Практики (часов)

8

Лабораторных (часов)

0

Самостоятельной работы (часов)

1


Содержание самостоятельной работы


Изучение теоретического материала. Построение машин Тьюринга для решения конкретных алгоритмических проблем.


Методические материалы и ссылки по теме

^ Вид материала

Описание материала

Файл материала

Учебное пособие

А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Часть 3. Тверь, 1998.

bookin.ps

Учебное пособие

М.А.Тайцлин. Теорема Кука.

cook1.ps


Отчетность

Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

февраль

10









Модуль 2 





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

  1. Неразрешимость логики предикатов.

  2. Существование конечной модели и существование периодической модели в арифметике.

  3. Построение формулы по машине Тьюринга.

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


Распределение времени



Лекций (часов)

10

Практики (часов)

6

Лабораторных (часов)

0

Самостоятельной работы (часов)

2


Содержание самостоятельной работы


Изучение теоретического материала.


Методические материалы и ссылки по теме

^ Вид материала

Описание материала

Файл материала

Учебное пособие

А.П.Столбоушкин, М.А.Тайцлин. Неразрешимость логики предикатов на конечных моделях

tra.pdf


Отчетность

Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

март

10









Модуль 3 





Название темы Представление рекурсивных функций в арифметике

  1. Китайская теорема об остатках.

  2. Функция Гёделя.

  3. Представление рекурсивных функций в арифметике.

  4. Неразрешимость арифметики.


Распределение времени



Лекций (часов)

8

Практики (часов)

4

Лабораторных (часов)

0

Самостоятельной работы (часов)

6


Содержание самостоятельной работы


Изучение теоретического материала. Задание конкретных функций формулами арифметики.


Отчетность

Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

апрель

10









Название темы Неполнота логики предикатов для PTIME

  1. Игры Эренфойхта.

  2. Неопределимость связности в логике предикатов.

  3. Определимость связности в PTIME.


Распределение времени



Лекций (часов)

10

Практики (часов)

4

Лабораторных (часов)

0

Самостоятельной работы (часов)

6


Содержание самостоятельной работы


Изучение теоретического материала. Построение невыразимых в логике предикатов глобальных предикатов из PTIME.


Методические материалы и ссылки по теме

 

^ Вид материала

Описание материала

Файл материала

Учебное пособие

М.А.Тайцлин. Теория баз данных

in.ps


Отчетность

Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

май

10









Название темы Метод резолюций

  1. Клаузулы. Резолюции. Алгоритм элиминации.

  2. Подстановки. Алгоритм унификации.

  3. Клаузулы в логике предикатов.

  4. Резолюции в логике предикатов.



Распределение времени



Лекций (часов)

10

Практики (часов)

8

Лабораторных (часов)

0

Самостоятельной работы (часов)

1


Содержание самостоятельной работы


Решение задач методом резолюций.


Методические материалы и ссылки по теме

 

^ Вид материала

Описание материала

Файл материала

Учебное пособие

М.А.Тайцлин. Резолюции.

resol.pdf


Отчетность

Форма

Срок

Балл

^ Материалы для подготовки

Контрольная работа

июнь

20




 



 

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

 

  1. А.П.Столбоушкин, М.А.Тайцлин. Математические основания информатики. Части 1, 2 и 3. Тверь, 1998.

  2. М.А.Тайцлин. Теорема Кука.

  3. А.И.Мальцев. Алгоритмы и рекурсивные функции. Москва. "Наука". 1965.

  4. М.А.Тайцлин. Резолюции.

  5. А.П.Столбоушкин, М.А.Тайцлин. Неразрешимость логики предикатов на конечных моделях.

 

 

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

 

  1. С.Кук. Характеристики машинных автоматов в терминах вычислителей, ограниченных во времени. В книге: Сложность вычислений и алгоритмов, Москва, Мир,1974.

 

 




Скачать 135.72 Kb.
оставить комментарий
Дата30.09.2011
Размер135.72 Kb.
ТипУчебно-методический комплекс, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх