Гайс, завтра постараюсь сделать пост, пока что ведутся визуальные изменения канала🧑💻. Половина канала уже изменена, так что ждать постов осталось немного. Также завтра будет оформлена навигация по числам типа 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 могла бы быть решена за полиномиальное время (то есть очень быстро).