Найдено результатов: 25

Алгоритмы для обработки и анализа звука

Хочется написать свой программный тюнер для гитары (на подобии AP Guitar Tuner), но к сожалению я в этой теме совершенно не ориентируюсь. Примерно себе представляю, что для этого нужно, но как подступиться к проблеме не знаю. Посоветуйте ресурсы или литературу на соответствующую тематику. Спасибо.

Аудио   Алгоритмы   Аналитика    

380   4   09:20, 17th August, 2020


Алгоритм для выделения ошибок?

Подскажите алгоритм для выделения ошибок.


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


К примеру

jahn => j^o^hn

однклассники => одн^о^классники

одноклaнсники => однокла^с^сники


Яндекс так делает yandex.ru/yandsearch?text=sphix&lr=2


За ссылки и описания буду признателен.

Алгоритмы    

377   2   10:12, 12th August, 2020


Помогите с алгоритмом

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

Алгоритмы    

329   3   20:33, 15th August, 2020


Что читать программисту, чтобы улучшить серьезную алгоритмическую базу, необходимую в корпоративном секторе?

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


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



Как программно определить уникальность текста в поисковых системах?

Интересно, как сервисы подобные copyscape,antiplagiat.ru определяют уникальность текста?



Алгоритм сравнения текстовых строк?

Посоветуйте алгоритм сравнения строк с принципом работы вроде:


'Иван Иваныч Иванов' = 'Иванов Иван Иваныч'

'Иван Иваныч' ~ 'Иванов Иваныч'

'Иван Иваныч Иванов с утра ходит без штанов' != 'Иванов Иван Иваныч одевает штаны на ночь'


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

UPD: Кажется придумал:

a — массив слов первой строки

b — массив слов второй строки


n — количество слов первой строки

m — количество слов второй строки


Сij — коэффициент похожести слов a[i] и b[j] (можно использовать soundex или Levenshtein distance)


K = (С11 + С12 +… + С1m + C21 + C22 +… + C2m +… + Cnm) / ((n + m) / 2)


Итого для примера, пусть Cij считается как a[i] == b[j] ? 1 : 0


a = ['Иван', 'Иваныч', 'Иванов']

b = ['Иванов', 'Иван', 'Иваныч']


K = (0 + 1 + 0 + 0 + 0 + 1 + 1 + 0 + 0) / ((3 + 3) / 2) = 3 / 3 = 1 — строки одинаковы


a = ['Иван', 'Иваныч']

b = ['Иванов', 'Иваныч']


K = (0 + 0 + 0 + 1) / ((2 + 2) / 2) = 1 / 2 = 0.5 — похожи, но не равны


Вроде логично.


Спасибо hamMElion, что напомнил разбить строки на слова %)

Алгоритмы   Обработка   текста    

332   6   10:57, 4th August, 2020


Сайт на английском с исходниками алгоритмов на многих языках программирования (wiki)

Подскажите, пожалуйста, адрес такого сайта. Недавно видел ссылку, но так и не добавил к себе. Теперь не могу отыскать.

Алгоритмы   Языки   программирования    

281   5   09:45, 26th August, 2020


Изучение основ программирования (алгоритмы, структуры данных...)

Я работаю программистом (.NET WPF), но чувствую, что мне часто не хватает знаний основ программирования (основные алгоритмы, структуры данных, итп), те вещи, которые люди обычно изучают в вузах. Моя специальность была не программирование, поэтому ничего из этого мы не изучали. Хотелось бы самостоятельно восполнить эти пробелы.

Какие материалы вы посоветуете для изучения? Сайты, книги, сайты с задачками и.т.п.

p.s. (О существовании труда Д. Кнута я конечно-же знаю, что еще помимо него? :)



Как лабиринт из текстового файла отобразить в виде двумерного массива?

Здравствуйте. Сейчас поздно и возможно я немножко торможу, но как-то не приходит в голову как проделать следующее:


допустим в текстовом файле в двумерной декартовой системе координат представлен простейший лабиринт в виде единиц (стены), нолей(комнаты) и двойки (финиш).Таким образом двойка находится по координатам (4,5)

1,1,1,2,1,1

1,0,0,0,0,1

1,0,1,1,0,1

1,0,0,1,0,1

1,1,1,1,1,1


Как преобразовать этот набор чисел в двумерный массив таким образом, чтобы каждое значение массива имело ключ как в декартовой системе координат? Тоесть, чтобы двойка находилась в array[4][5]

Алгоритмы   Массивы    

439   3   06:14, 9th August, 2020


Расположение частей распределённой базы данных

Расскажите, пожалуйста, как производят оптимизацию расположения частей распределённой базы данных? Интересуют более-менее готовые программные продукты и примеры решения задач.

