Ознакомиться с важной информацией: Майнер отключен!

Серия скринкастов "Вычисления" - Видеоуроки

Computation
Duration 01:54:50
Открыть все курсы от destroyallsoftware

Computation - Полный список уроков

Развернуть / Свернуть
  • Урок 1. Введение в вычисления 00:04:33
  • Урок 2. Вычисление путем изменения 00:12:34
  • Урок 3. Мощность машин Тьюринга 00:10:42
  • Урок 4. Вычисление путем построения 00:10:01
  • Урок 5. Мощность исчисления лямбда 00:12:15
  • Урок 6. Пределы вычислений 00:13:06
  • Урок 7. Распознавание простых языков 00:16:57
  • Урок 8. Распознавание языков программирования 00:14:30
  • Урок 9. Самые сложные языки 00:09:29
  • Урок 10. Заключительные замечания по расчетам 00:10:43

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

1. Введение в вычисления 

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

2. Вычисление путем изменения 

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

3. Мощность машин Тьюринга 

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

4. Вычисление путем построения 

Мы пишем простую, легко читаемую примерную функцию в Python. Затем удаляем функции Python одну за другой, превратив все это в лямбда-исчисление. В конце нет ничего, кроме (1) определений функций, которые принимают ровно один аргумент и (2) вызова функции с одним аргументом. В конце все еще есть вспомогательные функции, которые используют функции Python. В следующий раз мы удалим все из них, переопределяя числа и логические точки с нуля, используя только функции одного аргумента. 

5.  Мощность исчисления лямбда 

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

Примечание 1 (после того как вы просмотрели этот скринкаст): при преобразовании из цифр Church Numerals в числа Python нет ничего особенного (lambda x: x + 1) (0). Например, мы могли бы использовать (lambda x: x + "A") (""). В этом случае Church numeral 1 будет преобразовано в «А»; 2 будет преобразован в «AA» и тд.

Примечание 2: MULT можно записать немного более просто, поскольку lambda n: lambda m: n (ADD (m)) (ZERO), но более сложная версия, показанная в скринкасте, по-прежнему правильная.  

6. Пределы вычислений 

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

7. Распознавание простых языков 

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

8. Распознавание языков программирования 

Компиляторы и интерпретаторы должны понимать структуру кода для его запуска, так же как нам нужно понять структуру кода для его чтения. Этот скринкаст вводит контекстно-свободные языки, которые используются для определения синтаксисов Python, Lua, Lisp и многих других языков программирования. Начнем с простого синтетического примера, показывающего, почему контекстно-свободные языки более мощные, чем обычные языки. Затем мы рассмотрим фактические определения грамматики языков программирования Python и Lua. Мы анализируем фрагменты кода на каждом языке, используя определения грамматики языков, чтобы увидеть структуру кода так же, как это видит компилятор или интерпретатор. 

9. Самые сложные языки 

Мы заканчиваем иерархию Хомского, рассматривая контекстно-зависимые языки (включая C, JavaScript и многие другие языки программирования) и неограниченные грамматики, которые являются Тьюрингом. Мы также связываем неразрешимые проблемы с иерархией Хомского, рассматривая их как пятый уровень. Удивительно, но есть как минимум один язык программирования, грамматика которого технически неразрешима. 

10. Заключительные замечания по расчетам 

Мы изучаем некоторые любопытства, которые объединяют идеи в этой серии. Во-первых, как мы можем написать грамматику для синтаксиса самих регулярных выражений? То есть, каковы правила для действительного регулярного выражения? Аналогично, как мы можем написать грамматику для синтаксиса самих грамматических определений? (Ответы на них удивляют!) Наконец, как историческое разделение между машиной Тьюринга и исчислением лямбда связано с современным разделением между императивным и функциональным программированием? 

(Примечание: grammar-grammar, показанная в этом скринкасте, на самом деле не является грамматикой для себя по тривиальной причине: она использует двойные кавычки для литералов, но описывает только синтаксис с использованием одинарных кавычек. Изменение кавычек на '' " исправило бы проблему, хотя этот синтаксис менее понятен человеку, что не влияет на сделанные выводы.) 

Твоя оценка

1 0
Следи за последними обновлениями и новостями в наших пабликах facebook, или вступай в наш канал telegram.

Комментарии

Последнее добавленное

VR-разработчик. Разработки VR-приложения: от идеи до монетизации

VR-разработчик. Разработки VR-приложения: от идеи до монетизации

ru
VR-разработчик — это профессия будущего. Такие гиганты, как Facebook, YouTube, Google , находятся в постоянном поиске талантливых VR-специалистов. При этом войти в профессию очень легко, люди с любым бэкграундом могут начать обучение. Навыки VR-разработки, создания и ведения проектов...
Онлайн курс-интенсив «Развитие памяти и внимания»

Онлайн курс-интенсив «Развитие памяти и внимания»

ru
Как со 100% точностью запоминать большой объем любой информации на неограниченный срок? КТО и ЗАЧЕМ ХОДИТ В АПТЕКУ Спрос, как известно, рождает предложение. Поэтому в любой аптеке, на самом видном месте, наряду с лекарствами от простуды и гриппа, можно встретить препараты для улучшения памяти.
Основы Affinity Photo

Основы Affinity Photo

en
Руководство для новичков в самой горячей новой программе для редактирования изображений! Affinity Photo - самая новая программа для редактирования изображений для Mac и Windows. У нее есть много мощных инструментов, чтобы сделать Ваши фотографии действительно сияющими. Но вам нужно знать...
Практический онлайн-курс  «Дизайн мобильных приложений»

Практический онлайн-курс «Дизайн мобильных приложений»

ru
Курс для тех, кто хочет снимать сливки в профессии дизайнера, занимаясь самой передовой и востребованной отраслью — разработкой дизайна для мобильных приложений. 90 млрд приложений было загружено в 2016 году по всему миру, 5 место по числу загрузок заняла Россия, 33 приложения установлено...
Intermediate React

Intermediate React

en
Научитесь создавать масштабируемые приложения React с использованием инструментов и методов, доступных в экосистеме React. Вы будете тестировать свои компоненты React с помощью Jest, использовать CSS в JS, разделять код на React Loadable, использовать рендеринг на стороне сервера в React с Node...
[Перевод] [RU] Unreal Engine курс - Изучите C ++ и делайте игры

[Перевод] [RU] Unreal Engine курс - Изучите C ++ и делайте игры

ru
Узнайте, как создавать видеоигры с помощью Unreal Engine 4, бесплатной платформы для разработки игр, используемой студиями AAA класа и разработчиками indie по всему миру. Мы начинаем супер просто, поэтому вам не нужно никакого опыта в Unreal или программировании! С помощью наших онлайн-руководств...
Продвинутый курс GameDev: создаем полноценную игру для android

Продвинутый курс GameDev: создаем полноценную игру для android

ru
Пройдите курс по разработке игры, своим геймплеем напоминающую легендарную Flappy Bird, разработчик которой стал миллионером за короткий срок. В процессе прохождения курса GameDev мы с вами создадим полноценную игру, встроим в нее рекламный баннер AdMob и опубликуем в Google Play. Курс состоит...
Веб-скрапинг используя PhantomJS и CasperJS

Веб-скрапинг используя PhantomJS и CasperJS

en
Станьте лучшим разработчиком JavaScript и изучите Front-End тестирование. Мы будем использовать javascript, lodash и jquery для скрапинга. В этом курсе вы узнаете, как собирать данные с веб-страниц с помощью CasperJS. Этот курс состоит из 5 проектов, которые помогут вам в полной мере понять...
chat
logo