• Памяти Соломона Голомба (1932-2016): автора регистра сдвига с линейной обратной связью максимальной длины и полиомино

    • Перевод

    Перевод поста Стивена Вольфрама (Stephen Wolfram) "Solomon Golomb (1932–2016)".
    Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации




    Содержание


    Наиболее часто используемый математический алгоритм в истории
    Как я встретил Сола Голомба
    История Соломона Голомба
    Регистры сдвига
    Предыстория регистров сдвига
    Для чего нужны последовательности, генерируемые регистрами сдвига?
    Ну и где же эти регистры?
    Клеточные автоматы и регистры сдвига с нелинейной обратной связью
    Полиомино
    Остальная часть истории



    Наиболее часто используемый математический алгоритм в истории


    Октиллион. Миллиард миллиардов миллиардов. Это очень приблизительная оценка того, сколько раз мобильный телефон или другое устройство сгенерировало бит с помощью регистра сдвига с линейной обратной связью максимальной длины. Думаю, это самый используемый математический алгоритм в истории. Автор — Соломон Голомб, скончавшийся 1 мая, с которым мы были знакомы больше 35 лет.

    Основой книги Соломона Голомба «Последовательности регистрового сдвига», опубликованной в 1967 году, были его работы 1950-х гг. А ее содержание живет в каждой из современных систем связи. Прочтите спецификации для 3G, LTE, Wi-Fi, Bluetooth или даже для GPS, — и вы найдете упоминания о многочленах, определяющих последовательности, генерируемые регистрами сдвига, которые эти системы используют для кодирования отправляемых ими данных. Соломон Голомб — человек, который создал эти многочлены.
    Читать дальше о Соломоне Голомбе...
  • Функциональные языки в разработке аппаратуры

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

      Примеры проектов
      генерация безопасного кода на C (используется в лаборатории Касперского) Ivory, поддержка реактивного программирования на Arduino, и так далее Atom, Ion

      Но если спуститься еще ниже, на уровень аппаратуры, то неожиданно ФП оказывается очень кстати. Ведь блок комбитаторной логики не что иное, как функция из величин входящих сигналов в величины исходящих, а для последовательной логики достаточно добавить в параметры и результат старое и новое состояние.
      так как же это работает
    • Как мы придумали и сделали свою первую игру на Android. Часть 2: Уровни

        Привет, Мир! Мы два новоиспеченных разработчика мобильных игр, бывшие одноклассники, выпускники Казанского федерального университета, Айдар и Эд, продолжаем рассказ о разработке нашей первой игры «Syncomania» на Android.

        Для тех, кто только что присоединился, вкратце напомним содержание первой части:

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

        В этой статье мы расскажем о работе над уровнями игры и о некоторых принципах, которых мы придерживались. Возможно, они будут полезны и вам.
        Читать дальше →
      • Социальная Архитектура: стратагемы для успеха open source проектов

        • Перевод
        Питер Хинченс (Pieter Hintjens) — бельгийский разработчик, писатель. Занимал должность CEO и chief software designer для iMatix, компании, производящей free software, такие как библиотека ZeroMQ (библиотека берет на себя часть забот по буферизации данных, обслуживанию очередей, установлению и восстановлению соединений, и прочие вещи), OpenAMQ, Libero, GSL code generator, и веб-сервиса Xitami.

        • Автор более 30 протоколов и распределённых систем.
        • Основатель проекта Edgenet по созданию полностью безопасной, анонимной глобальной P2P-сети.
        • Президент ассоциации Foundation for a Free Information Infrastructure (FFII), которая воевала с патентным правом.
        • CEO сервиса по созданию собственных вики-проектов Wikidot.
        • Он был активистом open standards, и основателем Digital Standards Organization.
        • Питер в 2007 был назван одним из «50 самых влиятельных людей в области Интеллектуальная собственность».


        Когда Питер Хинченс узнал, что жить ему осталось несколько лет, он решил подвести итог своим трудам и систематизировать свое наследие. 3 октября 2016 Питер Хинченс решился на эвтаназию.

        Один из его предсмертных трудов — книга «Социальная Архитектура», про построение онлайн-сообществ по разработке open source проектов. Хочу представить вам переводы некоторых глав.

        Шаблоны для успеха


        Это глава с серией шаблонов поведения для достижения успеха в разработке программного обеспечения. Они стремятся включить всё, что отделяет успех от славной трагической неудачи. Они были написаны за один день как “религиозно-маниакальные догматы” руководителем и “всё остальное безумное” — коллегой. Для меня они являются наукой. Но относитесь к Ленивым перфекционистам и другим инструментам так, как вы относитесь к обычным инструментам — заточите их, используйте и выбросите, если подвернется что-то получше.

        Читать дальше →
        • +21
        • 10k
        • 4
      • Зачем нам всем нужен SAT и все эти P-NP (часть первая)

          SAT уже тем хорош, что он ум в порядок приводит
          Ломоносов (оригинал)

          Введение


          На хабре уже немало статей, посвященных проблеме P vs. NP и задаче о выполнимости логических формул (SATisfiability problem). Однако, большинство из них не отвечает на несколько самых важных вопросов. Почему эта проблема действительна важна для нас? Что будет, если её решат? Где это все вообще применяется? И почему необходимо иметь хотя бы общее представление, о чем там идет речь?

          image

          Если мы детально проанализируем наиболее заметные работы на хабре по данной теме [1, 2, 3, 4, 5, 6, 7], то заметим, что с одной стороны, люди обладающие знаниями в области вычислительной сложности не cмогут почерпнуть ничего принципиально нового в данных статьях. С другой стороны, данные статьи по-прежнему не являются общедоступными. Иллюстрация из заголовка наглядно демонстрирует проблему: тем, кому было не понятно, из неё ничего не ясно, а те, кто об этом уже слышал, в ней не нуждаются.

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

          Читать дальше →
        • Как посчитать перестановки. Лекция в Яндексе

            Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.



            Под катом — подробная текстовая расшифровка и большинство слайдов.
            Читать дальше →
          • Обзор языка Idris

            Agda is too mainstream!

            «Предвидение»

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

            Итак, Idris — чистый функциональный язык программирования общего назначения с зависимыми типами.
            Читать дальше →
            • +29
            • 17,4k
            • 7
          • Hello, TensorFlow. Библиотека машинного обучения от Google

            • Перевод
            • Tutorial

            tensorflow


            Проект TensorFlow масштабнее, чем вам может показаться. Тот факт, что это библиотека для глубинного обучения, и его связь с Гуглом помогли проекту TensorFlow привлечь много внимания. Но если забыть про ажиотаж, некоторые его уникальные детали заслуживают более глубокого изучения:


            • Основная библиотека подходит для широкого семейства техник машинного обучения, а не только для глубинного обучения.
            • Линейная алгебра и другие внутренности хорошо видны снаружи.
            • В дополнение к основной функциональности машинного обучения, TensorFlow также включает собственную систему логирования, собственный интерактивный визуализатор логов и даже мощную архитектуру по доставке данных.
            • Модель исполнения TensorFlow отличается от scikit-learn языка Python и от большинства инструментов в R.

            Все это круто, но TensorFlow может быть довольно сложным в понимании, особенно для того, кто только знакомится с машинным обучением.


            Как работает TensorFlow? Давайте попробуем разобраться, посмотреть и понять, как работает каждая часть. Мы изучим граф движения данных, который определяет вычисления, через которые предстоит пройти вашим данным, поймем, как тренировать модели градиентным спуском с помощью TensorFlow, и как TensorBoard визуализирует работу с TensorFlow. Наши примеры не помогут решать настоящие проблемы машинного обучения промышленного уровня, но они помогут понять компоненты, которые лежат в основе всего, что создано на TensorFlow, в том числе того, что вы напишите в будущем!

            Читать дальше →
          • Tarantool: как сэкономить миллион долларов на базе данных на высоконагруженном проекте

              Аникин Денис (@danikin, Mail.Ru)


              Денис Аникин

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

              Базы данных – это хранилище, более структурированное, чем файл, и обладающее рядом некоторых фич, которых у файла нет.



              Там можно делать запросы, там есть транзакции, индексирование, таблицы, устойчивые, более-менее надежные хранилища. На самом деле, базы данных – это более удобно, чем файлы.
              Читать дальше →
            • Симулятор нервной системы. Часть 1. Простой сумматор



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

                Частично система воплощена в простенькой программе, созданной на игровом движке Unity3D. Это своего рода симулятор нервной системы, благодаря которому возможно имитировать не только простые рефлексы, но и демонстрировать различные явления в нервной системе, такие как привыкание, сенсибилизация и образование условных рефлексов. А также возможно эмулировать временную и долговременную память и её консолидацию, эмоции и эмоциональное поведение. Причем как простые эмоции, к примеру, голод и насыщение, так и более сложные, такие как любопытство, страх или привязанность. Благодаря системе у нас появится возможность разобраться в предназначении различных областей мозга, в том, как происходит распознавание зрительных образов, как происходит обучение и эмоциональная оценка происходящего.
                Читать дальше →
              • Dagaz: В дебрях нотаций

                  imageПлюнь тому в глаза, кто скажет, что можно обнять необъятное!

                  Усердие всё превозмогает!
                   
                                            Козьма Прутков "Мысли и афоризмы


                  Люди постоянно что-то придумывают. После изобретения шахмат, было разработано ещё несколько тысяч похожих игр. Первоначально, по давней привычке, оставшейся ещё со времён сочинения античных мифов, создавались химеры, сочетавшие в себе качества двух и более шахматных фигур, но впоследствии фантазия авторов окрепла и стала выдавать более интересные варианты. Чтобы не запутаться во всём этом зоопарке, требовалась какая-то система, возможность классификации новых фигур. И она возникла. Собственно, я знаю их две. К сожалению, обе они не работают.
                  Читать дальше →
                  • +15
                  • 3,6k
                  • 4
                • Логика сознания. Часть 2. Дендритные волны

                    В предыдущей части мы показали, что в клеточном автомате могут возникать волны, имеющие специфический внутренний узор. Такие волны могут запускаться из любого места клеточного автомата и распространяться по всему пространству клеток автомата, перенося информацию. Соблазнительно предположить, что реальный мозг может использовать схожие принципы. Чтобы понять возможность аналогии, немного разберемся с тем, как работают нейроны реального мозга.
                    Читать дальше →
                  • Kefir.js — новая библиотека для функционального реактивного программирования (FRP) в JavaScript

                      Наверняка многие уже слышали о подходе FRP для организации асинхронного кода. На хабре уже писали об FRP (Реактивное программирование в Haskell, FRP на Bacon.js) и есть хорошие доклады на эту тему (Программировние UI с помощью FRP и Bacon.js, Functional Reactive Programming & ClojureScript, О Bacon.js от Juha Paananen — автора бекона)

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

                      Вот что это дает по сравнению с обратными вызовами:

                      1) Поток событий (Event stream) и значение меняющаяся во времени (Property / Behavior) становятся объектами первого класса. Это значит что их можно передавать в функции и возвращать из функций.

                      Например, можно создать объект содержащий клики на кнопку (поток событий), и дальше делать с ним всё, что можно делать с обычной переменной — передавать в функцию, возвращать из функции, сохранять как свойство другого обекта и т.д. Или можно создать объект отражающий текущий размер окна браузера (значение меняющаяся во времени).

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

                      К примеру можно написать функцию, возвращающую поток перетаскиваний (drag). В качестве параметров она будет принимать 3 потока — начало перетаскивания, движение, конец перетаскивания. Дальше можно передать в эту функцию: либо потоки для соответствующих событий мыши (mousedown, mousemove, mouseup), либо для touch событий (touchstart, touchmove, touchend). Сама же функция не будет ничего знать об источниках событий, а будет работать только с абстрактными потоками. Пример реализации на Bacon.

                      2) Явный state

                      Второе большое преимущество FRP это явное управление состоянием. Как известно, state — один из самых главных источников сложности программ, поэтому грамотное управление им позволяет писать более надежные и простые в поддержке программы. Отличный доклад от Рича Хикки о сложности (complexity) «Simple Made Easy».

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

                      Читать дальше →
                    • Логика сознания. Часть 1. Волны в клеточном автомате

                        Начнем разговор о мозге с несколько отвлеченной темы. Поговорим о клеточных автоматах. Клеточный автомат – это дискретная модель, которая описывает регулярную решетку ячеек, возможные состояния ячеек и правила изменений этих состояний. Каждая из ячеек может принимать конечное множество состояний, например, 0 и 1. Для каждой из ячеек определяется окрестность, задающая ее соседей. Состояние соседей и собственное состояние ячейки определяют ее следующее состояние.
                        Наиболее известный клеточный автомат – это игра «Жизнь». Поле в игре «Жизнь» состоит из ячеек. Каждая ячейка имеет восемь соседей. Задается начальная комбинация. Затем начинается смена поколений. Если у занятой ячейки два или три занятых (живых) соседа, то ячейка продолжает жить. Если соседей меньше 2 или больше 3, то ячейка умирает. Когда у пустой ячейки оказывается ровно 3 соседа в ней зарождается жизнь. Задав произвольную начальную комбинацию можно пронаблюдать ее эволюцию.
                        Читать дальше →
                      • Оптимизация Windows для использования SSD диска: мифы и реальность



                          Когда весь интернет пестрит холиварами на тему «SSD ненадежны» и «SSD настолько быстрые, что я больше никогда не буду работать с HDD», думаю самое время внести немного ясности в то море противоречевой информации о самих SSD и о настройке Windows для работы с ними.

                          Кто заинтересовался, прошу под кат.

                          Читать дальше →
                        • Почему, ну почему, эти #?@! придурки используют vi?

                          Предлагаю читателям "Хабрахабра" перевод статьи "Why, oh WHY, do those #?@! nutheads use vi?" за авторством John Beltran de Heredia.


                          Да, даже если вы не можете в это поверить, у редактора vi, увидевшего свет более тридцати лет назад (и его более молодого, всего-то пятнадцатилетнего лучшего клона & большого улучшения — vim) очень много фанатов.


                          Нет, они не динозавры, которые не хотят идти в ногу со временем — сообщество пользователей vi продолжает увеличиваться: я, который начал только два года назад (после десяти лет работы программистом). Мои друзья переходят на vi сейчас. Черт, большинство пользователей vi даже еще не были рождены, когда он был написан!


                          Да, есть конкретные причины, почему модель редактирования vi/vim превосходит любую другую. Вам не надо быть экспертом в Unix, чтобы использовать vi — он доступен бесплатно практически для любой существующей платформы; для большинства IDE существуют плагины, позволяющие использовать его возможности. Давайте же развеем некоторые заблуждения и рассмотрим пару примеров, демонстрирующих его превосходство.

                          Читать дальше →
                        • Байесовский анализ в Python

                          • Tutorial
                          Этот пост является логическим продолжением моего первого поста о Байесовских методах, который можно найти тут.
                          Я бы хотел подробно рассказать о том, как проводить анализ на практике.
                          Читать дальше →
                        • Введение в Байесовские методы

                          В качестве введения


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

                          • Перевод
                          В VoxImplant мы используем React.js и TypeScript для всех новых фронтенд-проектов. Но стараемся не зацикливаться на выбранных инструментах и внимательно смотрим по сторонам – не летит ли орел, не ползет ли змея, не случилось ли что интересное у других фреймворков. Недавно нам попалась статья, автор которой подробно и вдумчиво сравнивает React с Ember. И, да, у него большой опыт работы и с первым, и со вторым (а не как это обычно бывает). Предлагаем вашему вниманию адаптированный, и, надеемся, легко читаемый, перевод.
                          Читать дальше →
                        • Порталы в React.js

                          • Tutorial

                          image


                          Наверное, каждому фронтенд-разработчику доводилось делать разного рода выпадайки или всплывающие подсказки. И почти всегда настает момент, когда такую штуку надо отобразить внутри элемента с overflow: hidden. Настал такой момент и в SmartProgress.


                          Мы на SmartProgress используем React для разработки интерфейсов и нам очень хотелось найти react-way решение. На помощь нам спешат порталы.


                          Читать дальше →