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

Небольшой спойлер: в начале это казалось мне какой-то магией, но потом я понял подвох…

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

Вообще говоря, есть другие модели — Недетерминированная машина Тьюринга, Квантовые машины Тьюринга. Однако они (пока) являются только абстрактными моделями, не реализуемые на практике.

Полгода назад в Science Advances вышла интересная статья с моделью вычислений, которая существенно отличается от МТ и которую вполне возможно реализовать на практике (собственно статья и была о том, как они посчитали задачу SSP на реальном железе).

И да. Самое интересное в этой модели то, что, по заверению авторов, в ней можно решать (некоторые) задачи из класса NP полных задач за полином времени и памяти.

Мы снова в эфире и продолжаем цикл заметок Дата Сайентиста и сегодня представляю мой абсолютно субъективный чек-лист по выбору модели машинного обучения.

Это топ-10 свойств задачи и просто пунктов (без порядка в них), с точки зрения которых я начинаю выбор модели и вообще моделирование задачи по анализу данных.

Совсем не обязательно, что у вас он будет таким же — здесь все субъективно, но делюсь опытом из жизни.

Решил выложить код вычисления определителей. Код рабочий, хотя и не претендует на виртуозность. Просто было интересно решить эту задачу именно на Хаскелле. Рассмотрены два подхода к решению задачи: простая рекурсия и метод Гаусса.

Немного теории

Как известно, определитель квадратной матрицы n*n — это сумма n! слагаемых, каждое из которых есть произведение, содержащее ровно по одному элементу матрицы из каждого столбца и ровно по одному из каждой строки. Знак очередного произведения:

$$

определяется чётностью подстановки:

$$

Как известно, кривыми Безье нельзя построить дугу окружности или эллипса. В этой статье рассматриваются кривые, лишённые такого недостатка.

Перед вами доклад Марии Зеленовой zelma — разработчика в Едадиле. За час Маша рассказала, в чём состоит тестирование программ, какие тесты бывают, зачем их писать. На простых примерах можно узнать про библиотеки для тестирования Python-кода (unittest, pytest, mock), принципы их работы и отличия между ними.


— Добрый вечер, меня зовут Маша, я работаю в отделе подготовки анализа данных Едадила, и сегодня у нас с вами лекция про тестирование.

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

Именно так ошибку 2000 года восприняло общественное сознание. К примеру, британский политик-брекзитёр заявил, что опасения о влиянии роли Брекзита на экономику похожи на панику бага Y2K.

Об ошибке тысячелетия забыли почти сразу после наступления 2000 года. Даже в непрофильных изданиях месяцами обсуждали баг Y2K, но уже в первые дни нового года внимание к теме угасло. Завораживающая смена числа с 1999 на 2000 не создала катастроф, которыми так пугали. Скептики объявили, что деньги на устранение бага потратили впустую.

Происходящее за кулисами важнее представлений неспециалистов. Градус общественной паники действительно ушёл выше уровня, которого заслуживала ситуация. Реальная опасность компьютерных сбоев по всему миру 1 января 2000 года существовала и требовала вмешательства разработчиков ПО. Целые отделы программистов годами устраняли проблему Y2K.

В далекие времена, для IT-индустрии это 70-е годы прошлого века, ученые-математики (так раньше назывались программисты) сражались как Дон-Кихоты в неравном бою с компьютерами, которые тогда были размером с маленькие ветряные мельницы. Задачи ставились серьезные: поиск вражеских подлодок в океане по снимкам с орбиты, расчет баллистики ракет дальнего действия, и прочее. Для их решения компьютер должен оперировать действительными числами, которых, как известно, континуум, тогда как память конечна. Поэтому приходится отображать этот континуум на конечное множество нулей и единиц. В поисках компромисса между скоростью, размером и точностью представления ученые предложили числа с плавающей запятой (или плавающей точкой, если по-буржуйски).

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

Python и теория множеств

В Python есть очень полезный тип данных для работы с множествами – это set. Об этом типе данных, примерах использования, и небольшой выдержке из теории множеств пойдёт речь далее.

«Бегущий по лезвию», «Воздушная тюрьма», «Heavy Rain» — что общего между этими представителями массовой культуры? Во всех в той или иной степени присутствует древнее японское искусство по складыванию бумаги — оригами. В кино, играх и в реальной жизни оригами частенько используется в качестве символа определенных чувств, каких-то воспоминаний или своеобразного послания. Это скорее эмоциональная составляющая оригами, но с точки зрения науки в бумажных фигурках сокрыто множество интересных аспектов из самых разных направлений: геометрия, математика и даже механика. Сегодня мы с вами познакомимся с исследованием, в котором ученые из Американского института физики создали устройство хранения данных за счет складывания/раскладывания фигурок оригами. Как именно работает бумажная карта памяти, какие принципы в ней реализованы и сколько данных может хранить такое устройство? Ответы на эти вопросы мы найдем в докладе ученых. Поехали.

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

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

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

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

