Различия

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

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

Предыдущая версия справа и слева Предыдущая версия
Следующая версия
Предыдущая версия
links_other [12/04/2019 12:38]
Олег Альбертович Скворцов [Разное]
links_other [02/12/2019 12:27] (текущий)
Олег Альбертович Скворцов [TCP/IP]
Строка 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://​www.ibm.com/​support/​knowledgecenter/​ru/​ssw_aix_72/​network/​tcpip_intro.html| ]] 
 + 
 +[[https://​webonto.ru/​protokolyi-tcp-ip-prostyim-yazyikom/​]] 
 + 
 +[[https://​habr.com/​ru/​post/​326574/​]] 
 + 
 +[[http://​hron.com.ua/​it/​programmyi-os/​prostymi-slovami-printsip-raboty-internet-protokolov-tcp-ip/​]] 
 + 
 +[[https://​zametkinapolyah.ru/​kompyuternye-seti/​stek-protokolov-tcp-ip.html]] 
 + 
  
-[[https://​studfiles.net/​preview/​3276187/​ |Тема № 8. Жадные алгоритмы,​ теоретические основы,​ применение.]] 
  
  
Строка 629: Строка 802:
  
 [[https://​help.libreoffice.org/​Writer/​Instructions_for_Using_Writer/​ru]] [[https://​help.libreoffice.org/​Writer/​Instructions_for_Using_Writer/​ru]]
 +
 +
 +
 +
 +
CC Attribution-Noncommercial 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0