Математика для программистов от Otus

Программа курса

Программа состоит из 7 блоков, в каждый из которых входит несколько полезных тем. В конце обучения вам предстоит выполнить проект по одной из предложенных задач (разработать синтаксический анализатор языка программирования, вывод типов для языка C# или интерпретатор команд виртуальной машины Java). Также у вас есть возможность самостоятельно предложить тему, над которой вы хотели бы поработать. 

Вычисления

В модуль входит 3 темы. Разберётесь, в чём состоят ограничения модели вычислений и как они проявляются на практике. Научитесь определять проблемы сложности для произвольного проекта, обсудите основные виды сложности. Изучите некоторые неразрешимые проблемы. Научитесь объяснять, как они влияют на разработку ПО.

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

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

Изучите некоторые неразрешимые проблемы. Научитесь объяснять, как они влияют на разработку ПО.

Логика

В модуль входит 9 тем. Узнаете, как построить таблицу истинности булевой функции, произвести простейшие эквивалентные преобразования логических формул, проверить систему булевых функций на полноту. Обсудите применение импликации в программировании. Сможете построить СКНФ, СДНФ булевой функции. Научитесь производить эквивалентные преобразования логических формул с целью их упрощения. Научитесь проводить логический вывод в произвольном исчислении, обсудите свойства полноты и непротиворечивости. Узнаете, как произвести эквивалентные преобразования в исчислении высказываний и в исчислении предикатов. Научитесь производить доказательство свойств безопасности программ. Обсудите влияние противоречивости логики Хоара на разработку ПО. Разберётесь, почему и когда стоит отказаться от глобальных переменных с точки зрения полноты логик Хоара. Узнаете, как определить множество классов эквивалентности по произвольной процедуре, методу. Сможете построить множество тестов по классам эквивалентности. Изучите применение TDD с точки зрения логики Хоара. Научитесь определять код, использующий полиморфизм. Изучите 7 видов полиморфизма. Будете знать, как определять инвариант типа данных. Научитесь определять арифметику через лямбда-функции. Узнаете, как определить операторы языков программирования через лямбда-функции.

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

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

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

Узнаете, как произвести эквивалентные преобразования в исчислении высказываний и в исчислении предикатов.

Научитесь производить доказательство свойств безопасности программ. Обсудите влияние противоречивости логики Хоара на разработку ПО. Разберётесь, почему и когда стоит отказаться от глобальных переменных с точки зрения полноты логик Хоара.

Узнаете, как определить множество классов эквивалентности по произвольной процедуре, методу. Сможете построить множество тестов по классам эквивалентности. Изучите применение TDD с точки зрения логики Хоара.

Научитесь определять код, использующий полиморфизм. Изучите 7 видов полиморфизма.

Будете знать, как определять инвариант типа данных.

Научитесь определять арифметику через лямбда-функции. Узнаете, как определить операторы языков программирования через лямбда-функции.

Формальные языки

В модуль входит 5 тем. Изучите классификацию формальных языков Хомского. Сможете определить распознающую грамматику. Научитесь определять LL(1) грамматики, избавляться от рекурсий в начале правил, проверять критерий LL(1) грамматики. Узнаете, как строить автомат с магазинной памятью по LL(1) грамматике. Продолжите изучать начатую тему, посвящённую LR(1) - грамматикам, и углублять свои знания. Научитесь определять регулярные грамматики, проводить их проверку на соответствие критерию регулярности. Узнаете, как определять регулярные выражения. Разберётесь, как применять генератор компиляторов для построения синтаксических анализаторов.

Изучите классификацию формальных языков Хомского. Сможете определить распознающую грамматику.

Научитесь определять LL(1) грамматики, избавляться от рекурсий в начале правил, проверять критерий LL(1) грамматики. Узнаете, как строить автомат с магазинной памятью по LL(1) грамматике.

Продолжите изучать начатую тему, посвящённую LR(1) - грамматикам, и углублять свои знания.

Научитесь определять регулярные грамматики, проводить их проверку на соответствие критерию регулярности. Узнаете, как определять регулярные выражения.

Разберётесь, как применять генератор компиляторов для построения синтаксических анализаторов.

Реализация конструкций языков программирования

В этот модуль входит 5 тем. Научитесь переводить различные виды циклов в машинные команды. Узнаете историю развития циклов с точки зрения проблемы остановки машины Тьюринга. Изучите современный подход для реализации циклических операций. Научитесь преобразовывать выражение в обратную польскую запись. Сможете, пользуясь обратной польской записью, составлять тройки для преобразования в машинный код. Разберётесь, как преобразовывать вызов процедуры в машинный код. Усвоите разницу между прямым и обратным порядком передачи параметров с точки зрения ограничения возможности языков программирования. Будете знать разницу между вызовом процедуры и метода и понимать различия между вызовом виртуального метода и "обычного". Узнаете способы организации локальных переменных. Будете знать подход к определению ситуаций с выходом за границы диапазонов массива. Научитесь применять RAII, изучите особенности работы с рекурсивными функциями. Узнаете методы организации динамической кучи. Освоите приемы работы сборки мусора. Изучите механизм работы оператора new.

Научитесь переводить различные виды циклов в машинные команды. Узнаете историю развития циклов с точки зрения проблемы остановки машины Тьюринга. Изучите современный подход для реализации циклических операций.

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

Разберётесь, как преобразовывать вызов процедуры в машинный код. Усвоите разницу между прямым и обратным порядком передачи параметров с точки зрения ограничения возможности языков программирования. Будете знать разницу между вызовом процедуры и метода и понимать различия между вызовом виртуального метода и "обычного".

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

Узнаете методы организации динамической кучи. Освоите приемы работы сборки мусора. Изучите механизм работы оператора new.

ОПП концепции

В этом модуле 4 темы. Обсудите определение абстрагирования как сюръективного отображения. Изучите эффект переполнения и округления через алгебры, а также ограничения абстрагирования. Научитесь строить абстрагирования. Разберёте достаточное условие постоянной скорости разработки, изучите алгоритм применения SOLID принципов. Будете уметь, пользуясь алгоритмом применения SOLID принципов, писать код, устойчивый к изменениям требований. Разберёте примеры применения SOLID принципов в популярных фреймворках. Узнаете, как найти код, удовлетворяющий SOLID.

Обсудите определение абстрагирования как сюръективного отображения. Изучите эффект переполнения и округления через алгебры, а также ограничения абстрагирования. Научитесь строить абстрагирования.

Разберёте достаточное условие постоянной скорости разработки, изучите алгоритм применения SOLID принципов.

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

Разберёте примеры применения SOLID принципов в популярных фреймворках. Узнаете, как найти код, удовлетворяющий SOLID.

Распределенное и многопоточное программирование

В модуль входит 6 тем. Разберёте понятие Race Condition, обсудите отличие последовательного выполнения кода от выполнения в несколько потоков, а также процессы, свободные от взаимного вмешательства. Научитесь применять методы распараллеливания программ. Сможете сформулировать классические задачи многопоточного программирования. Научитесь применять потоко-безопасную очередь для написания потокобезопасного кода. Научитесь применять условные события для написания потокобезопасных тестов. Научитесь объяснять проектные решения с помощью CAP-теоремы. Сможете применить CAP-теорему. Разберёте свойство согласованности. Разберёте алгоритмы Paxos и Raft. Сможете объяснить отличие вычислений, основанных на системе обмена сообщениями, от вычислений на основе частично-определенных функций. Узнаете, как реализовать архитектуру Fog Cutter.

Разберёте понятие Race Condition, обсудите отличие последовательного выполнения кода от выполнения в несколько потоков, а также процессы, свободные от взаимного вмешательства. Научитесь применять методы распараллеливания программ.

Сможете сформулировать классические задачи многопоточного программирования. Научитесь применять потоко-безопасную очередь для написания потокобезопасного кода.

Научитесь применять условные события для написания потокобезопасных тестов.

Научитесь объяснять проектные решения с помощью CAP-теоремы. Сможете применить CAP-теорему. Разберёте свойство согласованности.

Разберёте алгоритмы Paxos и Raft.

Сможете объяснить отличие вычислений, основанных на системе обмена сообщениями, от вычислений на основе частично-определенных функций. Узнаете, как реализовать архитектуру Fog Cutter.

Проектная работа

Модуль посвящён проектной работе и состоит из 3 тем. Выберете и обсудите тему проекта, спланируете свою работу над ней. Ознакомитесь с регламентом работы над проектом. У нас будет возможность задать вопросы по проекту, ДЗ и курсу, которые у вас ещё остались.  Вам предстоить защитить свой проект и получить рекомендации экспертов.

Выберете и обсудите тему проекта, спланируете свою работу над ней. Ознакомитесь с регламентом работы над проектом.

У нас будет возможность задать вопросы по проекту, ДЗ и курсу, которые у вас ещё остались. 

Вам предстоить защитить свой проект и получить рекомендации экспертов.