Класс 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/ (Полезный материал)
🔗 Пол и потолок (6.3)
В общем гайс, ниче сложного, подается лишь одно число x, а вычисляет значение по двум функциям:
⬜️ Функция floor() из модуля math в Python используется для округления чисел с плавающей точкой в меньшую сторону.
⬜️ Функция math.ceil() из модуля math в Python позволяет округлить число до ближайшего целого числа в большую сторону.
🔗 Теперь код:
В общем гайс, ниче сложного, подается лишь одно число x, а вычисляет значение по двум функциям:
⬜️ Функция floor() из модуля math в Python используется для округления чисел с плавающей точкой в меньшую сторону.
⬜️ Функция math.ceil() из модуля math в Python позволяет округлить число до ближайшего целого числа в большую сторону.
🔗 Теперь код:
from math import*
x = float(input())
ans = floor(x) + ceil(x)
print(ans) #Я иду спать, всем сладких
🌶🌶 Квадратное уравнение (6.3)
Думали, эти формулы вам не пригодятся?)Хуй бы не там, ща быстренько решим:
🔗 Я максимально расписывал код, но можно и намного короче:
🔗🔗 Функция pow() возводит число в степень. Она принимает два параметра: какое число возводить и в какую степень возводить.
Думали, эти формулы вам не пригодятся?)
🔗 Я максимально расписывал код, но можно и намного короче:
from math import*
a = float(input())
b = float(input())
c = float(input())
D = pow(b, 2) - (4 * a * c)
if D > 0:
x1 = ((-b + sqrt(D))/(2 * a))
x2 = ((-b - sqrt(D))/(2 * a))
print(min(x1, x2))
print(max(x1, x2))
elif D == 0:
print(-b/(2 * a))
else:
print('Нет корней')
🔗🔗 Функция pow() возводит число в степень. Она принимает два параметра: какое число возводить и в какую степень возводить.
🔗А можно и вот так:
a=float(input())
b=float(input())
c=float(input())
d=b**2-4*a*c
if d < 0:
print("Нет корней")
⚙️ Квадрат числа (7.1)
"Функция range возвращает последовательность чисел в заданном диапазоне." Дак вот, поскольку нам сказали, что диапазон заканчивается на число (включительно), поэтому прибавляем единицу:
🔗 Код:
f' строки (если забыли)
"Функция range возвращает последовательность чисел в заданном диапазоне." Дак вот, поскольку нам сказали, что диапазон заканчивается на число (включительно), поэтому прибавляем единицу:
for i in range(n + 1):
🔗 Код:
n = int(input())
for i in range(n + 1):
print(f'Квадрат числа {i} равен {i ** 2} '
f' строки (если забыли)
🔗Всем доброй ночи гайс, знаю, вы спите. Это скорее вводный пост про Машинное обучение. Если Python я понимал хоть немного, когда начинал этот канал, то вот эту ху⚙️ню я не понимаю от слова совсем..
🔗Далеко я уходить не стал, решил взять книгу из той же серии, что и 'Грокаем Алгоритмы' (посоветовали).
Все остальное я, естественно, не забрасываю, будет все также в полном объеме!
🔗Далеко я уходить не стал, решил взять книгу из той же серии, что и 'Грокаем Алгоритмы' (посоветовали).
Все остальное я, естественно, не забрасываю, будет все также в полном объеме!
Начнем с простейших понятий и я пойду спать, уже завтра будем изучать дальше!
◽️ Здесь нам сразу говорят, что есть такая штука, как искусственный интеллект (это типа набор задач, в которых компьютер может
принимать решения.)
◽️ Машинное обучение, в свою очередь, является частью этой области (МО — это у нас — набор всех задач, в которых компьютер может принимать решения на основе данных).
🔗Таким образом, каждый раз, когда
мы заставляем компьютер решать задачи или принимать решения с помощью только данных, мы занимаемся машинным обучением (на опыте)
◽️ И, наконец, глубокое изучения — это целая область исследований, которая относится к машинному обучению (Это и есть нейросетки).
Кароч, на днях запилю уже какой-нибудь крутой пост о машинке. Это, скорее, было мое вводное слово, всем спокойно ночи!
◽️ Здесь нам сразу говорят, что есть такая штука, как искусственный интеллект (это типа набор задач, в которых компьютер может
принимать решения.)
◽️ Машинное обучение, в свою очередь, является частью этой области (МО — это у нас — набор всех задач, в которых компьютер может принимать решения на основе данных).
🔗Таким образом, каждый раз, когда
мы заставляем компьютер решать задачи или принимать решения с помощью только данных, мы занимаемся машинным обучением (на опыте)
◽️ И, наконец, глубокое изучения — это целая область исследований, которая относится к машинному обучению (Это и есть нейросетки).
Кароч, на днях запилю уже какой-нибудь крутой пост о машинке. Это, скорее, было мое вводное слово, всем спокойно ночи!