Demain n'existe pas!

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

Специально ко Дню Защитника Отечества на препарационный стол легли LCD и E-Ink дисплеи, которые, так или иначе, достались мне в несколько побитом жизнью виде.

Как Антон кидал телефон об стену, а также о результатах скрупулёзного разбора дисплеев читайте под катом.

Доброго вам дня, коллеги. Предлагаю вам прочитать статью о базовом аспекте вычислительной геометрии — точном вычислении предикатов.

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

В этой статье я расскажу, как избавиться от недостатков вычислений с плавающей точкой практически без ущерба для эффективности. План статьи:

• геометрический предикат «поворот»;
• противоречивость «наивной» реализации поворота;
• применение интервальной арифметики для упрощения расчета предикатов;
• длинная арифметика и несколько альтернативных способов вычислений предикатов;
• расчет погрешности вычисления поворота в числах с плавающей точкой.

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

На просторах рунета можно найти достаточно много статей с введением в Verilog HDL. Все они описывают синтаксис и семантику языка, но, к сожалению, не раскрывают основных парадигм, используемых при проектировании цифровых схем. Представьте себе, что вам объясняют синтаксис языка Java, но не рассказывают ничего про объектно-ориентированное проектирование. Если вы знакомы с ООП, то такого введения будет достаточно, но если вы знаете только Си, то писать скорей всего будете “по-старому”, создавая огромные классы со сложными методами.

Примерно так происходит с программистами, изучающими цифровую схемотехнику и языки описания аппаратуры. Быстро разобравшись с несложным синтаксисом языка, они начинают описывать конструкции, безумные с точки зрения хардверного инженера. Среди моих студентов встречались люди, написавшие “сортировку пузырьком” за такт, сумасшедшие асинхронные схемы, которые работали по-разному при каждом запуске и разной погоде за окном, огромные комбинационные делители, уводившие place&route в глубокую многочасовую задумчивость.

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

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

Дабы облегчить дальнейшее скачивание лекций выкладываю некоторые из ник как торренты.

На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.

Дорогой Хабр!



У нас для тебя небольшой подарок. Мы тут работали-работали и вот чего сделали.
Сняли и опубликовали почти тысячу лекций по IT и математике.

UPD2 Помогите, пожалуйста, оперативно решить вопрос насчёт организации торрентов на php.

Не так давно прошёл конкурс параллельного программирования Acceler8 2011. Суть задачи заключалась в поиске максимальной подматрицы в данной матрице (сумма элементов найденной подматрицы должна быть максимальной). После недолгого «гугления» было найдено, что некий алгоритм Тадао Такаока решает эту задачу быстрее других.

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

Однако всё, что удалось найти, — статьи на английском этого самого Тадао Такаоки (вот одна из этих статей). Пришлось переводить.

Сама идея алгоритма сначала казалась до безобразия простой:

Введение

Кому не приходилось изготавливать печатную плату? Дело это не очень сложное, а результат придаёт проекту завершённость. В этом посте я бы хотел рассказать о процессе создания печатной платы на дому. Я опишу фоторезистивный метод создания платы. Он довольно прост в применении и позволяет печатать весьма сложные платы. Более того, я обошёлся струйным принтером.

Пост содержит фотографии, видео и схемы.

Введение

[1]
Фракталом (лат.«fractus» – дроблёный, сломанный, разбитый) называют сложную геометрическую фигуру, обладающую свойством самоподобия, т.е. составленной из нескольких частей, каждая из которых подобна целой фигуре. В более широком смысле под фракталами понимают множества точек в евклидовом пространстве, имеющие промежуточную (дробную) метрическую размерность (размерность Хаусдорфа).
Размерность Хаусдорфа – естественный способ определить размерность множества в метрическом пространстве. Размерность Хаусдорфа согласуется с нашими обычными представлениями о размерности в тех случаях, когда эти обычные представления есть. Например, в трёхмерном евклидовом пространстве хаусдорфова размерность конечного множества равна нулю, размерность гладкой кривой – единице, размерность гладкой поверхности – двум и размерность множества ненулевого объёма – трём.

При разработке некоего программно-аппаратного комплекса потребовалось создать клиентское устройство, которое для прочих устройств должно выглядеть как обычная USB-флешка, или если более формально, то USB Mass Storage Device. Необычность устройства в том, что оно должно имитировать для внешнего мира файловую систему FAT с файлами достаточно большого размера (2GB и и более), при том, что сами файлы на устройстве, конечно, отсутствуют и находятся в сети. Да и вообще это не файлы, а некие аудио-потоки.

Задача, на первый взгляд, простая: на каждый запрос на чтение блока (команду SCSI) отдаем содержимое этого блока. Блок может либо принадлежать какому-нибудь из «файлов», либо содержать служебную информацию FAT.

Я считаю, что каждый программист должен написать свой компилятор.

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

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

Введение

В предыдущей статье я рассказал о понятиях категории и функтора в контексте категории Hask, состоящей из типов данных и функций языка Haskell. Теперь я хочу рассказать о другом примере категории, построенном из уже известных нам понятий, а так же о весьма важном понятии моноида.

Обозначения

В прошлый раз я хотел обозначить морфизм/функцию буквой f, но она была занята для обозначения функтора/переменной типа f – никакой проблемы с точки зрения языка Haskell в этом нет, но при невнимательном прочтении это может вызвать путаницу, и я использовал для морфизма букву g. Пустяк, но всё же, я считаю, что полезно визуально разделять сущности, имеющие разную природу. Обычные типы я буду называть их обычными именами, а вот переменные типов я буду называть маленькими греческими буквами, причём простые (∗) – буквами из начала алфавита, а параметрические (∗ → ∗) – буквами из конца алфавита (θ не из конца, но она смотрится лучше, чем χ, которая слишком похожа на X). Итак, в терминологии категории Hask:

