Как стать автором
Обновить
78
10
Владислав @rebuilder

Разработчик

Отправить сообщение

Век поиска кратчайшего решения задачи о кратчайшем пути

Уровень сложностиСредний
Время на прочтение22 мин
Количество просмотров9.1K

TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

Может показаться, что на самом деле просто не было существенного прогресса с 60х годов, так как Дейкстра предоставил почти асимптотически оптимальный алгоритм решения задачи. На самом деле нет, прогресс был и придумали много чего интересного, хоть и действительно с того времени фокус сместился на другие задачи. Приглашаю под кат если интересно узнать что такого напридумывали, что используется в современных логистических системах, почему меня огорчает отсутствие учёта флага единства в HOMM3 при расчёте пути, ну и наконец, что за мужики на картинке выше рядом с Дейкстрой?

Читать далее
Всего голосов 38: ↑38 и ↓0+40
Комментарии14

Решение систем линейных уравнений с помощью Python

Время на прочтение7 мин
Количество просмотров9.3K

Как‑то я наткнулась на статью, где говорилось о SymPy, а именно о возможности решения систем уравнений с ее помощью. Если кратко, то это бесплатная библиотека для символьных вычислений на языке Python. В символьных вычислениях компьютер работает с уравнениями и выражениями как с последовательностью символов, тогда как в численных оперирует приближёнными числовыми значениями.

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

Приятного прочтения )

Читать далее
Всего голосов 12: ↑11 и ↓1+12
Комментарии5

Как сделать интерактивную карту с маршрутами на Python

Время на прочтение7 мин
Количество просмотров29K

Распространённая задача программистов в работе с геопространственными данными — отобразить маршруты между различными точками. Решением, которое может понадобиться в разработке веб-сайта, делимся к старту курса по Fullstack-разработке на Python.

Читать далее
Всего голосов 11: ↑10 и ↓1+10
Комментарии5

SQL в Фокусе: Полное Руководство. 100 ключевых Вопросов с собеседований

Уровень сложностиСредний
Время на прочтение65 мин
Количество просмотров38K


В этой статье мы разберем самые простые и продвинутые аспекты языка SQL через 100 ключевых вопросов, которые встречаются на собеседованиях. Независимо от того, являетесь ли вы начинающим или опытным разработчиком баз данных, здесь вы найдете интересные и полезные аспекты для себя.

Давайте погружаться в мир SQL и раскрывать его тайны через популярные вопросы и ответы с собеседований. Готовы начать?

Читать
Всего голосов 31: ↑20 и ↓11+12
Комментарии27

Экономика загородного дома. Как утеплить дом и не разориться?

Время на прочтение30 мин
Количество просмотров46K

Экономичное отопление. Как утеплить дом и не разориться?

Каждый городской житель мечтает о загородном доме.

Тишина, свежий воздух!

И тут же вы едете смотреть участок земли в превосходном живописном и экологичном месте.

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

И тут внезапно выясняется, что газа нет!

Что это означает?

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

15кВт — много это или мало?

Ответ как обычно прячется в самом вопросе, а именно: Смотря для чего?

Ниже приведён проект реального одноэтажного дома. (см.рис.1–2)

Читать далее
Всего голосов 88: ↑66 и ↓22+60
Комментарии408

SQLite — замечательная встраиваемая БД (часть 3)

Время на прочтение9 мин
Количество просмотров200K
Первая часть — вводная.
Вторая часть — быстрый старт.

Третья часть — тонкости и особенности.

Читать дальше →
Всего голосов 90: ↑85 и ↓5+80
Комментарии33

16-, 8- и 4-битные форматы чисел с плавающей запятой

Уровень сложностиСредний
Время на прочтение15 мин
Количество просмотров24K

Уже лет 50, со времён выхода первого издания «Языка программирования Си» Кернигана и Ритчи, известно, что «числа с плавающей запятой» одинарной точности имеют размер 32 бита, а числа двойной точности — 64 бита. Существуют ещё и 80-битные числа расширенной точности типа «long double». Эти типы данных покрывали почти все нужды обработки вещественных чисел. Но в последние несколько лет, с наступлением эпохи больших нейросетевых моделей, у разработчиков появилась потребность в типах данных, которые не «больше», а «меньше» существующих, потребность в том, чтобы как можно сильнее «сжать» типы данных, представляющие числа с плавающей запятой.

