17 июня 2022

πŸ“ 10 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π·Π½Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΊΠΎΠ΄Π΅Ρ€

iOS-developer, ИВ-ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Ρ‡ΠΈΡ†Π°, ΠΏΠΈΡˆΡƒ ΡΡ‚Π°Ρ‚ΡŒΠΈ ΠΈ Π³Π°ΠΉΠ΄Ρ‹.
Знакомимся с Π΄Π΅ΡΡΡ‚ΡŒΡŽ маст-хэв для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π΅Ρ€Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±ΡƒΠ΄ΡƒΡ‚ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹ΠΌΠΈ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ (исходный ΠΊΠΎΠ΄ прилагаСтся).
πŸ“ 10 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π·Π½Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΊΠΎΠ΄Π΅Ρ€
Данная ΡΡ‚Π°Ρ‚ΡŒΡ являСтся ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄ΠΎΠΌ. Бсылка Π½Π° ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»ΡŒΠ½ΡƒΡŽ ΡΡ‚Π°Ρ‚ΡŒΡŽ.

Π—Π°Ρ‡Π΅ΠΌ Π²ΠΎΠΎΠ±Ρ‰Π΅ ΠΈΠ·ΡƒΡ‡Π°Ρ‚ΡŒ Π³Ρ€Π°Ρ„ΠΎΠ²Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹?

Π“Ρ€Π°Ρ„ΠΎΠ²Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‚ собой ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ шагов для ΠΎΠ±Ρ…ΠΎΠ΄Π° Π³Ρ€Π°Ρ„Π° Ρ‡Π΅Ρ€Π΅Π· Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ (ΡƒΠ·Π»Ρ‹). НСкоторыС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ для поиска ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ ΡƒΠ·Π»Π° ΠΈΠ»ΠΈ ΠΏΡƒΡ‚ΠΈ ΠΌΠ΅ΠΆΠ΄Ρƒ двумя Π·Π°Π΄Π°Π½Π½Ρ‹ΠΌΠΈ ΡƒΠ·Π»Π°ΠΌΠΈ.

Π”Π°Π½Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡŽΡ‚ Π½Π° сайтах ΡΠΎΡ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Ρ… сСтСй, Π² ΠΌΠΎΠ΄Π΅Π»ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ³ΠΎ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°, Π° Ρ‚Π°ΠΊΠΆΠ΅ Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΈΡ… Π΄Ρ€ΡƒΠ³ΠΈΡ… сфСрах. Π― ΠΏΡ€ΠΈΠ»ΠΎΠΆΠΈΠ» свой исходный ΠΊΠΎΠ΄ для всСх Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², ΠΏΡ€ΠΎ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΡ‹ Π±ΡƒΠ΄Π΅ΠΌ Π³ΠΎΠ²ΠΎΡ€ΠΈΡ‚ΡŒ Π½ΠΈΠΆΠ΅.

1. Поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ (Breadth First Searching)

Поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ β€” это рСкурсивный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ поиска всСх Π²Π΅Ρ€ΡˆΠΈΠ½ Π³Ρ€Π°Ρ„Π° ΠΈΠ»ΠΈ Π΄Π΅Ρ€Π΅Π²Π°. ΠžΠ±Ρ…ΠΎΠ΄ начинаСтся с ΠΊΠΎΡ€Π½Π΅Π²ΠΎΠ³ΠΎ ΡƒΠ·Π»Π° ΠΈ Π·Π°Ρ‚Π΅ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ исслСдуСт всС сосСдниС ΡƒΠ·Π»Ρ‹. Π—Π°Ρ‚Π΅ΠΌ выбираСтся блиТайший ΡƒΠ·Π΅Π» ΠΈ ΠΈΡΡΠ»Π΅Π΄ΡƒΡŽΡ‚ΡΡ всС нСисслСдованныС ΡƒΠ·Π»Ρ‹. ΠŸΡ€ΠΈ использовании BFS для ΠΎΠ±Ρ…ΠΎΠ΄Π° любой ΡƒΠ·Π΅Π» Π³Ρ€Π°Ρ„Π° ΠΌΠΎΠΆΠ½ΠΎ ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ ΠΊΠΎΡ€Π½Π΅Π²Ρ‹ΠΌ ΡƒΠ·Π»ΠΎΠΌ.

