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

Основная информация

Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.

Рейтинг: 0
Создана 5 лет назад
Владелец root

Стена группы

Загрузка...
Den
2 года назад
#

Марафонский раунд Яндекс.Алгоритма 2017



И вновь, как и в прошлые годы, приближается финал конкурса Яндекс.Алгоритм. В этом году мы ввели новый раунд — марафонский. Он представляет из себя одну оптимизационную задачу без точного решения, которую участникам предлагалось «покрутить» в течение 48 часов. Такой формат похож на решение практических задач больше, чем популярные соревнования по спортивному программированию.




Особенностью большинства практических задач является отсутствие точного решения — или же алгоритмы его нахождения оказываются слишком медленными. Команде и отдельному разработчику нужно сделать хороший прототип решения, который будет внедряться в окончательный алгоритм. Задачи подобного рода давно встречаются в соревнованиях TopCoder, ежегодных соревнованиях Marathon24, Deadline24, Google Hash Code и других. Конкурс длится больше стандартных алгоритмических раундов, так что участники могут в спокойной обстановке и в удобное для себя время реализовать придуманный метод.



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



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



Источник
2 года назад
#

Волшебное введение в алгоритмы классификации



Перевод статьи Брайна Беренда.

Когда вы впервые приступаете к изучению теории анализа и обработки данных, то одними из первых вы изучаете алгоритмы классификации. Их суть проста: берётся информация о конкретном результате наблюдений (data point), на основании которой этот результат относится к определённой группе или классу.

Хороший пример — спам-фильтр электронной почты. Он должен помечать входящие письма (то есть результаты наблюдений) как «спам» или «не спам», ориентируясь на информацию о письмах (отправитель, количество слов, начинающихся с прописных букв, и так далее).



Это пример хороший, но скучный. Спам-классификацию приводят в качестве примера на лекциях, презентациях и конференциях, так что вы наверняка уже не раз слышали о нём. Но что если поговорить о другом, более интересном алгоритме классификации? Каком-то более странном? Более… волшебном?

Всё верно! Сегодня мы поговорим о Распределяющей шляпе (Sorting Hat) из мира Гарри Поттера. Возьмём какие-то данные из сети, проанализируем и создадим классификатор, который будет сортировать персонажей по разным факультетам. Должно получиться забавно!

Источник
Den
2 года назад
#

Полезные функции Google Таблиц, которых нет в Excel



Cтатья написана в соавторстве с Ренатом Шагабутдиновым.

image

В этой статье речь пойдет о нескольких очень полезных функциях Google Таблиц, которых нет в Excel (SORT, объединение массивов, FILTER, IMPORTRANGE, IMAGE, GOOGLETRANSLATE, DETECTLANGUAGE)

Очень много букв, но есть разборы интересных кейсов, все примеры, кстати, можно рассмотреть поближе в Google Документе
goo.gl/cOQAd9 (файл-> создать копию, чтобы скопировать файл себе на Google Диск и иметь возможность редактирования).

Источник
2 года назад
#

Материалы студенческой школы «Recent Advances in Algorithms»



Recent Advances in Algorithms

В конце мая в Петербурге в ПОМИ РАН прошла международная студенческая школа
«Recent Advances in Algorithms». Идея школы заключалась в том, чтобы ведущие учёные рассказали о последних достижениях в области алгоритмов. В результате у нас получился следующий список курсов.

Список лекторов

Источник
2 года назад
#

Архитектура и алгоритмы индексации аудиозаписей ВКонтакте





Расскажем о том, как устроен поиск похожих треков среди всех аудиозаписей ВКонтакте.

Зачем всё это надо?

У нас действительно много музыки. Много — это больше 400 миллионов треков, которые весят примерно 4 ПБ. Если загрузить всю музыку из ВКонтакте на 64 ГБ айфоны, и положить их друг на друга, получится башня выше Эйфелевой. Каждый день в эту стопку нужно добавлять еще 25 айфонов — или 150 тысяч новых аудиозаписей объёмом 1.5 ТБ.

Конечно, далеко не все эти файлы уникальны. У каждого аудио есть данные об исполнителе и названии (опционально — текст и жанр), которые пользователь заполняет при загрузке песни на сайт. Премодерации нет. В результате мы получаем одинаковые песни под разными названиями, ремиксы, концертные и студийные записи одних и тех же композиций, и, конечно, совсем неверно названные треки.

Если научиться достаточно точно находить одинаковые (или очень похожие) аудиозаписи, можно применять это с пользой, например:

  • не дублировать в поиске один трек под разными названиями;

  • предлагать прослушать любимую композицию в более высоком качестве;

  • добавлять обложки и текст ко всем вариантам песни;

  • усовершенствовать механизм рекомендаций;

  • улучшить работу с жалобами владельцев контента.



Источник
2 года назад
#

Нечеткий поиск по названиям



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

