Программа для конвертирования видео файлов. Any Video Converter Free позволяет перекодировать популярные видео форматы (AVI, MOV, RM, MPEG, DVD, WMV, MP4 и FLV) в DVD, VCD, MP4 или FLV.
Бесплатная программа для записи CD и DVD, Blu-Ray и HD-DVD дисков. Она поддерживает запись и создание ISO-образов, имеет многоязычный интерфейс. Все пользователи, даже предприятия, могут пользоваться программой бесплатно. Программа не содержит adware или похожих компонентов.
Интерпретатор Машины Поста 1.0
Интерпретатор Машины Поста. Исполняет алгоритмы для машины Поста. Есть демо, примеры, файл справки (как по самой программе, так и по теории алгоритмических моделей)
Источник: ukrainskaya-elena.jimdofree.com
Лабораторная работа №13 Тема: «Разработка программ для машины Поста»
Цель: Сформировать умения и навыки по разработке программ для машины Поста. Развить аналитическое и логическое мышление, математическую интуицию, посредством разработки алгоритмов задач для логических машин.
Что такое машина Поста. Душкин объяснит
Теоретическая часть:
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из:
- бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
- головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.
Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.
Система команд Машины Поста
Практическая часть
Задание №1 Выполнить задачи, используя эмулятор Поста
Вариант №1
- Увеличить на3 данный массив справа от него, через ячейку, и затем стереть исходный. Каретка находится над крайней левой меткой.
- Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.
- На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.
Вариант №2
Автоматическая обработка данных. Машина Поста
- Увеличить на 4 данный массив слева от него, через ячейку, и затем стереть исходный. Каретка находится над крайней левой меткой.
- Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайней справа, и двух крайних слева и поставить каретку в исходное положение.
- На ленте заданы два массива — m и n. Вычислить сумму этих массивов. Каретка располагается над левой ячейкой правого массива
Вариант №3
- Увеличить на 5данный массив справа от него, через две ячейки, и затем стереть исходный. Каретка находится над крайней левой меткой.
- Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив, и в новом массиве убрать предпоследнюю метку справа Каретка находится над крайней левой меткой первого массива.
- На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над последней меткой левого массива.
Вариант 4
- Увеличить на 6 данный массив справа от него, через две ячейки, и затем стереть исходный. Каретка находится над крайней левой меткой.
- Составить задачу нахождения суммы любого количества массивов, которые отделены друг от друга одной ячейкой. Каретка находится над крайней левой меткой первого массива.
- На ленте заданы два массива — m и n. Вычислить сумму этих массивов. Каретка располагается над предпоследней ячейкой правого массива
Задание 2. Ответить на контрольные вопросы.
1.Какие действия допустимы для каретки в машине Поста? Тьюринга?
3. Объясните порядок работы машины Поста.
3. Что представляет собой таблица машины Поста?
4. Напишите команду «Записать метку», «Снять метку » в эмуляторе.
5.Как остановить программу в эмуляторе?
Задание 3. Сделать вывод о проделанной работе.
Герасимова Светлана Александровна
Содержимое разработки
Лабораторная работа №13
Тема: «Разработка программ для машины Поста»
Цель: Сформировать умения и навыки по разработке программ для машины Поста. Развить аналитическое и логическое мышление, математическую интуицию, посредством разработки алгоритмов задач для логических машин.
Теоретическая часть:
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из:
-82%
Источник: videouroki.net
Программа машины Поста
Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки, Эта работа происходит по инструкции определенного вида, называемой программой. Для машины Поста возможно составление различных программ. Посмотрим, как устроена программа.
Каждая программа машины Поста состоит из команд. Командой машины Поста будем называть выражение, имеющее один из следующих шести видов (буквы i, j, j1, j2 означают всюду натуральные числа 1,2,3,4,5. ):
Первый вид. Команды движения вправо
Второй вид. Команды движения влево
Третий вид. Команды печатания метки
Четвертый вид. Команды стирания метки
Пятый вид. Команды передачи управления
.
Шестой вид. Команды остановки
является командой движения вправо,
— командой передачи управления, а
6386. Стоп
Число 1, стоящее в начале команды, называется номером команды. Так, у приведенных только что команд номера суть соответственно 137, 25 и 6386. Число j, стоящее в конце команды (а у команд передачи управления — каждое из чисел j1 и j2), будем называть отсылкой (при этом в команде передачи управления j1 — верхней, а j2 — нижней отсылкой). У команд остановки нет отсылки. Так, у приведенных только что команд отсылками служат числа 1, 32, 25, причем 32 — верхняя отсылка, а 25 — нижняя отсылка.
Программой машины Поста будем называть конечный непустой (т. е. содержащий хотя бы одну команду) список команд машины Поста, обладающий следующими двумя свойствами:
- На первом место в этом списке стоит команда с номером 1, на втором месте (если оно есть) — команда с номером 2 и т. д.; вообще на А-м месте стоит команда с номером Н.
- Отсылка любой из команд списка совпадает с номером некоторой (другой или той же самой) команды списка (более точно: для каждой отсылки каждой команды списка найдется в списке такал команда, номер которой равен рассматриваемой отсылке) .
Например, следующий список будет программой машины Поста:
А эти два списка не будут программами машины Поста, хотя и составлены из команд машины Поста:
(не выполнено первое условие);
(не выполнено второе условие).
Для наглядности программы машины Поста мы будем записывать столбиком. Число команд программы называется длиной программы.
Упражнение. Выпишите все программы машины Поста длины l. Сколько существует программ. длины 2, длины 3, длины n?
Работа машины Поста
Чтобы машина Поста начала работать, надо задать, во-первых, некоторую программу, а во-вторых, некоторое ее (машины) состояние, т. е. как-то расставить метки по секциям ленты (в частности, можно все секции оставить пустыми) и поставить каретку против одной из секций. Как правило, мы будем предполагать, что в начальном (т. е. в задаваемом вначале) состоянии машины каретка ставится всегда против секции с номером (координатой) нуль. При таком соглашении начальное состояние машины полностью определено состоянием ленты.
Как уже говорилось, программа является той инструкцией, на основании которой работает машина. Работа машины на основании заданной программы (и при заданном начальном состоянии) происходит следующим образом. .Машина приводится в начальное состояние и приступает к выполнению первой команды программы (что значит «выполнить команду», будет объяснено ниже). Эта команда выполняется за один шаг, после чего машина приступает к выполнению той команды, номер которой (назовем его к) равен отсылке (одной из отсылок, если их две) первой команды. Эта команда также выполняется за один шаг, после чего начинается выполнение команды, номер которой равен отсылке команды с номером а. Вообще каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k-м шаге выполнялась команда с номером i, тогда, если эта команда имеет единственную отсылку j, то па k-1-м шаге выполняется команда с номером j; если эта команда имеет две отсылки j1 и j2, то на k + 1-м шаге выполняется одна из двух команд— с номером j1 или с номером j2 (какая именно, будет указано ниже); если, наконец, выполняющаяся на k-м шаге команда вовсе не имеет отсылки, то на k+1-м шаге и на всех последующих шагах не выполняется никакая команда: машина останавливается. Осталось объяснить, что значит выполнить команду и какая из отсылок — при наличии двух — выбирается в качестве номера следующей команды.
Выполнение команды движения вправо состоит в том, что каретка сдвигается на одну секцию вправо. Выполнение команды движения влево состоит в том, что каретка сдвигается на одну секцию влево.
Выполнение команды печатания метки состоит в том, что каретка ставит метку на обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая перед началом выполнения команды секция пуста; если же на обозреваемой, секции уже стоит метка, команда считается невыполнимой. Выполнение команды стирания метки состоит в том, что каретка уничтожает метку в обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая секция отмечена; если же !!а обозреваемой секции и так кет метки, команда считается невыполнимой. Выполнение команды передачи управления с верхней отсылкой j1 и нижней отсылкой j2 никак не изменяет состояния машины: пи одна из меток по уничтожается и не ставится, и каретка также остается неподвижной (машина делает, так сказать, «шаг па месте»); однако если секция, обозреваемая перед началом выполнения этой команды, была пуста, то следующей должка выполняться команда с номером j1, если же эта секция была отмечена, следующей должна выполняться команда с номером j2 (роль команды передачи управления сводится, следовательно, к тому, что каретка во время выполнения этой команды как бы «распознает», стоит ли перед ней метка, — именно это имелось в виду в предпоследней фразе § 1). Выполнение команды остановки тоже никак не меняет состояния машины и состоит в том, что машина останавливается.
Если теперь, задавшись программой и каким-либо начальным состоянием, пустить машину в ход, то осуществится один из следующих трех вариантов:
- В ходе выполнения программы машина дойдет до выполнения невыполнимой команды безрезультатная остановка.
- В ходе выполнения программы машина дойдет до выполнения команды остановки; программа в этом случае считается выполненной, машина останавливается; происходит так называемая результативнаяостановка.
- В ходе выполнения программы машина не дойдет до выполнения ни одной из команд, указанных в первых двух вариантах; выполнение программы при этом никогда не прекращается, машина никогда не останавливается; процесс работы машины происходит бесконечно.
Источник: studfile.net