Гайс, завтра постараюсь сделать пост, пока что ведутся визуальные изменения канала🧑💻. Половина канала уже изменена, так что ждать постов осталось немного. Также завтра будет оформлена навигация по числам типа float (а точнее проблема этих чисел).
👍2
⭕️‼️ Курс по Python никуда не денется, сегодня будет пост за долгое время, но, параллельно этому будем изучать новую науку 🔗
⭕️ Эти дни я занимался визуалом канала, вы можете это заметить по измененной навигации и измененным постам с самого начала создания канала.
⭕️ Теперь к каждому посту будет прилагаться код для собственной проверки.
🧑💻Всем удачного использования канала
⭕️ Эти дни я занимался визуалом канала, вы можете это заметить по измененной навигации и измененным постам с самого начала создания канала.
⭕️ Теперь к каждому посту будет прилагаться код для собственной проверки.
🧑💻Всем удачного использования канала
🔗 Гайс ку, разберем сегодня библиотеку Math 🧑💻
Она содержит полезные математические функции и константы. ⭕️ Все вычисления происходят на множестве вещественных чисел.
Для начала, нам конечно же нужно подключить эту библиотеку, чтобы мы могли с ней работать. ⭕️ Еще стоит сказать, что библиотека math является стандартной в Python и устанавливать ее отдельно не нужно.
🔗 Подключить библиотеку можно вот так:
🔗 Теперь мы можем спокойно вызывать функции библиотеки, например, можем найти логарифм:
⭕️ Выше мы используем функцию 🟰math.log(x, base)🟰 для вычисления логарифма.
Аргумент x - это число, base - основание. То есть, логарифм 128 по основанию 2 будет равен 7.
🔗 Вычисление натурального логарифма будет выглядеть немного короче:
⭕️ В примере выше подается лишь один аргумент 🟰x🟰, основание у нас итак известно, приблизительно 2,718.
🔗 Вычисление математической константы π
🔗 Вычисление числа Эйлера (e)
➗‼️Так, вроде немного разобрались, теперь перейдем к функциям (Теоретико-числовые функции и функции представления) ✖️ :
🔗 Функция 🟰math.ceil()🟰 округляет аргумент до большего целого числа:
🔗 Функция 🟰math.floor()🟰 также округляет аргумент, но, в меньшую сторону, наоборот:
🔗 Функция 🟰math.copysign()🟰 принимает два аргумента. Возвращает первый аргумент (с плавающей точкой), но со знаком второго.
🔗 Функция 🟰math.fabs()🟰 возвращает абсолютное значение аргумента:
🔗 Функция 🟰math.comb(n, k)🟰 показывает сколькими способами можно выбрать k объектов из множества n элементов. (Формулу я прикреплю после)
⁉️ Допустим, перед нами 8 футболок разных. Сколько есть способов выбрать 4 разные?
🔗 Вычисление факториала. ‼️ Входящее значение должно быть целочисленным и неотрицательным:
🔗 Функция 🟰math.fmod(a, b)🟰 считает остаток от деления a на b (По сути, аналог оператора '%' - деление по модулю ‼️).
🔗 Функция 🟰math.fsum()🟰 вычисляет сумму элементов итерируемого объекта. ⭕️ Пример для списка:
🔗 Функция 🟰math.gcd(a, b)🟰 возвращает наибольший общий делитель a и b (НОД):
🔗 Функция 🟰math.prod()🟰 принимает итерируемый объект, а возвращает произведение элементов:
⭕️ Степенные и логарифмические функции:
🔗 Возврат квадратного корня из аргумента, функция math.sqrt().
Их ,конечно, больше, но, эти ,как по мне, основные ‼️(На❌уя столько запятых придумали)
Она содержит полезные математические функции и константы. ⭕️ Все вычисления происходят на множестве вещественных чисел.
Для начала, нам конечно же нужно подключить эту библиотеку, чтобы мы могли с ней работать. ⭕️ Еще стоит сказать, что библиотека math является стандартной в Python и устанавливать ее отдельно не нужно.
🔗 Подключить библиотеку можно вот так:
import math
🔗 Теперь мы можем спокойно вызывать функции библиотеки, например, можем найти логарифм:
import math
x = 128
base = 2
result = math.log(x, base)
print(result) #Вывод: 7
⭕️ Выше мы используем функцию 🟰math.log(x, base)🟰 для вычисления логарифма.
Аргумент x - это число, base - основание. То есть, логарифм 128 по основанию 2 будет равен 7.
🔗 Вычисление натурального логарифма будет выглядеть немного короче:
import math
print(math.log(10))#Вывод: 2.302585...
⭕️ В примере выше подается лишь один аргумент 🟰x🟰, основание у нас итак известно, приблизительно 2,718.
🔗 Вычисление математической константы π
import math
print(math.pi) #Вывод: 3.14159...
🔗 Вычисление числа Эйлера (e)
import math
print(math.e)
➗‼️Так, вроде немного разобрались, теперь перейдем к функциям (Теоретико-числовые функции и функции представления) ✖️ :
🔗 Функция 🟰math.ceil()🟰 округляет аргумент до большего целого числа:
import math
print(math.ceil(6.000004)) #Вывод: 7
🔗 Функция 🟰math.floor()🟰 также округляет аргумент, но, в меньшую сторону, наоборот:
import math
print(math.floor(8.99)) #Вывод: 8
🔗 Функция 🟰math.copysign()🟰 принимает два аргумента. Возвращает первый аргумент (с плавающей точкой), но со знаком второго.
import math
print(math.copysign(9, -14)) #Вывод: -9.0
🔗 Функция 🟰math.fabs()🟰 возвращает абсолютное значение аргумента:
import math
print(math.fabs(-146)) #Вывод: 146.0
🔗 Функция 🟰math.comb(n, k)🟰 показывает сколькими способами можно выбрать k объектов из множества n элементов. (Формулу я прикреплю после)
⁉️ Допустим, перед нами 8 футболок разных. Сколько есть способов выбрать 4 разные?
import math
print(math.comb(8, 4)) #Вывод: 70
🔗 Вычисление факториала. ‼️ Входящее значение должно быть целочисленным и неотрицательным:
import math
print(math.factorial(9)) #Вывод: 362880
🔗 Функция 🟰math.fmod(a, b)🟰 считает остаток от деления a на b (По сути, аналог оператора '%' - деление по модулю ‼️).
import math
print(math.fmod(16, 5)) #Вывод: 1.0
import math
print(math.fmod(11, -4)) #Вывод: 3.0
🔗 Функция 🟰math.fsum()🟰 вычисляет сумму элементов итерируемого объекта. ⭕️ Пример для списка:
import math
arr = [1, 4, 7, 9, 13]
print(math.fsum(arr)) #Вывод: 34.0
🔗 Функция 🟰math.gcd(a, b)🟰 возвращает наибольший общий делитель a и b (НОД):
import math
a = 32
b = 8
print(math.gcd(a, b)) #Вывод: 8
🔗 Функция 🟰math.prod()🟰 принимает итерируемый объект, а возвращает произведение элементов:
import math
multiple_list = [7, 2, 6]
print(math.prod(multiple_list)) #Вывод: 84
⭕️ Степенные и логарифмические функции:
🔗 Возврат квадратного корня из аргумента, функция math.sqrt().
import math
print(math.sqrt(16)) #Вывод: 4.0
Их ,конечно, больше, но, эти ,как по мне, основные ‼️(На❌уя столько запятых придумали)
👍2
🧑💻 Давайте поговорим о синтаксисе инструкции 🟰import🟰 .
0️⃣⭕️ Мы уже разобрались с тем, что она нужна для импорта модулей в наш код.
1️⃣❗️В этом примере импортируется весь модуль math, и для доступа к его функциям используется синтаксис math.название_функции, в данном случае ( math.sqrt ):
2️⃣⭕️ Мы также можем импортировать только определённые функции или переменные из модуля:
❗️⏫Как вы можете заметить, сравнивая с прошлым примером, мы уже не ставим префикс ( или приставку 🟰math🟰, называйте как хотите ), поскольку мы уже импортировали нужные функции напрямую.
3️⃣ Теперь поговорим про псевдонимы:
⭕️ Нужно это для для сокращения имя модуля (они создаются с помощью ключевого слова 🟰as🟰), вдруг нам не нравится имя модуля или просто нужно повысить читаемость кода.
4️⃣❗️ Импорт всех функций и компонентов модуля:
Синтаксис максимально простой:
🔗 Пример кода:
0️⃣⭕️ Мы уже разобрались с тем, что она нужна для импорта модулей в наш код.
import [название модуля] #Синтаксис
1️⃣❗️В этом примере импортируется весь модуль math, и для доступа к его функциям используется синтаксис math.название_функции, в данном случае ( math.sqrt ):
import math
print(math.sqrt(16))
2️⃣⭕️ Мы также можем импортировать только определённые функции или переменные из модуля:
from math import sqrt, pi
print(sqrt(64))
print(pi)
❗️⏫Как вы можете заметить, сравнивая с прошлым примером, мы уже не ставим префикс ( или приставку 🟰math🟰, называйте как хотите ), поскольку мы уже импортировали нужные функции напрямую.
3️⃣ Теперь поговорим про псевдонимы:
from [название модуля] import [название функции] as [псевдоним] # Синтаксис
⭕️ Нужно это для для сокращения имя модуля (они создаются с помощью ключевого слова 🟰as🟰), вдруг нам не нравится имя модуля или просто нужно повысить читаемость кода.
4️⃣❗️ Импорт всех функций и компонентов модуля:
Синтаксис максимально простой:
from math import *
🔗 Пример кода:
from math import *
print(sqrt(64))
print(pi)
🔗 Средние значения 6.3
Все просто, прописываем формулу по техническому заданию и все 🧑💻
🔗 Код:
Все просто, прописываем формулу по техническому заданию и все 🧑💻
🔗 Код:
import math
a = float(input())
b = float(input())
midl_cr = (a + b)/2
midl_gr = math.sqrt(a*b)
midl_garm = (2 * a * b)/(a + b)
midl_sqr = math.sqrt((a**2 + b**2) / 2)
print(midl_cr)
print(midl_gr)
print(midl_garm)
print(midl_sqr)
🔗Navigation The traveling Salesman Problem (TSP)
0️⃣⁉️ Задача коммивояжёра — как ее рассчитать?
1️⃣🔗 Расчет для 5 городов (пример)
2️⃣🧑💻 Гамильтонов цикл и Гамильтонов путь (А также два основных вида задачи)
3️⃣🟰Класс P (Полиномиальное время)🟰
4️⃣⚙️ Класс NP (Недетерминированное полиномиальное время)
5️⃣‼️ Основные тезисы ‼️
6️⃣🌶🌶 Почему задача до сих пор не решена и почему вашего компьютера на нее не хватит
7️⃣ Время выполнения различных алгоритмов (Дополнительно, но очень годно)
__________________________________
🟰Н А В И Г А Ц И Я🟰
🟰 В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰
0️⃣⁉️ Задача коммивояжёра — как ее рассчитать?
1️⃣🔗 Расчет для 5 городов (пример)
2️⃣🧑💻 Гамильтонов цикл и Гамильтонов путь (А также два основных вида задачи)
3️⃣🟰Класс P (Полиномиальное время)🟰
4️⃣⚙️ Класс NP (Недетерминированное полиномиальное время)
5️⃣‼️ Основные тезисы ‼️
6️⃣🌶🌶 Почему задача до сих пор не решена и почему вашего компьютера на нее не хватит
7️⃣ Время выполнения различных алгоритмов (Дополнительно, но очень годно)
__________________________________
🟰Н А В И Г А Ц И Я🟰
🟰 В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰
Так решена ли задача о коммивояжере или нет? 🔗 Пост об этом 🔗
🧑💻Вы, наверное, все спите, но, да ладно. Мы уже разбирали задачу о коммивояжере и даже решали ее (очень подробно), пост для навигации я уже написал выше⏫.
Дак вот, пару слов о задаче, чтобы вы вспомнили:
◽️ Если прям кратко, нам нужно найти кратчайший маршрут, проходящий через множество городов и возвращающийся в начальную точку (Не обязательно мы возвращаемся обратно, это скорее по классике, вариант без возврата даже будет попроще).
◽️🔗 Так, теперь смотрите, поговорим о разнице этих двух кентов:
⚪️ В классической TSP задаче нам нужно найти кратчайший путь, скажем, A → B → C → D → A. 🔗 Уже заметили, что мы возвращаемся обратно? Дак вот, то, что мы по факту ищем, называется 🟰гамильтоновым циклом🟰. Все куда проще, чем кажется! Берем тот же пример: A → B → C → D → A — это самый обычный граф, а цикл, который проходит через каждую вершину ровно один раз и возвращается обратно и называется 🟰гамильтоновым🟰. То есть, наш цикл проходит через каждую вершину ровно один раз и заходит в начальную точку! Представьте себе поставки грузовых автомобилей, которые возвращаются на склад, они выехали и заехали в одну и ту же точку.
⚪️ Теперь, касаемо Open TSP задачи (без возврата в начальную точку или вершину): допустим, A → B → C → D — такой наш маршрут, уже без возврата. В этой задаче уже попроще, на этот раз мы ищем 🟰гамильтонов путь🟰 (Начинается в одной вершине и заканчивается в другой, он проходит через все вершины графа ровно один раз, но не возвращается в исходную точку.) Я же говорил, что не так уж и сложно!
🔗 Полезная ссылочка:
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit
🧑💻Вы, наверное, все спите, но, да ладно. Мы уже разбирали задачу о коммивояжере и даже решали ее (очень подробно), пост для навигации я уже написал выше⏫.
Дак вот, пару слов о задаче, чтобы вы вспомнили:
◽️ Если прям кратко, нам нужно найти кратчайший маршрут, проходящий через множество городов и возвращающийся в начальную точку (Не обязательно мы возвращаемся обратно, это скорее по классике, вариант без возврата даже будет попроще).
◽️🔗 Так, теперь смотрите, поговорим о разнице этих двух кентов:
⚪️ В классической TSP задаче нам нужно найти кратчайший путь, скажем, A → B → C → D → A. 🔗 Уже заметили, что мы возвращаемся обратно? Дак вот, то, что мы по факту ищем, называется 🟰гамильтоновым циклом🟰. Все куда проще, чем кажется! Берем тот же пример: A → B → C → D → A — это самый обычный граф, а цикл, который проходит через каждую вершину ровно один раз и возвращается обратно и называется 🟰гамильтоновым🟰. То есть, наш цикл проходит через каждую вершину ровно один раз и заходит в начальную точку! Представьте себе поставки грузовых автомобилей, которые возвращаются на склад, они выехали и заехали в одну и ту же точку.
⚪️ Теперь, касаемо Open TSP задачи (без возврата в начальную точку или вершину): допустим, A → B → C → D — такой наш маршрут, уже без возврата. В этой задаче уже попроще, на этот раз мы ищем 🟰гамильтонов путь🟰 (Начинается в одной вершине и заканчивается в другой, он проходит через все вершины графа ровно один раз, но не возвращается в исходную точку.) Я же говорил, что не так уж и сложно!
🔗 Полезная ссылочка:
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit
🧑💻 Продолжаем дискуссию, решена ли она?
⚫️ Теперь говорим о классах сложности этих двух задач:
◾️ Начнем с P (Полиномиальное время). Класс P состоит из задач, которые могут быть решены детерминированным алгоритмом за полиномиальное время относительно размера входных данных. Теперь поясню:
◼️ Детерминированный алгоритм — значит предопределенный, ▪️давайте еще проще▪️, помните бинарный поиск? У нас всего один алгоритм выполнения — постоянное деление пополам и сравнение с результатом, и никуда в сторону мы не 'отходим', действуем по заданному алгоритму. ⚫️ Подводя итоги, в детерминированном алгоритме всего один возможный путь развития событий. Есть у нас входные данные, значит алгоритм будет выполнять один и тот же набор действий!
⚫️ Что такое полиномиальное время?
Представим функцию вида: T(n) = nᵏ. В данном примере, k - константа, является полиномиальной, то есть, это многочлен от размера входных данных n. 🔗Ща все поймете🔗,
Квадратичное время: T(n) = n², Здесь, если n удвоить, количество шагов увеличится в четыре раза. То есть, переменная k показывает, как быстро работает алгоритм в зависимости от размера входных данных. Эти алгоритмы сложности O(n), O(n²), O(n³) являются быстрыми с полиномиальным временем.
🖤 Задачи из класса P считаются эффективно решаемыми на практике, так как их время решения увеличивается относительно медленно с ростом размера входных данных.
⚫️ Теперь говорим о классах сложности этих двух задач:
◾️ Начнем с P (Полиномиальное время). Класс P состоит из задач, которые могут быть решены детерминированным алгоритмом за полиномиальное время относительно размера входных данных. Теперь поясню:
◼️ Детерминированный алгоритм — значит предопределенный, ▪️давайте еще проще▪️, помните бинарный поиск? У нас всего один алгоритм выполнения — постоянное деление пополам и сравнение с результатом, и никуда в сторону мы не 'отходим', действуем по заданному алгоритму. ⚫️ Подводя итоги, в детерминированном алгоритме всего один возможный путь развития событий. Есть у нас входные данные, значит алгоритм будет выполнять один и тот же набор действий!
⚫️ Что такое полиномиальное время?
Представим функцию вида: T(n) = nᵏ. В данном примере, k - константа, является полиномиальной, то есть, это многочлен от размера входных данных n. 🔗Ща все поймете🔗,
Квадратичное время: T(n) = n², Здесь, если n удвоить, количество шагов увеличится в четыре раза. То есть, переменная k показывает, как быстро работает алгоритм в зависимости от размера входных данных. Эти алгоритмы сложности O(n), O(n²), O(n³) являются быстрыми с полиномиальным временем.
🖤 Задачи из класса P считаются эффективно решаемыми на практике, так как их время решения увеличивается относительно медленно с ростом размера входных данных.
Класс NP (Недетерминированное полиномиальное время), мы уже близки.
⚫️ Класс NP состоит из задач, для которых, решение уже известно (TSP как раз сюда и относится), 🟰🟰"Мы можем проверить его правильность за полиномиальное время с помощью детерминированного алгоритма." — Это означает, что время проверки зависит от размера входных данных n и растет как многочлен от n, а процесс проверки следует одному возможному развитию событий (св-во детерминированности)🟰🟰.
⚫️ Класс NP состоит из задач, для которых, решение уже известно (TSP как раз сюда и относится), 🟰🟰"Мы можем проверить его правильность за полиномиальное время с помощью детерминированного алгоритма." — Это означает, что время проверки зависит от размера входных данных n и растет как многочлен от n, а процесс проверки следует одному возможному развитию событий (св-во детерминированности)🟰🟰.
Нам осталось действительно немного, эти классы необходимо было разобрать понимания задачи. Уже сегодня продолжим об этом, я пойду спать 💤
⚪️ Краткие тезисы прошлых постов
🔗 Класс P (Polynomial time):
0️⃣ У нас есть задачи, время выполнения которых зависит от количества входных данных, это означает, 🟰за полиноминальное время🟰.
1️⃣ Еще один момент, такие задачи решаются детерминированным алгоритмом, это означает, что есть всего один возможный путь развития событий. Все эти вышеописанные свойства характерны для класса P.
2️⃣ Задачи класса P эффективны на практике, поскольку время решения увеличивается относительно медленно с ростом размера входных данных.
⚪️ Если задача находится в классе P, значит, мы можем найти её решение относительно быстро, даже если размер входных данных огромен)
🔗 Класс NP (Non-deterministic Polynomial time):
3️⃣ Касаемо класса NP, к которому и относится наша задача о коммивояжере:
Этот класс включает задачи, которые можно проверить за полиноминальное время детерминированным алгоритмом (То есть, быстро и с определенным алгоритмом выполнения). Но, решение может занять куда больше времени, больше чем полиноминальное. Заметьте, что речь идет лишь о проверке уже найденного решения, а не о нахождении решения)
⚪️ Полиномиальное время — это мера того, насколько быстро алгоритм может решить задачу в зависимости от размера входных данных.
4️⃣ Если быть еще точнее, у класса NP есть подкласс NP - полные задачи. Это самые 🌶 сложные задачи этого класса. Туда как раз и относится наша задача о коммивояжере. Если мы найдем ее за полиноминальное время — каждая задача в классе NP могла бы быть решена за полиномиальное время (то есть очень быстро).
🔗 Класс P (Polynomial time):
0️⃣ У нас есть задачи, время выполнения которых зависит от количества входных данных, это означает, 🟰за полиноминальное время🟰.
1️⃣ Еще один момент, такие задачи решаются детерминированным алгоритмом, это означает, что есть всего один возможный путь развития событий. Все эти вышеописанные свойства характерны для класса P.
2️⃣ Задачи класса P эффективны на практике, поскольку время решения увеличивается относительно медленно с ростом размера входных данных.
⚪️ Если задача находится в классе P, значит, мы можем найти её решение относительно быстро, даже если размер входных данных огромен)
🔗 Класс NP (Non-deterministic Polynomial time):
3️⃣ Касаемо класса NP, к которому и относится наша задача о коммивояжере:
Этот класс включает задачи, которые можно проверить за полиноминальное время детерминированным алгоритмом (То есть, быстро и с определенным алгоритмом выполнения). Но, решение может занять куда больше времени, больше чем полиноминальное. Заметьте, что речь идет лишь о проверке уже найденного решения, а не о нахождении решения)
⚪️ Полиномиальное время — это мера того, насколько быстро алгоритм может решить задачу в зависимости от размера входных данных.
4️⃣ Если быть еще точнее, у класса NP есть подкласс NP - полные задачи. Это самые 🌶 сложные задачи этого класса. Туда как раз и относится наша задача о коммивояжере. Если мы найдем ее за полиноминальное время — каждая задача в классе NP могла бы быть решена за полиномиальное время (то есть очень быстро).
‼️Наконец, мы подошли к итогам (Самое важное)‼️
⭕️ Метод, который мы разбирали (брутфорс, перебор всех значений) является неэффективным, особенно для 66 городов) Вы просто прикиньте факториал из 66 перестановок! Только одни бл❌ть перестановки! А еще не забывайте, что нам нужно рассчитать маршруты между городами (или точками, как хотите), затем посчитать это все и сравнить и только потом, найти минимальный маршрут)
⭕️ Задача о коммивояжере считается NP полной (complete), это, чтобы вы просто понимали, эквивалентно по сложности всем задача класса NP)
Факториал 24 это уже 620448401733239439360000 перестановок, поэтому о 66 городах смысла говорить просто нет!
‼️На текущий момент не существует известного алгоритма, который бы мог решить задачу коммивояжера за полиномиальное время (то есть, эффективно) для всех возможных случаев. (Но при этом, есть алгоритмы покруче брутфорса, надеюсь, попозже мы их обязательно разберем)
🔗 P = NP:
Вопрос о равенстве двух классов до сих пор не решен, но многие склонны к не равенству, поскольку, вот уже более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач.
🔗 Полезные ссылки:
https://en.wikipedia.org/wiki/List_of_NP-complete_problems (List of NP-complete problems)
https://habr.com/ru/articles/43224/ (Полезный материал)
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit (Гамильтонов цикл и Путь)
https://skillbox.ru/media/code/big-o-notation-chto-eto-takoe-i-kak-eye-poschitat/ (Полезный материал)
⭕️ Метод, который мы разбирали (брутфорс, перебор всех значений) является неэффективным, особенно для 66 городов) Вы просто прикиньте факториал из 66 перестановок! Только одни бл❌ть перестановки! А еще не забывайте, что нам нужно рассчитать маршруты между городами (или точками, как хотите), затем посчитать это все и сравнить и только потом, найти минимальный маршрут)
⭕️ Задача о коммивояжере считается NP полной (complete), это, чтобы вы просто понимали, эквивалентно по сложности всем задача класса NP)
Факториал 24 это уже 620448401733239439360000 перестановок, поэтому о 66 городах смысла говорить просто нет!
‼️На текущий момент не существует известного алгоритма, который бы мог решить задачу коммивояжера за полиномиальное время (то есть, эффективно) для всех возможных случаев. (Но при этом, есть алгоритмы покруче брутфорса, надеюсь, попозже мы их обязательно разберем)
🔗 P = NP:
Вопрос о равенстве двух классов до сих пор не решен, но многие склонны к не равенству, поскольку, вот уже более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач.
🔗 Полезные ссылки:
https://en.wikipedia.org/wiki/List_of_NP-complete_problems (List of NP-complete problems)
https://habr.com/ru/articles/43224/ (Полезный материал)
https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit (Гамильтонов цикл и Путь)
https://skillbox.ru/media/code/big-o-notation-chto-eto-takoe-i-kak-eye-poschitat/ (Полезный материал)