Алговики - Вклад [ru]

Anton121 Test Page

2022-05-09T18:09:50Z

Anton121: /* Так, ну допустим, посмотрим, как здесь отображается текст!' */

=='''''Посмотрим, как здесь отображается текст''''==
''Организуем список, варианты входа в критическую секцию:''
* pragma critical
* pragma atomic
* locks
* Other knowledges
Just statistic about Covid-19 new victims
[https://yandex.ru/covid19/stat?utm_source=main_graph&utm_source=main_notif&geoId=225 Covid-19 statistic]
[[Файл:Bigstock.jpg|мини|<big>Push to make your life easier!</big>]]
Снизу текста должно быть написанонижний 
Сверху текста должно быть написаноВерхний
{| class="wikitable sortable"
|-
! 2019 !! 2020 !! 2021
|-
| 7,5 bil || 7,7 bil || 7,9 bil
|-
| 90% || 99% ||
* <big>121%</big>
* 122%
|}
[[Открытая_энциклопедия_свойств_алгоритмов| Главная страница]]
<gallery>
Bigstock.jpg|Эти кнопки
Bigstock.jpg|Для тестирования
Bigstock.jpg|Добавления
Bigstock.jpg|Картинок
</gallery>

Так, дальше я просто скопировал код для какого-то шаблона
:<math>
A \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix} = \sum_{\begin{smallmatrix} \gamma_{1} < \gamma_{2} < \cdots < \gamma_{k} \end{smallmatrix}} L \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\end{pmatrix} U\begin{pmatrix}
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix}
</math>

Anton121 Test Page

2022-05-09T16:31:34Z

Anton121:

=='''''Так, ну допустим, посмотрим, как здесь отображается текст!''''==
''Организуем списочек, варианты входа в критическую секцию:''
* pragma critical
* pragma atomic
* locks
* Other knowledges
Just statistic about Covid-19 new victims
[https://yandex.ru/covid19/stat?utm_source=main_graph&utm_source=main_notif&geoId=225 Covid-19 statistic]
[[Файл:Bigstock.jpg|мини|<big>Push to make your life easier!</big>]]
Снизу текста должно быть написанонижний 
Сверху текста должно быть написаноВерхний
{| class="wikitable sortable"
|-
! 2019 !! 2020 !! 2021
|-
| 7,5 bil || 7,7 bil || 7,9 bil
|-
| 90% || 99% ||
* <big>121%</big>
* 122%
|}
[[Открытая_энциклопедия_свойств_алгоритмов| Главная страница]]
<gallery>
Bigstock.jpg|Эти кнопки
Bigstock.jpg|Для тестирования
Bigstock.jpg|Добавления
Bigstock.jpg|Картинок
</gallery>

Так, дальше я просто скопировал код для какого-то шаблона
:<math>
A \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix} = \sum_{\begin{smallmatrix} \gamma_{1} < \gamma_{2} < \cdots < \gamma_{k} \end{smallmatrix}} L \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\end{pmatrix} U\begin{pmatrix}
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix}
</math>

Anton121 Test Page

2022-05-09T16:27:44Z

Anton121:

=='''''Так, ну допустим, посмотрим, как здесь отображается текст!''''==
''Организуем списочек, варианты входа в критическую секцию:''
* pragma critical
* pragma atomic
* locks
* Other knowledges
Just statistic about Covid-19 new victims
[https://yandex.ru/covid19/stat?utm_source=main_graph&utm_source=main_notif&geoId=225 Covid-19 statistic]
[[Файл:Bigstock.jpg|мини|<big>Push to make your life easier!</big>]]
Снизу текста должно быть написанонижний 
Сверху текста должно быть написаноВерхний
{| class="wikitable sortable"
|-
! 2019 !! 2020 !! 2021
|-
| 7,5 bil || 7,7 bil || 7,9 bil
|-
| 90% || 99% ||
* <big>121%</big>
* 122%
|}
[[Открытая_энциклопедия_свойств_алгоритмов| Главная страница]]
<gallery>
Bigstock.jpg|Нужно больше
Bigstock.jpg|Кнопок
Bigstock.jpg|Нужно больше
Bigstock.jpg|Золота
</gallery>

Так, дальше я просто скопировал код для какого-то шаблона
:<math>
A \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix} = \sum_{\begin{smallmatrix} \gamma_{1} < \gamma_{2} < \cdots < \gamma_{k} \end{smallmatrix}} L \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\end{pmatrix} U\begin{pmatrix}
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix}
</math>

Anton121 Test Page

2022-05-09T16:27:06Z

Anton121: /* Так, ну допустим, посмотрим, как здесь отображается текст, карл!' */

