Category: Математика

02
Окт
2022

Как записать в переменную уравнения с неизвестными параметрами для дальнейшего их нахождения?

Вопрос звучит довольно запутано, сам понимаю. Сразу приведу пример своей программы, делаю оптимизацию функции по градиентному методу со сферической нормой, для этого
Задаю значения функций
def f(x, y):
return pow(x, 2) + 3*pow(y, 2)

d…

02
Окт
2022

Как записать в переменную уравнения с неизвестными параметрами для дальнейшего их нахождения?

Вопрос звучит довольно запутано, сам понимаю. Сразу приведу пример своей программы, делаю оптимизацию функции по градиентному методу со сферической нормой, для этого
Задаю значения функций
def f(x, y):
return pow(x, 2) + 3*pow(y, 2)

d…

26
Сен
2022

Обратное число по модулю / RSA

Пытаюсь реализовать генерацию параметров для алгоритма RSA, но при вычислении параметра d, где d = e^-1 mod f получаю неверный ответ. Это происходит непостоянно и иногда, при новом запуске программы я получаю верное значение d. Все парамет…

24
Сен
2022

Как сделать ответ целого числа а не десятичной дроби?

Я делаю математический тест в котором есть функция деления. Делители выдают случайные числа и ответ получается дробью. Как сделать так, чтоб когда пользователь писал ответ, ему было бы достаточно написать целое число и не писать саму десят…

19
Сен
2022

Неверный подсчет определителя произвольной матрицы

Функция det2by2(m) вычисляет определитель матрицы 2×2, функция detNbyN(m) вычисляет определитель матрицы любого размера. Функция minor(m, num) вычисляет минор матрицы, здесь num – индекс числа первой строки матрицы. Определитель матрицы в …

13
Сен
2022

🪄 Из-за ненависти к Fortran создал свой язык и доказал, что программирование – это не колдовство

В небольшой статье узнаем об одном из пионеров кодинга, нидерландском ученом Эдсгере Дейкстра, доказавшим всему миру, что программирование – это не фантастика, а интеллектуальное ремесло.

Рождение программиста

Эдсгер Вибе Дейкстра, уроженец голландского Роттердама, появился на свет в 1930 году в семье ученых: отец был химиком, мать – математиком. Они привили мальчику любовь к точным наукам и после окончания школы он стал студентом Лейденского университета, поступив на отделение, где готовили математиков и физиков-теоретиков.

В вузе будущему лауреату премии Тьюринга представился случай познакомится с первыми вычислительными машинами и с загадочной, но такой манящей наукой – программированием. Параллельно с учебой он подрабатывал в Математическом центре столицы Нидерландов, где с другими разработчиками трудился над довольно крупным проектом по созданию компьютера ARMAC. В конце 4-го курса перед ним встал вопрос: продолжать карьеру теоретического физика или все-таки бросить нелюбимое дело и окунуться с головой в область, захватившую все его сознание. Вот что вспоминал ученый о принятом судьбоносном решении в начале своего пути:

«… передо мной стоял трудный вопрос – либо прекратить программировать и стать респектабельным теоретическим физиком, либо все-таки завершить начатое мной обучение с минимальными усилиями и стать… вот только кем? Программистом? Но разве это респектабельная профессия? Ведь пока неизвестно, что такое программирование? В чем должен был состоять тот солидный объем знаний, который позволил бы считать программирование научной дисциплиной?»

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

Дейкстра был творческим разработчиком и внес в кодерские постулаты несколько глобальных вещей. Он является одним из основоположников концепции структурного программирования – то есть методологии, при которой написание кода ведется небольшими блоками. А еще в конце 60-х он в пух и прах разнес целесообразность использования goto в одной из своих статей, называвшейся: Goto considered harmful («Оператор Goto считается вредным»). В результате всех этих действий был внедрен совершенно новый подход к разработке, предотвращающий появление «спагетти-кода», при котором программа пишется пошагово и состоит из ветвлений, циклов и подпрограмм.

