Раньше мне часто приходилось собеседовать людей на различные позиции, большая часть из них были разработчики приложений и баз данных. Процесс этот довольно утомительный, т.к. программисты люди смелые, творческие, любознательные и целеустремленные.
В моей практике были всякие вопросы. В статье я выделю три основных типа и расскажу, на чем я в итоге остановился и почему.
Читать полностью »
Рубрика «Алгоритмы» - 271
Две задачки для собеседования разработчиков
2013-05-16 в 14:28, admin, рубрики: sql, Алгоритмы, вопросы, задание, Программирование, собеседование, метки: вопросы, задание, собеседованиеВычисление n-го знака числа Пи без вычисления предыдущих
2013-05-15 в 16:32, admin, рубрики: Алгоритмы, математика, число пи, метки: Алгоритмы, математика, число пи С недавних пор существует элегантная формула для вычисления числа Пи, которую в 1995 году впервые опубликовали Дэвид Бэйли, Питер Борвайн и Саймон Плафф:
Казалось бы: что в ней особенного — формул для вычисления Пи великое множество: от школьного метода Монте-Карло до труднопостижимого интеграла Пуассона и формулы Франсуа Виета из позднего Средневековья. Но именно на эту формулу стоит обратить особое внимание — она позволяет вычислить n-й знак числа пи без нахождения предыдущих. За информацией о том, как это работает, а также за готовым кодом на языке C, вычисляющим 1 000 000-ый знак, прошу под хабракат.
Читать полностью »
Тщетные попытки победить лотерею
2013-05-14 в 9:35, admin, рубрики: алгоритм, Алгоритмы, игра, искусственный интеллект, лотерея, математика, теория вероятностей, метки: алгоритм, игра, лотерея, теория вероятностей Представим воображаемый хитрого дядю, который хочет обмануть и заработать деньги на «лопухах». Назовем его Геннадий Обмануев.
В самый обычный вторник, Геннадию Обмануеву вдруг пришла гениальная идея: создать лотерею, в которой каждый игрок может сам указывать свой шанс на победу и, следовательно, множитель выигрыша и играть на выставленных им правилах! Для того, чтобы всегда оставаться в плюсе, Геннадий в конце каждой удачной игры берет символическую плату в 5% от выигрыша.
*если кратко об игре
Как и в случае с казино, чем дольше игрок играет в такую игру — тем более вероятно, что он, в конце концов, проиграет. Но неужели нельзя обмануть хитрого дядю, придумав чудесную тактику, благодаря которой можно увеличить свои шансы на победу?
Читать полностью »
Разбор «лохотрона» на игральных картах
2013-05-11 в 10:17, admin, рубрики: Алгоритмы, карты, лохотрон, математика, развод, теория вероятностей, метки: карты, лохотрон, развод, теория вероятностейВместо вступления
В стандартной колоде для покера 54 карты. Без двух джокеров, которые не участвуют в игре, выходит 52 карты. Если вы хорошенько перемешаете колоду, то, возможно, создадите уникальную комбинацию из карт, которую никогда никто не создавал до вас. Потому что различных вариантов расположений 52 карт равно: 
Что-то мне подсказывает, что комбинация на изображении не так уникальна.
Теперь к теме
Недавно я узнал про метод «барного развода» на игральных картах, благодаря которому «умные дяди» выигрывают приличные суммы. Суть такова:
«Разводчик» приходит в бар и некоторое время болтает с окружающими, чаще всего присоединяется к большим компаниям молодых людей. Он пытается влиться в компанию и стать «своим» среди окружающих. После того, как он заслужил некоторое доверие и к нему привыкли, разводчик выбирает самого вспыльчивого и разводит его на спор:
Я слышал, что у [блондинов/низких людей/тех, кто носит кепки/любой подходящий вариант] интуиция просто отстой! Вот спорим, что ты не сможешь угадать (в этот момент разводчик достает колоду карт) цвет каждой следующей карты? Можешь перетасовать колоду, как захочешь! За каждую угаданную карту плачу по тысяче рублей! А если не угадаешь, то ты даешь мне один рубль, потом докидываешь до двух, до четырех рублей и дальше, ну ты понял? И чтобы было честно — остановить игру может лишь тот, кто проигрывает. Идет?
Большинство читателей уже поняли схему и с улыбкой прикидывают сумму, которую может выиграть разводчик.
Мне стало интересно, до каких пор игрок выигрывает и как нужно действовать, чтобы увеличить шансы на выигрыш (лучший способ — отказаться от игры!). Естественно, правило про остановку игры я не учитываю, с ним выиграть невозможно.
Читать полностью »
Определение расстояния между географическими точками в MySQL
2013-05-09 в 6:10, admin, рубрики: mysql, Алгоритмы, геолокация, хранимые процедуры, метки: mysql, геолокация, хранимые процедурыПри разработке современного сайта часто возникает необходимость реализовать функционал вывода близлежащих географических точек. Самым оптимальным способом решения этой задачи является перекладывание работы по реализации определения точек на плечи MySQL. Если конкретней, то нам будут нужны возможности пространственных расширений MySQL (до версии 5.0.16 эти расширения были доступны только для MyISAM, более поздние версии MySQL поддерживают работу пространственных расширений с InnoDB, NDB, BDB и ARCHIVE).
Расстояние между точками будет вычисляться по формуле Хаверсина. Формула позволяет получать расстояние между точками с очень низкой погрешностью (величина погрешности прямо пропорциональна расстоянию между точками, и не превышает 10-20 километров при вычислении очень больших расстояний, например между штаб-квартирой Google в Калифорнии (37.422045, -122.084347) и оперным театром в Сиднее, Австралия (-33.856553, 151.214696)).
Некриптографические хеш-функции и DoS атака на них
2013-05-07 в 3:26, admin, рубрики: CRC, hmac, mac, Алгоритмы, информационная безопасность, криптография, метки: CRC, hmac, macНекриптографические хеш-функции применяются там, где важна скорость и не так важна возможность атаки на характеристики функции. Последнее время активно обсуждается атака на алгоритмическую сложность хеш-таблиц, которая может привести к DoS. Мы рассмотрим современные некриптографические хеш-функции, их свойства, и возможные методы защиты от атаки на хеш-таблицы.
Некриптографические хеш-функции
Если криптографические хеш-функции у всех на слуху, то про некриптографические (хеш-функции общего назначения) известно мало. Некриптографические функции применяются там, где на данные не воздействуют третьи лица (злоумышленник). Например, такие функции могут использоваться для построения хеш-таблиц.
Критерии, которые важны для некриптографических хеш-функций:Читать полностью »
Путешествия во времени и программирование 2: парадоксы
2013-05-07 в 1:18, admin, рубрики: алгоритм "Жизнь", Алгоритмы, будущее здесь, Программирование, путешествия во времени, метки: путешествия во времени 
Эпоха путешествий во времени еще не наступила, а человечество уже давно пытается разрешить сопутствующие им парадоксы. Мы поговорим о самом очевидном из них: что же все-таки произойдет при вмешательстве в ход истории? Существует несколько вариантов того, как поток времени реагирует на действия путешественника из будущего. Эти модели можно увидеть в фантастических фильмах, о них все больше начинают говорить ученые, но какая модель ближе к истине — единого мнения пока нет. Мы только начинаем проникать в тайны времени, и еще не обладаем возможностью экспериментировать с перемещениями в прошлое. Что же можно прояснить в данном вопросе уже сейчас? Под катом нас ждет экскурсия по основам механики времени, мы порассуждаем о парадоксах, и проведем небольшой эксперимент. Да, это будет испытание виртуальной машины времени, построенной на основе алгоритма «Жизнь»!Читать полностью »
Генератор Федеративного Фильтра Калмана с использованием Генетических Алгоритмов
2013-05-01 в 12:30, admin, рубрики: .net, async, genetic algorithms, parallel programming, simulation, tpl, Алгоритмы, генетические алгоритмы, параллельное программирование, фильтр калмана, метки: async, genetic algorithms, parallel programming, simulation, tpl, генетические алгоритмы, фильтр калмана В рамках своей научной активности реализовал так называемый Федеративный Фильтр Калмана (Federated Kalman Filter). В этой статье рассказывается о том, что такое «Федеративный ФК», чем он отличается от обобщенного, а также описывается консольное приложение, реализующее данный фильтр и генетические алгоритмы для подбора параметров его математической модели. Приложение было реализовано с использованием TPL (Task Parallel Library), поэтому пост будет интересен не только специалистам по цифровой обработке сигналов.
Читать полностью »
Популяционный алгоритм, основанный на поведении косяка рыб
2013-04-29 в 14:03, admin, рубрики: Алгоритмы, генетический алгоритм, оптимизация, метки: генетический алгоритм, оптимизацияВ рамках данного сообщества неоднократно обсуждались генетические алгоритмы и их применение на практике. В этой статье я хотел бы поделиться относительно новым методом оптимизации функций, основанным на поведении косяка рыб в условиях поиска пищи.Читать полностью »
Порождающие грамматики Хомского
2013-04-24 в 18:05, admin, рубрики: Алгоритмы, математика, ПрограммированиеНебольшое предисловие
Этот текст является продолжением поста , в котором автор попытался как можно более просто и без сложных математических выкладок описать понятия формального языка и грамматики. На этот текст пришло достаточно много откликов и автор счел себя обязанным написать продолжение.
Ниже описывается формализм порождающих грамматик Хомского. Методы задания языка с помощью порождающих грамматик сейчас довольно популярны, особенно для машинной обработки компьютерных языков. Но обычно изучение порождающих грамматик в теории трансляторов заканчивается на контекстно-свободных грамматиках. Последние являются довольно узким специальным классом порождающих грамматик Хомского и обычно используются как вид категориальных грамматик (как конкретно это делается, будет показано ниже) для задания синтаксических анализаторов. Последнее обстоятельство только затуманивает понимание подхода Хомского. Дальнейшее изложение предназначено тем, кому интересно понять, в чем состоит этот подход.