Т.е., например:
есть несколько соединённых серверов под распределённую БД по всей стране, которые одновременно являются и клиентами этой БД.
В базе данных есть множество таблиц.
Есть статистика по запросам с клиентов к конкретным таблицам.
Есть некоторая цена хранения данных на определённом сервере.
Есть некоторая цена передачи, известная для каждой пары сервер-клиент.

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

Существуют ли такие средства для решения этой задачи применительно к каким-нибудь БД (Oracle или другие)?
Или под каждую систему реализуется узкоспециализированное средство?
Или никто просто не парится с решением этой задачи, а данные раскидываются на глазок?

И может быть у кого-нибудь есть примеры систем с распределённой базой данных, которые были оптимизированы таким путём?

Спасибо!



Алгоритмы: где почитать?

Требуется ссылка на русскоязычные ресурсы/книги, на которых можно найти описания различных алгоритмов (новые и старые), написанных интересным языком (т.е. чтобы это было не сухое унылое описание, и к тому же, в каком-то неудобном для чтения формате).

Алгоритмы    

296   7   03:40, 21st August, 2020


Выбор некриптографического алгоритма хеширования?

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


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


То, что удалось найти самому:

  • fnv-1a — самый распространенный по описанию в сети;
  • lookup3 — то, к чему склоняюсь сам; на мой взгляд — наиболее оптимальный, но смущает отсутствие ссылок на успешное применение в проектах, как у fnv;
  • MurmurHash2 — судя по доступным тестам — самый быстрый, есть истории применения (libmemcached, Hadoop); но какая-то неадекватная ситуация с коллизиями на определенных тестовых наборах — simon-says.vox.com/library/post/murmur-hash-very-f... — "...one pathological input sequence of 2^32 values causes the algorithm to suffer from a rate of hash collision as high as 97.6%"

Алгоритмы   Хеширование    

362   2   11:11, 4th August, 2020


Определение части речи слова?

Какие есть алгоритмы определения части речи слова?


Кроме перечисления окончаний в голову ничего не пришло.

<br/>
 /*<br/>
 Группы окончаний:<br/>
 1. прилагательные<br/>
 2. причастие<br/>
 3. глогол<br/>
 4. существительное<br/>
 */<br/>
 <br/>
 $groups = array(<br/>
 1 =&gt; array ('ее','ие','ые','ое','ими','ыми','ей','ий','ый','ой','ем','им','ым','ом','его','ого','ему','ому','их','ых','ую','юю','ая','яя','ою','ею'),<br/>
 2 =&gt; array ('ивш','ывш','ующ','ем','нн','вш','ющ','щ'),<br/>
 3 =&gt; array ('ила','ыла','ена','ейте','уйте','ите','или','ыли','ей','уй','ил','ыл','им','ым','ен','ило','ыло','ено','ят','ует','уют','ит','ыт','ены','ить','ыть','ишь','ую','ю','ла','на','ете','йте','ли','й','л','ем','н','ло','но','ет','ют','ны','ть','ешь','нно'),<br/>
 4 =&gt; array ('а','ев','ов','ие','ье','е','иями','ями','ами','еи','ии','и','ией','ей','ой','ий','й','иям','ям','ием','ем','ам','ом','о','у','ах','иях','ях','ы','ь','ию','ью','ю','ия','ья','я'),);<br/>

Алгоритмы    

357   10   06:44, 22nd August, 2020


Разделять ли содержимое объекта и данные по его расположению в иерархии?

Звучит наверное не совсем понятно, поэтому поясню:

Пусть у нас есть дерево комментариев (Nested Sets или еще что-то, в принципе не важно). Стоит ли выносить поля, не относящиеся напрямую к комментариям (lft, rgt, parent_id и т.д.) в отдельную таблицу БД? С одной стороны, мы избавляемся от привязки к конкретной структуре комментариев (всегда можно поменять NS на MP или еще что-то), а с другой — появляются сложности с объединением этих таблиц.



Поиск по массиву цветов

Есть массив цветов (rgb). Элементов — около миллиона. В массиве ищется наиболее близкий цвет к заданному (критерий близости- это близость точки rgb к точке r1g1b1, т.е. корень из суммы квадратов разниц каждой из трех компонентов цвета). Задача такая — осуществить поиск максимально быстро. Перебирать все элементы массива и для каждого искать близость к заданному цвету — слишком накладно (задача стоит заполнить новый массив еще на несколько миллионов элементов, для каждого делать полный перебор — долго). Как можно осуществить этот поиск? Может какие алгоритмы существуют?

Алгоритмы   Работа   с   цветом    

338   6   16:51, 5th August, 2020


Задача комивояжера

Допустим есть агентство курьерских услуг по городу. Пусть есть 5 курьеров. Метро, автобусы и курьеры ходить пешком тоже умеют Каждый курьер должен съездить в несколько мест.

Вопрос — КАК проложить оптимальный (по времени (в первую очередь) и деньгам) маршрут? (алгоритм). Да это задача комивояжера, но немного измененная.

