Итак, на выходных мы должны весело отдохнуть, а потому попробуем векторизовать изображение генетическим алгоритмом.
178.33
Рейтинг
Алгоритмы *
Все об алгоритмах
Сначала показывать
Порог рейтинга
Уровень сложности
Нерекурсивная выборка всего дерева Adjacency List
4 мин
4KВообще, чем мне не нравится Adjacency List, так это рекурсией, особенно, когда нужно выбрать дерево, без каких либо ограничений, например:
- Все дерево комментариев;
- Карта сайта;
- Навигационное меню;
- и т.д.;
+13
Атака зомби: математическая модель заражения
1 мин
4.2KВ одном из американских издательств вышел любопытный сборник научных работ по моделированию инфекционных болезней. Одна из статей в сборнике (18-страничный PDF) посвящена весьма «актуальной» сегодня теме — моделированию атаки зомби [When Zombies Attack!: Mathematical Modelling Of An Outbreak Of Zombie Infection – P. Munz, I. Hudea, J. Imad and R.J. Smith?].
Учёные составили базовую математическую модель скорости распространения атаки зомби, в зависимости от количества жителей.
Учёные составили базовую математическую модель скорости распространения атаки зомби, в зависимости от количества жителей.
+63
Структуры данных: бинарные деревья. Часть 2: обзор сбалансированных деревьев
6 мин
242KПервая статья цикла
Во второй статье я приведу обзор характеристик различных сбалансированных деревьев. Под характеристикой я подразумеваю основной принцип работы (без описания реализации операций), скорость работы и дополнительный расход памяти по сравнению с несбаланчированным деревом, различные интересные факты, а так же ссылки на дополнительные материалы.
Интро
Во второй статье я приведу обзор характеристик различных сбалансированных деревьев. Под характеристикой я подразумеваю основной принцип работы (без описания реализации операций), скорость работы и дополнительный расход памяти по сравнению с несбаланчированным деревом, различные интересные факты, а так же ссылки на дополнительные материалы.
+53
Алгоритмы на графах — Часть 2: Сортировка сетей
5 мин
23KПролог
В продолжение опубликованной на выходных статьи.Компиляторы — пожалуй одна из самых интересных тем системного программирования.
Эта статья не расскажет как написать идеальный, или, хотя бы, работающий компилятор, но она поможет прояснить пару аспектов его работы, при помощи метода топологической сортировки сети.
+62
Структуры данных: бинарные деревья. Часть 1
6 мин
368KИнтро
Этой статьей я начинаю цикл статей об известных и не очень структурах данных а так же их применении на практике.
В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.
Начать я решил с бинарных деревьев поиска, так как это достаточно базовая, но в то же время интересная штука, у которой к тому же существует большое количество модификаций и вариаций, а так же применений на практике.
+92
Алгоритмы на графах — Часть 1: Поиск в глубину и проблема взаимоблокировок
6 мин
66KНедавно на Хабре была статья, посвященная алгоритмам на графах. С позволения автора, мой первый хабратопик продолжит цикл.
Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.
Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.
+39
Поиск нечетких дубликатов. Алгоритм шинглов для веб-документов
4 мин
44KРанее я показал элементарную реализацию алгоритма шинглов, позволяющую определять, являются ли два документа почти дубликатами или нет. В этот раз я поясню реализацию алгоритма, описанную Зеленковым Ю. Г. и Сегаловичем И.В. в публикации «Сравнительный анализ методов определения нечетких дубликатов для Web-документов».
Этим я начинаю серию из трех теоретических статей, в которых постараюсь доступным языком описать принцип алгоритмов шинглов, супершинглов и мегашинглов для сравнение веб-документов.
Этим я начинаю серию из трех теоретических статей, в которых постараюсь доступным языком описать принцип алгоритмов шинглов, супершинглов и мегашинглов для сравнение веб-документов.
+51
Алгоритмы на графах — Часть 0: Базовые понятия
5 мин
260KВступление
Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.
Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.
+106
Максимальный поток минимальной стоимости. Решение в Excel
2 мин
5.6KВ ответ на аналогичный пост, который меня подстегнул к написанию этого…
Так как я закончил совсем недавно железнодорожный вуз, и курс логистики имел место там быть, нахлынули на меня приятные воспоминания. Как всегда все расчёты проводились, конечно же вручную, после, пораздумав немного была написана простенькая программка, так сказать, в помощь однокурсникам…
но какого же было моё удивление, когда я узнал, что всё это, как говориться, без меня придумано, да притом и ниодин раз ))).
Речь в статье пойдёт о решении транспортной задачи средствами Microsoft Excel.
как всегда всё гениальное просто, есть такой пунк меню — Поиск решений…
Так как я закончил совсем недавно железнодорожный вуз, и курс логистики имел место там быть, нахлынули на меня приятные воспоминания. Как всегда все расчёты проводились, конечно же вручную, после, пораздумав немного была написана простенькая программка, так сказать, в помощь однокурсникам…
но какого же было моё удивление, когда я узнал, что всё это, как говориться, без меня придумано, да притом и ниодин раз ))).
Речь в статье пойдёт о решении транспортной задачи средствами Microsoft Excel.
как всегда всё гениальное просто, есть такой пунк меню — Поиск решений…
+5
Задача о назначениях
12 мин
81KЗадача о наилучшем распределении некоторого числа работ между таким же числом исполнителей. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. Наиболее эффективным методом ее решения является венгерский метод. Задача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т.д.
+54
Фильтрация изображений методом свертки
6 мин
85KАвтором данного топика является хабраюзер Popik, который сам не может запостить этот топик в силу астральных причин.
Вероятно, большинство хабросообщества не понаслышке знает о фильтрах обработки изображений, таких как размытие, повышение резкости, нахождение краев, тиснение и прочие. Некоторые работали с ними более тесно, некоторые использовали их как данность. Однако все ли знают, как именно происходит фильтрация изображения, и что общего между перечисленными фильтрами? В данном топике я постараюсь в общем виде описать алгоритм, по которому это все выполняется, а так же приведу его реализацию.
Введение.
Вероятно, большинство хабросообщества не понаслышке знает о фильтрах обработки изображений, таких как размытие, повышение резкости, нахождение краев, тиснение и прочие. Некоторые работали с ними более тесно, некоторые использовали их как данность. Однако все ли знают, как именно происходит фильтрация изображения, и что общего между перечисленными фильтрами? В данном топике я постараюсь в общем виде описать алгоритм, по которому это все выполняется, а так же приведу его реализацию.
+85
Классические алгоритмы — интересна ли тема?
1 мин
15KДобрый день!
В последнее время сталкиваюсь с большим количеством разнообразных классических алгоритмов (как на занятиях в ВУЗе так и на практике в проектах), поэтому хочу поделиться с хабра-сообществом интересными материалами на данную тему. Думаю что далеко не все здесь знают о каких алгоритмах идет речь, но вполне возможно что они могли бы быть полезны вам.
В недавний пост: «Максимальный поток минимальной стоимости» навел меня на мысль попробовать описать каждый из этих классических алгоритмов отдельно и подробно.
То есть дать описание каждого алгоритма, вместе с его вычислительной сложностью и сферами применения.
Что я имею ввиду под «классические алгоритмы»:
BFS, DFS, Min Spanning Tree (Prim, ..), Shortest Path(Dijkstra, B-F) и многие другие. Это основные алгоритмы которые изучаются на курсе по алгоритмам и затем широко применяются в различных сферах.
Поэтому собственно вопрос, стоит ли освещать эту тему здесь или нет?
Заранее спасибо за комментарии!
В последнее время сталкиваюсь с большим количеством разнообразных классических алгоритмов (как на занятиях в ВУЗе так и на практике в проектах), поэтому хочу поделиться с хабра-сообществом интересными материалами на данную тему. Думаю что далеко не все здесь знают о каких алгоритмах идет речь, но вполне возможно что они могли бы быть полезны вам.
В недавний пост: «Максимальный поток минимальной стоимости» навел меня на мысль попробовать описать каждый из этих классических алгоритмов отдельно и подробно.
То есть дать описание каждого алгоритма, вместе с его вычислительной сложностью и сферами применения.
Что я имею ввиду под «классические алгоритмы»:
BFS, DFS, Min Spanning Tree (Prim, ..), Shortest Path(Dijkstra, B-F) и многие другие. Это основные алгоритмы которые изучаются на курсе по алгоритмам и затем широко применяются в различных сферах.
Поэтому собственно вопрос, стоит ли освещать эту тему здесь или нет?
Заранее спасибо за комментарии!
+202
Ближайшие события
Firebird Conf: конференция для разработчиков и администраторов СУБД Firebird
6 июня
09:00 – 20:00
Москва
Структурированное программирование
3 мин
5.4KВ начале 80-х годов XX века, в недрах проблемной лаборатории электронных вычислительных машин Московского государственного университета им. М.В.Ломоносова началась работа над необычным, по нынешним меркам, языком, а вернее системы, или даже сказать идеологии программирования.
+16
Максимальный поток минимальной стоимости
15 мин
84KТранспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).
Под катом очень-очень много текста, т.к. рассказывается один из вариантов решения данной задачи «в картинках» для тех, кто мало знаком с графами. Листинг прилагается.
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).
Под катом очень-очень много текста, т.к. рассказывается один из вариантов решения данной задачи «в картинках» для тех, кто мало знаком с графами. Листинг прилагается.
+157
Построение regexp'a по входным строкам S1..SN
3 мин
1.9KВот совершенно недавно столкнулся с задачкой, по которой не смог накопать не то, чтобы каких либо библиотек, но даже теории или алгоритмов. Т.к. время поджимало, решил сам разбираться с задачей. Написал статью для тех, кто с подобной задачей столкнется в будущем, да и интресна критика. Как бы вы решали подобную задачу?
На входе алгоритма есть набор строк S1..SN. Требуется, по данным строкам построить такое минимальное регулярное выражение R, чтобы R(Si)=true, i [1,N] (N порядка нескольких тысяч).
Требование минимальности — не строгое, и доказывать минимальность построенного regexp'a не требуется. Если строки S1..SN обладают некоторой схожей структурой, то regexp должен выявлять эту структуру. Стандартное задание программисту — в меру конкретизировано, но и с некоторой свободой действий.
Итак, задача ...
На входе алгоритма есть набор строк S1..SN. Требуется, по данным строкам построить такое минимальное регулярное выражение R, чтобы R(Si)=true, i [1,N] (N порядка нескольких тысяч).
Требование минимальности — не строгое, и доказывать минимальность построенного regexp'a не требуется. Если строки S1..SN обладают некоторой схожей структурой, то regexp должен выявлять эту структуру. Стандартное задание программисту — в меру конкретизировано, но и с некоторой свободой действий.
+38
GridStack — Пример практического применения flex+bison
31 мин
10KВ последнее время на Хабре появились несколько статей, посвящённых грамматическому разбору выражений.
И это замечательно! По моему скромному мнению, каждый программист должен хоть раз в жизни написать разбор выражения. Постараюсь и я внести свою лепту в общее дело.
Методов разбора существует множество (рекомендую следующий обзор Dick Grune, Ceriel J. H. Jacobs — Parsing Techniques: A Practical Guide, ISBN 0-13-651431-6). Причём реализации методов варьируются от полностью ручных до использования автоматизированных генераторов, таких как bison, antlr, lemon и других.
В то время, как ручное написание лексических и синтаксических (далее я буду называть из лексер и парсер) разборов позволяет достичь максимальной скорости и контроля (особенно над ошибками и способами их преодоления), использование генераторов позволяет сосредоточиться непосредственно на задаче, облегчает модификацию грамматики и бережёт время. Умение владеть такими инструментами позволяет чаще прибегать к DSL (Domain Specific Language) и вообще видеть возможность их применения.
Я хочу привести пример использования bison (парсер) и flex (лексер) в реальной жизни: от возникновения задачи, до её решения.
И это замечательно! По моему скромному мнению, каждый программист должен хоть раз в жизни написать разбор выражения. Постараюсь и я внести свою лепту в общее дело.
Методов разбора существует множество (рекомендую следующий обзор Dick Grune, Ceriel J. H. Jacobs — Parsing Techniques: A Practical Guide, ISBN 0-13-651431-6). Причём реализации методов варьируются от полностью ручных до использования автоматизированных генераторов, таких как bison, antlr, lemon и других.
В то время, как ручное написание лексических и синтаксических (далее я буду называть из лексер и парсер) разборов позволяет достичь максимальной скорости и контроля (особенно над ошибками и способами их преодоления), использование генераторов позволяет сосредоточиться непосредственно на задаче, облегчает модификацию грамматики и бережёт время. Умение владеть такими инструментами позволяет чаще прибегать к DSL (Domain Specific Language) и вообще видеть возможность их применения.
Я хочу привести пример использования bison (парсер) и flex (лексер) в реальной жизни: от возникновения задачи, до её решения.
+17
Prett Parsing — метод Вогана Пратта для разбора выражений
3 мин
5.4KВ тему компиляций и вычислений выражений.
В далёком 1973 году Воган Прэтт (Vaughan Pratt) предложил простой и эффективный метод разбора выражений, не использующий ни автоматы, ни грамматику как таковую.
Идея заключается в том, что каждый символ (token) наделяется свойствами:
lbp = приоритет связывания символа слева,
nud = функция, определяющая результат применения оператора в начале выражения,
led = функция, определяющая результат применения в середине выражения.
Основной разбор осуществляется по схеме:
Константы и переменные имеют приоритет связывания 0, а функция nud возвращает их значение (или ссылку). Поэтому применение разбора к константам сразу возратит их значение.
Для бинарных операторов функция led рекурсивно вызывает продолжение разбора (справа) вплоть до более низкого приоритета, и делает что-нибудь с уже накопленым (слева) результатом, и полученным рекурсивно.
Результат применения оператора аггрегируется для внешнего вызова.
Много-арные операторы — получают аргументы дополнительным вызовом функции разбора.
Префиксные операторы делаются с помощью определения для них функции nud.
Для правостороннего связывания меняется приоритет продолжения рекурсивного разбора.
На сайте effbot.org приводится подробная реализация на питоне.
Там же есть ссылки для жаваскрипта и схемы.
В далёком 1973 году Воган Прэтт (Vaughan Pratt) предложил простой и эффективный метод разбора выражений, не использующий ни автоматы, ни грамматику как таковую.
Идея заключается в том, что каждый символ (token) наделяется свойствами:
lbp = приоритет связывания символа слева,
nud = функция, определяющая результат применения оператора в начале выражения,
led = функция, определяющая результат применения в середине выражения.
Основной разбор осуществляется по схеме:
разбор(приоритет продолжения): вытолкнуть символ из входного потока результат = вызов nud этого символа пока приоритет lbp следующего в потоке символа > приоритета продолжения: вытолкнуть символ из входного потока результат = применени led этого символа к текущему результату
Константы и переменные имеют приоритет связывания 0, а функция nud возвращает их значение (или ссылку). Поэтому применение разбора к константам сразу возратит их значение.
Для бинарных операторов функция led рекурсивно вызывает продолжение разбора (справа) вплоть до более низкого приоритета, и делает что-нибудь с уже накопленым (слева) результатом, и полученным рекурсивно.
Результат применения оператора аггрегируется для внешнего вызова.
Много-арные операторы — получают аргументы дополнительным вызовом функции разбора.
Префиксные операторы делаются с помощью определения для них функции nud.
Для правостороннего связывания меняется приоритет продолжения рекурсивного разбора.
На сайте effbot.org приводится подробная реализация на питоне.
Там же есть ссылки для жаваскрипта и схемы.
+34
Вычисление значения выражения «на коленке»
2 мин
9.2KТема навеяна недавними постами Компилятор выражений и Вычисление значения выражения. Рассмотрены два подхода — построение семантического дерева выражения для быстрого вычисления и вычисление самого выражения на ходу при помощи двух своих стеков. Я же хочу показать довольно простой способ реализации, по сути алгоритма из первой статьи, но на базе рекурсии. Иногда бывает уместно переложить часть работы со стеком на комплиятор, благо современные ОС дают нам большой стек и возможность разумного использования рекурсии.
+6
Вычисление значения выражения
7 мин
47KВ продолжение поста Компилятор выражений. По просьбам читающих. Специально для michurin
Есть много способов вычислить значение выражения мне больше всего нравится метод с двумя стеками.
Нравится за его элегантность и простоту реализации.
Суть метода 2х стеков (наверняка у него есть красивое научное название.) заключается в том, что любое сложно выражение, в конечном счете, сводится к последовательности простых операций. В нашем случае это будет бинарная операция над операндами A и В.
Мы будем идти слева на право, добавляя операнды в один стек, а операции в другой. При каждом добавлении новой операции мы будем пытаться вытолкнуть из стека старые, руководствуясь приоритетами операций.
Есть много способов вычислить значение выражения мне больше всего нравится метод с двумя стеками.
Нравится за его элегантность и простоту реализации.
Суть метода 2х стеков (наверняка у него есть красивое научное название.) заключается в том, что любое сложно выражение, в конечном счете, сводится к последовательности простых операций. В нашем случае это будет бинарная операция над операндами A и В.
Мы будем идти слева на право, добавляя операнды в один стек, а операции в другой. При каждом добавлении новой операции мы будем пытаться вытолкнуть из стека старые, руководствуясь приоритетами операций.
+51
Вклад авторов
alizar 2899.5ZlodeiBaal 1506.0Fil 1460.0agorkov 1345.0haqreu 1139.0Leono 1086.0YUVladimir 1037.0valemak 1014.0mephistopheies 996.0Zalina 922.0