Развитие никому неизвестной науки


Конечно, Дейкстра сильно рисковал, выбрав достаточно экзотическую в то время профессию, ведь в 60-е годы людей с такой специальностью можно было пересчитать по пальцам, а компьютеров и вовсе было только два-три десятка. Будущее программирования считалось довольно туманным, но наш герой обладал волевыми качествами и за несколько лет изучения новой науки достиг немалых высот.

Намаявшись в самом начале своего пути с машинным кодом и с постоянным переписыванием одного и того же алгоритма для разных моделей компьютеров, он неизбежно стал смотреть в сторону высокоуровневых языков. Однако появившийся во второй половине 50-х FORTRAN, был далек от совершенства и пришелся Дейкстра не по нраву. Безусловно, FORTRAN для того времени был для человечества огромным шагом вперед, но ему недоставало простоты и логичности конструкций.

Поэтому в 1958 году небольшое сообщество программистов, в состав которого входил Эдгар, находясь в Цюрихе на очередной из технических конференций, решило разработать альтернативу FORTRAN – Алгол.

Язык получился довольно изящный, поскольку его разработка велась с присущими академической среде требованиями четкости и доказуемости. Главной задачей Дейкстры было создание компилятора нового языка. И поскольку он считал, что люди побыстрее должны уйти от ненавистного Fortrana, максимально не приспособленного под психологию человека, придумал себе челлендж в виде отказа от бритья, пока все не будет готово. Результатом этого испытания стали шестинедельная борода и язык Алгол-60, ставший впоследствии крепким фундаментом для многих современных языков программирования.

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста»

Гений программирования

Гениальный программист вел достаточно аскетическую жизнь и был по-хорошему «чудаковат». Он не пользовался благами цивилизации, в его квартире не было телевизора и телефона, он не смотрел художественные фильмы. Ему нравилось писать от руки, о чем красноречиво говорит довольно внушительный каталог его научных работ. К сожалению, детально разобрать их в нашей небольшой статье не получится. Скажем только, что это был ученый с большой буквы, внесший огромный вклад в развитие программирования, как науки.

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

Давайте вспомним эти мудрые фразы вместе:

  1. «Студентов, ранее изучавших Basic, практически невозможно обучить хорошему программированию. Как потенциальные программисты они подверглись необратимой умственной деградации».
  2. «Если отладка – процесс удаления ошибок, то программирование должно быть процессом их внесения».
  3. «Тестирование программ может служить для доказательства наличия ошибок, но никогда не докажет их отсутствия».

Сами его высказывания были не тщеславным желанием программиста блеснуть остроумием – их можно было назвать концентрированным выражением опыта, тонкой интуиции и аналитического ума. Он был ревностным приверженцем идеи безболезненного программирования и жестко реагировал на несовершенные и откровенно плохие разработки аппаратов и систем. Его современники вспоминали недоумение Дейкстры, когда ему сказали, что советское правительство решило копировать зарубежные образцы вычислительной техники, чтобы перевести на них всю советскую промышленность. А когда ученый узнал, что для клонирования выбрали модель IBM/360 (прообраз советской ЕС ЭВМ) – он назвал это решение «величайшей победой Запада в Холодной войне».

***

Боялся знаменитый голландец только лишь того, что программирование станет тривиальным процессом, занятием, доступным каждому. «Это обречено на провал», – говорил ученый о таком исходе. Интересно, как бы он оценил теперешнюю ситуацию в IT?

Материалы по теме

11
Сен
2022

Python как округлить число с дробной частью в меньшую сторону с заданным количеством знаков в дробной части?

Есть переменная, в которой число с дробной частью
value: ‘0.00051057’

Задача в том, чтобы получить число, в дробной части которого останется 6 знаков и округлить дробную часть в меньшую сторону
Почитал про math.ceil, ‎math.floor

10
Сен
2022

Функция стандартной библиотеки для сравнения вещественных чисел С/С++

