n итераций по m итераций, итого порядка n * m операций.Псевдокод:прочитать e // e[0 ... m - 1] - массив, в котором хранятся рёбра и их веса (first, second - вершины, соединяемые ребром, value - вес ребра)for i = 0 ... n - 1d[i] = 2000000000d[0] = 0for i = 1 ... nfor j = 0 ... m - 1if d[e[j].second] > d[e[j].first] + e[j].valued[e[j].second] = d[e[j].first] + e[j].valueif d[e[j].first] > d[e[j].second] + e[j].valued[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 = gfor i = 1 ... n + 1for j = 0 ... n - 1for k = 0 ... n - 1if 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