Метка «Алгоритмы» - 5

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

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

Осторожно, 4 мегабайта!
Читать полностью »

Читатели, добрый день!

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

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

image

Может есть еще люди, которые как-то с нею сталкивались? Но она меня окунула в невероятный мир алгоритмов, блок -схем. Я до сих пор помню как их рисовал на уроках по истории на последних страницах тетрадки. От блок схемы «Как завести хомячка» до «как познакомиться с девушкой». Потом был Basic, Pascal, Cobol, Prolog ,Delphi, C++ Builder, PHP. С некоторыми из них у меня было шапочное знакомство, другие даже выдерживали мой быдлокодинг, а с некоторыми вообще не сложилось.

Меня трудно назвать как-то, кроме быдлокодер. Да, у меня есть проекты, они приносят деньги. Их не один и не два. Живы и здоровы более 6-7 лет. Я не забивал себе голову рефакторингом (ну почти), ставил костыли и работал быстро. Оглядываясь назад мне ничуть не стыдно, хотя, те ребята, которые работают сейчас под моим началом, бывает, ворчат. Сейчас веду отдел программистов одной достаточно крупной компании, ко всему имею маленький онлайн-бизнес, который капает.
Читать полностью »

Графы для самых маленьких: Ford & Bellman или как понять, что ты попал в бесконечно далекое прошлоеВ предыдущих частях цикла мы рассмотрели алгоритмы DFS и BFS, позволяющие найти путь в графе и обладающие рядом других интересных свойств. Но в жизни очень часто оказывается, что гораздо проще выглядит модель задачи в виде графа с неодинаковыми длинами ребер. Поиском кратчайшего пути во взвешенном графе мы и займемся под катом.
Читать полностью »

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

В статье будет много картинок. Объяснение как решать задачу рекурсивно и как она решается бинарным поиском.
В общем статья посвящается тем смелым, кто пока еще боится Ханойской башни, но хочет перестать её бояться.
Читать полностью »

Добрый день, уважаемыее!
В предыдущих постах уже рассказывалось о двух алгоритмах, с помощью которых можно найти путь сквозь лабиринт: DFS и BFS. Всех, кто хочет еще немного поиздеваться над нашим лабиринтом, прошу под кат.
Читать полностью »

Как это сделано: парсинг статей

Для меня всегда было некоей магией то, как Getpocket, Readability и Вконтакте парсят ссылки на страницы и предлагают готовые статьи к просмотру без рекламы, сайдбаров и меню. При этом они практически никогда не ошибаются. А недавно подобная задача назрела и в нашем проекте, и я решил копнуть поглубже. Сразу скажу, что это «белый» парсинг, вебмастеры сами добровольно пользуются нашим сервисом.
Читать полностью »

В предыдущем посте рассказывалось об обходе графа в глубину. Сегодня я бы хотел рассказать о не менее важном алгоритме теории графов — об обходе в ширину.
В прошлый раз мы уже научились искать какой-нибудь путь сквозь лабиринт. Всех желающих найти кратчайший путь прошу под кат.
Читать полностью »

В этой статье хотелось бы рассказать об одном из самых распространенных алгоритмов на графах — об обходе в глубину — на примере решения задачи о нахождении пути сквозь лабиринт. Всем, кому это интересно — добро пожаловать под кат!
Графы для самых маленьких: DFS
Читать полностью »

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

Суть алгоритма заключена в использование структуры данных — бора и построения по нему конечного детерминированного автомата. Важно помнить, что задача поиска подстроки в строки тривиально реализуется за квадратичное время, поэтому для эффективной работы важно, чтоб все части Ахо-Корасика ассимптотически не превосходили линию относительно длинны строк. Мы вернемся к оценке сложности в конце, а пока поближе посмотрим на составляющие алгоритма.
Читать полностью »

Доброго времени суток, уважаемое сообщество.

Пред история

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

Вот собственно и он:

Алгоритм поиска путей в лабиринте

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

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


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