Если есть время, и заказчик хочет чуть большего, то гуглят реализацию наиболее популярного алгоритма (коим является «расстояние Левенштейна») и вписывают его.

В данной статье, я опишу сильно доработанный алгоритм, основанный, правда, на расстояния Левенштейна, и приведу примеры кода на C# нечеткого поиска по названиям, например: кафе, ресторанов или неких сервисов… В общем всё, что можно перечислить и имеет от одного до нескольких слов в своем составе:

«Яндекс», «Mail», «ProjectArmata», «world of tanks», «world of warships», «world of warplanes» и т.д.

Источник
2 года назад
#

Об оптимизации комбинаторных алгоритмов



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

Источник
2 года назад
#

Красно-черные деревья: коротко и ясно



История из жизни. Девушка предложила своему парню-программисту пройти психологический тест:

Девушка: Нарисуй дерево.
Программист: (рисует бинарное дерево)
Девушка: Нет, другое.
Программист: Я и красно-черное дерево могу нарисовать.


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



Источник
2 года назад
#

Быстрое восстановление данных. Чем нам помогут LRC?





В современном мире наблюдается экспоненциальный рост объемов данных. Перед вендорами СХД возникает целый ряд задач, связанных с колоссальными объемами информации. Среди них — защита пользовательских данных от потери и максимально быстрое восстановление данных в случае выхода из строя сервера или диска.

Источник
Den
2 года назад
#

Генерируем произвольные последовательности на выводах платы Raspberry Pi





Автор: Николай Хабаров, Embedded Expert DataArt, евангелист технологий умного дома.

В этой статье я расскажу, как написать обычное user space-приложение на Python для современного ARM-процессора с ОС Linux для генерирования сложных последовательностей импульсов на выводах платы. Суть идеи — использовать DMA-модуль процессора для копирования из предварительно подготовленного буфера в памяти в GPIO с высокой точностью по времени.

Когда речь заходит о необходимости сгенерировать сложную последовательность импульсов, например, для шаговых двигателей, обычно используют старые добрые простенькие микроконтроллеры с установленной специальной операционной системой реального времени или вообще без операционной системы. Реализация при этом, в лучшем случае, написана на C++. Сейчас процессоры шагнули далеко вперед и имеют массу преимуществ: производительность, возможность использования операционной системы Linux со всей инфраструктурой и ПО, а также высокоуровневых языков программирования, таких как Python. И все же современные микроконтроллеры для генерирования сложных последовательностей на выводах GPIO, как правило, не используют.

Я реализовал генерацию импульсов для управления шаговыми двигателями
проекта PyCNC — проекта контроллера машин с ЧПУ, станков, 3D-принтеров, полностью написанного на Python и запускаемого на современном ARM-процессоре на плате Raspberry Pi.

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

Источник
2 года назад
#

Где на дороге деньги лежат (алгоритм, позволяющий в полтора раза сократить издержки в такси)



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


А Вы когда-нибудь задумывались, за что мы платим, пользуясь такси?


Без сомнения, основную часть составляет плата за время водителя и издержки на автомобиль, однако было бы довольно опрометчиво считать, что эта плата распространяется только на то время, пока Вы в пути. Кода таксисту приходится долго ждать очередного заказа, кто заплатит за его время и простой машины? — в конечном итоге мы с вами. Таксист по праву не согласится на вознаграждение за день ниже его стоимости на трудовом рынке, выполняй он при этом в среднем пять заказов или двадцать пять. Мне стало интересно, каково время не выгодного никому простоя и как его можно уменьшить. Ниже я хотел бы поделиться с вами результатами собственного исследования этого вопроса.


Источник
2 года назад
#

Итоги первого раунда Russian Code Cup 2017


image
The Sword of Midnight by Mischeviouslittleelf


Второго апреля прошёл первый квалификационный раунд Russian Code Cup 2017, на котором были побиты рекорды посещаемости за последние три года. Предлагаем вам немного цифр и разбор задач раунда:


A. Марсианский волейбол
B. Раскраска стены
C. Магический артефакт
D. Менеджер памяти
E. ЛИСА


На раунд зарегистрировалось 4552 участника, из них 1001 — новички, открывшие для себя RCC лишь в этом году. Активных участников в этот раз оказалось в два раза больше, чем в 2015 и 2016 годах! Всего нам прислали 6586 решений. Как обычно, популярнее всего — C++ в разных вариациях (2346 решений — C++ 14, 1425 на плюсах 11-й версии и примерно по 500 решений у GNU C++ 6.2 и Visual C++ 2013). Второе место по популярности у Java 8.0 (649), а третье — у Python (402 на Python 3.5 + 60 решений на PyPy 2.4.0). Самыми непопулярными для спортивного программирования оказались Perl, D и Haskell (на последнем написали ровно одно решение за весь раунд). Список всех поддерживаемых нами языков можно найти здесь.


