мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия
Предыдущая версия
Следующая версияСледующая версия справа и слева
links_other [12/04/2019 12:38] – [Разное] ocalinks_other [02/12/2019 11:58] – [TCP/IP] oca
Строка 615: Строка 615:
 [[https://habr.com/ru/post/120343/]] Жадные алгоритмы [[https://habr.com/ru/post/120343/]] Жадные алгоритмы
  
-[[https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC]] Жадные алгоритмы+[[https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC | Жадный алгоритм 
 +(Материал из Википедии — свободной энциклопедии)]]  
 + 
 +[[https://studfiles.net/preview/3276187/ |Тема № 8. Жадные алгоритмы, теоретические основы, применение.]] (Есть проблемы) 
 + 
 + 
 +===== Визуализация алгоритмов ===== 
 + 
 +[[https://tproger.ru/digest/sorting-algorithms-visualized/]] 
 + 
 + 
 +===== Комбинаторика ===== 
 + 
 +=== Ссылки === 
 + 
 + 
 +===== Графы ===== 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BD%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0%D1%85| Алгоритмы на графах]] 
 + 
 +=== Алгоритмы === 
 + 
 +Компиляция (скромная форма плагиата) из Википедии. 
 + 
 +В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе: 
 + 
 +  * Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. 
 +  * Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес рёбер может быть отрицательным. Не может быть "отрицательных  циклов" 
 +  * Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе. 
 +  * Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми парами вершин **взвешенного ориентированного графа**. 
 +  * Алгоритм Джонсона также находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. 
 +  * Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (рёбер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Также используется для поиска кратчайшего расстояния на карте в стратегических играх. 
 +  * Поиск кратчайшего пути на основе алгоритма Килдала. 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B|Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm)]] — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS. 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%B5%D0%BB%D0%BB%D0%BC%D0%B0%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%BE%D1%80%D0%B4%D0%B0|Алгоритм Беллмана — Форда]] — алгоритм поиска кратчайшего пути во взвешенном графе. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом. 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0|Алгори́тм Левита (Levit’s algorithm)]] — алгоритм на графах, находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм также работает для графов с рёбрами отрицательного веса. Алгоритм широко применяется в программировании и технологиях. 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B8|Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли)]] — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину. 
 + 
 +В основном используется при компьютерной трассировке (разводке) печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх. 
 + 
 +Волновой алгоритм в контексте поиска пути в лабиринте был предложен Э. Ф. Муром. Ли независимо открыл этот же алгоритм при формализации алгоритмов трассировки печатных плат в 1961 году. 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%BE%D0%BD%D1%81%D0%BE%D0%BD%D0%B0|Алгоритм Джонсона]] — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом. Назван в честь Д. Б. Джонсона[en], опубликовавшего алгоритм в 1977 году. 
 + 
 +=== Методы обхода графа === 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83|Поиск в глубину (англ. Depth-first search, DFS)]] — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин[1]. 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83|Поиск в ширину (англ. breadth-first search, BFS)]]) — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из **неинформированных**(это не ругань, термин) алгоритмов поиска. 
 + 
 +Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах. 
 + 
 +Поиск в ширину может применяться для решения задач, связанных с теорией графов: 
 + 
 +  * Волновой алгоритм поиска пути в лабиринте 
 +  * Волновая трассировка печатных плат 
 +  * Поиск компонент связности в графе 
 +  * Поиск кратчайшего пути между двумя узлами невзвешенного графа 
 +  * Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа 
 +  * Нахождение кратчайшего цикла в ориентированном невзвешенном графе 
 +  * Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами 
 +  * Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа) 
 + 
 +[[https://ru.wikipedia.org/wiki/A*|Поиск A* (произносится «А звезда» или «А стар», от англ. A star)]] — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). 
 + 
 +Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет), и функции эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x)). 
 + 
 +Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. 
 + 
 +Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Новый алгоритм достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*. 
 + 
 +[[https://habr.com/ru/post/65367/| Алгоритмы на графах — Базовые понятия]] 
 + 
 +[[https://proglib.io/p/graphs-algoguide/| 10 алгоритмов на графах в гифках]] 
 + 
 +[[https://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2]] 
 + 
 +[[https://informatics.mccme.ru/course/view.php?id=6]] 
 + 
 +[[http://www.codenet.ru/progr/other/prbook/]] 
 + 
 +[[http://study-and-dev.com/blog/sda_theory_graphs/]] 
 + 
 +[[https://codeforces.com/blog/entry/5558]] 
 + 
 +[[https://www.yaklass.ru/p/informatika/11-klass/grafy-i-algoritmy-na-grafakh-40408]] 
 + 
 +[[http://neerc.secna.ru/Algor/algo_base.html]] 
 + 
 +[[http://e-maxx.ru/algo/]] 
 + 
 +[[https://tproger.ru/articles/pathfindings/|Алгоритмы поиска пути в графе]] 
 + 
 +[[http://inf-w.ru/?page_id=7359]] 
 + 
 +[[https://acm.bsu.by/wiki/%D0%A2%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2| Терминология теории графов]] 
 + 
 +[[https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2| Глоссарий теории графов]] 
 + 
 + 
 +----------------- 
 + 
 +[[https://proglib.io/p/awesome-algorithms/]] 
 + 
 +[[https://proglib.io/p/required-programmer-algorithms/]] 
 + 
 +[[https://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2]] 
 + 
 + 
 + 
 +===== Комбинаторика ===== 
 + 
 +[[http://mathematichka.ru/school/combinatorics/combination.html|Формулы комбинаторики.]] 
 + 
 +[[https://math.ru/lib/363|Комбинаторика. Наум Яковлевич Виленкин]] 
 + 
 +===== ЕГЭ по информатике ===== 
 + 
 +Онлайн Тесты 
 + 
 +[[https://iq2u.ru/tests/35?level=13]] 
 + 
 +[[https://edunews.ru/ege/informatika/test/]] 
 + 
 +[[https://yandex.ru/tutor/subject/?subject_id=6]] 
 + 
 +[[https://examer.ru/ege_po_informatike/2020/]]  разрозненные задания! 
 + 
 +[[http://ogege.ru/kursy_i_predmety/informatika/online_test_ege]] 
 + 
 +[[]] 
 + 
 + 
 + 
 + 
 +[[https://onlyege.ru/trenirovochnyj-variant-ege-2020-po-informatike-2-s-otvetami/]] 
 + 
 +[[https://bingoschool.ru/ege/informatics/tasks/
 + 
 +[[https://oltest.ru/tests/informacionnye_tehnologii/informatika/]] 
 + 
 +[[https://testedu.ru/test/informatika/]] 
 + 
 +[[https://testserver.pro/index/common/nform]] 
 + 
 + 
 + 
 +[[https://banktestov.ru/test/education/informatika]]  Разные тесты 
 + 
 + 
 +===== TCP/IP ===== 
 + 
 +[[https://wiki.merionet.ru/seti/13/nat-na-palcax-chto-eto/]] 
 + 
 +[[http://citforum.ru/nets/comer/contents.shtml| Д. Комер "Межсетевой обмен с помощью TCP/IP"]] 
 + 
 +[[https://sonikelf.ru/terminologiya-kompyuternoj-seti-ili-chto-est-chto-ip-tcp-udp-icmp-mac-i-pr/#chto-takoe-maska-adresa-podset|Что такое IP, TCP, UDP, ICMP, MAC и прочее — терминология сети]]   
 + 
 +[[http://www.ofnet.ru/osnovy-interneta/tcpip/| Протокол TCP/IP или как работает Интернет (для чайников)]]
  
-[[https://studfiles.net/preview/3276187/ |Тема № 8. Жадные алгоритмы, теоретические основы, применение.]] 
  
  
Строка 629: Строка 790:
  
 [[https://help.libreoffice.org/Writer/Instructions_for_Using_Writer/ru]] [[https://help.libreoffice.org/Writer/Instructions_for_Using_Writer/ru]]
 +
 +
 +
 +
 +