Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.

FDTD (Finite Difference Time Domain) — метод конечных разностей во временной области — самый «честный» метод решения задача электродинамики от низких частот до видимого диапазона. Суть — решение уравнений Максвелла «в лоб». Здесь неплохо расписано. Особенно посмотрите сетку.

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

Представлена реализация алгоритма на Java и C++.

Основная тема этой части – оптимизация работы с глобальной памятью при программировании GPU.

У GPU есть ряд особенностей, игнорирование которых может стоить многократной потери производительности при использовании глобальной памяти. Но если учесть все тонкости, то можно получить действительно эффективные CUDA-программы.

Приступаем.

Предисловие

​Все началось более 2-х лет тому назад, и я перешел на 4-й курс специальности "Бизнес-информатика" Томского Государственного Университета Систем Управления и Радиоэлектроники (ТУСУР). До окончания ВУЗА оставалась не много времени, и перспектива написания диплома уже маячила перед глазами. Мысль о покупке готовой работы не рассматривалась. Хотелось реально что-то сделать самому. Вариантов тем дипломных проектов рассматривалось много: и проекты конфигураций для автоматизации производственных нужд компании и проект внедрения Документооборота своими силами на 3 территориальные единицы и более 500 активных пользователей и внедрение ЭДО. Короче много всего что было в голове, но ничего из этого не вдохновляло. А это было главное.

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

Британская компания, две американские компании и 18 университетов (включая российские МИЭТ, ИТМО, СГАУ, ННТУ) сотрудничали, чтобы выпустить современный курс по микроконтроллерам c небольшой привязкой к интернету вещей. Об этом – сегодняшний пресс-релиз Imagination Technologies, Microchip Technology и Digilent (отделения National Instruments). Главный автор — профессор Александр Дин из университета Северной Каролины. В отличие от более легковестных курсов интернета вещей, новый курс подводит под предмет твердую инженерную базу – в нем подробно обсуждается использование RTOS-ов, архитектура микропроцессорного ядра микроконтроллера, протоколы периферии и даже оптимизация алгоритмов при программировании.



Скачать курс можно здесь:

https://community.imgtec.com/downloads/connected-microcontroller-lab-v1.2/

В пресс-релизе, помимо цитат из США, Великобритании, Германии, Китая, есть и цитата из России:

“MIET is part of Imagination’s MIPSfpga and Connected MCU Lab beta-testing programs. Our students have benefited from the MIPSfpga hands-on workshops and we are looking forward to implementing the Connected MCU Lab at our university because this course offers an up-to-date and well-structured curriculum for teaching embedded solutions to future engineers.”

– Alexey Pereverzev, Head of Computer Engineering, National Research University of Electronic Technology (MIET), Russia

Пару десятков слайдов из курса, чтобы вы почувствовали его вкус:

Введение

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

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

F_n= F_n-1+ F_n-2

и F₁= F₂=1.

Всем привет!

Ни для кого не секрет, что интерес к машинному обучению и искусственному интеллекту растет в лучшем случае по экспоненте. Тем временем мой Яндекс Диск превратился в огромную свалку пейперс, а закладки в Google Chrome превратились в список, длина которого стремится к бесконечности с каждым днем. Таким образом, дабы упростить жизнь себе и вам, решил структурировать информацию и дать множество ссылок на интересные ресурсы, которые изучал я и которые рекомендую изучать вам, если вы только вначале пути (буду пополнять список постоянно).

Путь для развития новичка я вижу примерно так:

Перевод поста Stephen Wolfram "I Wrote a Book—To Teach the Wolfram Language".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации

---

Книга «Элементарное введение в язык Wolfram Language» доступна для вас в печатной форме, бесплатно в Интернете, а также в других формах.



Я не был уверен, что когда-нибудь напишу еще одну книгу. Моя последняя книга — Новый вид науки — заняла у меня более десяти лет интенсивной сосредоточенной работы и является моим крупнейшим проектом из всех, что я когда-либо делал.

Но некоторое время назад я понял, что мне придется написать еще одну книгу — такую, которая бы познакомила людей, не знакомых с программированием, с языком Wolfram Language и способами мышления в вычислительной сфере, которые преподносит этот язык.

Результат — книга Элементарное введение в язык Wolfram Language, вышедшая сегодня в печать. Она также свободно доступна в Интернете, и в других формах.

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

Лекция рассчитана на старшеклассников – студентов Малого ШАДа, но и взрослые смогут почерпнуть из нее много полезного.



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

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

Начать стоит от печки, то есть с постановки задачи. Откуда берется сама задача word embedding?
Лирическое отступление: К сожалению, русскоязычное сообщество еще не выработало единого термина для этого понятия, поэтому мы будем использовать англоязычный.
Сам по себе embedding — это сопоставление произвольной сущности (например, узла в графе или кусочка картинки) некоторому вектору.

