Алгоритмы → Использование нечетких бинарных отношений при решении задачи о назначениях (распределение персонала) из песочницы
Задача о назначениях известна достаточно давно, основные алгоритмы ее решения уже описаны на Хабарахабре (см. например Задача о назначениях). Тем не менее задача до сих пор актуальна при распределении сотрудников по должностям, в случае когда сотрудников и должностей и критериев очень много, обычные методы окажутся очень трудоемкими
для лица, принимающего решение (ЛПР). Более того, на данный момент для решения такой задачи возможно использование генетического алгоритма и его модификации (интерактивный генетический алгоритм). То есть возникает достаточно сложная многокритериальная задача поиска оптимальной альтернативы, которю можно разбить на две задачи. Если вакансия одна, а претендентов много, то для ЛПР для выбора эффективным будет использование метода многокритериальный выбора альтернатив с использованием правил нечеткого вывода (Многокритериальный выбор альтернатив с использованием правил нечеткого вывода.).
В данной статье предпринимается попытка решить задачу о назначениях в случае нескольких должностей и нескольких вакансий с помощью методов нечеткой логики, а именно с помощью использования нечетких бинарных отношений. Предложения/замечания/улучшения приветствуются.
для лица, принимающего решение (ЛПР). Более того, на данный момент для решения такой задачи возможно использование генетического алгоритма и его модификации (интерактивный генетический алгоритм). То есть возникает достаточно сложная многокритериальная задача поиска оптимальной альтернативы, которю можно разбить на две задачи. Если вакансия одна, а претендентов много, то для ЛПР для выбора эффективным будет использование метода многокритериальный выбора альтернатив с использованием правил нечеткого вывода (Многокритериальный выбор альтернатив с использованием правил нечеткого вывода.).
В данной статье предпринимается попытка решить задачу о назначениях в случае нескольких должностей и нескольких вакансий с помощью методов нечеткой логики, а именно с помощью использования нечетких бинарных отношений. Предложения/замечания/улучшения приветствуются.
Python → Обычная (или не совсем обычная) транслитерация на Python
Как-то раз возникла необходимость написать транслитерацию на Python — из кириллицы в латиницу. Из слова «ситх» получается «sith», а из «шелест» выходит «shelest».
Казалось бы, чего тут вообще писать — задача едва сложнее print "Hello world". И это отчасти так — но не совсем.
Дело в том, что некоторые буквы в русском языке при транслитерации преобразуются не в одну, а сразу несколько латинских букв: это Ж, Ц, Ч, Ш, Щ, Ю и Я. По сути, если бы правилами транслитерации предполагалось преобразовывать их в одну латинскую букву, то транслитерация русского в английский действительно была бы не намного сложнее той самой простейшей программы.
Но, поскольку правила транслитерации мы менять точно не собираемся, то посмотрим, что получится при использовании обычной транслитерации.
К примеру, фраза «ШАПКА и Юля» преобразуется в «SHAPKA и YUlya», либо в «ShAPKA и Yulya» — в зависимости от того, что задано в таблице транслитерации для «Ш» и «Ю» (иногда задаётся «SH» и «YU», а иногда «Sh» и «Yu»).
То есть регистр следующей буквы в стандартных функциях транслитерации не учитывается, и все буквы в верхнем регистре заменяются по общим правилам. Поэтому в ходе транслитерации для слов «ЧАША» и «Щи» легко получается что-то вроде «ChAShA» или «SCHi», когда реально мы скорее хотели получить «CHASHA» и «Schi».
Тем не менее, все найденные реализации транслитерации из кириллицы в латиницу на Python, как выяснилось, эту особенность не учитывали. Это и многочисленные решения, приведённые на форумах, и библиотека pytils, реализующая транслитерацию в одном из своих модулей.
Значит, напишем свою функцию транслитерации, с блэкджеком и^W^W^W^H^H. :)
Казалось бы, чего тут вообще писать — задача едва сложнее print "Hello world". И это отчасти так — но не совсем.
Дело в том, что некоторые буквы в русском языке при транслитерации преобразуются не в одну, а сразу несколько латинских букв: это Ж, Ц, Ч, Ш, Щ, Ю и Я. По сути, если бы правилами транслитерации предполагалось преобразовывать их в одну латинскую букву, то транслитерация русского в английский действительно была бы не намного сложнее той самой простейшей программы.
Но, поскольку правила транслитерации мы менять точно не собираемся, то посмотрим, что получится при использовании обычной транслитерации.
К примеру, фраза «ШАПКА и Юля» преобразуется в «SHAPKA и YUlya», либо в «ShAPKA и Yulya» — в зависимости от того, что задано в таблице транслитерации для «Ш» и «Ю» (иногда задаётся «SH» и «YU», а иногда «Sh» и «Yu»).
То есть регистр следующей буквы в стандартных функциях транслитерации не учитывается, и все буквы в верхнем регистре заменяются по общим правилам. Поэтому в ходе транслитерации для слов «ЧАША» и «Щи» легко получается что-то вроде «ChAShA» или «SCHi», когда реально мы скорее хотели получить «CHASHA» и «Schi».
Тем не менее, все найденные реализации транслитерации из кириллицы в латиницу на Python, как выяснилось, эту особенность не учитывали. Это и многочисленные решения, приведённые на форумах, и библиотека pytils, реализующая транслитерацию в одном из своих модулей.
Значит, напишем свою функцию транслитерации, с блэкджеком и^W^W^W^H^H. :)
JAVA → Из Басры в Рим. Преобразовываем арабские числа в римские из песочницы
Доброе время суток, Хабраюзер.
Разрабатывая в основном для платформы J2ME, я всегда старался вносить какие то изюминки в свои проекты. Так, однажды, мне понадобилось выделить пункты меню.
Стандартное решение, через тире или пронумеровав их, использовать не очень хотелось, но другие варианты тогда у меня отсутствовали. Обдумывая как бы лучше оформить эти пункты, я случайно наткнулся на свою старую школьную тетрадку по истории, в которой пункты были пронумерованы с использованием римских цифр. Бинго!
Стоит признаться, на то время моих познаний в римских цифрах хватало только для подсчета до второго-третьего десятка. Что вообще то для нумерации пунктов должно было хватить. Но как любой программист, захотелось иметь готовое решение, которое смогло бы переводить любые целые десятичные арабские числа в эквивалентные им римские.
Разрабатывая в основном для платформы J2ME, я всегда старался вносить какие то изюминки в свои проекты. Так, однажды, мне понадобилось выделить пункты меню.
Стандартное решение, через тире или пронумеровав их, использовать не очень хотелось, но другие варианты тогда у меня отсутствовали. Обдумывая как бы лучше оформить эти пункты, я случайно наткнулся на свою старую школьную тетрадку по истории, в которой пункты были пронумерованы с использованием римских цифр. Бинго!
Стоит признаться, на то время моих познаний в римских цифрах хватало только для подсчета до второго-третьего десятка. Что вообще то для нумерации пунктов должно было хватить. Но как любой программист, захотелось иметь готовое решение, которое смогло бы переводить любые целые десятичные арабские числа в эквивалентные им римские.
Алгоритмы → Алгоритм Тадао Такаока для нахождения максимальной подматрицы или Maximum Subarray Problem из песочницы
Не так давно прошёл конкурс параллельного программирования Acceler8 2011. Суть задачи заключалась в поиске максимальной подматрицы в данной матрице (сумма элементов найденной подматрицы должна быть максимальной). После недолгого «гугления» было найдено, что некий алгоритм Тадао Такаока решает эту задачу быстрее других.
«Вызов принят!», и я начала искать этот алгоритм везде, где только можно, задавшись целью реализовать его. Не смотря на то, что распараллеливается он плохо и в своей сложности содержит немаленькую константу.
Однако всё, что удалось найти, — статьи на английском этого самого Тадао Такаоки (вот одна из этих статей). Пришлось переводить.
Сама идея алгоритма сначала казалась до безобразия простой:
«Вызов принят!», и я начала искать этот алгоритм везде, где только можно, задавшись целью реализовать его. Не смотря на то, что распараллеливается он плохо и в своей сложности содержит немаленькую константу.
Однако всё, что удалось найти, — статьи на английском этого самого Тадао Такаоки (вот одна из этих статей). Пришлось переводить.
Сама идея алгоритма сначала казалась до безобразия простой:
Искусственный интеллект → Иерархическая Темпоральная Память (НТМ) и алгоритмы ее самообучения
Привет всем Хабражителям, кто интересуется вопросами искусственного интеллекта! Всех с Прошедшими праздниками! Пора двигаться дальше.
В конце прошлого года я закончил перевод последней версии документа о «Hierarchical Temporal Memory» (HTM), который теперь можно найти рядом с оригиналом на сайте Numenta.com.
Что это такое и зачем оно все? Это последняя разработка весьма небезысвестного Джеффа Хокинса сотоварищи, моделирующая работу отдельных слоев коры головного мозга. Эта штуковина позволяет (еслине накосячить все сделать правильно) выделять из входного потока данных сходные события, их последовательности, проводить их распознавание и предсказание. Всех, кого интересуют подробности, милости прошу под хабракат.
В конце прошлого года я закончил перевод последней версии документа о «Hierarchical Temporal Memory» (HTM), который теперь можно найти рядом с оригиналом на сайте Numenta.com.
Что это такое и зачем оно все? Это последняя разработка весьма небезысвестного Джеффа Хокинса сотоварищи, моделирующая работу отдельных слоев коры головного мозга. Эта штуковина позволяет (если
Алгоритмы → Кучи. Часть 1. Биномиальная куча из песочницы
Здравствуйте, Хабросообщество!
На хабре есть описание множества интересных структур данных, таких как деревья отрезков, дуча и т.п. Если Вам интересны сложные структуры данных, то добро пожаловать под кат!
На хабре есть описание множества интересных структур данных, таких как деревья отрезков, дуча и т.п. Если Вам интересны сложные структуры данных, то добро пожаловать под кат!
Алгоритмы → Что такое искусственные нейронные сети?
Искусственные нейронные сети применяются в различных областях науки: начиная от систем распознавания речи до распознавания вторичной структуры белка, классификации различных видов рака и генной инженерии. Однако, как они работают и чем они хороши?
Программирование → Рейтинг на основании истории
Постановка задачи
Контекст: есть шахматный турнир с достаточно большим количеством игроков самого разного уровня.
Приняты решения: не разбивать игроков на чётко определённые группы (друг друга не знаем ещё, непонятно, кого куда помещать), не делать турнир «на вылет» (много новичков, им просто обидно будет вылететь после первой партии). Более-менее (вручную) справляемся с выбором партнёром примерно одинакового уровня.
Задача: сделать систему рейтинга по результатам турнира. Поскольку играем не «на вылет», финала нет. Учитывать количество очков несерьёзно из-за разношерстности игроков. То есть система рейтинга должна быть такой, что выигрыш у самого слабого игрока или проигрыш у самого сильного практически не должны влиять на наш рейтинг.
Алгоритмы → Алгоритм определения движения через сравнение двух кадров из песочницы
Здравствуйте, хабражители.
Хочу с вами поделиться своими наработками по обработке изображений. В последнее время занимаюсь написанием домашнего сервера под «умный дом» и начал с видеонаблюдения.
Задача оказалась не такой тривиальной. По поводу всего видеонаблюдения я напишу отдельно (если кому-то это интересно), а сейчас хотел бы затронуть тему «Алгоритм определения движения через сравнение двух кадров».
Этот алгоритм необходим для включения (выключения) записи видео с видеокамер.
Хочу с вами поделиться своими наработками по обработке изображений. В последнее время занимаюсь написанием домашнего сервера под «умный дом» и начал с видеонаблюдения.
Задача оказалась не такой тривиальной. По поводу всего видеонаблюдения я напишу отдельно (если кому-то это интересно), а сейчас хотел бы затронуть тему «Алгоритм определения движения через сравнение двух кадров».
Этот алгоритм необходим для включения (выключения) записи видео с видеокамер.
MySQL → Использование бинарного поиска для оптимизации запроса на выборку данных из песочницы
Введение
Сейчас очень популярна тем оптимизации работы с различными СУБД. На многочисленных форумах ведутся дискуссии о «самой лучшей СУБД в мире», но часто все это перетекает в необоснованные выкрики о том, что «я познал смысл жизни и понял, что самое лучшее хранилище данных — Х».
Да, несомненно, сейчас мы можем наблюдать активное развитие NoSQL решений, которые позволяют делать многое. Но данная статья не о них. Так вышло, что я сменил работу и в нагрузку мне достался один очень интересный проект на связке php+MySQL. В нем есть много хороших решений, но он писался без расчёта на большую аудиторию. За несколько лет существования количество активных пользователей начало приближаться к числам с 7 нулями. Так как проект представляет из себя подобие социальной сети с игровыми элементами, то таблица с пользователями оказалась не самой «тяжёлой» из всех. В наследство мне достались таблицы с десятками миллионов вещей пользователей, личных сообщений, биллинговыми записями и т. п. Проект начали рефакторить, разбивать на несколько серверов и достигли значительных результатов. Сейчас все стабильно.
Но недавно мне на почту прислали новую задачу. Суть заключалась в сборе статистики. Проанализировав требования я понял, что для выполнения достаточно написать один единственный запрос, выполняющий 3 INNER JOIN'а на таблицы, размеры которых впечатляли. Каждая таблица в среднем содержала 40 миллионов записей. Получается, что временная таблица состояла бы из 4*4*4*10^21 = 64*10^21 записей. Это колоссальная цифра. И загружать СУБД таким запросом для сбора статистики — непозволительная роскошь.
Далее, собственно, я и хочу представить решение данной абстрактной задачи, которое пришло мне в голову, когда я вспоминал занятия по информатике на первом курсе университета.