Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Есть хорошая статья Питера Норвига, в которой он рассказывает как написать спеллчекер в 20 строк кода. В этой статье он показывает как поисковые системы могут исправлять ошибки в запросах. И делает это довольно элегантно. Однако, у его подхода есть два серьезных недостатка. Во-первых, исправление более трех ошибок требует больших ресурсов. А гугл, кстати, неплохо справляется и с четырьмя ошибками. Во-вторых, нет возможности проверки связного текста.



Итак, хочется исправить эти проблемы. А именно, написать корректор коротких фраз или запросов, который:

• умел бы выявлять три (и более) ошибки в запросе;
• умел бы проверять «разорванные» или «слипшиеся» фразы, например expertsexchange — experts_exchange, ma na ger — manager
• не требовал много кода для реализации
• мог бы достраиваться до исправления ошибок на других языках и других типов" ошибок

Остальное — под катом.

Небольшой топик-рассуждение на тему перехода на другой язык программирования, и развития знаний. Важно ли изучение дополнительных языков для программиста? Что важнее — язык или архитектура?

Предисловие

Совсем недавно в этом блоге была опубликована статья, посвященная алгоритму поведения роя пчел. Данная статья рассказывает о другом алгоритме роевого интеллекта, называемом муравьиным алгоритмом. Она состоит из введения, вкратце рассказывающего о заимствованном природном механизме, описания оригинального алгоритма Марко Дориго, обзора других муравьиных алгоритмов и заключения, в котором указываются области применения муравьиных алгоритмов и перспективные направления в их исследованиях.

Введение

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

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

Возможно, многие из читателей задавались вопросом, как людям удаётся собирать кубик Рубика 3×3 за 7 секунд. Если даже предположить, что рекордсмену сильно повезло, то таблица мирового рейтинга по среднему из пяти результатов уже не оставляет сомнений: если больше 80 человек в среднем укладываются в 12 секунд, очевидно они что-то знают. В этом кратком обзоре я постараюсь приоткрыть секреты скоростной сборки. Сразу оговорюсь, что после прочтения этой статьи вы не станете чемпионами: здесь приведены только основные моменты и ссылки на более подробную информацию. Кроме того, даже после изучения метода полностью вам потребуются долгие тренировки для достижения хороших результатов. Зато вы получите неплохое представление о том, как это делается, и при желании будете знать, куда двигаться дальше. Я думаю, при достаточной усидчивости после нескольких месяцев тренировок многие смогут достичь среднего результата в районе 30 секунд.

Однажды мне понадобилось решить простенькую (как мне тогда казалось) задачу – в PHP-скрипте узнать длительность mp3-файла. Я слышал о ID3 тегах и сразу подумал, что информация о длительности хранится либо в тегах, либо в заголовках mp3-файла. Поверхностные поиски в интернете показали что за пару-тройку минут решить эту задачу не получится. Поскольку от природы я довольно любопытен а время не поджимало — решил не использовать сторонние инструменты а разобраться в одном из самых популярных форматов самостоятельно.

Если Вам интересно, что там внутри – добро пожаловать под кат (трафик).

[FF D8]

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

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

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

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

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

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

В данной статье речь пойдёт о системе управления содержимым Riot, написанной на Java. Система основана на Spring Framework, использует Ajax.



Я приведу основные возможности системы и пошагово расскажу, как её установить. Статья адресована всем тем, кто интересуется системами управления содержимым на Java.

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

Так что же такое генетический алгоритм? Если верить википедии, то генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Т.е. генетический алгоритм работает наподобие нашей с вами эволюции. Сначала создаются начальные популяции, затем они скрещиваются между собой (при этом возможно возникновение мутаций). Популяции выжившие в процессе естественного отбора проверяются на удовлетворение заданным критериям. Если удовлетворяют — все счастливы, если нет — вновь скрещиваются и так до финальной победы.

Как это все выглядит вы можете увидеть на следующем рисунке:

Достаточно регулярно на хостинге не оказывается предустановленной библиотеки для той или иной программы. И не всегда хостер удовлетворяет просьбу установить библиотеку требуемой версии. Бывает, что библиотека есть, но устаревшая. Или сломался у хостера сервер, он перекинул сайт на другой, а там более новая версия библиотеки, не совместимая с той, на которой работает программное обеспечение сайта (пользователи Django прекрасно поймут меня). Что делать? Искать опять новый хостинг? Всегда быть готовым переписать свою программу под другую версию библиотеки? Наш путь — поставить её самостоятельно. В самом крайнем случае, придётся просто переустановить её. Кроме бинарных модулей PHP почти все библиотеки для популярных веб-технологий можно поставить к себе в домашний каталог не трогая хостера и не завися от него. Кстати сказать, это можно делать не только на шаред-хостинге, но также и на виртуальных серверах — проекты становятся слабо зависящими от того, кто и как настраивал виртуальный сервер. Сложно?

Я искренне хочу помочь ребятам стартаперам, который продвигают продукт «3D-витрина». И предлагаю хабросообществу смелый эксперимент:

− давайте придумаем интересные идеи, которые бы ребята смогли отснять, и чтобы это работало как вирусный маркетинг!

Небольшое вступление

Как только в России стало известно о маркетинге, о мозговом штурме огромное число конкретных лентяев устремилось продавать себя предприятиям как маркетологов, хотя на самом деле они были не маркетологи, а просто шарлатаны. Тот, чье имя в рунете нельзя называть, остудил горячие головы легендарной статьей о маркетинге.

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

Описание

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

Рассмотрим параметры, которые есть у Wayfinder. Указанные параметры относятся к первой версии.

В мире существуют тысячи CMS для самых разных целей, самого разного качества, самой разной перспективы, стоимости, распространённости и так далее. Серьёзно опробовать их все — нереально. Поэтому когда я только знакомился с миром движков для сайтов, выбирать приходилось наугад. Ниже я опишу свои впечатления от знакомства с теми или иными движками для тех или иных целей. К некоторым приложу краткое описание особенностей, впечатление о прочих состоит только из заглядывания в админку. Заметки эти составлялись и редактировались в течении долгого времени, но сейчас я решил, что лучше опубликовать их в нынешнем виде, чем ещё полгода-год по чуть-чуть редактировать не добавляя ничего принципиально нового.
Преимущество отдаётся бесплатным движкам. Платные будут рассматриваться только для сравнения или от безысходности, т.е. если нет бесплатных аналогов. Также ограничение на технологии: php. О движках на перле и питоне я не более чем слышал, на шарпе и джаве имел дело с самописными.
Итак, рассматриваются

• CMS общего назначения. Информационные сайты, визитки, блоги…
• Многофункциональные монстры.
• Галереи.
• Социальные сети.
• Форумы.
• Интернет-магазины.

Вы когда-нибудь интересовались откуда атакующий знает какие порты открыты в системе? Или как узнать, какие приложения запущены на сервере, не спрашивая об этом администратора? Вы можете сделать все это и даже больше вместе с небольшим инструментом под названием Nmap.

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

Amy Editor

Созданый в 2007 Петром Кронторадом (Petr Krontorad), Amy Editor продвинутый редактор с интерфейсом в стиле Mac. Amy Editor имеет в наличие кучу полезных опций, такие как нумерация строк, подсветка синтаксиса, сниппеты для более чем 20 языков, совместное использование и прочее.

» http://www.amyeditor.com

Доброго времени суток, хабрапользователи!

После моих постов:
Дистанционное управление по ИК
Ant-bot. Ворклог. Часть 1
Создаем робота в домашних условиях
Меня довольно часто стали спрашивать о том, какую литературу можно почитать по данному предмету. Чтобы помочь всем и сразу, я решил написать данный пост. =)
Под катом вы можете посмотреть — какую литературу использую я в процессе своих работ.

Как то стало интересно что значат разные буковки/цифарки через точку в названиях видеофайлов.

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

Перевод отличной статейки. Думаю, будет полезна как новичкам, которые только приступили к использованию jQuery, так и тем, кто уже какое-то время с ним работает. А кого-то, возможно, заставит глянуть эту чудесную библиотечку. Многие советы имеют отношение не только к jQuery, но и к JavaScript в целом. Лично для меня была весьма и весьма познавательной, посему и захотелось донести это «до масс». Перевод не дословный, но передающий смысл и максимально адаптированный к русскому языку.

Далее все написано от имени автора оригинальной статьи.

Введение

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

Я не эксперт в jQuery. И даже не претендую, поэтому, если встретите ошибки, смело поправляйте меня и вносите предложения по улучшению (поправлять и присылать поправки нужно автору статьи, а не перевода — зам. пер.).

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

Содержание

1. Загружайте фреймворк с Google Code
2. Используйте «шпаргалку» (cheat sheet)
3. Соединяйте все ваши скрипты и уменьшайте размер файла
4. Используйте возможности Firebug для ведения логов
5. Минимизируйте операции выборки в пользу кэширования
6. Сводите манипуляции с DOM-деревом к минимуму
7. Оборачивайте все в единый элемент, когда речь идет о любой вставке в DOM
8. Используйте «id» вместо классов, где это возможно
9. Задайте контекст своим селекторам
10. Используйте последовательности вызовов методов с умом
11. Научитесь правильно использовать анимацию
12. Научитесь назначать и делегировать события
13. Используйте классы для сохранения состояния
14. Еще лучше — используйте встроенный в jQuery метод data() для сохранения состояния
15. Пишите собственные селекторы
16. Подготавливайте HTML и модифицируйте его, когда страница загружена
17. Используйте «отложенную загрузку» (lazy loading) для определенного контента для выигрыша в общей скорости и преимуществ для SEO
18. Используйте служебные функции jQuery
19. Используйте «noconflict» для переименования глобального объекта «jquery», когда используете его с другими фреймворками
20. Как узнать что картинки загружены?
21. Всегда используйте последнюю версию
22. Как проверить, что элемент существует?
23. Добавляйте класс «JS» в элемент «html»
24. Возвращайте «false» для отмены поведения по-умолчанию
25. Короткая запись для события готовности документа

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