Обзорный практикум по содержанию ФГОС к тринадцатой паре 11 класса
Машина Тьюринга — не единственная попытка строго сказать, что такое алгоритм. В том же 1936 году Эмиль Пост описал машину ещё проще, а в конце 1940-х — начале 1950-х А. А. Марков предложил нормальные алгорифмы — преобразования слов по формулам. Все эти модели равносильны: что вычисляет одна, вычисляют и другие.
| команда | что делает |
|---|---|
| V j | поставить метку, перейти к j |
| X j | стереть метку, перейти к j |
| → j / ← j | каретку на клетку вправо / влево, перейти к j |
| ? i; j | клетка пуста — к i, отмечена — к j |
| ! | стоп |
Метка в уже отмеченную клетку и стирание пустой — аварийная
остановка, результата нет. Пример: 1. → 2,
2. ? 3; 1, 3. V 4, 4. ! — каретка
идёт вправо по ряду меток до первой пустой клетки и ставит в неё метку:
ряд стал на одну метку длиннее.
Пиши столбиком: номер команды, номер клетки, пуста она или отмечена. Шаг — одна выполненная команда, «!» тоже считается. Лента перерисовывается после каждого V и X.
Работает со словом — строкой символов. Схема — упорядоченный список формул P → Q («заменить P на Q») и заключительных P →· Q. λ — пустое слово. Один шаг:
Ни одна формула не подходит — тоже стоп. Пример: схема ba → ab
на слове bab: bab ⇒ abb, больше ba нет — стоп.
Алгорифм сортирует буквы.
По одной формуле в строке, по порядку; заключительная — с точкой после стрелки, пустое слово — λ или ничего:
*a -> b* *b -> a* * ->. λ λ -> *
Эта схема меняет a на b и b на a. Приём бегунка: формула с пустой
левой частью ставит служебную метку * в начало слова, формулы вида
*a → …* проводят её по слову, а заключительная стирает в
конце. Формула λ → * подходит к любому слову — поэтому её
пишут последней. Порядок формул — часть алгорифма.
Обзорный практикум по содержанию ФГОС к тринадцатой паре 11 класса
Машина Тьюринга — не единственная попытка строго сказать, что такое алгоритм. В том же 1936 году Эмиль Пост описал машину ещё проще, а в конце 1940-х — начале 1950-х А. А. Марков предложил нормальные алгорифмы — преобразования слов по формулам. Все эти модели равносильны: что вычисляет одна, вычисляют и другие.
| команда | что делает |
|---|---|
| V j | поставить метку, перейти к j |
| X j | стереть метку, перейти к j |
| → j / ← j | каретку на клетку вправо / влево, перейти к j |
| ? i; j | клетка пуста — к i, отмечена — к j |
| ! | стоп |
Метка в уже отмеченную клетку и стирание пустой — аварийная
остановка, результата нет. Пример: 1. → 2,
2. ? 3; 1, 3. V 4, 4. ! — каретка
идёт вправо по ряду меток до первой пустой клетки и ставит в неё метку:
ряд стал на одну метку длиннее.
Пиши столбиком: номер команды, номер клетки, пуста она или отмечена. Шаг — одна выполненная команда, «!» тоже считается. Лента перерисовывается после каждого V и X.
Работает со словом — строкой символов. Схема — упорядоченный список формул P → Q («заменить P на Q») и заключительных P →· Q. λ — пустое слово. Один шаг:
Ни одна формула не подходит — тоже стоп. Пример: схема ba → ab
на слове bab: bab ⇒ abb, больше ba нет — стоп.
Алгорифм сортирует буквы.
По одной формуле в строке, по порядку; заключительная — с точкой после стрелки, пустое слово — λ или ничего:
*a -> b* *b -> a* * ->. λ λ -> *
Эта схема меняет a на b и b на a. Приём бегунка: формула с пустой
левой частью ставит служебную метку * в начало слова, формулы вида
*a → …* проводят её по слову, а заключительная стирает в
конце. Формула λ → * подходит к любому слову — поэтому её
пишут последней. Порядок формул — часть алгорифма.