• Объекты: α, β, γ, δ ∷ ∗
• Функторы: θ, φ, ψ, ω ∷ ∗ → ∗
• Морфизмы: f, g, h ∷ α → β

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

Ещё одно замечание, касательно терминологии: как вы уже заметили, то, что я в прошлый раз называл словом “кайнд” (kind), я теперь называю словом “сорт” – это считается общепринятым переводом.

Категория с объектом Hask

Давайте рассмотрим категорию, в которой будет только один объект – сама категория Hask. Что же будет морфизмами в такой категории? Это должны быть какие-то отображения Hask → Hask, и мы уже знаем такой тип отображений – это эндофункторы категории Hask, то есть типы сорта ∗ → ∗, воплощения класса Functor. Теперь нужно продумать как устроены единичный морфизм и композиция в этой категории, так чтобы они удовлетворяли аксиомам.

Эта статья ориентирована на новичков в программировании ПЛИС на языке VHDL и тех, кто хочет научиться это делать. Ранее на хабре уже была рассмотрена статья с аналогичной задачей, реализованной на PIC-контроллере. А в этой статье речь пойдет об изменении яркости свечения светодиода с помощью ПЛИС.
Итак, цель работы: Освоить понятие ШИМ и применить его в изменении яркости светодиода. Для реализации воспользоваться языком программирования VHDL в среде разработки Xilinx ISE Project Navigator v12.3.

Вступление

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

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

Эта статья во многом повторяет (в том числе заимствует иллюстрации) раздел из английской Haskell Wikibook, но тем не менее не является непосредственным переводом.

Что такое категория?

Примеры

Для наглядности рассмотрим сначала пару картинок изображающих простые категории. На них есть красные кружочки и стрелки:

Красные кружочки изображают «объекты», а стрелки – «морфизмы».

Я хочу привести один наглядный пример из реальной жизни, который даст какое-то интуитивное представление о природе объектов и морфизмов:

Можно считать города «объектами», а перемещения между городами – «морфизмами». Например, можно представить себе карту авиарейсов (как-то не нашёл я удачную картинку) или карту железных дорог – они будут похожи на картинки выше, только сложнее. Следует обратить внимание на два момента, которые кажутся в реальности само собой разумеющимися, но для дальнейшего имеют важное значение:

• Бывает, что из одного города в другой никак не попасть поездом или самолётом – между этими городами нет морфизмов.
• Если мы перемещаемся в пределах одного и того же города, то это тоже морфизм – мы как бы путешествуем из города в него же.
• Если из Санкт-Петербурга есть поезд до Москвы, а из Москвы есть авиарейс в Амстердам, то мы можем купить билет на поезд и билет на самолёт, “скомбинировать” их и таким образом попасть из Санкт-Петербурга в Амстердам – то есть можно на нашей карте нарисовать стрелку от Санкт-Петербурга до Амстердама изображающую этот скомбинированный морфизм.

Надеюсь, с этим примером всё понятно. А теперь немного формализма для чёткости.

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика. Другие части:

• Часть 1. Необходимый минимум
• Часть 3. Прочие аспекты TH

Монада цитирования

Поскольку шаблоны должны возвращать свои значения обёрнутыми в монаду Q, для этого имеется набор вспомогательных функций, которые “поднимают” (оборачивают в Q) конструкторы типов Exp, Lit, Pat: lamE (соотв. LamE), varE, appE, varP и т.д. В их сигнатурах так же используются переобозначенные поднятые типы: ExpQ = Q Exp, LitQ = Q Lit, PatQ = Q Pat… (все их можно найти в модуле Language.Haskell.TH.Lib). Используя эти функции, можно значительно сократить код, реже используя do-синтаксис.
В TH также есть функция lift, которая поднимает до Q Exp значение любого типа из класса Lift.
В некоторых редких случаях, вам может понадобиться не генерация уникального имени, а использование точного имени идентификатора из внешнего (по отношению к шаблону) кода. Для этих целей есть (чистая) функция mkName ∷ String → Name. Есть также вспомогательная функция dyn s = return (VarE (mkName s)), которая возвращает значение Exp представляющее переменную с данным именем (dyn ∷ String → Q Exp).

Цитирующие скобки

Построение значений Exp, представляющих абстрактное синтаксическое дерево — трудоёмкая и скучная работа. Но к счастью, в Template Haskell есть цитирующие скобки, которые преобразуют конкретный Haskell-код в структуру, представляющую его.

Большинству разработчиков известно, что сборщик мусора в Java не является универсальным механизмом, позволяющим программисту полностью забыть о правилах использования памяти и о том, в каких случаях осуществляется его работа. Ниже описаны типичные случаи утечки памяти в java-приложениях, встречающиеся повсеместно.
Итак, о чём должен помнить каждый java-программист.

Сколько я себя помню, всегда мечтала сделать процессор. Наконец, вчера я его сделала. Не бог весть что: 8 бит, RISC, текущая рабочая частота — 4 кГц, но он работает. Пока что в программе моделирования логических цепей, но все мы знаем: «сегодня — на модели, завтра — на деле!».

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

Передаваемые по SSL-соединению данные можно расшифровать! Для этого Джулиану Риццо и Тай Дуонгу удалось использовать недоработки в самом протоколе SSL. И пусть речь пока не идет о полной дешифровке трафика, разработанная ими утилита BEAST может извлечь из зашифрованного потока то, что представляет собой наибольший интерес, — секретные кукисы с идентификатором сессии пользователя.

Одной из «визитных карточек» Хаскеля являются отложенные, или ленивые, вычисления. Эта особенность языка не только открывает множество возможностей, но и создаёт некоторые проблемы, особенно со скоростью работы программ.

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