Хотелось бы чтобы программа отправила курьера с ветки на ветки метро на автобусе за 10 минут и 20 рублей, а не на метро через центр за 40 минут и 19 рублей.

т.е. есть список метро и адрес куда отвести (метро привязано к адресу). Есть 5 курьеров и 25 передач которые нужно вести (по 5 на каждого). Нужно каждому курьеру передать 5 передач чтобы время и стоимость были оптимальны. Ну и вес туда, же.

Как представлю что это такое… становится не по себе. Уже морально готов к полному перебору, но не могу пока придумать алгоритм

Алгоритмы    

333   5   19:11, 6th August, 2020


Как запрограммировать набор условий возникновения события?

Допустим, мне надо, чтобы при выполнении определенных условий возникало событие. Например, «если А > 2000 и Б = 1, то [возникло событие]» или еще как-нибудь.
Суть в том, что пользователь должен иметь возможность сам создать такое условие, динамически выбрав параметры (если, и, или, больше, меньше, сколько раз, в какое время и т.п.). Это также облегчение задачи программисту, которому не надо каждый раз хардкодить условия в алгоритме. Не смог найти описание подобного алгоритма в интернете, но помню, что это было в какой-то cms. Пока думаю о варианте формы, которая постит в табличку с нужными столбцами строки, из которых собирается это условие в дальнейшем. Но это не тру-выход, мне кажется.

Программирование   Алгоритмы    

371   3   01:13, 4th August, 2020


Качественную литературу или сайты по алгоритмам и решению олимпиадных задач?

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

Алгоритмы    

397   4   15:03, 29th August, 2020


Поиск данных с учетом большого числа критериев

Вот сразу вспомнилось, примерно похоже на мою задачу:
Яндекс.Маркет подбор мобилок

Взгляните на панель справа, дофига всяких критериев выбрать можно и работает очень быстро. Как делаются подобные штуки? Какие подходы используются, устройство базы данных? В идеале нужен некий универсальный механизм, который мог бы искать по любому произвольному очень большому набору критериев, по огромному количеству объектов (>100 000) с разным набором полей, делать это максимально быстро, по возможности обходясь без over 9000 серверов.



Алгоритм поиска схожих объектов?

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


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


Т.е. у каждого объекта для каждого классификатора имеем своё соответствие.


Вопрос:


как быстро найти n наиболее (или наименее) схожих объектов для объекта X, когда порядок объектов исчисляется десятками миллионов, а классификаторов десятками тысяч?

Алгоритмы   Классификация    

271   4   11:02, 7th August, 2020


Есть ли здесь бывшие олимпиадники? Как олимпиады помогли Вам?

Добрый вечер.

Этот вопрос уже обсуждался и на Codeforces, и, наверное, даже на TopCoder.

Хочу задать вопрос здесь.

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

Алгоритмы    

353   13   21:06, 1st October, 2020


Веб-приложение: запрет многократных голосований пользователем

Первый раз занимаюсь написанием веб-приложения и возникают вопросы как правильнее было-бы поступить.

Вот например на хабре за топик можно проглосовать только один раз. Как это правильнее реализовать? Хранить с каждым топиком список проголосовавших пользователей? А если же объектов очень много, например комментарии?

Алгоритмы   Веб-разработка    

305   3   19:11, 5th August, 2020


Немного о кармообразовании и его истории

Я на хабре уже давно, зарегистрировался еще до введения системы инвайтов. За кармой особо никогда не стремился, но в силу интереса иногда слежу за ее изменениями.

Сейчас меня разбирает любопытство — а как изменялись алгоритмы ее начисления во времени? И почему сейчас эти алгоритмы такие как они есть?

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

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

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

Хабр   Алгоритмы    

310   2   08:31, 2nd October, 2020


Решение задач по программированию он-лайн. Варианты

Хотелось бы добавить на один ресурс возможность решать задачи по программированию, например, как на Timus. Само веб-приложение написано на Java, хостится все это дело под Ubuntu.

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

Видится такое решение проблемы: создать простые desktop приложения под основные ОС (или написать одно кроссплатформенное), которые будут уметь запускать процессы локально, собирать полученные данные и общаться с сервером. То есть человек скачивает программу и получает возможность решать задачи практически на любом языке программирования.

Собственно вопросы:
1. Как бы вы отнеслись к необходимости скачивать некоторый софт и запускать у себя? Подразумевается, что сайт в принципе trusted и информация о разработчиках сайта является открытой.
2. Может быть у вас есть другие идеи по организации процесса решения задач и проверки результатов.

Заранее спасибо за ваши ответы.



Как найти функцию зная только точки?

Предположим у меня есть набор заначений на плоскости XY, подскажите как найти функцию для этих точек или посоветуй какую нить литературу в этом направлении

Алгоритмы    

289   6   05:50, 26th September, 2020