Я, честно говоря, был удивлён, когда узнал о существовании 4-битного формата для представления чисел с плавающей запятой. Да как такое вообще возможно? Лучший способ узнать об этом — самостоятельно поработать с такими числами. Сейчас мы исследуем самые популярные форматы чисел с плавающей запятой, создадим с использованием некоторых из них простую нейронную сеть и понаблюдаем за тем, как она работает.

Читать далее
Всего голосов 88: ↑87 и ↓1+130
Комментарии99

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

Время на прочтение7 мин
Количество просмотров41K

Новое доказательство за авторством австралийского писателя-фантаста Грега Игана и доказательство от 2011 года, анонимно опубликованное в сети, признали значительными прорывами в области изучения загадки, которую математики исследуют уже 25 лет




16 сентября 2011 года один фанат аниме опубликовал на форуме математический вопрос 4chan, касающийся культового сериала "Меланхолия Харухи Судзумии". Первый сезон шоу, где были и путешествия во времени, показали в порядке, отличном от хронологического, а во время дальнейшего показа и выпуска на DVD порядок эпизодов снова меняли. В интернете фанаты спорили о том, в каком порядке лучше смотреть сериал, а автор вопроса поинтересовался: если бы зрители захотели посмотреть сериал во всех возможных порядках, какое количество эпизодов было бы в кратчайшем их списке? [имеется в виду список, в котором можно найти любую последовательность эпизодов / прим. перев.]
Читать дальше →
Всего голосов 64: ↑62 и ↓2+60
Комментарии77

5 известных нерешённых задач, условие которых нетрудно понять

Время на прочтение3 мин
Количество просмотров44K

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

Эти задачи показались мне интересными, поэтому я решил написать про них статью. И нет, здесь не будет их доказательств.

Поехали!
Всего голосов 51: ↑51 и ↓0+51
Комментарии82

Моделирование нелинейных функций и ограничений в задачах линейного программирования

Уровень сложностиСредний
Время на прочтение7 мин
Количество просмотров2.9K

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

Читать далее
Всего голосов 8: ↑8 и ↓0+8
Комментарии0

Квантовые компьютеры. С точки зрения традиционного программиста-математика. Часть 1

Время на прочтение8 мин
Количество просмотров14K

Квантовые компьютеры. С точки зрения традиционного программиста-математика.
Часть 1. Основы. Квантовый регистр.

О чем эта публикация

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

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

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

Читать далее
Всего голосов 37: ↑37 и ↓0+37
Комментарии26

Ядро планеты Python. Интерактивный учебник

Время на прочтение67 мин
Количество просмотров32K

Добрый день! Меня зовут Михаил Емельянов, недавно я опубликовал на «Хабре» небольшую статью с примерным путеводителем начинающего Python-разработчика. Пользуясь этим материалом как своего рода оглавлением книги, я написал первые четыре главы мини-учебника «Ядро планеты Python», где постарался коротко, но достаточно ёмко раскрыть специфику, удобство, красоту и силу этого прекрасного языка.


Оригинал учебника лежит на GitHub, вы вольны сколько угодно дополнять и переделывать его. Самое главное — учебник написан на Jupiter Notebook, а это значит, что вы можете интерактивно редактировать код, мгновенно добавляя новые сущности или проясняя непонятные моменты.


Core of the planet Python

Читать дальше →
Всего голосов 66: ↑66 и ↓0+66
Комментарии25

Алгоритмы быстрого умножения чисел: от столбика до Шенхаге-Штрассена

Уровень сложностиСредний
Время на прочтение26 мин
Количество просмотров38K

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

И уж конечно, никогда при написании a * b мы не задумываемся о том, как реализовано умножение чисел a и b в нашем языке. Какие вообще есть алгоритмы умножения? Это какая-то нетривиальная задача?

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

Скорее к формулам!
Всего голосов 173: ↑173 и ↓0+173
Комментарии28

5 лайфхаков Python, которые сделают ваш код более читабельным и элегантным

Время на прочтение3 мин
Количество просмотров30K

Привет, Хабр! В этой статье я продемонстрирую 5 трюков Python на понятных для новичков примерах, которые помогут вам писать более элегантный Python код в вашей повседневной работе.

Читать далее
Всего голосов 32: ↑23 и ↓9+17
Комментарии22

Shortest Common Superstring Problem

