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




Скачать 43.03 Kb.
НазваниеМатематическая логика и теория алгоритмов
Дата19.01.2013
Размер43.03 Kb.
ТипДокументы
Математическая логика и теория алгоритмов

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

Настоящее пособие предназначено для студентов заочной формы обучения. Пособие определяет круг вопросов для самостоятельной подготовки по курсу «Математическая логика и теория алгоритмов», посвященного изложению основ математической логики, базовых алгоритмов дискретной математики, абстрактных машин, формализующих понятие алгоритма. Большое внимание уделено практическим аспектам обсуждаемых понятий: автоматизации логического вывода, проверки корректности программ, автоматическому построению синтаксических анализаторов, криптографическим системам.


Введение в математическую логику

Формальные модели.

Логика высказываний. Автоматизация доказательства теорем: метод резолюций.

Исчисление предикатов (предикаты, кванторы, свойства, свободные и связанные переменные, логический вывод в логике предикатов). Теоремы Гёделя о неполноте. Доказательство корректности программ методом логического вывода.


Теория алгоритмов

Конечный автомат. Определение и границы возможностей (невозможность реализации алгоритма перемножения натуральных чисел).

Машина Тьюринга. Пример программы умножения натуральных чисел в единичной записи.

Границы возможностей машины Тьюринга: теорема Райса (проблема останова).


Языки и грамматики

Языки (определение, операции над языками). Грамматики (определение). Контекстно-свободные грамматики: запись в форме Бэкуса-Наура и синтаксической диаграммы. Автоматные грамматики и языки. Регулярные множества и регулярные выражения. Проектирование синтаксических анализаторов.


Сложность алгоритмов

Классы сложности алгоритмов.

Примеры алгоритмов различной сложности:

- алгоритмы над числами (обычный и расширенный алгоритм Евклида, умножение целых чисел и разложение целых чисел на множители).

Классы трудоемкости P, PC, NP.

Метод ветвей и границ.

Криптография: практическое использование результатов теории сложности алгоритмов.

Указания к использованию литературы


Формальные модели. Логика высказываний.

(КА гл. 6, п. 6.1, 6.2 с. 217-261)

(НО гл.4, п.4.1-4.3, с. 100-118)

Автоматизация доказательства теорем: метод резолюций.

(НО гл. 4, п.4.5, с. 127-133)

Исчисление предикатов (предикаты, кванторы, свойства, свободные и связанные переменные, логический вывод в логике предикатов). Теоремы Гёделя о неполноте. Доказательство корректности программ методом логического вывода.

(НО гл.4, п.4.4, с. 118-127).

Конечный автомат. Определение и границы возможностей (невозможность генерации непериодической последовательности).

(КА гл.8, с. 295-298, с.316)

Машина Тьюринга. Пример программы умножения натуральных чисел в единичной записи.

Границы возможностей машины Тьюринга: теорема Райса (проблема останова).

(КА г.5, с.144-162, 176-178)

Языки (определение, операции над языками). Грамматики (определение).

Контекстно-свободные грамматики: запись в форме Бэкуса-Наура и синтаксической диаграммы. (КА гл.7, п.7.1, с.261-279)

Автоматные грамматики и языки. Регулярные множества и регулярные выражения.

(КА гл.8, п.8.2, с.313-330)

Проектирование синтаксических анализаторов.

(ВТ, гл.5, п.5.1, 5.2, 5.3, 5.4, с.319-335)

Примеры алгоритмов различной сложности: алгоритмы над числами (обычный и расширенный алгоритм Евклида, умножение целых чисел и разложение целых чисел на множители).

(ВИ гл.1, $1, с.7-24).

Классы трудоемкости P, PC, NP.

(КА гл.9, п.9.1, 9.2, с. 351-358, 381-384, 398-399)

Метод ветвей и границ.

(КА гл.9, п.9.3, с.399-411)

Криптография: практическое использование результатов теории сложности алгоритмов.

(ВИ гл.2, $5, гл.3, $1-6, с.30-48, НО гл.6, п.6.5, с.180-188).


Литература:

1. (КА) Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. с. 144-411.

2. (НО) Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001. с. 100-134, 180-188.

