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

Все темы данного раздела:

Структуры и алгоритмы обработки данных
Дисциплина по направлению 230100.62 – Информатика и вычислительная техника   Лекции   Разработал ст. преподаватель кафедры ИТИС

Асимптотическая временная эффективность
Поведение временной сложности алгоритма в пределе, при увеличении размера задачи, называется асимптотической временной эффективностью. Используются обозначения: Θ – обозначен

Основы анализа программ
  Последовательность действий алгоритма определяется входными данными   Например, алгоритм поиска наибольшего элемента в списке из N элементов &

Необходимые математические сведения
  Округление числа Х влево называется наибольшее целое число, не превосходящее Х. |_ 2,5_| = 2, |_- 7,3_| = -8   Округление числа Х

Метод подстановок
Последовательно производим подстановки и пытаемся уловить общий принцип.   Пример 1. Имеем рекуррентное соотношение      

Численный алгоритм
Программа a:=x; b:=y; c:=0; while b ≠ 0 do {} {} b:=b-1; c:=c+a end {}   Для данной программы определите, что

Динамическое программирование
Динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения.. Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами

Перемножение нескольких матриц
Мы хотим найти произведение A1A2×…×An (1) последовательности п матриц (A1,

Количество расстановок скобок
Простой перебор всех возможных расстановок скобок не даст эффективного алгоритма. Разобъем матрицы на группы по три: произведение для каждой группы можно вычислить двумя способами, так что

Предполагается
матрица Ai имеет размер pi-1 × pi при i = 1,2,2,…,n на входе последовательность  

Теорема 1.
Пусть Z = z1, z2, . . . zk - одна из наибольших общих подпоследовательностей для X = x1, x2,

Рекуррентная формула
Теорема 1 показывает, что нахождением НОП последовательностей и сводится к решению либо одной, либо двух подзадач. Если , то достаточно найти НОП последовательностей и дописать к ней в конце . Если

Включить в стек
• procedure push(var stak:massiv; stksiz:integer; var stktop:integer; data:integer; var pr:boolean); • begin • {vkl} • if stktop >= stksiz then pr:=false • el

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

Хеширование
Хеширование — преобразование по определённому алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями

Реализация словарей
Сортированные или неотсортированные связанные списки; Двоичные векторы (когда элементы множества можно сопоставить с элементами множества целых чисел 1,…., N для некоторого

Анализ хеширования с цепочками
(открытое хеширование) Пусть T – хеш-таблица с m позициями, в которую занесено n элементов/ Коэффициент заполнениятаблицы &#

Открытая адресация
(Закрытое хеширование) Все записи хранятся в самой хэш-таблице. Каждая ячейка таблицы содержит либо элемент динамического множества, либо NIL. h:U × {0, 1, …, m

Поиск слова в тексте
Текст хранится в виде последовательности литер. Необходимо отыскать в нем первое появление определенного «слова», которое можно определить как последовательность литер не длиннее самого текста.

Сортировка
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На прак

Сортировка вставками
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод

Корневая сортировка
При корневой сортировке упорядочивание списка происходит без непосредственного сравнения ключевых значений между собой. При этом создается набор «стопок», а элементы распределяются по стопкам в зав

Сортировка слиянием
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например —

Управление с помощью таблиц
Программа «лексический анализатор» Операция читать_лит – читает очередную литеру анализируемого текста и выдает код, класс литеры. В начале каждого

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

Представление кратчайших путей в алгоритме
Пусть G=(V,E) - заданный граф. Для каждой вершины vÎV мы будем помнить ее предшественника p[v] . Предшественник – это либо другая вершина, либо NIL.

Релаксация
Все алгоритмы для поиска кратчайших путей основаны на технике, называемой релаксацией. Для каждой вершины vÎ V мы храним некоторое число d[v], являющееся

Алгоритм Дейкстры
Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G=(V,E) с исходной вершиной s; в котором веса всех ребер неотрицатель

Алгоритм Беллмана-Форда
Алгоритм Беллмана-Форда решает задачу о кратчайших путях из одной вершины для случая, когда весам ребер разрешено быть отрицательными. Алгоритм возвращает значение TRUE, если в графе нет ц

Максимальный поток
Сетью называется ориентированный граф G=(V,E), каждому ребру (u,v) Î E которого поставлено в соответствие число c(u,v)³0

Упрощенная математическая модель
Задача о минимальном покрывающем дереве Пусть имеется связный неориентированный граф G=(V,E), в котором V – множество контактов, а E – множество их возмо

Теорема
Пусть G=(V,E) - связный неориентированный граф, на множестве вершин которого определена вещественная функция w. Пусть A - множество ребер, являющееся подмножеством некот

Алгоритм Крускала
В любой момент работы алгоритма Крускала множество A выбранных ребер (часть будущего остова) не содержит циклов. Оно соединяет вершины графа в несколько связных компонент, каждая из которых

Алгоритм Прима
  В алгоритме Прима растущая часть остова представляет собой дерево (множество ребер которого есть A). Формирование дерева начинается с произвольной корневой вершины r.

Поиск в глубину
Стратегия поиска в глубину – идти «вглубь», пока это возможно, и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не обнаружены все вершины, достижимые из исход

АВЛ-деревья
1962 год Московские математики Г.М.Адельсон-Вельский и Е.М.Ландис предложили схему самобалансирующегося поискового дерева. Для балансировки дерева требуется произвести каждый раз небольшие