obsidian/Computer Science/Вычислительные системы/Модель вычислений.md

MoC - Model of Computation

1. MoC предоставляет язык для описания моделей процессов/программ/структур
2. MoC определяет возможности вычислительной машины
3. MoC характеризует, как исполняется модель (программа): возможные состояния вычислителя, их последовательность, правила переходов (детерменированные или нет)
4. MoC, обычно, минималистичны относительно реальных вычислителей

Последовательные модели

Sequential models Относительно просто реализуются в виде аппаратных схем

Конечные автоматы

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

Автомат с магазинной памятью

Например, парсеры

Достоинства

• Таблица состояний
• Верифицируемость переходов
• Простая реализация в схемотехнике и ПО

Машина Тьюринга

Включает:

• Неограниченную двустороннюю ленту, разделенную на ячейки
• Устройство управления (головка записи-чтения), которое может находиться в конечном числе состояний Управляющее устройство может:
• Перемещаться по ленте влево и вправо
• Читать и записывать в ячейки символы конечного алфавита Машина Тьюринга

1. Не может быть реализована на практике (нет бесконечной ленты)
2. Обладает полнотой по Тьюрингу (можно реализовать любой известный алгоритм)
3. Проблема остановки
4. Данные и управление отделены
5. Ориентирована на реализацию

Random Access Machine

Функциональные модели

Functional models Представление вычислительного процесса как совокупности символов и правил их преобразований

1. Арифметика
2. Лямбда исчисление (полнота по Тьюрингу)
3. Combinatory logic
4. General recursive functions
5. Abstract rewriting systems Программа/данные - математический объект Возможна Тьюринг неполнота

Лямбда исчисление

4 вида выражений

1. Переменная: x, y\ \text{и} \ z
2. Константа: a,b,c
3. Коминация (вызов): s\ t
4. Абстракция: \lambda x.s

3 вида редукций/подстановки

1. Переименование переменных: \lambda u.u\ v \xrightarrow{\alpha} \lambda w.w\ v
2. Применение функции (подстановка аргумента): (\lambda x.s)\ t \xrightarrow{\beta} s[t/x]
3. Сокращение аргумента: \lambda u.v\ u \xrightarrow{\eta} v

Параллельные модели

Системы, включающие несколько взаимодействующих процессов

• Kahn process networks - однонаправленные каналы с неограниченными буферами (+- как в гошке)
• Actor model - отправка сообщений в "почтовые ящики" (как в Erlang)
• Discrete Event - события в заданные моменты времени (цифровые схемы)
• Multi-Thread Model - общая память (как в джаве)
• Synchronous Data Flow - синхронизированные потоки данных

Близкие понятия

Парадигмы программирования

Способ классификации языков программирования на основе их функций. Языки могут относиться к нескольким парадигмам

Стиль программирования

Это набор правил или рекомендации, используемых при написании исходного кода компьютерной программы

Применение на практике

1. Computer Science. Формальные модели
2. Дизайн ЯПов
3. Ограничение творческого порыва, контроль сложности
4. Модель-ориентированная инженерия

Model-Driven Engineering

1. Разработка через моделирование предметной области
2. Автоматическая генерация кода из моделей
3. Повышение уровня абстракции при разработке
4. Сокращение разрыва между требованиями и реализацией
5. Улучшение коммуникации между заинтересованными сторонами
6. Снижение сложности разработки масштабных систем