3. (ВТ) Вирт Н. Алгоритмы + Структуры данных = Программы. – М.: Мир, 1985. с. 319-335.

4. (ВИ) Виноградов И.М. Основы теории чисел. – М: Наука, 1981. с. 7-15, с. 47-48.

Список вопросов к экзамену


1) Формальные модели математической логики.

2) Логика высказываний. Автоматизация доказательства теорем: метод резолюций.

3) Исчисление предикатов.

4) Теоремы Гёделя о неполноте. Доказательство корректности программ методом логического вывода.

5) Конечный автомат. Определение и границы возможностей.

6) Машина Тьюринга. Границы возможностей машины Тьюринга.

7) Языки (определение, операции над языками). Грамматики (определение). Контекстно-свободные грамматики: запись в форме Бэкуса-Наура и синтаксической диаграммы.

8) Автоматные грамматики и языки. Регулярные множества и регулярные выражения.

9) Проектирование синтаксических анализаторов.

10) Классы сложности алгоритмов.

11) Примеры алгоритмов различной сложности: алгоритмы над числами.

12) NP- полные задачи.

13) Криптография: практическое использование результатов теории сложности алгоритмов.

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


1. Приведите протокол работы алгоритма поиска наибольшего общего делителя чисел 123456 и 4321.

2. Запишите утверждение, состоящее в том, что h есть наибольший общий делитель чисел f и g в терминах предиката D(x,y), означающего «x делит y» и предиката G(x,y). означающего «x больше или равно y».

3. Постройте конечный автомат для распознавания языка {abncma}.

Опишите грамматику языка {abncma} в форме Бэкуса-Наура.

4. Постройте машину Тьюринга для вычитания натуральных чисел в единичном коде (из n вычесть m (n>m), если первое число записано n единицами на ленте машины, затем следует разделитель, например, *, после которого идут m единиц второго числа).

5. Поставьте электронную подпись на сообщении, заданным двузначным числом 27, используя код RSA с открытыми частями m=17*23 и e= 125.

6. Классифицируйте по трудоемкости их решения следующие задачи:

а) перемножение целых чисел, размер задачи определяется длиной минимального из чисел n;

б) разложение целых чисел на множители, размер задачи определяется длиной числа n;

в) доказательство того, что логическое выражение, заданное логической формулой, состоящей из переменных и логических связок, является тавтологией, размер задачи определяется количеством символов n, входящих в формулу;

г) нахождение кратчайшего пути, соединяющего две заданные вершины взвешенного графа, размер задачи определяется числом вершин графа n;

д) нахождение кратчайшего пути, проходящего через все вершины взвешенного графа, размер задачи определяется числом вершин графа n.

Похожие:

Математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Математическая логика и теория алгоритмов icon«Математическая логика и теория алгоритмов»
Математическая логика и теория алгоритмов" является фундаментальное образование в области принципов построения эффективных и надежных...
Математическая логика и теория алгоритмов iconРабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов
Математическая логика и теория алгоритмов в соответствии требованиями фгос впо, утвержденного приказом Министра образования и науки...
Математическая логика и теория алгоритмов iconПрограмма дисциплины математическая логика и теория алгоритмов
Рабочая программа дисциплины "Математическая логика и теория алгоритмов" предназначена для студентов 3 курса
Математическая логика и теория алгоритмов iconУльянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов
Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: Мгапи, 2003. – 80 с
Математическая логика и теория алгоритмов iconМатематическая логика и теория алгоритмов

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

Математическая логика и теория алгоритмов iconУчебно-методический комплекс по дисциплине математическая логика и теория алгоритмов
Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»
Математическая логика и теория алгоритмов iconТемы курсовых работ по дисциплине «Математическая логика и теория алгоритмов»
В. А. Молчанов, В. Е. Новиков, Т. М. Отрыванкина, П. Н. Пронин, В. Е. Фирстов. – Оренбург: гоу огу, 2004. – 68 с
Математическая логика и теория алгоритмов iconМатематическая логика и теория алгоритмов
Автор: д-р физ мат наук, профессор, зав кафедрой компьютерной безопасности и математических методов обработки информации Дурнев В....
Разместите кнопку на своём сайте:
Библиотека


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