ΠŸΡ€ΠΎΡΡ‚ΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для BFS, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π½ΡƒΠΆΠ½ΠΎ Π·Π°ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ:

  1. ΠŸΠ΅Ρ€Π΅ΠΉΠ΄ΠΈΡ‚Π΅ Π½Π° сосСднюю Π½Π΅Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Π½Π½ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ. ΠžΡ‚ΠΌΠ΅Ρ‚ΡŒΡ‚Π΅ ΠΊΠ°ΠΊ Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Π½Π½ΡƒΡŽ. ΠžΡ‚ΠΎΠ±Ρ€Π°Π·ΠΈΡ‚Π΅ это. Π’ΡΡ‚Π°Π²ΡŒΡ‚Π΅ Π΅Π΅ Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ.
  2. Если смСТная Π²Π΅Ρ€ΡˆΠΈΠ½Π° Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½Π°, ΡƒΠ΄Π°Π»ΠΈΡ‚Π΅ ΠΏΠ΅Ρ€Π²ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ ΠΈΠ· ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ.
  3. ΠŸΠΎΠ²Ρ‚ΠΎΡ€ΡΠΉΡ‚Π΅ шаг 1 ΠΈ шаг 2, ΠΏΠΎΠΊΠ° ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ Π½Π΅ станСт пустой.

БхСматичСскоС прСдставлСниС ΠΎΠ±Ρ…ΠΎΠ΄Π° BFS:

Поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ (Breadth First Searching)
Поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ (Breadth First Searching)

Бсылка Π½Π° ΠΊΠΎΠ΄: Поиск Π² ΡˆΠΈΡ€ΠΈΠ½Ρƒ

2. Поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ (Depth First Searching)

Поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ ΠΈΠ»ΠΈ ΠΎΠ±Ρ…ΠΎΠ΄ Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ β€” это рСкурсивный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ поиска всСх Π²Π΅Ρ€ΡˆΠΈΠ½ Π³Ρ€Π°Ρ„Π° ΠΈΠ»ΠΈ Π΄Ρ€Π΅Π²ΠΎΠ²ΠΈΠ΄Π½ΠΎΠΉ структуры Π΄Π°Π½Π½Ρ‹Ρ….

Алгоритм поиска Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ (DFS) осущСствляСт поиск Π²Π³Π»ΡƒΠ±ΡŒ Π³Ρ€Π°Ρ„Π°, Π° Ρ‚Π°ΠΊΠΆΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ стСк, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π΅ Π·Π°Π±Ρ‹Ρ‚ΡŒ Β«ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒΒ» ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ для Π½Π°Ρ‡Π°Π»Π° поиска, ΠΊΠΎΠ³Π΄Π° Π½Π° любой ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ‚ Ρ‚ΡƒΠΏΠΈΠΊ.

ΠŸΡ€ΠΎΡΡ‚ΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π½ΡƒΠΆΠ½ΠΎ Π·Π°ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ, для DFS:

  1. ΠŸΠΎΡΠ΅Ρ‚ΠΈΡ‚Π΅ сосСднюю Π½Π΅ΠΏΠΎΡΠ΅Ρ‰Π΅Π½Π½ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ. ΠžΡ‚ΠΌΠ΅Ρ‚ΡŒΡ‚Π΅ ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅Ρ‰Π΅Π½Π½ΡƒΡŽ. ΠžΡ‚ΠΎΠ±Ρ€Π°Π·ΠΈΡ‚Π΅ это. Π”ΠΎΠ±Π°Π²ΡŒΡ‚Π΅ Π² стСк.
  2. Если смСТная Π²Π΅Ρ€ΡˆΠΈΠ½Π° Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½Π°, Ρ‚ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Π° бСрСтся ΠΈΠ· стСка. Π‘Ρ‚Π΅ΠΊ Π²Ρ‹Π²Π΅Π΄Π΅Ρ‚ всС Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹, Ρƒ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π½Π΅Ρ‚ смСТных Π²Π΅Ρ€ΡˆΠΈΠ½.
  3. ΠŸΠΎΠ²Ρ‚ΠΎΡ€ΡΠΉΡ‚Π΅ шаги 1 ΠΈ 2, ΠΏΠΎΠΊΠ° стСк Π½Π΅ станСт пустым.

