Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов




НазваниеУльянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов
страница1/25
Дата24.02.2013
Размер0.83 Mb.
ТипРеферат
  1   2   3   4   5   6   7   8   9   ...   25



МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ


Кафедра

Персональные компьютеры и сети”


Ульянов М.В., Шептунов М.В.


МАТЕМАТИЧЕСКАЯ ЛОГИКА И

ТЕОРИЯ АЛГОРИТМОВ


Часть II


ТЕОРИЯ АЛГОРИТМОВ


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


Москва

2003



УДК 519.713


Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: МГАПИ, 2003. – 80 с.


ISBN 5-8068-02 68 - Х


Рекомендовано Ученым Советом МГАПИ в качестве учебного пособия для специальности 2201.


Рецензенты: к.т.н., проф. Зеленко Г.В.

к.т.н., проф. Рощин А.В.


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

Для специальности 2201 «Вычислительные машины, комплексы, системы и сети» это издание может быть использовано в качестве учебного пособия по разделу «Теория алгоритмов» дисциплины «Математическая логика и теория алгоритмов».

Во второй части учебного пособия рассмотрены основы таких разделов теории алгоритмов как: классическая теория алгоритмов (машина Поста, машина Тьюринга, алгоритмически неразрешимые задачи), асимптотический анализ сложности алгоритмов, сложностные классы и практический сравнительный анализ вычислительных алгоритмов.




 Ульянов М.В., Шептунов М.В., 2003

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

1. ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ 6

1.1 Исторический обзор 6

1.2 Цели и задачи теории алгоритмов 6

1.3 Практическое применение результатов теории алгоритмов 7

1.4 Формализация понятия алгоритма 7

1.5 Вопросы для самоконтроля 8

2. МАШИНА ПОСТА 9

2.1 Основные понятия и операции 9

2.2 Финитный 1 – процесс 9

2.3 Способ задания проблемы и формулировка 1 10

2.4 Вопросы для самоконтроля 11

3. МАШИНА ТЬЮРИНГА И АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ 12

3.1. Машина Тьюринга 12

3.2. Алгоритмически неразрешимые проблемы 13

3.3. Проблема соответствий Поста над алфавитом Σ 15

3.4 Вопросы для самоконтроля 17

4. ВВЕДЕНИЕ В АНАЛИЗ АЛГОРИТМОВ 18

4.1. Сравнительные оценки алгоритмов 18

4.2 Система обозначений в анализе алгоритмов 18

4.3 Классификация алгоритмов по виду функции трудоёмкости 19

4.4 Асимптотический анализ функций 20

4.5 Вопросы для самоконтроля 23

5. ТРУДОЕМКОСТЬ АЛГОРИТМОВ И ВРЕМЕННЫЕ ОЦЕНКИ 24

5.1. Элементарные операции в языке записи алгоритмов 24

5.2 Примеры анализа простых алгоритмов 25

5.3. Переход к временным оценкам 26

5.4 Пример пооперационного временного анализа 27

5.5 Вопросы для самоконтроля 29

6. ТЕОРИЯ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ И СЛОЖНОСТНЫЕ КЛАССЫ ЗАДАЧ 30

6.1 Теоретический предел трудоемкости задачи 30

6.2 Сложностные классы задач 30

6.3 Проблема P = NP 31

6.4 Класс NPC (NP – полные задачи) 32

6.5 Примеры NP – полных задач 33

6.6 Вопросы для самоконтроля 34

7. ПРИМЕР ПОЛНОГО АНАЛИЗА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ О СУММЕ 36

7.1 Формулировка задачи и асимптотическая оценка 36

7.2 Алгоритм точного решения задачи о сумме (метод перебора) 36

7.3 Анализ алгоритма точного решения задачи о сумме 37

7.4 Вопросы для самоконтроля 39

8. РЕКУРСИВНЫЕ ФУНКЦИИ И АЛГОРИТМЫ 40

8.1 Рекурсивные функции 40

8.2 Рекурсивная реализация алгоритмов 41

8.3 Анализ трудоемкости механизма вызова процедуры 43

8.4 Анализ трудоемкости алгоритма вычисления факториала 45

8.5 Вопросы для самоконтроля 45

9. РЕКУРСИВНЫЕ АЛГОРИТМЫ И МЕТОДЫ ИХ АНАЛИЗА 46

9.1 Логарифмические тождества 46

9.2 Методы решения рекурсивных соотношений 46

9.3 Рекурсивные алгоритмы. 46

9.4 Основная теорема о рекуррентных соотношениях 47

9.5 Вопросы для самоконтроля 47

10. ПРЯМОЙ АНАЛИЗ РЕКУРСИВНОГО ДЕРЕВА ВЫЗОВОВ 48

10.1 Алгоритм сортировки слиянием 48

10.2 Слияние отсортированных частей (Merge) 48

10.3 Подсчет вершин в дереве рекурсивных вызовов 49

10.4 Анализ трудоемкости алгоритма сортировка слиянием 50

10.5 Вопросы для самоконтроля 50

11. ТЕОРИЯ И АЛГОРИТМЫ МОДУЛЯРНОЙ АРИФМЕТИКИ 51

11.1 Алгоритм возведения числа в целую степень 51

11.2 Сведения из теории групп 53

11.3 Сведения из теории простых чисел 53

11.4 Вопросы для самоконтроля 54

12. КРИПТОСИСТЕМА RSA И ТЕОРИЯ АЛГОРИТМОВ 55

12.1 Мультипликативная группа вычетов по модулю n 55

12.2 Степени элементов в Zn* и поиск больших простых чисел 55

12.3 Криптосистема RSA 56

12.4 Криптостойкость RSA и сложность алгоритмов факторизации 56

12.5 Вопросы для самоконтроля 57

ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ 58

ЛИТЕРАТУРА 60



ВВЕДЕНИЕ


Теория алгоритмов - это наука, изучающая общие свойства и закономерности алгоритмов, разнообразные формальные модели их представления. На основе формализации понятия алгоритма возможно сравнение алгоритмов по их эффективности, проверка их эквивалентности, определение областей применимости.

Разработанные в 1930-х годах разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч), равно как и предложенные в 1950-х годах модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.

В настоящее время полученные на основе теории алгоритмов практические рекомендации получают всё большее распространение в области проектирования и разработки программных систем. В связи с этим в государственный стандарт введёна специальная дисциплина “Математическая логика и теория алгоритмов”. Описание государственного стандарта регламентирует включение в состав дисциплины ряда понятий и методов теории алгоритмов, которые и отражены в настоящем учебном пособии.

Во второй части учебного пособия рассмотрены основы таких разделов теории алгоритмов как: классическая теория алгоритмов (машина Поста, машина Тьюринга, алгоритмически неразрешимые проблемы), асимптотический анализ сложности алгоритмов, включая сложность рекурсивных реализаций, сложностные классы P, NP, NPC, включая проблему P = NP и практический сравнительный анализ алгоритмов. На примере криптосистемы RSA показана практическая важность результатов теории алгоритмов.

1. ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ
  1   2   3   4   5   6   7   8   9   ...   25

Похожие:

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

Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов iconМатематическая логика и теория алгоритмов

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


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