Рубрика «дейкстра»

Сотни тысяч маршрутов в секунду на ядро. Опыт Яндекс.Маршрутизации - 1

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

Соревнование от Яндекс.Такси: разбор бэкенд-трека чемпионата по программированию - 1

Вручение призов участникам трека бэкенда

Мы завершаем серию разборов второго чемпионата по программированию. В последние недель мы опубликовали разборы трёх треков: по ML, фронтенду и мобильной разработке. Осталось разобрать трек по бэкенду. Он оказался самым популярным: 2682 человека приняли участие в квалификации, 320 из них дошли до финала. Задачи для бэкенд-разработчиков придумала команда Яндекс.Такси.
Читать полностью »

Начнем с этой всем известной фразы. Итак, были отечественные крутые теплые ламповые (часто в буквальном смысле) наработки, уникальные, созданные талантами. А потом руководство завело бульдозер, который срыл все это подчистую, и засадил все безликими IBM. Так меня учили. Но по мере того, как мне попадались старые книги по программированию (а отчасти я сам свидетель той эпохи — о СССР я знаю не по рассказам), эта картина стала рушиться. У меня сейчас под рукой сейчас три книги, и мы используем их. Итак:

Дейкстра: Величайшей победой Запада в холодной войне над СССР был переход на IBM — myth busted - 1
Читать полностью »

О структуре параллельных вычислений или доводы против оператора «Go» - 1

Каждый язык, поддерживающий параллельные (конкурентные, асинхронные) вычисления, нуждается в способе запуска кода параллельно. Вот примеры из разных API:

go myfunc();                                // Golang

pthread_create(&thread_id, NULL, &myfunc);  /* C with POSIX threads */

spawn(modulename, myfuncname, [])           % Erlang

threading.Thread(target=myfunc).start()     # Python with threads

asyncio.create_task(myfunc())               # Python with asyncio

Есть много вариантов нотации и терминологии, но одна семантика — запустить myfunc параллельно основной программе и продолжить родительский поток выполнения (англ. "Control Flow")

Читать полностью »

Приветствую всех и особенно тех кто интересуется задачами дискретной математики и теорией графов.

Предыстория

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

Читать полностью »

M* — алгоритм поиска кратчайшего пути, через весь мир, на смартфоне - 1

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

Под катом представлена обобщенная эвристика к алгоритму A*, полезная именно в свете практической пригодности на больших графах при ограниченных ресурсах, например, на мобилке.
Читать полностью »

В продолжение статей про устройство таблицы маршрутизации и про реализацию протокола BGP в Quagga, в настоящей статье я разберу как работает протокол OSPF. Я ограничусь случаем для одной OSPF зоны без редистрибъюции маршрутов из других протоколов маршрутизации.
Читать полностью »

image
Изображение с сайта abv24.com

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

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

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

Сейчас это не кажется чем-то необычным, но в 50-е годы это прозвучало как откровение. Дейкстра понял и убедительно показал, как теория может и должна помочь практике.Читать полностью »

image

Некоторые считают, что современный мир почти не знает Никлауса Вирта и даже не догадывается о его огромном вкладе в мировую компьютерную науку. Кто-то полагает его «отцом Паскаля». Вирта вспоминают не только педагоги в ВУЗах, когда преподают студентам Turbo Pascal, но и коммерческие разработчики, пишущие на Delphi.

На самом деле, Никлаус Вирт является инженером с большой буквы, его вклад в развитие языков программирования не ограничивается Паскалем, а только начинается с него. Кроме того, Вирт — педагог, общественный деятель и, можно сказать, философ. Попробуем оценить реальный масштаб его личности и вклад в ИТ-индустрию.Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js