Приходится часто делать сравнения с вещественными числами, и выполняю эту операцию следующим образом:
fabs(matrix_[i][j] – other.matrix_[i][j]) > EPS

Ранее я случайно находил метод который выполнял следующее:
bool fdif(a, b) {
return…

02
Сен
2022

Геометрические вычисления [закрыт]

Дана сторона квадрата a. Найти его периметр.
Дан радиус окружности r. Найти длину окружности и площадь круга.
Результат каждого вычисления выводите в новой строке с точностью до десятых.
мой код:
public class Task18 {
public static voi…

17
Авг
2022

Что делать если numexpr не работет с большой степенью?

Когда я пишу большое число и возвожу тоже в большую стерпеть мне ничего не выводится а когда я закрываю скрипт с помою ctrl+c то мне выдаёт ошибку KeyboardInterrupt. except ловит исключение но оно срабатывает только после ctrl+c, при повто…

13
Авг
2022

Перевод пикселей в миллиметры

Есть картинка поля(вид сверху) в реальности у него размеры 3000×2000 мм. Так же есть это поле в виде картинки с размерами 1532×1022 пикселей. Я ставлю на этой картинке 2 точки и между ними строится отрезок. Далее я вычисляю длину этого отр…

28
Июл
2022

В Python добавить элементы списка

Решаю задачу, в рамках которой пытаюсь заполнить новый список param_list. Логика формирования его элементов представлена ниже:

В результате же реализации моего кода в список добавляется лишь первый элемент poly_0 = x_j – x_col_list[0]. Он…

27
Июл
2022

Ряд суммы обратных квадратов на java

Здравствуйте!
Подскажите пожалуйста, в чем проблема.
Хочу написать программу на java которая считает сумму обратных квадратов для определеного количества членов. Код прилагается.
public class Main {
public static void main(String[] arg…

24
Июл
2022

Вращение осей используя кватернионы

Не могу разобраться как вращать плоскость вместе с вращением осей.
Пробовал и матрицы и углы Ейлера. Теперь остановился на кватернионах но проблема все та же: Крутишь по Х, потом по Y. Y поворачивается относительно нового поворота по оси X…

06
Июл
2022

🎲 Орел или решка? Основы теории вероятностей простыми словами

Теория вероятностей – это раздел математики, изучающий случайные события, их свойства и действия над ними. В этой статье мы рассмотрим ее определение, основы и применение. Плюс три простых задачи с решениями.

Данная статья является переводом. Ссылка на оригинальную статью.

❓ Что такое теория вероятностей?

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

Определение теории вероятностей

Теория вероятностей – это область математики и статистики, которая занимается определением вероятностей, связанных со случайными событиями. Существует два основных подхода к изучению теории вероятностей: теоретический и экспериментальный. Теоретическая вероятность определяется на основе логических рассуждений без проведения экспериментов. В отличие от нее, экспериментальная вероятность определяется на основе исторических данных путем проведения повторных экспериментов.

Пример теории вероятностей

Предположим, нам необходимо определить вероятность выпадения числа 4 при бросании игральной кости. Число благоприятных исходов равно 1. Возможные исходы игральной кости – {1, 2, 3, 4, 5, 6}. Из этого следует, что всего существует 6 исходов. Таким образом, вероятность выпадения 4 при бросании игральной кости, используя теорию вероятности, можно вычислить как 1 / 6 ≈ 0,167.

🎲 Основы теории вероятностей

Мы можем понять эту область математики с помощью нескольких основных терминов, напрямую связанных с теорией вероятностей.

Случайный эксперимент

Случайный эксперимент в теории вероятностей – это испытание, которое повторяется несколько раз для получения четко определенного набора возможных результатов. Подбрасывание монеты является примером случайного эксперимента.

Пространство выборки

Пространство выборки можно определить как множество всех возможных исходов, полученных в результате проведения случайного эксперимента. Например, пространство выборки при подбрасывании симметричной монеты (fair coin), стороны которой – это орел и решка.

Событие

Теория вероятностей определяет событие как набор исходов эксперимента, который образует подмножество пространства выборки.

Примеры событий:

  1. Независимые – те, на которые не влияют другие события, являются независимыми.
  2. Зависимые – те, на которые влияют другие события.
  3. Взаимоисключающие – события, которые не могут произойти в одно и то же время.
  4. Равновероятные – два или более события, которые имеют одинаковые шансы произойти.
  5. Исчерпывающие – это события, которые равны выборочному пространству эксперимента.

Случайная величина

В теории вероятностей случайную переменную можно определить как величину, которая принимает значение при всех возможных исходах эксперимента.

Существует два типа случайных величин:

  1. Дискретная случайная величина – принимает точные значения, такие как 0, 1, 2…. Описывается кумулятивной функцией распределения и функцией массы вероятности.
  2. Непрерывная случайная величина – переменная, которая может принимать бесконечное число значений. Для определения характеристик этой переменной используются кумулятивная функция распределения и функция плотности вероятности.

Вероятность

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

Формула вероятности P(A): количество благоприятных исходов для A делимое на общее количество возможных исходов.
Формула вероятности P(A): количество благоприятных исходов для A делимое на общее количество возможных исходов.

Условная вероятность

Ситуация, когда необходимо определить вероятность наступления события, притом что другое событие уже произошло.

Обозначается как P(A | B).

Если хочешь подтянуть свои знания по математике, загляни на наш курс «Математика для Data Science», на котором ты:

  • Усвоишь специальную терминологию и сможешь читать статьи по Data Science без постоянных обращений к поисковику.
  • Подготовишься к успешной сдачи вступительных экзаменов в Школу анализа данных Яндекс.
  • Овладеешь математическим аппаратом, который необходим, чтобы стать специалистом в Data Science.

Ожидание

Ожидание случайной величины X можно определить как среднее значение результатов эксперимента, проводимого многократно. Ожидание обозначается как E[X]. Также известно как среднее значение случайной величины.

Дисперсия

Дисперсия – это мера, которая показывает, как распределение случайной величины изменяется относительно среднего значения. Дисперсия определяется как среднее квадратичное отклонение от среднего значения случайной величины. Обозначается как Var[X].

Функция распределения теории вероятностей

Распределение вероятностей или кумулятивная функция распределения – это функция, которая моделирует все возможные значения эксперимента, используя случайную переменную. Распределение Бернулли и биномиальное распределение – это примеры дискретных распределений вероятностей. Например, нормальное распределение представляет собой пример непрерывного распределения.

Массовая функция вероятности

Массовая функция вероятности определяется как вероятность того, что дискретная случайная величина будет в точности равна определенному значению.

Функция плотности вероятности

Функция плотности вероятности – это вероятность того, что непрерывная случайная величина принимает множество возможных значений.

Формулы теории вероятностей

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

Наиболее важные формулы:

  1. Теоретическая вероятность: Число благоприятных исходов / Число возможных исходов.
  2. Эмпирическая вероятность: Число случаев, когда событие происходит / Общее число испытаний.
  3. Правило сложения: P(A ∪ B) = P(A) + P(B) – P(A∩B), где A и B – события.
  4. Правило комплементарности: P(A’) = 1 – P(A). P(A’) означает вероятность того, что событие не произойдет.
  5. Независимые события: P(A∩B) = P(A) ⋅ P(B).
  6. Условная вероятность: P(A | B) = P(A∩B) / P(B).
  7. Теорема Байеса: P(A | B) = P(B | A) ⋅ P(A) / P(B).
  8. Массовая функция вероятности: f(x) = P(X = x).
  9. Функция плотности вероятности: p(x) = p(x) = dF(x) / dx, где F(x) – кумулятивная функция распределения.
  10. Ожидание непрерывной случайной величины: ∫xf(x)dx, где f(x) является МФВ (Массовой функцией вероятности).
  11. Ожидание дискретной случайной величины: ∑xp(x), где p(x) – это ФПВ (Функцией плотности вероятности).
  12. Дисперсия: Var(X) = E[X2] – (E[X])2.

Применение теории вероятностей

Теория вероятностей используется во многих областях и помогает оценить риски, которые связаны с теми или иными решениями. Некоторые из направлений, где применяют теорию вероятностей:

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

🏋️ Практические задания


Задача 1: При бросании двух игральных костей, какова вероятность того, что выпадет комбинация, сумма которой будет равна 8?

Решение

Задача 2: Какова вероятность вытащить карту королеву из колоды?

Решение

Задача 3: Из 10 человек 3 купили карандаши, 5 купили тетради, а 2 купили и карандаши, и тетради. Если покупатель купил тетрадь, какова вероятность того, что он также купил карандаш?

Решение

В заключение

Подведем итоги:

  • Теория вероятностей – это раздел математики, в котором рассматриваются вероятности случайных событий.
  • Понятие вероятности объясняет возможность наступления того или иного события.
  • Значение вероятности всегда лежит между 0 и 1.
  • В теории вероятностей все возможные исходы случайного эксперимента составляют пространство выборки.
  • Теория вероятностей использует такие важные понятия, как случайные величины и кумулятивные функции распределения для моделирования случайного события. Сюда же относится определение различных вероятностей, связанных с этим.

Если хочешь подтянуть свои знания по математике, загляни на наш курс «Математика для Data Science», который включает в себя:

  • 47 видеолекций и 150 практических заданий.
  • Консультации с преподавателями курса.
27
Июн
2022

Как расчитать цену, если известна только текущая цена и процент?

Пример:
На сайте в карточке товара прописана текущая цена изделия, например – 1000. И прописана скидка – 50% (Т.е эта цена уже со скидкой 50%)
Как посчитать цену без скидки, если известно только текущая цена (1000) и скидка (50)?
Цена това…

17
Июн
2022

📐 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)

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

Ниже проиллюстрирован алгоритм кратчайшего пути с одним источником. Здесь наличие одного источника означает, что мы должны найти кратчайший путь от источника ко всем узлам.


После применения алгоритма Дейкстры:

Алгоритм Дейкстры (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, пока мы не получим минимальное остовное дерево.

Получим:

Алгоритм Прима (Prim's Algorithm)
Алгоритм Прима (Prim’s Algorithm)

Ссылка на код: Алгоритм Прима

9. Алгоритм Краскала (Kruskal’s Algorithm)

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

Простой алгоритм Краскала, который следует запомнить:

  1. Сначала отсортируйте все ребра по весу (от наименьшего к наибольшему).
  2. Теперь возьмите ребро с наименьшим весом и добавьте его в остовное дерево. Если добавляемое ребро создает цикл, не берите такое ребро.
  3. Продолжайте добавлять ребра, пока не достигнете всех вершин и не будет создано минимальное остовное дерево.

Ссылка на код: Алгоритм Краскала

10. Алгоритм Косараджу (Kosaraju’s Algorithm)

Если мы можем достичь каждой вершины компонента из любой другой вершины этого компонента, то он называется сильно связанным компонентом (SCC). Одиночный узел всегда является SCC. Алгоритм Флойда-Уоршалла относится к методам полного перебора. Но для получения наилучшей временной сложности мы можем использовать алгоритм Косараджу.

Простой алгоритм Косараджу, который следует запомнить:

  1. Выполните обход графа DFS. Поместите узел в стек перед возвратом.
  2. Найдите граф транспонирования, поменяв местами ребра.
  3. Извлекайте узлы один за другим из стека и снова в DFS на модифицированном графе.

Получим:

Алгоритм Косараджу (Kosaraju's Algorithm)
Алгоритм Косараджу (Kosaraju’s Algorithm)

Ссылка на код: Алгоритм Косараджу

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

  • живые вебинары 2 раза в неделю;
  • 47 видеолекций и 150 практических заданий;
  • консультации с преподавателями курса.
***

Материалы по теме