n итераций по m итераций, итого порядка n * m операций.

Псевдокод:

прочитать e // e[0 ... m - 1] - массив, в котором хранятся рёбра и их веса (first, second - вершины, соединяемые ребром, value - вес ребра)

for i = 0 ... n - 1

d[i] = 2000000000

d[0] = 0

for i = 1 ... n

for j = 0 ... m - 1

if d[e[j].second] > d[e[j].first] + e[j].value

d[e[j].second] = d[e[j].first] + e[j].value

if d[e[j].first] > d[e[j].second] + e[j].value

d[e[j].first] = d[e[j].second] + e[j].value

вывести d

Алгоритм Флойда-Уоршелла

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

Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
n итераций по n итераций по n итераций, итого порядка n^3 операций.
Псевдокод:

прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет

d = g

for i = 1 ... n + 1

for j = 0 ... n - 1

for k = 0 ... n - 1

if d[j][k] > d[j][i - 1] + d[i - 1][k]

d[j][k] = d[j][i - 1] + d[i - 1][k]

вывести d

10. 
    Строки
    

Строки

1. Поиск подстроки:
Префикс-функцией от строки ss называется массив pp, где p_ipi равно длине самого большого префикса строки s_0 s_1 s_2 \ldots s_is0s1s2…si, который также является и суффиксом ii-того префика (не считая весь ii-й префикс).

Z-функция от строки ss определяется как массив zz, такой что z_izi равно длине максимальной подстроки, начинающейся с ii-й позиции, которая равна префиксу ss.

2. Хеширование:

---

Полиномиальное хеширование
Коллизии хешей
Проверки на изоморфизм
3. Строковые структуры
Автоматы — абстрактные математические объекты, как-то реагирующие на некоторые события, или символы.

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

Автоматы могут описывать много различных процессов и вычислений. Например, компьютер сам по себе является частным случаем реализации автомата: состоянием является содержимое оперативной памяти и регистров, событиями — взаимодействие с пользователем, правилами перехода — архитектура.
Другим примером являются клеточные автоматы, возможно знакомые читателю по игре «Жизнь» Джона Конвея. В ней состояние и правила переходов автомата определяется состоянием каждой индивидуальной клетки, так, что правила применяются сразу ко всей решетке.

---

Смотрите также файлы

• Министерство образования Республики Башкортостан.docx

• При каком положительном значении параметра t прямые, заданные уравнениями 3tx.doc

• Социальная педагогика как вид профессиональной деятельности.docx

• Тесты для самоконтроля Ситуационные задачи.doc

• Задача 1 Для ступенчатого стального стержня находящегося под воздействием заданных внешних сил.docx