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

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

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.

Комментарии

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

Angular - концепции, код и коллективная мудрость

Angular - концепции, код и коллективная мудрость

en
Изучите основные понятия, играйте с кодом, станьте грамотным Angular разработчиком. Подумайте о том, чтобы пройти этот курс, если вы являетесь разработчиком, который хочет быстро изучить Angular концепции, не имея необходимости читать онлайн-доки, сообщения в блогах, вопросы GitHub и сообщения...
Сэмюэл Л. Джексон учит играть | Мастер клас

Сэмюэл Л. Джексон учит играть | Мастер клас

en
В детстве Сэмюэл Л. Джексон так сильно заикался, что почти не разговаривал. Сегодня он один из самых успешных актеров в мире, с ролями в более чем 100 фильмах, в том числе Pulp Fiction и The Avengers. Впервые звезда учит, как он создает незабываемые персонажи, мощные выступления и долговременную...
Armin van Buuren учит танцевальной музыке | Мастер класс

Armin van Buuren учит танцевальной музыке | Мастер класс

en
Каждую неделю Armin van Buuren отправляет 41 миллион слушателей в «State of Trance» на его радиошоу. В своем первом в мире онлайн-классе дилер, продающий платину, разрывает свои хиты и строит трек с нуля - чтобы показать вам, как он производит, исполняет и продвигает танцевальную музыку.
Java Professional v2

Java Professional v2

ru
Курс "Java Professional" ориентирован на комплексное и глубокое изучение возможностей Java Core. Он будет интересен тем программистам, которые уже имеют опыт работы с языком Java и хотят познакомиться с его дополнительными тонкостями, а также особенностями эффективного использования языка.
Python и Flask Bootcamp: Cоздавайте веб-сайты с помощью Flask!

Python и Flask Bootcamp: Cоздавайте веб-сайты с помощью Flask!

en
Создавайте потрясающие веб-сайты, используя мощный Flask фреймворк для Python! Добро пожаловать в лучший онлайн-ресурс, чтобы узнать, как создавать сайты с Python и Flask! Этот курс станет вашим полным окончательным руководством по разработке полнофункциональных веб-сайтов с Flask фреймворком.
Курс Ultimate Advanced Laravel Pro (включая Vuejs)

Курс Ultimate Advanced Laravel Pro (включая Vuejs)

en
Изучите передовые концепции фреймворков laravel и vuejs, а также создайте и разверните полный проект. ПОСЛЕДНИЙ LARAVEL КУРС, который вам когда-либо понадобится. Этот курс охватывает расширенные возможности laravel с глубоким погружением в исходный код, объяснением основных концепций и шаблонов...
Визуализации данных с D3.js

Визуализации данных с D3.js

en
Cоздавайте красивые визуализации данных с помощью d3.js. Интенсивное введение в библиотеку D3. Этот курс поднимет вас в D3 до такой степени, что вы сможете построить практически любую визуализацию, которую вы можете себе представить. Курс научит вас программировать в последней версии D3 - версия 5.x
3D-программирование с помощью WebGL и Babylon.js для начинающих

3D-программирование с помощью WebGL и Babylon.js для начинающих

en
Обновите свои навыки и будьте готовы к будущему, включив 3D-технологии в свой портфель навыков. В настоящее время поддерживается всеми браузерами, WebGL - это JavaScript API, который позволяет вам отображать 3D-изображения в браузере без использования плагинов. Существующие библиотеки...
Google Material Design для WPF разработчика

Google Material Design для WPF разработчика

ru
Видео курс Google Material Design предназначен для людей, которые уже имеют уверенные знания языка программирования C# и имеют опыт разработки на этом языке. Курс также будет полезен .NET разработчикам, желающим расширить свой стек знаний технологией WPF. Обучение по курсу будет состоять из двух...
chat
logo