БхСматичСскоС прСдставлСниС ΠΎΠ±Ρ…ΠΎΠ΄Π° DFS:

Поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ (Depth First Searching)
Поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ (Depth First Searching)

Бсылка Π½Π° ΠΊΠΎΠ΄: Поиск Π² Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ

Если Ρ…ΠΎΡ‡Π΅ΡˆΡŒ ΠΏΠΎΠ΄Ρ‚ΡΠ½ΡƒΡ‚ΡŒ свои знания ΠΏΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌ, загляни Π½Π° наш курс «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β», Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Ρ‚Ρ‹:

  • ΡƒΠ³Π»ΡƒΠ±ΠΈΡˆΡŒΡΡ Π² Ρ‚Π΅ΠΎΡ€ΠΈΡŽ структур Π΄Π°Π½Π½Ρ‹Ρ…;
  • Π½Π°ΡƒΡ‡ΠΈΡˆΡŒΡΡ Ρ€Π΅ΡˆΠ°Ρ‚ΡŒ слоТныС алгоритмичСскиС Π·Π°Π΄Π°Ρ‡ΠΈ;
  • Π½Π°ΡƒΡ‡ΠΈΡˆΡŒΡΡ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΡ€ΠΈ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ.

3. ВопологичСская сортировка (Topological Sorting)

ВопологичСская сортировка для ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ ацикличСского Π³Ρ€Π°Ρ„Π° (DAG) β€” это Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ΅ упорядочиваниС Π²Π΅Ρ€ΡˆΠΈΠ½, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Π²Π΅Ρ€ΡˆΠΈΠ½Π° u ΠΏΡ€Π΅Π΄ΡˆΠ΅ΡΡ‚Π²ΡƒΠ΅Ρ‚ v для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½Π½ΠΎΠ³ΠΎ Ρ€Π΅Π±Ρ€Π° uv (Π² порядкС ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ). ВопологичСская сортировка для Π³Ρ€Π°Ρ„Π° Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Π°, Ссли Π³Ρ€Π°Ρ„ Π½Π΅ являСтся DAG.

Для ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π³Ρ€Π°Ρ„Π° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒΡΡ Π±ΠΎΠ»Π΅Π΅ ΠΎΠ΄Π½ΠΎΠΉ топологичСской сортировки.

ΠŸΡ€ΠΎΡΡ‚ΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ слСдуСт Π·Π°ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ, для топологичСской сортировки:

1. ΠžΡ‚ΠΌΠ΅Ρ‚ΡŒΡ‚Π΅ u ΠΊΠ°ΠΊ ΠΏΠΎΡΠ΅Ρ‰Π΅Π½Π½ΡƒΡŽ

2. Для всСх Π²Π΅Ρ€ΡˆΠΈΠ½ v, смСТных с u, Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚Π΅:

2.1. Если v Π½Π΅ посСщСнная, Ρ‚ΠΎ:

2.2. ВыполняСм TopoSort (Π½Π΅ забывая ΠΏΡ€ΠΎ стСк)

2.3. Π¦ΠΈΠΊΠ» Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½

3. Π—Π°ΠΏΠΈΡˆΠΈΡ‚Π΅ u Π² стСк

БхСматичСскоС прСдставлСниС топологичСской сортировки:

