Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритмы и алгоритмические языки

Читайте также:
  1. CRC-алгоритмы обнаружения ошибок
  2. VII. Алгоритмы продаж
  3. Алгоритмы и алгоритмические языки
  4. Алгоритмы расчета физических величин по показаниям датчиков Линейное энерговыделение
  5. АЛГОРИТМЫ СЛ-Я И В-Я ВЕЩЕСТВЕННЫХ ЧИСЕЛ
  6. Государственный язык – турецкий. Языки делового общения – английский, немецкий, французский.

 

 

Доцент каф. Вычислительной математики

Механико-Математического ф-та

МГУ им. М.В.Ломоносова

Староверов В.М.

2010г.


 

 


Лекция 1............................................................................................................................. 5

Представление чисел в ЭВМ....................................................................................... 5

Целые.......................................................................................................................... 5

Вещественные............................................................................................................ 5

Ошибки вычислений.................................................................................................... 9

Лекция 2........................................................................................................................... 11

Алгоритмы. Сведение алгоритмов........................................................................... 11

Нижние и верхние оценки......................................................................................... 11

Сортировки.................................................................................................................. 13

Постановка задачи................................................................................................... 13

Сортировка пузырьком........................................................................................... 14

Сортировка слиянием с рекурсией........................................................................ 16

Сортировка слиянием без рекурсии...................................................................... 18

Лекция 3........................................................................................................................... 19

Алгоритмы. Сведение алгоритмов........................................................................... 19

Сортировки и связанные с ними задачи................................................................... 19

QuickSort.................................................................................................................. 19

Доказательство корректности работы алгоритма............................................... 22

Оценки времени работы алгоритма...................................................................... 23

Некоторые задачи, сводящиеся к сортировке..................................................... 26

Лекция 4........................................................................................................................... 31

Алгоритмы. Сведение алгоритмов........................................................................... 31

Сортировки и связанные с ними задачи................................................................... 31

HeapSort или сортировка с помощью пирамиды................................................ 31

Алгоритмы сортировки за время O(N)................................................................. 33

Сортировка подсчетом............................................................................................ 33

Цифровая сортировка............................................................................................ 34

Сортировка вычерпыванием................................................................................. 34

Лекция 5........................................................................................................................... 37

Алгоритмы. Сведение алгоритмов........................................................................... 37

Порядковые статистики.............................................................................................. 37

Поиск порядковой статистики за время Q(N) в среднем.................................... 37

Поиск порядковой статистики за время Q(N) в худшем случае........................ 39

Язык программирования C........................................................................................... 40

Переменные................................................................................................................ 41

Структуры данных.......................................................................................................... 43

Вектор........................................................................................................................... 43

Стек............................................................................................................................... 44

Лекция 6........................................................................................................................... 47

Структуры данных (+ в языке С: массивы, структуры, оператор typedef).............. 47

Стек............................................................................................................................... 47

Стек. Реализация 1 (на основе массива)............................................................... 47

Стек. Реализация 2 (на основе массива с использованием общей структуры). 48

Стек. Реализация 3 (на основе указателей)........................................................... 48

Стек. Реализация 4 (на основе массива из двух указателей).............................. 49

Стек. Реализация 5 (на основе указателя на указатель)....................................... 49

Очередь......................................................................................................................... 50

Дек................................................................................................................................. 51

Списки.......................................................................................................................... 52

Стандартная ссылочная реализация списков....................................................... 53

Ссылочная реализация списков с фиктивным элементом.................................. 55

Реализация L2-списка на основе двух стеков...................................................... 56

Реализация L2-списка с обеспечением выделения/освобождения памяти....... 57

Лекция 7........................................................................................................................... 58

Структуры данных. Графы............................................................................................ 58

Графы............................................................................................................................ 58

Поиск пути в графе с наименьшим количеством промежуточных вершин..... 58

Представление графа в памяти ЭВМ.................................................................... 63

........................................................................................................................................... 66

Лекция 8........................................................................................................................... 67

Структуры данных. Графы............................................................................................ 67

Поиск кратчайшего пути в графе......................................................................... 67

Лекция 9........................................................................................................................... 72

Бинарные деревья поиска............................................................................................... 72

Поиск элемента в дереве........................................................................................ 73

Добавление элемента в дерево............................................................................... 73

Поиск минимального и максимального элемента в дереве................................ 74

Удаление элемента из дерева................................................................................. 74

Поиск следующего/предыдущего элемента в дереве.......................................... 74

Слияние двух деревьев........................................................................................... 74

Разбиение дерева по разбивающему элементу..................................................... 75

Сбалансированные и идеально сбалансированные бинарные деревья поиска........ 76

Операции с идеально сбалансированным деревом............................................. 77

Операции со сбалансированным деревом............................................................ 78

Поиск элемента в дереве........................................................................................ 78

Добавление элемента в дерево............................................................................... 78

Удаление элемента из дерева................................................................................. 82

Поиск минимального и максимального элемента в дереве................................ 82

Поиск следующего/предыдущего элемента в дереве.......................................... 82

Слияние двух деревьев........................................................................................... 82

Разбиение дерева по разбивающему элементу..................................................... 84

Лекция 10......................................................................................................................... 86

Красно-черные деревья.................................................................................................. 86

Отступление на тему языка С. Поля структур......................................................... 86

Отступление на тему языка С. Бинарные операции............................................... 88

Высота красно-черного дерева.................................................................................. 88

Добавление элемента в красно-черное дерево......................................................... 89

Однопроходное добавление элемента в красно-черное дерево............................. 91

Удаление элемента из красно-черного дерева......................................................... 93

Лекция 11......................................................................................................................... 96

B-деревья......................................................................................................................... 96

Высота B-дерева.......................................................................................................... 97

Поиск вершины в B-дереве........................................................................................ 98

Отступление на тему языка С. Быстрый поиск и сортировка в языке С.............. 98

Добавление вершины в B-дерево............................................................................ 100

Удаление вершины из B-дерева............................................................................... 101

Лекция 12....................................................................................................................... 105

Хеширование................................................................................................................. 105

Метод многих списков............................................................................................. 105

Метод линейных проб.............................................................................................. 106

Метод цепочек........................................................................................................... 110

Хэш-функции............................................................................................................. 113

Хэш-функции на основе деления........................................................................ 113

Хэш-функции на основе умножения.................................................................. 113

CRC-алгоритмы обнаружения ошибок....................................................................... 114

Лекция 14....................................................................................................................... 118

Поиск строк.................................................................................................................... 118

Отступление на тему языка С. Ввод-вывод строк из файла................................. 118

Алгоритм поиска подстроки с использованием хеш-функции (Алгоритм Рабина-Карпа) 119

Конечные автоматы.................................................................................................. 120

Отступление на тему языка С. Работа со строками............................................... 121

Алгоритм поиска подстроки, основанный на конечных автоматах................... 121

Лекция 15....................................................................................................................... 123

Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции) 123

Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов) 125

Эвристика стоп-символа...................................................................................... 125

Эвристика безопасного суффикса....................................................................... 127

Форматы BMP и RLE................................................................................................ 130


Лекция 1


Дата добавления: 2015-10-30; просмотров: 123 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
The form the schedule of performance and delivery of works| Typedef struct CVertex2_

mybiblioteka.su - 2015-2024 год. (0.01 сек.)