Рубрика «Алгоритмы» - 260

в 14:42, , рубрики: python, алгоритм, Алгоритмы, судоку, метки: , ,

sudoku250title
Доброго времени суток!

Думаю, головоломка Судоку не нуждается в представлении. Многие из нас проводят за её решением достаточно много времени. Например, когда нужно убить время в дороге или просто поворочать мозги, чтобы не сохли. На хабре есть довольно много постов о решении головоломки. Но когда человек решает с десяток, а может и сотню головоломок, то найдётся пытливый ум, который задаст себе вопрос «А как же получается таблица Судоку, имеющая единственное решение? И как можно описать алгоритм для сетки 9x9?».

Приведённый алгоритм является вполне логичным. Но моей задачей было описание и реализация. Обо всём этом написано под катом.

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

в 13:35, , рубрики: Bootstrap, data mining, Алгоритмы, бутстрап, математика, статистика, метки: , ,

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

В статистике тоже есть нечестный метод, который позволяет получить примерный ответ на многие практические вопросы без анализа, грубой компьютерной силой: бутстрап (англ. bootstrap). Придумал и опубликовал его в 1979 году Брэдли Эфрон.
Читать полностью »

в 14:16, , рубрики: .net, mongodb, RabbitMQ, wcf, Алгоритмы, генетические алгоритмы, генетический алгоритм, метки: , , , , , , ,

Решение транспортной задачи при помощи генетического алгоритма как часть SOA

Приветствую уважаемое читатели!

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

Формулировка задачи

Википедия формулирует задачу следующим образом — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе.

Например – необходимо спланировать доставку бутылей воды по городу, известны потребности каждого заказчика, грузоподъёмность транспортных средств и расстояния между точками.

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

в 10:50, , рубрики: Алгоритмы, оптимизация, перебор, метки: ,

В прошлой статье я писал про эвристические методы оптимизации перебора. В этой статье я расскажу вам о ещё одной, но уже асимптотической оптимизации — meet-in-the-middle.

Типичные для этого метода снижения асимптотики: Meet in the middle: оптимизация перебора и не только и Meet in the middle: оптимизация перебора и не только.

Вступление

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

Meet-in-the-middle имеет смысл применять, если для конкретной задачи выполняются два условия:
1) Время обработки половины данных асимптотически меньше времени получения итогового ответа.
2) Известен асимптотически более быстрый способ получения ответа для всей задачи с использованием информации об обработки её половинок.
Читать полностью »

в 16:22, , рубрики: Алгоритмы, поиск подстроки в строке, метки: ,

В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

index = -1
for i in xrange(len(haystack)-len(needle)+1):
    success = True
    for j in xrange(len(needle)):
        if needle[j]<>haystack[i+j]:
            success = False
            break
    if success:
        index = i
        break
print index

Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае.Читать полностью »

в 15:23, , рубрики: python, Алгоритмы, безопасность, информационная безопасность, сайты, сканеры, уязвимости, метки: , , , ,

Время было вечером, делать было нечего… Было решено удивить читателей. Но как? Банальные поиски уязвимостей на известных сайтах уже никому не интересны. Чтож, значит включим фантазию… Ведь у пользователей тоже есть сайты! Срочно проверить их на стойкость!
Читать полностью »

в 14:51, , рубрики: Алгоритмы, математика, Научно-популярное, статистика, метки: ,

image

Нормальное распределение (распределение Гаусса) всегда играло центральную роль в теории вероятностей, так как возникает очень часто как результат воздействия множества факторов, вклад любого одного из которых ничтожен. Центральная предельная теорема (ЦПТ), находит применение фактически во всех прикладных науках, делая аппарат статистики универсальным. Однако, весьма часты случаи, когда ее применение невозможно, а исследователи пытаются всячески организовать подгонку результатов под гауссиану. Вот про альтернативный подход в случае влияния на распределение множества факторов я сейчас и расскажу.
Читать полностью »