ВопологичСская сортировка (Topological Sorting)
ВопологичСская сортировка (Topological Sorting)

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ топологичСской сортировки для этого Π³Ρ€Π°Ρ„Π°:

5 β†’ 4 β†’ 2 β†’ 3 β†’ 1 β†’ 0

Бсылка Π½Π° ΠΊΠΎΠ΄: ВопологичСская сортировка

4. ΠžΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΈΠ΅ Ρ†ΠΈΠΊΠ»Π° с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Кана (Kahn's Algorithm)

Алгоритм топологичСской сортировки Кана β€” это Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ обнаруТСния Ρ†ΠΈΠΊΠ»ΠΎΠ² Π½Π° Π±Π°Π·Π΅ эффСктивной топологичСской сортировки.

Π Π°Π±ΠΎΡ‚Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° осущСствляСтся ΠΏΡƒΡ‚Π΅ΠΌ нахоТдСния Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π±Π΅Π· входящих Π² Π½Π΅Π΅ Ρ€Π΅Π±Π΅Ρ€ ΠΈ удалСния всСх исходящих Ρ€Π΅Π±Π΅Ρ€ ΠΈΠ· этой Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹.

Бсылка Π½Π° ΠΊΠΎΠ΄: ΠžΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΈΠ΅ Ρ†ΠΈΠΊΠ»Π° с использованиСм Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Кана

5. Алгоритм ДСйкстры (Dijkstra's Algorithm)

Алгоритм ДСйкстры позволяСт Π½Π°ΠΉΡ‚ΠΈ ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΠΉ ΠΏΡƒΡ‚ΡŒ ΠΌΠ΅ΠΆΠ΄Ρƒ Π»ΡŽΠ±Ρ‹ΠΌΠΈ двумя Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ Π³Ρ€Π°Ρ„Π°. Он отличаСтся ΠΎΡ‚ минимального остовного Π΄Π΅Ρ€Π΅Π²Π° Ρ‚Π΅ΠΌ, Ρ‡Ρ‚ΠΎ ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠ΅Π΅ расстояниС ΠΌΠ΅ΠΆΠ΄Ρƒ двумя Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ ΠΌΠΎΠΆΠ΅Ρ‚ Π½Π΅ Π²ΠΊΠ»ΡŽΡ‡Π°Ρ‚ΡŒ всС Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ Π³Ρ€Π°Ρ„Π°.

НиТС ΠΏΡ€ΠΎΠΈΠ»Π»ΡŽΡΡ‚Ρ€ΠΈΡ€ΠΎΠ²Π°Π½ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠ΅Π³ΠΎ ΠΏΡƒΡ‚ΠΈ с ΠΎΠ΄Π½ΠΈΠΌ источником. Π—Π΄Π΅ΡΡŒ Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ источника ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π½Π°ΠΉΡ‚ΠΈ ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΠΉ ΠΏΡƒΡ‚ΡŒ ΠΎΡ‚ источника ΠΊΠΎ всСм ΡƒΠ·Π»Π°ΠΌ.

πŸ“ 10 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π·Π½Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΊΠΎΠ΄Π΅Ρ€

ПослС примСнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ДСйкстры:

Алгоритм ДСйкстры (Dijkstra's Algorithm)
Алгоритм ДСйкстры (Dijkstra's Algorithm)

Бсылка Π½Π° ΠΊΠΎΠ΄: Алгоритм ДСйкстры

6. Алгоритм Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π° (Bellman Ford's Algorithm)

Алгоритм Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π° ΠΏΠΎΠΌΠΎΠ³Π°Π΅Ρ‚ Π½Π°ΠΌ Π½Π°ΠΉΡ‚ΠΈ ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΠΉ ΠΏΡƒΡ‚ΡŒ ΠΎΡ‚ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΊΠΎ всСм Π΄Ρ€ΡƒΠ³ΠΈΠΌ Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌ взвСшСнного Π³Ρ€Π°Ρ„Π°. Он ΠΏΠΎΡ…ΠΎΠΆ Π½Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ДСйкстры, Π½ΠΎ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΠ²Π°Ρ‚ΡŒ Π³Ρ€Π°Ρ„Ρ‹, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Ρ€Π΅Π±Ρ€Π° ΠΌΠΎΠ³ΡƒΡ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Ρ†ΠΈΠΊΠ»Ρ‹ с ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ вСсом.

Алгоритм ДСйкстры (Π½Π΅ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΠ²Π°Π΅Ρ‚ Ρ†ΠΈΠΊΠ» с ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ вСсом) ΠΌΠΎΠΆΠ΅Ρ‚ Π΄Π°Ρ‚ΡŒ Π½Π΅Π²Π΅Ρ€Π½Ρ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ Ρ‡Π΅Ρ€Π΅Π· Ρ†ΠΈΠΊΠ» с ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ вСсом ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Ρ‚ ΠΊ ΡƒΠΌΠ΅Π½ΡŒΡˆΠ΅Π½ΠΈΡŽ Π΄Π»ΠΈΠ½Ρ‹ ΠΏΡƒΡ‚ΠΈ. ДСйкстра Π½Π΅ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌ для Π³Ρ€Π°Ρ„ΠΈΠΊΠΎΠ² с ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌΠΈ вСсами, Π° Π‘Π΅Π»Π»ΠΌΠ°Π½-Π€ΠΎΡ€Π΄, Π½Π°ΠΎΠ±ΠΎΡ€ΠΎΡ‚, ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌ для Ρ‚Π°ΠΊΠΈΡ… Π³Ρ€Π°Ρ„ΠΈΠΊΠΎΠ². Π‘Π΅Π»Π»ΠΌΠ°Π½-Π€ΠΎΡ€Π΄ Ρ‚Π°ΠΊΠΆΠ΅ ΠΏΡ€ΠΎΡ‰Π΅, Ρ‡Π΅ΠΌ ДСйкстра ΠΈ Ρ…ΠΎΡ€ΠΎΡˆΠΎ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ для систСм с распрСдСлСнными ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Π°ΠΌΠΈ.

Алгоритм Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π° (Bellman Ford's Algorithm)
Алгоритм Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π° (Bellman Ford's Algorithm)

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π°:

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π°
Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π‘Π΅Π»Π»ΠΌΠ°Π½Π°-Π€ΠΎΡ€Π΄Π°

Бсылка Π½Π° ΠΊΠΎΠ΄: Алгоритм Π‘Π΅Π»Π»ΠΌΠ°Π½Π° Π€ΠΎΡ€Π΄Π°

7. Алгоритм Π€Π»ΠΎΠΉΠ΄Π°-Π£ΠΎΡ€ΡˆΠ°Π»Π»Π° (Floyd-Warshall Algorithm)

Алгоритм Π€Π»ΠΎΠΉΠ΄Π°-Π£ΠΎΡ€ΡˆΠ°Π»Π»Π° β€” это Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ поиска ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠ΅Π³ΠΎ ΠΏΡƒΡ‚ΠΈ ΠΌΠ΅ΠΆΠ΄Ρƒ всСми ΠΏΠ°Ρ€Π°ΠΌΠΈ Π²Π΅Ρ€ΡˆΠΈΠ½ Π²ΠΎ взвСшСнном Π³Ρ€Π°Ρ„Π΅. Π­Ρ‚ΠΎΡ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΠΊΠ°ΠΊ для ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Ρ…, Ρ‚Π°ΠΊ ΠΈ для Π½Π΅ΠΎΡ€ΠΈΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Ρ… Π²Π·Π²Π΅ΡˆΠ΅Π½Π½Ρ‹Ρ… Π³Ρ€Π°Ρ„ΠΎΠ². Но это Π½Π΅ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ для Π³Ρ€Π°Ρ„ΠΎΠ² с ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌΠΈ Ρ†ΠΈΠΊΠ»Π°ΠΌΠΈ (Π³Π΄Π΅ сумма Ρ€Π΅Π±Π΅Ρ€ Π² Ρ†ΠΈΠΊΠ»Π΅ ΠΎΡ‚Ρ€ΠΈΡ†Π°Ρ‚Π΅Π»ΡŒΠ½Π°). Π—Π΄Π΅ΡΡŒ Π±ΡƒΠ΄Π΅Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒΡΡ концСпция динамичСского программирования.

Алгоритм, Π»Π΅ΠΆΠ°Ρ‰ΠΈΠΉ Π² основС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π€Π»ΠΎΠΉΠ΄Π°-Π£ΠΎΡ€ΡˆΠ°Π»Π»Π°:

Dij(k) ← min ( Dij(k-1), Dij(k-1)+Dkj(k-1))

Бсылка Π½Π° ΠΊΠΎΠ΄: Алгоритм Π€Π»ΠΎΠΉΠ΄Π°-Π£ΠΎΡ€ΡˆΠ°Π»Π»Π°

8. Алгоритм ΠŸΡ€ΠΈΠΌΠ° (Prim's Algorithm)

Алгоритм ΠŸΡ€ΠΈΠΌΠ° β€” это ΠΆΠ°Π΄Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для поиска минимального остовного Π΄Π΅Ρ€Π΅Π²Π° ΠΈΠ· Π³Ρ€Π°Ρ„Π°. Алгоритм ΠŸΡ€ΠΈΠΌΠ° Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ подмноТСство Ρ€Π΅Π±Π΅Ρ€, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ ΠΊΠ°ΠΆΠ΄ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ Π³Ρ€Π°Ρ„Π°, Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ сумма вСсов Ρ€Π΅Π±Π΅Ρ€ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Π½Π°.

ΠŸΡ€ΠΎΡΡ‚ΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠŸΡ€ΠΈΠΌΠ°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ слСдуСт Π·Π°ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ:

  1. Π’Ρ‹Π±Π΅Ρ€ΠΈΡ‚Π΅ минимальноС остовноС Π΄Π΅Ρ€Π΅Π²ΠΎ со случайно Π²Ρ‹Π±Ρ€Π°Π½Π½ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½ΠΎΠΉ.
  2. НайдитС всС Ρ€Π΅Π±Ρ€Π°, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡŽΡ‰ΠΈΠ΅ Π΄Π΅Ρ€Π΅Π²ΠΎ с Π½ΠΎΠ²Ρ‹ΠΌΠΈ Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ, Π½Π°ΠΉΠ΄ΠΈΡ‚Π΅ ΠΌΠΈΠ½ΠΈΠΌΡƒΠΌ ΠΈ Π΄ΠΎΠ±Π°Π²ΡŒΡ‚Π΅ Π΅Π³ΠΎ Π² Π΄Π΅Ρ€Π΅Π²ΠΎ.
  3. ΠŸΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠ°ΠΉΡ‚Π΅ ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡ‚ΡŒ шаг 2, ΠΏΠΎΠΊΠ° ΠΌΡ‹ Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ минимальноС остовноС Π΄Π΅Ρ€Π΅Π²ΠΎ.
πŸ“ 10 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π·Π½Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΊΠΎΠ΄Π΅Ρ€

ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠΌ:

Алгоритм ΠŸΡ€ΠΈΠΌΠ° (Prim's Algorithm)
Алгоритм ΠŸΡ€ΠΈΠΌΠ° (Prim's Algorithm)

Бсылка Π½Π° ΠΊΠΎΠ΄: Алгоритм ΠŸΡ€ΠΈΠΌΠ°

9. Алгоритм ΠšΡ€Π°ΡΠΊΠ°Π»Π° (Kruskal's Algorithm)

Алгоритм ΠšΡ€Π°ΡΠΊΠ°Π»Π° ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для нахоТдСния минимального остовного Π΄Π΅Ρ€Π΅Π²Π° для связного взвСшСнного Π³Ρ€Π°Ρ„Π°. Основная Ρ†Π΅Π»ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° β€” Π½Π°ΠΉΡ‚ΠΈ подмноТСство Ρ€Π΅Π±Π΅Ρ€, с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΎΠ±ΠΎΠΉΡ‚ΠΈ ΠΊΠ°ΠΆΠ΄ΡƒΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ Π³Ρ€Π°Ρ„Π°. Он являСтся ΠΆΠ°Π΄Π½Ρ‹ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ, Ρ‚. ΠΊ. Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ этапС вмСсто поиска глобального ΠΎΠΏΡ‚ΠΈΠΌΡƒΠΌΠ°.

ΠŸΡ€ΠΎΡΡ‚ΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠšΡ€Π°ΡΠΊΠ°Π»Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ слСдуСт Π·Π°ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ:

  1. Π‘Π½Π°Ρ‡Π°Π»Π° отсортируйтС всС Ρ€Π΅Π±Ρ€Π° ΠΏΠΎ вСсу (ΠΎΡ‚ наимСньшСго ΠΊ Π½Π°ΠΈΠ±ΠΎΠ»ΡŒΡˆΠ΅ΠΌΡƒ).
  2. Π’Π΅ΠΏΠ΅Ρ€ΡŒ Π²ΠΎΠ·ΡŒΠΌΠΈΡ‚Π΅ Ρ€Π΅Π±Ρ€ΠΎ с наимСньшим вСсом ΠΈ Π΄ΠΎΠ±Π°Π²ΡŒΡ‚Π΅ Π΅Π³ΠΎ Π² остовноС Π΄Π΅Ρ€Π΅Π²ΠΎ. Если добавляСмоС Ρ€Π΅Π±Ρ€ΠΎ создаСт Ρ†ΠΈΠΊΠ», Π½Π΅ Π±Π΅Ρ€ΠΈΡ‚Π΅ Ρ‚Π°ΠΊΠΎΠ΅ Ρ€Π΅Π±Ρ€ΠΎ.
  3. ΠŸΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠ°ΠΉΡ‚Π΅ Π΄ΠΎΠ±Π°Π²Π»ΡΡ‚ΡŒ Ρ€Π΅Π±Ρ€Π°, ΠΏΠΎΠΊΠ° Π½Π΅ достигнСтС всСх Π²Π΅Ρ€ΡˆΠΈΠ½ ΠΈ Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ создано минимальноС остовноС Π΄Π΅Ρ€Π΅Π²ΠΎ.

Бсылка Π½Π° ΠΊΠΎΠ΄: Алгоритм ΠšΡ€Π°ΡΠΊΠ°Π»Π°

10. Алгоритм ΠšΠΎΡΠ°Ρ€Π°Π΄ΠΆΡƒ (Kosaraju's Algorithm)

Если ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ Π΄ΠΎΡΡ‚ΠΈΡ‡ΡŒ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π° ΠΈΠ· любой Π΄Ρ€ΡƒΠ³ΠΎΠΉ Π²Π΅Ρ€ΡˆΠΈΠ½Ρ‹ этого ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π°, Ρ‚ΠΎ ΠΎΠ½ называСтся сильно связанным ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚ΠΎΠΌ (SCC). ΠžΠ΄ΠΈΠ½ΠΎΡ‡Π½Ρ‹ΠΉ ΡƒΠ·Π΅Π» всСгда являСтся SCC. Алгоритм Π€Π»ΠΎΠΉΠ΄Π°-Π£ΠΎΡ€ΡˆΠ°Π»Π»Π° относится ΠΊ ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌ ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π°. Но для получСния Π½Π°ΠΈΠ»ΡƒΡ‡ΡˆΠ΅ΠΉ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ слоТности ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠšΠΎΡΠ°Ρ€Π°Π΄ΠΆΡƒ.

ΠŸΡ€ΠΎΡΡ‚ΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠšΠΎΡΠ°Ρ€Π°Π΄ΠΆΡƒ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ слСдуСт Π·Π°ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ:

  1. Π’Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚Π΅ ΠΎΠ±Ρ…ΠΎΠ΄ Π³Ρ€Π°Ρ„Π° DFS. ΠŸΠΎΠΌΠ΅ΡΡ‚ΠΈΡ‚Π΅ ΡƒΠ·Π΅Π» Π² стСк ΠΏΠ΅Ρ€Π΅Π΄ Π²ΠΎΠ·Π²Ρ€Π°Ρ‚ΠΎΠΌ.
  2. НайдитС Π³Ρ€Π°Ρ„ транспонирования, помСняв мСстами Ρ€Π΅Π±Ρ€Π°.
  3. Π˜Π·Π²Π»Π΅ΠΊΠ°ΠΉΡ‚Π΅ ΡƒΠ·Π»Ρ‹ ΠΎΠ΄ΠΈΠ½ Π·Π° Π΄Ρ€ΡƒΠ³ΠΈΠΌ ΠΈΠ· стСка ΠΈ снова Π² DFS Π½Π° ΠΌΠΎΠ΄ΠΈΡ„ΠΈΡ†ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎΠΌ Π³Ρ€Π°Ρ„Π΅.
πŸ“ 10 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π·Π½Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΊΠΎΠ΄Π΅Ρ€

ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠΌ:

Алгоритм ΠšΠΎΡΠ°Ρ€Π°Π΄ΠΆΡƒ (Kosaraju's Algorithm)
Алгоритм ΠšΠΎΡΠ°Ρ€Π°Π΄ΠΆΡƒ (Kosaraju's Algorithm)

Бсылка Π½Π° ΠΊΠΎΠ΄: Алгоритм ΠšΠΎΡΠ°Ρ€Π°Π΄ΠΆΡƒ

Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ познакомились с самыми Π²Π°ΠΆΠ½Ρ‹ΠΌΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π·Π½Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ программист, Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‰ΠΈΠΉ с Π³Ρ€Π°Ρ„Π°ΠΌΠΈ. Если Ρ…ΠΎΡ‚ΠΈΡ‚Π΅ ΠΏΠΎΠ΄Ρ‚ΡΠ½ΡƒΡ‚ΡŒ ΠΈΠ»ΠΈ ΠΎΡΠ²Π΅ΠΆΠΈΡ‚ΡŒ знания ΠΏΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌ ΠΈ структурам Π΄Π°Π½Π½Ρ‹Ρ…, загляни Π½Π° наш курс «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β», ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ Π² сСбя:

  • ΠΆΠΈΠ²Ρ‹Π΅ Π²Π΅Π±ΠΈΠ½Π°Ρ€Ρ‹ 2 Ρ€Π°Π·Π° Π² нСдСлю;
  • 47 Π²ΠΈΠ΄Π΅ΠΎΠ»Π΅ΠΊΡ†ΠΈΠΉ ΠΈ 150 практичСских Π·Π°Π΄Π°Π½ΠΈΠΉ;
  • ΠΊΠΎΠ½ΡΡƒΠ»ΡŒΡ‚Π°Ρ†ΠΈΠΈ с прСподаватСлями курса.
***

ΠœΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹ ΠΏΠΎ Ρ‚Π΅ΠΌΠ΅

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊΠΈ

ΠœΠ•Π ΠžΠŸΠ Π˜Π―Π’Π˜Π―

ΠšΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΈ

Π’ΠΠšΠΠΠ‘Π˜Π˜

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ вакансию
ML- ΠΈΠ½ΠΆΠ΅Π½Π΅Ρ€
Москва, ΠΏΠΎ ΠΈΡ‚ΠΎΠ³Π°ΠΌ собСсСдования

Π›Π£Π§Π¨Π˜Π• БВАВЬИ ПО Π’Π•ΠœΠ•