=='''''Так, ну допустим, посмотрим, как здесь отображается текст!''''==
''Организуем списочек, варианты входа в критическую секцию:''
* pragma critical
* pragma atomic
* locks
* Other knowledges
Just statistic about Covid-19 new victims
[https://yandex.ru/covid19/stat?utm_source=main_graph&utm_source=main_notif&geoId=225 Covid-19 statistic]
[[Файл:Bigstock.jpg|мини|<big>Push to make your life easier!</big>]]
Снизу текста должно быть написанонижний штангенциркуль 
Сверху текста должно быть написаноВерхний Луивитон
{| class="wikitable sortable"
|-
! 2019 !! 2020 !! 2021
|-
| 7,5 bil || 7,7 bil || 7,9 bil
|-
| 90% || 99% ||
* <big>121%</big>
* 122%
|}
[[Открытая_энциклопедия_свойств_алгоритмов| Главная страница]]
<gallery>
Bigstock.jpg|Нужно больше
Bigstock.jpg|Кнопок
Bigstock.jpg|Нужно больше
Bigstock.jpg|Золота
</gallery>

Так, дальше я просто скопировал код для какого-то шаблона
:<math>
A \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix} = \sum_{\begin{smallmatrix} \gamma_{1} < \gamma_{2} < \cdots < \gamma_{k} \end{smallmatrix}} L \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\end{pmatrix} U\begin{pmatrix}
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix}
</math>

Шаблон:PushButton

2022-05-02T15:18:22Z

Anton121:

[{{{link|https://parallel.ru/}}} <span style="font-size:{{{size|initial}}}; color:{{{color|white}}};
font-style:{{{style|initial}}}; background-color:{{{b-color|none}}}; font-weight: {{{weight|initial}}};
text-decoration:{{{decoration|initial}}}; text-transform:{{{transform|initial}}}"
class="mw-ui-button mw-ui-progressive"> {{{text|Get Perf.Data}}} ]

Anton121 Test Buttons

2021-11-07T14:52:12Z

Anton121:

== Постановка задачи ==

Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Подграф, являющийся деревом и проходящий через все вершины
<math>G</math>, называется ''основным деревом''. Остовное дерево называется ''минимальным'', если суммарный вес его рёбер является минимальным среди всех остовных
деревьев.

Постановка задачи и алгоритм её решения были впервые опубликованы в работе Отакара Борувки<ref name=boruvka>Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti Alexander Daryin, no. 3 (1926): 37–58.</ref>. Английское название задачи – Minimum Spanning Tree (MST).

== Варианты задачи ==

Если исходный граф <math>G</math> несвязный, то набор минимальных остовных деревьев для всех компонент связности называется ''минимальным остовным лесом'' (Minimum
Spanning Forest, MSF).

Для графа с целочисленными весами возможно использование специальных приёмов, таких как [[wikipedia:ru:Поразрядная сортировка|поразрядная сортировка]], что приводит к
алгоритмам, решающим задачу за линейное время.

В распределённой задаче может присутствовать дополнительное требование, что обмен данными происходит только вдоль рёбер графа.

== Свойства задачи ==

'''Веса'''. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, <math>[0, 1]</math>.

'''Существование и единственность'''. Минимальный опорный лес всегда существует, а если все веса рёбер различны, то он единственный. Как уже отмечалось, всегда можно сделать веса рёбер различными. Если условие различных весов не выполняется, легко построить пример, в котором будет существовать более одного минимального остовного дерева.

'''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих
<math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.

'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

'''Минимальное ребро графа'''. Если <math>e^*</math> – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву. На этом свойстве основан [[алгоритм Крускала]].

'''Ассоциативность по рёбрам'''. Пусть <math>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда

:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>

'''Количество рёбер''' остовного леса для графа с <math>n</math> вершинами и <math>c</math> компонентами связности равно <math>n-c</math>. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее.

== Описание входных и выходных данных ==

'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j},
v^{(2)}_{j})</math> с весами <math>f_j</math>).

'''Объём входных данных''': <math>O(m + n)</math>.

'''Выходные данные''': список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).

'''Объём выходных данных''': <math>O(n)</math>.

== Алгоритмы решения задачи ==

Существует три классических подхода к решению задачи:
* [[Алгоритм Борувки]];<ref name=boruvka />
* [[Алгоритм Крускала]];<ref>Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7, no. 1 (1956): 48–48. doi:10.1090/S0002-9939-1956-0078686-7.</ref>
* [[Алгоритм Прима]].<ref>Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.</ref><ref>Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.</ref>
Во всех случаях последовательная сложность алгоритма <math>O(m \ln n)</math> при использовании обычных структур данных. (Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.)

Все другие алгоритмы, как правило, являются вариацией на тему одного из трёх перечисленных, или их комбинацией.
* '''Алгоритм GHS''' (Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> и его последующие версии<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref> являются распределённым вариантом алгоритма Борувки. Это алгоритм обычно используется для автоматического распределённого построения остовного дерева сетью коммутаторов.
* '''Алгоритм Габова''' и др.<ref>Gabow, Harold N, Zvi Galil, Thomas H Spencer, and Robert Endre Tarjan. “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs.” Combinatorica 6, no. 2 (June 1986): 109–22. doi:10.1007/BF02579168.</ref> использует [[wikipedia:ru:Фибоначчиева куча|фибоначчиеву кучу]] для упорядочения рёбер в алгоритме Борувки. Сложность <math>O(m \ln \beta (m, n))</math>.
* '''Алгоритм Фредмана и Уилларда'''<ref>Fredman, Michael L, and Dan E Willard. “Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.” Journal of Computer and System Sciences 48, no. 3 (June 1994): 533–51. doi:10.1016/S0022-0000(05)80064-9.</ref> предназначен для графов с целочисленными весами и имеет линейную оценку сложности <math>O(m)</math>. Используется алгоритм Прима в сочетании со специально разработанным алгоритмом кучи ([[wikipedia:AF-heap|AF-heap]]).
* '''Алгоритм Каргера''' и др.<ref>Karger, David R, Philip N Klein, and Robert Endre Tarjan. “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.” Journal of the ACM 42, no. 2 (March 1, 1995): 321–28. doi:10.1145/201019.201022.</ref> решает задачу ''в среднем'' за линейное время <math>O(m)</math>. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.)

Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем <math>O(m \ln n)</math>, как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров.

== Ресурс параллелизма ==

# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

== Ссылки ==

<references />
== '''LinkButtons''' ==

Все кнопки ниже ведут на "yandex.ru" (Просто показано их разное "оформление") 

<s>{{PushButton|link = https://yandex.ru/|text = Yandex}}</s>
{{PushButton|link = https://yandex.ru/|text = Yandex|color = yellow|weight = 900}}
{{PushButton|link = https://yandex.ru/|text = Yandex|decoration = underline}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|weight = bold}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|color = yellow|b-color = red|weight = bold}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|color = yellow|weight = 900|decoration = line-through}}
----
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px}}
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px|weight = bold|decoration = underline|color = orange}}

Anton121 Test Buttons

2021-11-07T13:05:11Z

Anton121:

{{algorithm
| name = Алгоритм поиска в ширину (BFS)
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>N/A, \max O(|V|) </math>
| pf_width = <math>N/A, \max O(|E|) </math>
| input_data = <math>O(|V| + |E|)</math>
| output_data = <math>O(|V|)</math>
}}

Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

'''Поиск в ширину''' (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Кроме того, поиск в ширину позволяет решать задачу проверки достижимости (существуют ли пути между вершиной источником и остальными вершинами графа). Впервые алгоритм поиска в ширину описан в работах Мура<ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> и Ли<ref>Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.</ref>.

Алгоритм основан на обходе вершин графа "по слоям". На каждом шаге есть множество "передовых" вершин, для смежных к которым производится проверка, относятся ли они к еще не посещенным. Все еще не посещенные вершины добавляются в новое множество "передовых" вершин, обрабатываемых на следующем шаге. Изначально в множество "передовых" вершин входит только вершина-источник, от которой и начинается обход.

В последовательном случае алгоритм имеет алгоритмическую сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> - число вершин в графе, <math>|E|</math> - число ребер в графе.

=== Математическое описание алгоритма ===

Пусть задан граф <math>G = (V, E)</math> без весов, и с выделенной вершиной-источником <math>u</math>. Путем <math>P(u,v)</math> между вершинами <math>u</math> и <math>v</math> называется множество ребер <math>(u, v_1), (v_1, v_2), ... (v_{n-1}, v)</math>. Длиной пути <math>d(u,v)</math> обозначим число ребер в данном пути между вершинами <math>u</math> и <math>v</math>. Поиск в ширину находит кратчайшие пути <math>d(u,v)</math> от вершины <math>u</math> до всех остальных вершин графа описанным далее образом.

В начале работы алгоритма расстояние до вершины-источника <math>d(u)=0</math>, до остальных вершин <math>d(v) = \infty, \forall v \neq u </math>. Также в начале работы алгоритма инициализируется множество <math>F = \{u\}</math>.

Далее на каждом шаге алгоритма строится множество вершин <math>P = {w} </math>, таких, что для <math>\forall v \in F \exists (v, w) \in E | d(w) = \infty </math>, при этом обновляются расстояния <math>d(w)=d(v)+1</math> для <math>\forall w \in P </math>. Затем производится переход на следующий шаг до тех пор, пока <math>P \neq \emptyset</math>; при этом в начале каждого шага множество F заменяется на P.

=== Вычислительное ядро алгоритма ===

Вычислительным ядром алгоритма является обход вершин, смежных с выбранной вершиной <math>v</math>, с последующим добавлением еще не посещенных вершин в множество <math>P</math>. Данная операция выполняется на каждом шаге для каждой вершины <math>v \in F</math>.

=== Макроструктура алгоритма ===

Алгоритм последовательно уточняет значения функции <math>d(v)</math>.

Структуру можно описать следующим образом:

1. Инициализация: всем вершинам присваивается предполагаемое расстояние <math>d(v)=\infty</math>, кроме вершины-источника, для которой <math>d(u)=0</math> .

2. Помещение вершины источника <math>v</math> в множество "передовых" вершин <math>F</math>.

3. Обход вершин множества <math>F</math>.

а) Инициализация множества <math>P=\emptyset</math>.

б) Для каждой вершины <math>v \in F</math> обход всех вершин <math>w | \exists (v, w)</math> (смежных с ней), c помещением в множество <math>P</math> таких вершин <math>w | d(w)=\infty</math>.

в) Замена множества <math>F</math> на <math>P</math> и переход на шаг 3 в случае, если множество <math>F \neq \emptyset</math>.

=== Схема реализации последовательного алгоритма ===

Простейшая версия алгоритма поиск в ширину может быть реализована при помощи очередей на языке C++ следующим образом.
Код приведен в предположении, что граф хранится в формате сжатого списка смежности: для каждой вершины в массиве vertices_to_edges_ptrs хранятся индекс начала и индекс конца списка смежных с ней вершин из массива dst_ids.

<source lang="C++">

// init distances
for(int i = 0; i < vertices_count; i++)
_result[i] = MAX_INT;

// init queue and first vertex
std::queue<int> vertex_queue;
vertex_queue.push(_source_vertex);
_result[_source_vertex] = 1;

// do bfs
while(vertex_queue.size() > 0)
{
int cur_vertex = vertex_queue.front();
vertex_queue.pop();

long long first = vertices_to_edges_ptrs[cur_vertex];
long long last = vertices_to_edges_ptrs[cur_vertex + 1];
for(long long i = first; i < last; i++)
{
int dst_id = dst_ids[i];
if(_result[dst_id] == MAX_INT)
{
_result[dst_id] = _result[src_id] + 1;
vertex_queue.push(dst_id);
}
}
}

</source>

=== Последовательная сложность алгоритма ===

Алгоритм имеет последовательную сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> и <math>|E|</math> - число вершин и ребер графа соответственно: алгоритм инициализирует начальный массив расстояний - <math>O(|V|)</math> операций, а затем обходит каждую вершину один единственный раз - <math>O(|E|)</math> операций. Данная оценка верна в случае, если формат хранения графа позволяет обходить вершины, смежные к выбранной (к примеру форматы списка смежности, сжатого списка смежности). При использовании других форматов оценка сложности может быть большей.

=== Информационный граф ===

Информационный граф классического алгоритма поиска в ширину приведен на рисунке 1.

[[Файл:Classical_BFS_ig.png|thumb|center|500px|Рисунок 1. Информационный граф алгоритма BFS.]]

На рисунке 1 используются следующие обозначения:

[1] - добавление вершины-источника <math>u</math> к множеству <math>F</math>.

[2] - извлечение добавленной вершины <math>v</math> из множества <math>F</math>.

[3] - проверка расстояний до вершин, смежных с вершиной <math>v</math>.

[4] - добавление еще не посещенных вершин в множество <math>P</math>.

[5] - замена множества <math>F</math> на <math>P</math> и проверка его пустоты. В случае непустого множества - переход на следующую итерацию, иначе завершение работы алгоритма.

Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, моделирующей данное множество.

В результате часто используется модификация алгоритма (далее алгоритм-2), использующая набор независимых структур данных для каждого из параллельных процессов. Информационный граф данного подхода приведен на рисунке 2.

[[Файл:BFS_ig_parallel_queues.png|thumb|center|500px|Рисунок 2. Информационный граф алгоритма BFS (независимые структуры данных).]]

Обозначения для рисунка 2:

[1] - добавление вершины-источника в множество <math>F</math>.

[2] - разделение данных множества <math>F</math> между процессами

[3] - помещение в множества <math>F_i</math> соответствующих данных из <math>F</math> каждым процессом с номером i.

[4] - извлечение очередной вершины из множеств <math>F_i</math>, обход её соседей и добавление их в множество <math>P_i</math> в случае, если они еще не посещены

[5] - попарное слияние множеств <math>P_i</math> для различных процессов, итоговое преобразование их в множество <math>F</math>.

[6] - проверка условия выхода из цикла

Кроме того, в случае, если реализация структур данных, моделирующих множества <math>F</math> и <math>P</math>, невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.

[[Файл:quadratic_BFS_ig.png|thumb|center|500px|Рисунок 3. Информационный граф алгоритма BFS (квадратичный подход к распараллеливанию).]]

Обозначения для рисунка 3:

[1] - инициализация расстояний до вершины-источника

[2] - инициализация расстояний до остальных вершин графа

[3] - загрузка информации об очередном ребре и обновление дистанций до соответствующих вершин.

[4] - проверка условия выхода из цикла

=== Ресурс параллелизма алгоритма ===

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

Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: <math>\sum_{n=1}^{p} degree(v_i)</math>, при этом для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме и может быть оценена только сверху (не более <math>|V|</math>).

При квадратичном подходе к параллельной реализации алгоритма на каждом шаге выполняется <math>O(|E|)</math> операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна <math>O(|E|)</math>. Число шагов алгоритма, как и в классическом случае, зависит от структуры графа и может быть оценено сверху как <math>O(|V|)</math>.

=== Входные и выходные данные алгоритма ===
'''Входные данные''': граф <math>G(V, E)</math>, <math>|V|</math> вершин <math>v_i</math> и <math>|E|</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math>, вершина-источник <math>u</math>.

'''Объём входных данных''': <math>O(|V| + |E|)</math>.

'''Выходные данные''' (возможные варианты):
# для каждой вершины <math>v</math> исходного графа расстояние <math>d(v)</math>, определенное как число ребер, лежащих на кратчайшем пути от вершины <math>u</math> к <math>v</math>.
# для каждой вершины <math>v</math> исходного графа значение достижимости (достижима или нет) от вершины-источника <math>u</math>.

'''Объём выходных данных''': <math>O(|V|)</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
** MPI: {{Buttonlinkimp|12}}
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/breadth_first_search.html breadth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]</code>).{{Buttonlinkimp|11}}
* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/ParallelBreadthFirstVisit.html ParallelBreadthFirstVisit]</code>), многопоточная реализация.
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.breadth_first_search.bfs_edges.html bfs_edges]</code>).
* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.BFS networkit.graph.BFS]</code>).
* RCC for CPU {{Buttonlinkimp|9}}
* RCC for GPU {{Buttonlinkimp|26}}
* Gap {{Buttonlinkimp|36}}
* Litra {{Buttonlinkimp|39}}
== Литература ==

<references />

[[Категория:Статьи в работе]]

[[En:Breadth-first search (BFS)]]
== '''LinkButtons''' ==

Все кнопки ниже ведут на "yandex.ru" (Просто показано их разное "оформление") 

<s>{{PushButton|link = https://yandex.ru/|text = Yandex}}</s>
{{PushButton|link = https://yandex.ru/|text = Yandex|color = yellow|weight = 900}}
{{PushButton|link = https://yandex.ru/|text = Yandex|decoration = underline}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|weight = bold}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|color = yellow|b-color = red|weight = bold}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|color = yellow|weight = 900|decoration = line-through}}
----
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px}}
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px|weight = bold|decoration = underline|color = orange}}

Anton121 Test Buttons

2021-11-07T13:00:36Z

Anton121:

== '''LinkButtons''' ==

Все кнопки ниже ведут на "yandex.ru" (Просто показано их разное "оформление") 

<s>{{PushButton|link = https://yandex.ru/|text = Yandex}}</s>
{{PushButton|link = https://yandex.ru/|text = Yandex|color = yellow|weight = 900}}
{{PushButton|link = https://yandex.ru/|text = Yandex|decoration = underline}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|weight = bold}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|color = yellow|b-color = red|weight = bold}}
{{PushButton|link = https://yandex.ru/|text = Yandex|style = italic|color = yellow|weight = 900|decoration = line-through}}
----
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px}}
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px|weight = bold|decoration = underline|color = orange}}
 
{{algorithm
| name = Алгоритм поиска в ширину (BFS)
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>N/A, \max O(|V|) </math>
| pf_width = <math>N/A, \max O(|E|) </math>
| input_data = <math>O(|V| + |E|)</math>
| output_data = <math>O(|V|)</math>
}}

Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

'''Поиск в ширину''' (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Кроме того, поиск в ширину позволяет решать задачу проверки достижимости (существуют ли пути между вершиной источником и остальными вершинами графа). Впервые алгоритм поиска в ширину описан в работах Мура<ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> и Ли<ref>Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.</ref>.

Алгоритм основан на обходе вершин графа "по слоям". На каждом шаге есть множество "передовых" вершин, для смежных к которым производится проверка, относятся ли они к еще не посещенным. Все еще не посещенные вершины добавляются в новое множество "передовых" вершин, обрабатываемых на следующем шаге. Изначально в множество "передовых" вершин входит только вершина-источник, от которой и начинается обход.

В последовательном случае алгоритм имеет алгоритмическую сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> - число вершин в графе, <math>|E|</math> - число ребер в графе.

=== Математическое описание алгоритма ===

Пусть задан граф <math>G = (V, E)</math> без весов, и с выделенной вершиной-источником <math>u</math>. Путем <math>P(u,v)</math> между вершинами <math>u</math> и <math>v</math> называется множество ребер <math>(u, v_1), (v_1, v_2), ... (v_{n-1}, v)</math>. Длиной пути <math>d(u,v)</math> обозначим число ребер в данном пути между вершинами <math>u</math> и <math>v</math>. Поиск в ширину находит кратчайшие пути <math>d(u,v)</math> от вершины <math>u</math> до всех остальных вершин графа описанным далее образом.

В начале работы алгоритма расстояние до вершины-источника <math>d(u)=0</math>, до остальных вершин <math>d(v) = \infty, \forall v \neq u </math>. Также в начале работы алгоритма инициализируется множество <math>F = \{u\}</math>.

Далее на каждом шаге алгоритма строится множество вершин <math>P = {w} </math>, таких, что для <math>\forall v \in F \exists (v, w) \in E | d(w) = \infty </math>, при этом обновляются расстояния <math>d(w)=d(v)+1</math> для <math>\forall w \in P </math>. Затем производится переход на следующий шаг до тех пор, пока <math>P \neq \emptyset</math>; при этом в начале каждого шага множество F заменяется на P.

=== Вычислительное ядро алгоритма ===

Вычислительным ядром алгоритма является обход вершин, смежных с выбранной вершиной <math>v</math>, с последующим добавлением еще не посещенных вершин в множество <math>P</math>. Данная операция выполняется на каждом шаге для каждой вершины <math>v \in F</math>.

=== Макроструктура алгоритма ===

Алгоритм последовательно уточняет значения функции <math>d(v)</math>.

Структуру можно описать следующим образом:

1. Инициализация: всем вершинам присваивается предполагаемое расстояние <math>d(v)=\infty</math>, кроме вершины-источника, для которой <math>d(u)=0</math> .

2. Помещение вершины источника <math>v</math> в множество "передовых" вершин <math>F</math>.

3. Обход вершин множества <math>F</math>.

а) Инициализация множества <math>P=\emptyset</math>.

б) Для каждой вершины <math>v \in F</math> обход всех вершин <math>w | \exists (v, w)</math> (смежных с ней), c помещением в множество <math>P</math> таких вершин <math>w | d(w)=\infty</math>.

в) Замена множества <math>F</math> на <math>P</math> и переход на шаг 3 в случае, если множество <math>F \neq \emptyset</math>.

=== Схема реализации последовательного алгоритма ===

Простейшая версия алгоритма поиск в ширину может быть реализована при помощи очередей на языке C++ следующим образом.
Код приведен в предположении, что граф хранится в формате сжатого списка смежности: для каждой вершины в массиве vertices_to_edges_ptrs хранятся индекс начала и индекс конца списка смежных с ней вершин из массива dst_ids.

<source lang="C++">

// init distances
for(int i = 0; i < vertices_count; i++)
_result[i] = MAX_INT;

// init queue and first vertex
std::queue<int> vertex_queue;
vertex_queue.push(_source_vertex);
_result[_source_vertex] = 1;

// do bfs
while(vertex_queue.size() > 0)
{
int cur_vertex = vertex_queue.front();
vertex_queue.pop();

long long first = vertices_to_edges_ptrs[cur_vertex];
long long last = vertices_to_edges_ptrs[cur_vertex + 1];
for(long long i = first; i < last; i++)
{
int dst_id = dst_ids[i];
if(_result[dst_id] == MAX_INT)
{
_result[dst_id] = _result[src_id] + 1;
vertex_queue.push(dst_id);
}
}
}

</source>

=== Последовательная сложность алгоритма ===

Алгоритм имеет последовательную сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> и <math>|E|</math> - число вершин и ребер графа соответственно: алгоритм инициализирует начальный массив расстояний - <math>O(|V|)</math> операций, а затем обходит каждую вершину один единственный раз - <math>O(|E|)</math> операций. Данная оценка верна в случае, если формат хранения графа позволяет обходить вершины, смежные к выбранной (к примеру форматы списка смежности, сжатого списка смежности). При использовании других форматов оценка сложности может быть большей.

=== Информационный граф ===

Информационный граф классического алгоритма поиска в ширину приведен на рисунке 1.

[[Файл:Classical_BFS_ig.png|thumb|center|500px|Рисунок 1. Информационный граф алгоритма BFS.]]

На рисунке 1 используются следующие обозначения:

[1] - добавление вершины-источника <math>u</math> к множеству <math>F</math>.

[2] - извлечение добавленной вершины <math>v</math> из множества <math>F</math>.

[3] - проверка расстояний до вершин, смежных с вершиной <math>v</math>.

[4] - добавление еще не посещенных вершин в множество <math>P</math>.

[5] - замена множества <math>F</math> на <math>P</math> и проверка его пустоты. В случае непустого множества - переход на следующую итерацию, иначе завершение работы алгоритма.

Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, моделирующей данное множество.

В результате часто используется модификация алгоритма (далее алгоритм-2), использующая набор независимых структур данных для каждого из параллельных процессов. Информационный граф данного подхода приведен на рисунке 2.

[[Файл:BFS_ig_parallel_queues.png|thumb|center|500px|Рисунок 2. Информационный граф алгоритма BFS (независимые структуры данных).]]

Обозначения для рисунка 2:

[1] - добавление вершины-источника в множество <math>F</math>.

[2] - разделение данных множества <math>F</math> между процессами

[3] - помещение в множества <math>F_i</math> соответствующих данных из <math>F</math> каждым процессом с номером i.

[4] - извлечение очередной вершины из множеств <math>F_i</math>, обход её соседей и добавление их в множество <math>P_i</math> в случае, если они еще не посещены

[5] - попарное слияние множеств <math>P_i</math> для различных процессов, итоговое преобразование их в множество <math>F</math>.

[6] - проверка условия выхода из цикла

Кроме того, в случае, если реализация структур данных, моделирующих множества <math>F</math> и <math>P</math>, невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.

[[Файл:quadratic_BFS_ig.png|thumb|center|500px|Рисунок 3. Информационный граф алгоритма BFS (квадратичный подход к распараллеливанию).]]

Обозначения для рисунка 3:

[1] - инициализация расстояний до вершины-источника

[2] - инициализация расстояний до остальных вершин графа

[3] - загрузка информации об очередном ребре и обновление дистанций до соответствующих вершин.

[4] - проверка условия выхода из цикла

=== Ресурс параллелизма алгоритма ===

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

Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: <math>\sum_{n=1}^{p} degree(v_i)</math>, при этом для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме и может быть оценена только сверху (не более <math>|V|</math>).

При квадратичном подходе к параллельной реализации алгоритма на каждом шаге выполняется <math>O(|E|)</math> операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна <math>O(|E|)</math>. Число шагов алгоритма, как и в классическом случае, зависит от структуры графа и может быть оценено сверху как <math>O(|V|)</math>.

=== Входные и выходные данные алгоритма ===
'''Входные данные''': граф <math>G(V, E)</math>, <math>|V|</math> вершин <math>v_i</math> и <math>|E|</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math>, вершина-источник <math>u</math>.

'''Объём входных данных''': <math>O(|V| + |E|)</math>.

'''Выходные данные''' (возможные варианты):
# для каждой вершины <math>v</math> исходного графа расстояние <math>d(v)</math>, определенное как число ребер, лежащих на кратчайшем пути от вершины <math>u</math> к <math>v</math>.
# для каждой вершины <math>v</math> исходного графа значение достижимости (достижима или нет) от вершины-источника <math>u</math>.

'''Объём выходных данных''': <math>O(|V|)</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
** MPI: {{Buttonlinkimp|12}}
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/breadth_first_search.html breadth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]</code>).{{Buttonlinkimp|11}}
* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/ParallelBreadthFirstVisit.html ParallelBreadthFirstVisit]</code>), многопоточная реализация.
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.breadth_first_search.bfs_edges.html bfs_edges]</code>).
* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.BFS networkit.graph.BFS]</code>).
* RCC for CPU {{Buttonlinkimp|9}}
* RCC for GPU {{Buttonlinkimp|26}}
* Gap {{Buttonlinkimp|36}}
* Litra {{Buttonlinkimp|39}}
== Литература ==

<references />

[[Категория:Статьи в работе]]

[[En:Breadth-first search (BFS)]]

Anton121 Test Buttons

2021-11-06T17:30:57Z

Anton121:

Шаблон:PushTheStrangeButton

2021-11-06T17:21:36Z

Anton121: Полностью удалено содержимое страницы

Anton121 Test Buttons

2021-11-06T17:20:18Z

Anton121: Новая страница: «== '''LinkButtons''' == Все кнопки ниже ведут на "yandex.ru" (Просто показано их разное "оформление")...»

Шаблон:PushButton

2021-11-06T16:25:22Z

Anton121:

[{{{link|https://parallel.ru/}}} <span style="font-size:{{{size|initial}}}; color:{{{color|white}}};
font-style:{{{style|initial}}}; background-color:{{{b-color|none}}}; font-weight: {{{weight|initial}}};
text-decoration:{{{decoration|initial}}}; text-transform:{{{trasform|initial}}}"
class="mw-ui-button mw-ui-progressive"> {{{text|Get Perf.Data}}} ]

Шаблон:PushButton

2021-11-06T16:03:58Z

Anton121: Новая страница: «[{{{link|https://parallel.ru/}}} <span style="font-size:{{{size|initial}}}; color:{{{color|white}}}; font-style:{{{style|initial}}}; background-color:{{{b-color|...»

[{{{link|https://parallel.ru/}}} <span style="font-size:{{{size|initial}}}; color:{{{color|white}}};
font-style:{{{style|initial}}}; background-color:{{{b-color|none}}}; font-weight: {{{type|initial}}};
text-decoration:{{{decoration|initial}}}; text-transform:{{{trasform|initial}}}"
class="mw-ui-button mw-ui-progressive"> {{{text|Get Perf.Data}}} ]

Шаблон:PushTheStrangeButton

2021-11-06T16:00:19Z

Anton121:

[{{{link|https://parallel.ru/}}} <span style="font-size:{{{size|initial}}}; color:{{{color|white}}};
font-style:{{{style|initial}}}; background-color:{{{b-color|none}}}; font-weight: {{{type|initial}}};
text-decoration:{{{decoration|initial}}}; text-transform:{{{trasform|initial}}}"
class="mw-ui-button mw-ui-progressive"> {{{text|Get Perf.Data}}} ]

Шаблон:PushTheStrangeButton

2021-11-06T15:39:12Z

Anton121:

[{{{link|https://parallel.ru/computers/top500.list46.html}}} Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T15:38:04Z

Anton121:

[{{{1}}} Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T15:36:55Z

Anton121:

== [{{{1}}} Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T15:33:27Z

Anton121:

[{{{1}}}
Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T15:30:41Z

Anton121:

[{{{1}}}
Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T15:25:22Z

Anton121:

[{{{link|https://parallel.ru/computers/top500.list46.html}}}
Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T15:24:03Z

Anton121:

[{{{1|https://parallel.ru/computers/top500.list46.html}}}
Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T15:04:34Z

Anton121:

[{{{1}}} Go_To_Site Push the button]

Шаблон:PushTheStrangeButton

2021-11-06T14:59:16Z

Anton121: Новая страница: «[{{{1}}} Go_To_Site ...»

[{{{1}}} Go_To_Site Push the button]

Anton121 Test Page

2021-10-07T20:11:00Z

Anton121: /* Так, ну допустим, посмотрим, как здесь отображается текст, карл!' */

=='''''Так, ну допустим, посмотрим, как здесь отображается текст, карл!''''==
''Организуем списочек, варианты входа в критическую секцию:''
* pragma critical
* pragma atomic
* locks
* My knowledges have come out
We are gonna organise a little break and show static about Covid-19 new victims
[https://yandex.ru/covid19/stat?utm_source=main_graph&utm_source=main_notif&geoId=225 Covid-19 statistic]
[[Файл:Bigstock.jpg|мини|<big>Push to make your life easier!</big>]]
Снизу текста должно быть написанонижний штангенциркуль 
Сверху текста должно быть написаноВерхний Луивитон
{| class="wikitable sortable"
|-
! 2019 !! 2020 !! 2021
|-
| 7,5 bil || 7,7 bil || 7,9 bil
|-
| 90% || 99% ||
* <big>121%</big>
* 122%
|}
[[Открытая_энциклопедия_свойств_алгоритмов| Главная страница]]
<gallery>
Bigstock.jpg|Нужно больше
Bigstock.jpg|Кнопок
Bigstock.jpg|Нужно больше
Bigstock.jpg|Золота
</gallery>

Так, дальше я просто скопировал код для какого-то шаблона
:<math>
A \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix} = \sum_{\begin{smallmatrix} \gamma_{1} < \gamma_{2} < \cdots < \gamma_{k} \end{smallmatrix}} L \begin{pmatrix}
\alpha_{1} & \alpha_{2} & \cdots & \alpha_{k} \\
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\end{pmatrix} U\begin{pmatrix}
\gamma_{1} & \gamma_{2} & \cdots & \gamma_{k} \\
\beta_{1} & \beta_{2} & \cdots & \beta_{k} \\
\end{pmatrix}
</math>

Файл:Bigstock.jpg

2021-10-07T19:35:55Z

Anton121:

Just for my test page

Anton121 Test Page

2021-10-07T19:29:21Z

Anton121: Новая страница: «=='''''Так, ну допустим, посмотрим, как здесь отображается текст, карл!''''== ''Организуем списо...»