в 6:21, , рубрики: Алгоритмы, искусственный интеллект, Компьютерная лингвистика, конечные автоматы, морфологический анализ, метки: , ,

Автоматический анализ текстов практически всегда связан с работой со словарями. Они используются для морфологического анализа, выделения персон (нужны словари личных имен и фамилий) и организаций, а также других объектов.

В общем виде словарь — множество записей вида {строка, данные ассоциированные с этой строкой}.

Например, для морфологического анализа словарь состоит из троек {словоформа, нормальная форма, морфологические характеристики}. При анализе слова «мыла» из предложения «мама мыла раму» надо уметь получать следующие варианты анализа:

Нормальная форма Характеристики
МЫЛО S (существительное), РОД (родительный падеж), ЕД (единственное число), СРЕД (средний род), НЕОД
(неодушевленность)
МЫЛО S (существительное), ИМ (именительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫЛО S (существительное), ВИН (винительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫТЬ V (глагол), ПРОШ (прошедшее время), ЕД (единственное число), ИЗЪЯВ (изъявительное наклонение), ЖЕН (женский род), НЕСОВ (несовершенный вид)

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

в 15:16, , рубрики: Алгоритмы, Блог компании Яндекс, разбор задач, Спортивное программирование, яндекс, яндекс.алгоритм, метки: , , ,

Буквально пару часов назад Санкт-Петербурге завершился открытый чемпионат по программированию Яндекс.Алгоритм 2013. Состязания состояли из нескольких онлайн-раундов по 100 минут, за победу боролись более 3000 программистов из 84 стран. По результатам трёх отборочных раундов в финал вышли 25 лучших. Финал состоялся в Доме учёных имени Горького (дворец Великого князя Владимира Александровича)

image

Финалисты должны были решить шесть алгоритмических задач за 100 минут. Первое место занял недавний победитель ACM ICPC 2013 в составе команды НИУ ИТМО Геннадий Короткевич (tourist), который набрал меньше всего штрафного времени. Второе место досталось выпускнику НИУ ИТМО Евгению Капуну (eatmore). Третье место занял представитель Тайваня Ши Бисюнь.

В подготовке заданий для чемпионата участвовали специалисты из нескольких стран: России, Беларуси, Польши и Японии. Главными составителями задач стали разработчики минского офиса Яндекса (как и все сотрудники компании, к участию в состязаниях они не допускались). Мы попросили всех авторов разобрать задания, которые они подготовили для участников Яндекс.Алгоритма. Кстати, все задачи не удалось решить никому, лучший результат — три решённые задачи — показали только три участника.
Читать полностью »

в 12:12, , рубрики: Алгоритмы, деревья, массив, Программирование, структура данных, метки: , ,

Здравствуйте.

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

У меня просто была проблема, которая оказалась не проблемой в реальном мире, но кажется я решил её в мире абстрактном.

Проблема была следующая: есть список элементов определённой длины. Мы должны быстро получать элемент по индексу, а так же иметь возможность вставить/удалить с любой позиции элемент. Причём чтобы остальные «пододвинулись», либо схлопнулись. Очевидно, что ни линейный список, ни массив не подходят. А обычное дерево не имеет возможности получить элемент по индексу без обхода дерева, которое тоже O(N) и лучше мы бы использовали список.

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

Асимптоматика свойственная дереву: O(log N) на все операции. Вставка/удаление в наивной реализации O((log N)^2), но мне кажется, что это можно оптимизировать.

В этой статье (первой, надеюсь не последней) я опишу, что представляет из себя это дерево, а так же как совершать над ним операции. Если всё работает так, как мне кажется и вы не найдёте никаких проблем, которые нельзя починить — мир получает прекрасную (как мне кажется) структуру данных. Иначе мне будет стыдно.
Читать полностью »

1...1020...259260261...270280...311
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js