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






Скачать 43.03 Kb.
НазваниеМатематическая логика и теория алгоритмов
Дата публикации14.02.2015
Размер43.03 Kb.
ТипДокументы
l.120-bal.ru > Математика > Документы
Математическая логика и теория алгоритмов

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

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

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

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

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

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

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

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

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

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

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

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

Классы трудоемкости 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Программа дисциплины Математическая логика и теория алгоритмов Для...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230400. 62 «Информационные...

Математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов
Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Математическая логика и теория алгоритмов iconУчебно-методический комплекс по дисциплине «Математическая логика и теория алгоритмов»
Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»

Математическая логика и теория алгоритмов iconРабочая программа составлена в соответствии с требованиями фгос впо...
Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,...

Математическая логика и теория алгоритмов iconА. Л. Гудков 16 января 2012 г
«Математическая логика и теория алгоритмов» является формирование представлений о методах и моделях описания предметной и проблемной...

Математическая логика и теория алгоритмов iconЛогика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов
Б. А. Кушнер. Лекции по конструктивному математическому анализу. – М.: Наука, 1973. – 448 с

Математическая логика и теория алгоритмов iconРоссийской Федерации Федеральное государственное бюджетное образовательное...
Изучение дисциплины базируется на курсах “Информатика”, “Дискретная математика”, “Математическая логика и теория алгоритмов”, “Структуры...

Математическая логика и теория алгоритмов iconРадиофизический факультет
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...

Математическая логика и теория алгоритмов iconРабочая программа по дисциплине В. В математическая логика и теория алгоритмов
Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность

Вы можете разместить ссылку на наш сайт:


Литература


При копировании материала укажите ссылку ©ucheba 2000-2015
контакты
l.120-bal.ru
..На главную