https://se.moevm.info/ 2026-05-25T20:53:00+00:00 https://se.moevm.info/ https://se.moevm.info/lib/exe/fetch.php/wiki:logo.png text/html 2025-08-29T07:34:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://se.moevm.info/doku.php/courses:algorithms_building_and_analysis:materials:a_star_ways?rev=1756452849&do=diff Эвристические алгоритмы Эвристический алгоритм - алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который точно известно, что он дает достаточно хорошее решение в большинстве случаев.$>0$$A^*$$f(x)$$f(x) = h(x) + g(x)$$A^*$$A^*$$h(u) = |ux - goal.x| + |uy - goal.y|$$h(u) = \max ( |ux - goal.x|, |uy - goal.y| )$$ h(u) = \sqrt{(ux - goal.x)^2 + (uy + goal.y)^2} $$g(x)$$h(x)$$А^*$$A^*$$А^*$$А^*$$$ O ( |V|^2 ) $$$$ O ( |V| \cdot \log |V| ) $$… text/html 2025-08-29T07:34:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://se.moevm.info/doku.php/courses:algorithms_building_and_analysis:materials:aho-corasick?rev=1756452849&do=diff Алгоритм Ахо-Корасик Введение Дополним обычную задачу поиска подстроки в тексте необходимостью найти вхождения k подстрок. Нам известны алгоритмы, производящие поиск для одной подстроки, длина которой не превосходит длины текста за O(n), где n – длина текста. Таким образом, если пользоваться этими алгоритмами, то для k подстрок нам придётся выполнить k процедур поиска, что приведёт к результирующей сложности в O(nk), что не очень-то и эффективно. Для решения этой проблемы существует алгоритм А… text/html 2025-08-29T07:34:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://se.moevm.info/doku.php/courses:algorithms_building_and_analysis:materials:graph_coloring_notes?rev=1756452849&do=diff [В работе] Конспект лекции по раскраскам Раскраска графа * * * * * * * Раскраска графа Когда говорят о раскраске графов, почти всегда подразумевают под этим раскраску их вершин, то есть присвоение цветовых меток вершинам графа так, чтобы любые две вершины, имеющие общее ребро, имели разные цвета. Так как графы, в которых есть петли, не могут быть раскрашены таким образом, они не являются предметом обсуждения.$O(3^n)$$O(1.232^n)$$O(2^n)$$n$$\le \frac{n}{3}$$$ Cn^0 … text/html 2025-08-29T07:34:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://se.moevm.info/doku.php/courses:algorithms_building_and_analysis:materials:np_full_tasks_notes?rev=1756452849&do=diff NP класс и NP-полные задачи Вопросы и ответы про $NP, P$ и т.д. Что такое класс $P$? $P$ -- класс задач, решаемых за полиномиальное (от размера входа) время. Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д. $T(n)=O(n^k)$$k$$n$$m$$n$$NP$$NP$$P$$NP$$NP$$NP$$NP$$NP$$NP$$NP$$NP$$NP$$NP$$NP$$NP$$P=NP$$P$$NP$$P$$NP=P$$NP$$P$… text/html 2025-08-29T07:34:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://se.moevm.info/doku.php/courses:algorithms_building_and_analysis:materials:shortest_ways?rev=1756452849&do=diff Кратчайшие пути Постановка задачи Задача о кратчайшем пути - задача поиска кратчайшего пути от заданной вершины до заданной или до всех остальных.$v$$v^2$$O(v^2)$$O( ln⁡(v) )$$n$$0$$n - 1$$i - j$$w_{ij}$$i - j$$w_{ij} = + \infty$$w%%_{%%ii} = 0$$a_{ij}^{k}$$i$$j$$k$$a_{ij}^{0}$$i$$j$$i - j$$a_{ij}^{0} = w{ij}$$a_{ij}^{1} = w{ij}$$a_{ij}^{2}$$a{ij}^{n}$$a_{ij}^{n}$$i$$j$$a_{ij}^{0}, a_{ij}^{1}, a_{ij}^{2}, \dots, a_{ij}^{n}$$k$$a_{ij}^{0} = w{ij}$$a_{ij}^{k - 1}$$a_{ij}^{k}$$i$$j$$k$$k - 1$$k -… text/html 2026-05-24T09:43:55+00:00 Anonymous (anonymous@undisclosed.example.com) https://se.moevm.info/doku.php/courses:algorithms_building_and_analysis:materials:start?rev=1779615835&do=diff Материалы Книги * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест. «Алгоритмы: построение и анализ» * Седжвик Р., Уэйн К. «Алгоритмы на Java