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

Алгоритмы и алгоритмические языки. Доцент каф. Вычислительной математики

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

 

 

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

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

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

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

2010г.


 

 

Лекция 1. 5

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

Целые. 5

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

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

Лекция 2. 9

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

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

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

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

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

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

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

Лекция 3. 15

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

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

QuickSort. 15

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

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

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

Лекция 4. 25

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

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

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

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

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

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

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

Лекция 5. 31

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

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

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

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

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

Переменные. 35

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

Вектор. 37

Стек. 38

Лекция 6. 41

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

Стек. 41

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

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

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

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

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

Очередь. 44

Дек. 45

Списки. 46

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

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

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

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

Лекция 7. 52

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

Графы.. 52

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

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

Лекция 8. 60

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

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

Лекция 9. 65

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Лекция 10. 78

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

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

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

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

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

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

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

Лекция 11. 88

B-деревья. 88

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

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

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

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

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

Лекция 12. 97

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

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

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

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

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

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

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

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

Лекция 14. 109

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

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

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

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

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

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

Лекция 15. 114

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

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

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

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

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


Лекция 1


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


 

 

Читайте в этой же книге: Нижние и верхние оценки. | Постановка задачи | Сортировка пузырьком. | Сортировка слиянием с рекурсией. | Сортировка слиянием без рекурсии. | Доказательство корректности работы алгоритма. | Оценки времени работы алгоритма. | Некоторые задачи, сводящиеся к сортировке. | Сортировки и связанные с ними задачи. | SortB (A, N, M, B) |
<== предыдущая страница | следующая страница ==>
Stages of construction of algorithm with structural scheme use| Представление чисел в ЭВМ

mybiblioteka.su - 2015-2022 год. (0.042 сек.)