contact: gorbenko.aa@gmail.com
Практики. Написать программу для машины Тьюринга
Автоматы
- Посещение лекций
- Работа на практиках
Философия
Теория
Важно формализовать понятие алгоритма
- Формализация
- Оценка сложности
- Сравнение
Понятие алгоритма появилось в 10 веке. Перематываем
Практика
Мы живем в мире с огромным объемом информации. Надо что-то с этим делать
Алгоритм
Link to original
Теория алгоритмов оценивает возможности того, что можно вычислить, а что никогда вычислить не удастся
Нейронные сети
Это вынужденная мера, чтобы анализировать большие данные
Нужно решать проблемы сейчас
- Вычислимость
- Выразимость
Выразительность
Возможность описать что-то несколькими способами
Link to original
Выразимость
Свойство выражать что-либо наиболее полно и точно, а также способность делать это эффективно
Link to original
Языки
Естественные языки
Искусственные языки
Теория машины Тьюринга
Ключевое слово курса - вычислимость
1936, Алан Тьюринг придумал машину Тьюринга (эквивалент компьютеров в смысле возможности вычислимости)
Если что-то можно посчитать на Машине Тьюринга, это можно посчитать на компьютере
Машина Тьюринга
Неформальное определение
Устройство, состоящее из двух частей:
- бесконечной одномерной ленты, разделённой на ячейки,
- головки, которая представляет собой детерминированный конечный автомат.
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку. Если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
Формальное определение
вопрос найти формальное определение из лекций
Link to original
Программа - слово в грамматике. Цель компилятора сперва - допустить слово (программу)
Допуск - допуск