Время на прочтение9 мин
Количество просмотров11K
Проблема кратчайшей общей надстроки формулируется следующим образом: найти кратчайшую строку, такую, что каждая строка из заданного набора являлась бы её подстрокой. Эта проблема имеет место как в биоинформатике (задача сборки генома в общем случае) так и в сжатии данных (вместо данных хранить их надстроку и последовательность пар, вида (индекс вхождения, длина)).

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

Осторожно, 4 мегабайта!
Читать дальше →
Всего голосов 32: ↑30 и ↓2+28
Комментарии5

Обзор основных методов математической оптимизации для задач с ограничениями

Время на прочтение7 мин
Количество просмотров54K
Я долго готовился и собирал материал, надеюсь в этот раз получилось лучше. Эту статью посвящаю основным методам решения задач математической оптимизации с ограничениями, так что если вы слышали, что симплекс-метод — это какой-то очень важный метод, но до сих пор не знаете, что он делает, то возможно эта статья вам поможет.

P. S. Статья содержит математические формулы, добавленные макросами хабраредактора. Говорят, что они иногда не отображаются. Также есть много анимаций в формате gif.
Читать дальше →
Всего голосов 29: ↑29 и ↓0+29
Комментарии20

Напильник и щепотка фантазии… или как слепить Enterprise из SQL Server Express Edition

Время на прочтение27 мин
Количество просмотров9.4K
Проснись… ты всегда ощущал, что мир не в порядке. Странная мысль, но ее не отогнать – она как заноза в мозгу. Ты всю жизнь живешь в темнице ограничений и правил, навязанных всесильным Майкрософтом, и даже не осознаешь этого.

Нажмешь дизлайк и сказке конец – ты закроешь вкладку и продолжишь бесцельно бродить по рекомендациям Хабра и YouTube.

Захочешь продолжить и войдешь в страну чудес – я покажу тебе насколько глубока… невозможная… кроличья нора успешной разработки на SQL Server Express Edition.

Читать дальше →
Всего голосов 11: ↑9 и ↓2+10
Комментарии14

Работаем с JSON в SQL Server 2016

Время на прочтение10 мин
Количество просмотров109K
JSON сейчас один из самых используемых форматов данных в разработке. Большинство современных сервисов возвращают информацию в виде JSON. JSON также предпочитаемый формат для хранения структурированный информации в файлах, например. Так как очень много данных используется в JSON-формате, то поддержка JSON в SQL Server особенно становится актуальной, чтобы иметь возможность обмениваться данными с другими сервисами.

JSON стал одной из самых востребованных фич, добавленных в SQL Server 2016. Далее в статье мы рассмотрим основные механизмы работы с JSON.
Читать дальше →
Всего голосов 19: ↑19 и ↓0+19
Комментарии8

Владельцы MAPS.ME отменили изменения и вернули старое приложение. Надолго ли?

Время на прочтение7 мин
Количество просмотров65K

Слева — старое приложение, справа — декабрьская версия от южнокорейцев. Источник: «Смерть MAPS.ME?»

В ноябре 2020 года Mail.Ru Group продала MAPS.ME южнокорейской компании Daegu Limited (входит в состав платёжной системы Parity.com), и уже 20 декабря 2020 года новые владельцы выпустили обновление, которое практически убило приложение.

Много лет это бесплатное приложение для мобильных устройств работало на свободных картах OpenStreetMap, отличалось великолепной производительностью и маленьким размером карт, но новые хозяева его переписали. На скриншотах вверху сравниваются карты одного и того же места.

К счастью, новые владельцы осознали глубину своей ошибки и откатили изменения. В апдейте от 30 декабря 2020 года восстановлена вся функциональность. Казалось бы, победа? Справедливость восторжествовала? Нет, в это слабо верится.
Читать дальше →
Всего голосов 55: ↑48 и ↓7+56
Комментарии58

Удивительно быстрые алгоритмы

Время на прочтение5 мин
Количество просмотров25K

Изучая программирование я встречаю примеры невозможных алгоритмов. Интуиция говорит, что такого не может быть, но компьютер опровергает её простым запуском кода. Как такую задачу, требующую минимум кубических затрат по времени, можно решить всего за квадрат? А вон ту я точно решу за линию. Что? Есть гораздо более эффективный и элегантный алгоритм, работающий за логарифм? Удивительно!


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


Интересно? Добро пожаловать под кат!

Читать дальше →
Всего голосов 19: ↑17 и ↓2+21
Комментарии28

Информация

В рейтинге
426-й
Откуда
Краснодарский край, Россия
Зарегистрирован
Активность