Источник
2 года назад
#
Лекции Техносферы. Подготовительный курс «Алгоритмы и структуры данных» (весна 2016)

Лекции техносферы

Цель этого курса — познакомить слушателей с основными алгоритмами, применяемыми для разработки программного обеспечения. Вы научитесь выбирать подходящие структуры данных и алгоритмы для реализации возникающих задач, и узнаете, как использовать языки С/С++ для реализации алгоритмов.

Курс ведет Сергей Бабичев, доцент кафедр информатики и вычислительной математики, а также теоретической и прикладной информатики в МФТИ. Под катом вас ждет восемь лекций:

  • Лекция 1. «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»

  • Лекция 2. «Жадные алгоритмы»

  • Лекция 3. «Сортировки»

  • Лекция 4. «Поиск. Списки»

  • Лекция 5. «Деревья»

  • Лекция 6. «Хеш-таблицы»

  • Лекция 7. «Динамическое программирование»

  • Лекция 8. «Алгоритмы на графах»


Лекция 1. «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»



Подробнее
3 года назад
#
Время учиться: дайджест бесплатных образовательных материалов от Mail.Ru Group

Операция Ы

Как говорят, «кризис — пора возможностей». И поэтому сейчас самое время начать вкладывать в саморазвитие, осваивать новую профессию или повышать свою квалификацию. Займитесь изучением языков программирования, обретением навыков разработки, тестирования и вообще всячески прокачивайте свой IT-скилл. Ведь чем больше вы знаете, тем прочнее будете стоять на ногах. А чтобы вам было легче сориентироваться и выбрать направление, мы сделали подборку наших бесплатных образовательных материалов, курсов и инициатив за 2015–2016 годы.

Подробнее
4 года назад
#
Гибридная реализация алгоритма MST с использованием CPU и GPU

Введение

Решение задачи поиска минимальных остовных деревьев ( MST — minimum spanning tree) является распространенной задачей в различных областях исследований: распознавание различных объектов, компьютерное зрение, анализ и построение сетей (например, телефонных, электрических, компьютерных, дорожных и т.д.), химия и биология и многие другие. Существует по крайней мере три известных алгоритма, решающих данную задачу: Борувки, Крускала и Прима. Обработка больших графов (занимающих несколько ГБ) является достаточно трудоемкой задачей для центрального процессора (CPU) и является востребованной в данное время. Все более широкое распространение получают графические ускорители (GPU), способные показывать намного большую производительность, чем CPU. Но задача MST, как и многие задачи по обработке графов, плохо ложатся на архитектуру GPU. В данной статье будет рассмотрена реализация данного алгоритма на GPU. Также будет показано, как можно использовать CPU для построения гибридной реализации данного алгоритма на общей памяти одного узла (состоящего из GPU и нескольких CPU).

Описание формата представления графов

Кратко рассмотрим структуру хранения неориентированного взвешенного графа, так как в дальнейшем она будет упоминаться и преобразовываться. Граф задается в сжатом CSR (Compressed Sparse Row) [1] формате. Данный формат широко распространен для хранения разреженных матриц и графов. Для графа с N вершинами и M ребрами необходимо три массива: X, A и W. Массив X размера N + 1, остальные два – 2*M, так как в неориентированном графе для любой пары вершин необходимо хранить прямую и обратную дуги. В массиве X хранится начало и конец списка соседей, которые хранятся в массиве А, то есть весь список соседей вершины J находится в массиве A с индекса X[J] до X[J+1], не включая его. По аналогичным индексам хранятся веса каждого ребра из вершины J. Для иллюстрации на рисунке ниже слева показан граф из 6 вершин, записанный с помощью матрицы смежности, а справа – в CSR формате (для упрощения, вес каждого ребра не указан).

Алгоритм MST

Тестируемые графы

Сразу опишу на каких графах происходило тестирование, так как для описания алгоритмов преобразования и алгоритма MST потребуется знание структуры рассматриваемых графов. Для оценки производительности реализации используются два вида синтетических графов: RMAT-графы и SSCA2-графы. R-MAT-графы хорошо моделируют реальные графы из социальных сетей, Интернета [2]. В данном случае рассматриваются RMAT-графы со средней степенью связности вершины 32, а количество вершин является степенью двойки. В таком RMAT-графе имеется одна большая связная компонента и некоторое количество небольших связных компонент или висящих вершин. SSCA2-граф представляет собой большой набор независимых компонент, соединенных ребрами друг с другом [3]. SSCA2-граф генерируется таким образом, чтобы средняя степень связности вершины была близка к 32, а eё количество вершин также является степенью двойки. Таким образом, рассматриваются два совершенно разных по структуре графа.

Подробнее
10 11 13

Авторизация

Войдите, используя Ваш аккаунт

Войти с помощью

Пользователи

КАРКАМ

Нетология