Когда мы слышим о сверточных нейронных сетях (CNN), мы обычно думаем о компьютерном зрении. CNN лежали в основе прорывов в классификации изображений — знаменитый AlexNet, победитель соревнования ImageNet в 2012 году, с которого начался бум интереса к этой теме. С тех пор сверточные сети достигли большого успеха в распознавании изображений, в силу того факта, что они устроены наподобие зрительной коры головного мозга — то есть умеют концентрироваться на небольшой области и выделять в ней важные особенности. Но, как оказалось, CNN хороши не только для этого, но и для задач обработки естественного языка (Natural Language Processing, NLP). Более того, в недавно вышедшей статье [1] от коллектива авторов из Intel и Carnegie-Mellon University, утверждается, что они подходят для этого даже лучше RNN, которые безраздельно властвовали областью на протяжении последних лет.

Сверточные нейронные сети

Для начала немного теории. Что такое свертка? Мы не будем на этом останавливаться подробно, так как про это написана уже тонна материалов, но все-таки кратко пробежаться стоит. Есть красивая визуализация от Стэнфорда, которая позволяет ухватить суть:


Источник

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

A. Маленькие числа
B. Новая клавиатура
C. Складывание фигуры
D. Остроугольные треугольники
E. Объединение массивов
F. Два поддерева

В раунде участвовали 603 человека: приблизительно по 200 лучших программистов с каждого квалификационного раунда. По результатам отборочного раунда мы взяли в финал 55 участников.

Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?

Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.

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

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

В общем, те кому не интересно — читают следующую новость, а остальных — прошу пройти

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

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

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

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

Введение

В научных вычислениях мы часто используем числа с плавающей запятой (плавающей точкой). Эта статья представляет собой руководство по выбору правильного представления числа с плавающей запятой. В большинстве языков программирования есть два встроенных вида точности: 32-битная (одинарная точность) и 64-битная (двойная точность). В семействе языков C они известны как float и double, и здесь мы будем использовать именно такие термины. Есть и другие виды точности: half, quad и т. д. Я не буду заострять на них внимание, хотя тоже много споров возникает относительно выбора half vs float или double vs quad. Так что сразу проясним: здесь идёт речь только о 32-битных и 64-битных числах IEEE 754.

Статья также написана для тех из вас, у кого много данных. Если вам требуется несколько чисел тут или там, просто используйте double и не забивайте себе голову!

Статья разбита на две отдельные (но связанные) дискуссии: что использовать для хранения ваших данных и что использовать при вычислениях. Иногда лучше хранить данные во float, а вычисления производить в double.

В результате размышлений над особенностями стандарта IEEE754, я пришел к выводу, что многие положения, на которых основывается данный стандарт, зиждутся на ошибочном методологическом подходе. А именно, авторы стандарта за основу рассуждений взяли заданный формат машинного слова. Затем, исходя из заданного формата, были сформулированы требования к множеству чисел, которые могут быть представимы в этом формате. Было высказано ряд бездоказательных суждений. Например, о предпочтении использования в компьютерной арифметике дробной мантиссы. Или об обязательной потере точности, при представлении чисел в ненормализованном виде, а также недопустимости неоднозначного представления действительных чисел в экспоненциальном виде.

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

Предлагаемая здесь работа является логическим продолжением предыдущих двух моих топиков на Хабре. В своих рассуждениях я оттолкнулся от естественного представления чисел и ограничений, которые накладываются на числа, вследствие конечности носителя, на который они записываются. Такой подход позволил получить ряд очень важных выводов. Основной из них заключается в том, что процесс нормализации не является обязательным на всех этапах проведения арифметических операций. Более того, именно обязательная нормализация привела к необходимости введения специального класса денормализованных чисел, что существенно увеличило программно-аппаратные затраты.

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

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

Среди всего разнообразия форматов представления действительных чисел в компьютерной технике особое место отведено формату чисел с плавающей точкой (ЧПТ), который запротоколирован в стандарте IEEE754. Главные достоинства чисел с плавающей точкой, как известно, заключаются в том, что они позволяют производить вычисления в большом диапазоне значений и при этом вычисления организуются инструментарием двоичной арифметики, легко реализуемой на вычислительном устройстве. Однако последнее обстоятельство таит в себе подводные камни, которые являются причиной того, что расчеты, сделанные с использованием этого формата, могут приводить к совершенно непредвиденным результатам.

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

В настоящей статье мы не приводим теоретических выкладок, которые объясняют причину появления этих ошибок. Это тема следующего топика. Здесь мы только постараемся привлечь внимание специалистов к проблеме катастрофической неточности вычислений, возникающей при проведении арифметических операций над десятичными числами при использовании двоичной арифметики. Рассматриваемые здесь примеры неумолимо наталкивают на мысль о целесообразности использования формата с плавающей точкой в том виде, как его трактует стандарт IEEE754.

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