Ну, приступим.

Это статья была написана для людей, которым всегда интересно знать как работают разные вещи. Для тех разработчиков которые обычно пишут свои программы на высоком уровне, C, C++ или Java — не важно, но при этом столкнулись с необходимостью сделать что-то на низком уровне. Мы будем рассматривать низкоуровневое программирование на примере работы bootloader-а.

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

Что такое шум Перлина?

Шум Перлина придуман в 1983 году Кеном Перлином (получившим за это достижение премию Американской Академии кинематографических искусств и наук). Видите ли, в те времена все стремились к фотореализму, но его всегда не хватало. Кен Перлин придуман этот алгоритм шума, чтобы избавиться от жалкого «компьютерного» внешнего вида 3D-моделей. Шум — это генератор случайных чисел в компьютерной графике. Это случайный неструктурированный паттерн, он полезен в тех случаях, когда требуется источник подробных деталей, недостающих в очевидной структуре¹. Шум Перлина — это многомерный алгоритм, используемый в процедурной генерации, текстурах, генерации рельефа, генерации карт, генерации поверхностей, генерации вершин, и так далее, и тому подобное.

Псевдотонирование: обзор

Про сегодняшнюю тему для программирования графики — псевдотонирование (дизеринг, псевдосмешение цветов) — я получаю много писем, что может показаться удивительным. Вы можете подумать, что псевдотонирование — это не то, чем программисты должны заниматься в 2012 году. Разве псевдосмешение — не артефакт история технологий, архаизм времён, когда дисплей с 16 миллионами цветов программистам и пользователям мог только сниться? Почему я пишу статью о псевдотонировании в эпоху, когда дешевые мобильные телефоны работают с великолепием 32-битной графики?

На самом деле псевдотонирование по-прежнему остаётся уникальным методом не только по практическим соображениям (например, подготовка полноцветного изображения для печати на чёрно-белом принтере), но и по художественным. Дизеринг также находит применение в веб-дизайне, где этот полезный метод используется для сокращения числа цветов изображения, что уменьшает размер файла (и трафик) без ущерба для качества. Он также используется при уменьшении цифровых фотографий в формате RAW в 48 или 64 бита на пиксель до RGB в 24 бита на пиксель для редактирования.

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

Квантизация — уменьшение цветов изображения (wiki). Конечно, сейчас мало кому это необходимо, но задача сама по себе интересная.


Квантизированная Лена привлекает внимание

Например, старый добрый формат GIF использует палитру, максимум на 256 цветов. Если вы захотите сохранить серию своих селфи как gif-анимацию (кому бы это надо было), то первое, что вам, а точнее программе, которую вы будете для этого использовать, надо будет сделать – создать палитру. Можно использовать статическую палитру, например web-safe colors, алгоритм квантизации получиться очень простым и быстрым, но результат будет «не очень». Можно создать оптимальную палитру на основе цветов изображения, что даст результат наиболее визуально похожий на оригинал.

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

Далее вас ждёт скучное и непонятное повествование о методе медианного сечения, алгоритму рассеивания ошибок (шума квантизации) по Флойду-Стейнбергу (и не только), особенностях цветового восприятия человеческого глаза, а так же немного говнокода.

В этой статье Вы узнаете всё о Вавилонской библиотеке, а самое главное — как воссоздать её, да и вообще любую библиотеку.

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

Каждый решает проблему обучения по-своему. Кто-то читает много литературы, кто-то старается поскорее перейти к практике и разбираться по ходу дела, кто-то пытается объяснять друзьям всё, что сам изучает. А мы решили совместить эти подходы. Итак, в этом курсе статей мы будем шаг за шагом демонстрировать, как пишется простая операционная система. Статьи будут носить обзорный характер, то есть в них не будет исчерпывающих теоретических сведений, однако мы будем всегда стараться предоставить ссылки на хорошие теоретические материалы и ответить на все возникающие вопросы. Чёткого плана у нас нет, так что многие важные решения будут приниматься по ходу дела, с учётом ваших отзывов.

Всем привет! Сегодня мы напишем загрузчик, который будет выводить «Hello World» и запустим его на VirtualBox. Писать будем на ассемблере FASM. Скачать его можно отсюда. Также нам понадобится собственно VirtualBox и UltraISO. Перед тем как писать код, разберемся как загружаются операционные системы.

Итак, когда мы нажимаем большую кнопку включения на нашем компьютере запускается система, которая есть на любом компьютере — BIOS (Basic Input/Output System или базовая система ввода/вывода). Задача BIOS это:

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.