- Главная
- Информатика
- Реализация кодировщика\декодировщика на основе структуры Машины Тьюринга
Содержание
- 2. Цели и задачи работы Нынешнее программирование многогранно и используется в таких важных сферах как строительство, бизнес
- 3. Содержание Машина Тьюринга и Алан Тьюринг Структура машины Тьюринга Такт работы машины Тьюринга Программа для машины
- 4. Машина Тьюринга и Алан Тьюринг Концепция абстрактной вычислительной машины была предложена Аланом Тьюрингом в 1936 году.
- 5. Структура машины Тьюринга Машина Тьюринга (МТ) состоит из двух частей – ленты и автомата: Лента используется
- 6. Такт работы машины Тьюринга МТ работает тактами (по шагам), которые выполняются один за другим. На каждом
- 7. Программа для машины Тьюринга Сама по себе МТ ничего не делает. Для того чтобы заставить её
- 8. Программа для машины Тьюринга Если входное слово пустое, то автомат может смотреть в любую клетку, т.к.
- 9. Пример Данная МТ позволяет заменить все «0» в слове на «1» и наоборот. Слово: 100011 Запись
- 10. Описание алгоритма шифрования методом одноалфавитной подстановки Есть алфавит, состоящий, к примеру, из символов «АБВГДЕ» (при этом
- 11. Реализация алгоритма шифрования методом одноалфавитной подстановки при помощи детерминированной машины Тьюринга . Постановка задачи. У нас
- 12. Описание алгоритма симметричного шифрования методом перестановки. Данный алгоритм заключается в следующем. У нас есть слово, которое
- 13. Реализация алгоритма симметричного шифрования методом перестановки при помощи детерминированной машины Тьюринга Постановка задачи. У нас есть
- 14. Заключение МТ позволяет в полной мере реализовать простейшие алгоритмы шифрования, однако следует учитывать, что при использовании
- 15. Задача для реализации кодировщика\декодировщика на основе МТ Программы кодировщика\декодировщика на основе структуры Машины Тьюринга на английском
- 16. Функция Fnull() Блок-схема
- 17. Функция Fone() Блок-схема
- 18. Функция Ftwo () Блок-схема
- 19. Функция FNnull() Блок-схема
- 20. Функция FNone() Блок-схема
- 21. Функция FNtwo () Блок-схема
- 22. Блок-схема тела программы
- 23. Результат работы программы Режим кодирования: Вводимое слово: Hi, my name is Anya Ashaeva. I live in
- 24. Результат работы программы Режим кодирования: Вводимое слово: Hi, my name is Anya Ashaeva. I live in
- 25. Результат работы программы Режим кодирования: Вводимое слово: Hi, my name is Anya Ashaeva. I live in
- 26. Результат работы программы Режим декодирования: Вводимое слово: Ij. nz obnf jt Bozb Btibfwb) J mjwf jo
- 27. Результат работы программы Режим декодирования: Вводимое слово: Kc# bq jybz cl Yjqy Ylkyzay@ C xcaz cj
- 28. Результат работы программы Режим декодирования: Вводимое слово: Kc# bq jybz cl Yjqy Ylkyzay@ C xcaz cj
- 30. Скачать презентацию
Слайд 2Цели и задачи работы
Нынешнее программирование многогранно и используется в таких важных сферах
Цели и задачи работы
Нынешнее программирование многогранно и используется в таких важных сферах

Открытие машины Тьюринга привело к более глубокому познанию цифровых компьютеров и исчислений, включая понимание того, что существуют некоторые вычислительные проблемы, не решаемые на общих пользовательских ЭВМ.
Целью работы является реализация программы кодировщика\декодировщика на основе структуры Машины Тьюринга.
Слайд 3Содержание
Машина Тьюринга и Алан Тьюринг
Структура машины Тьюринга
Такт работы машины Тьюринга
Программа для машины
Содержание
Машина Тьюринга и Алан Тьюринг
Структура машины Тьюринга
Такт работы машины Тьюринга
Программа для машины

Пример
Описание алгоритма шифрования методом одноалфавитной подстановки
Реализация алгоритма шифрования методом одноалфавитной подстановки при помощи детерминированной машины Тьюринга . Постановка задачи.
Описание алгоритма симметричного шифрования методом перестановки.
Реализация алгоритма симметричного шифрования методом перестановки при помощи детерминированной машины Тьюринга
Заключение
Задача для реализации кодировщика\декодировщика на основе МТ
Функция Fnull()
Функция Fone()
Функция Ftwo ()
Функция FNnull()
Функция FNone()
Функция FNtwo ()
Блок-схема тела программы
Результат работы программы
Литература
Слайд 4Машина Тьюринга и Алан Тьюринг
Концепция абстрактной вычислительной машины была предложена Аланом Тьюрингом в 1936
Машина Тьюринга и Алан Тьюринг
Концепция абстрактной вычислительной машины была предложена Аланом Тьюрингом в 1936

Именно он показал возможность существования универсальной вычислительной машины (машины Тьюринга), способной выполнить любую эффективную процедуру.
Машина Тьюринга — это строгое математическое построение, математический аппарат, созданный для решения определенных задач. Этот математический аппарат был назван “машиной” по той причине, что по описанию его составляющих частей и функционированию он похож на вычислительную машину. Принципиальное отличие машины Тьюринга от вычислительных машин состоит в том, что ее запоминающее устройство представляет собой бесконечную ленту: у реальных вычислительных машин запоминающее устройство может быть как угодно большим, но обязательно конечным. Машину Тьюринга нельзя реализовать именно из-за бесконечности ее ленты. В этом смысле она мощнее любой вычислительной машины.
Слайд 5Структура машины Тьюринга
Машина Тьюринга (МТ) состоит из двух частей – ленты и
автомата:
Лента
Структура машины Тьюринга
Машина Тьюринга (МТ) состоит из двух частей – ленты и
автомата:
Лента

Автомат – это активная часть МТ. В каждый момент он размещается под одной из клеток ленты и видит её содержимое; это видимая клетка, а находящийся в ней символ – видимый символ; содержимое же соседних и других клеток автомат не видит. Кроме того, в каждый момент автомат находится в одном из предложенных состояний. Находясь в некотором состоянии, автомат выполняет какую-то определённую операцию (например, перемещается направо по ленте, заменяя все символы b на a), находясь в другом состоянии – другую операцию.
Автомат может выполнять три элементарных действия:
1) записывать в видимую клетку новый символ (менять содержимое других клеток автомат не может);
2) сдвигаться на одну клетку влево или вправо («перепрыгивать» сразу через несколько клеток автомат не может);
3) переходить в новое состояние.
Ничего другого делать автомат не умеет, поэтому все более сложные операции так или иначе должны быть сведены к этим трём элементарным действиям.
Слайд 6Такт работы машины Тьюринга
МТ работает тактами (по шагам), которые выполняются один за
Такт работы машины Тьюринга
МТ работает тактами (по шагам), которые выполняются один за

записывает некоторый символ S’ в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется);
2) сдвигается на одну клетку влево (обозначение – L, от left), либо на одну клетку вправо (обозначение – R, от right), либо остается неподвижным (обозначение – N).
3) переходит в некоторое состояние q’ (в частности, может остаться в прежнем состоянии).
Запись такта для конфигурации называют командой (машины Тьюринга).
Слайд 7Программа для машины Тьюринга
Сама по себе МТ ничего не делает. Для того
Программа для машины Тьюринга
Сама по себе МТ ничего не делает. Для того

работать, надо написать для неё программу. Эта программа
записывается в виде следующей таблицы:
Слева перечисляются все состояния, в которых может находиться автомат, сверху – все символы, которые автомат может видеть на ленте. На пересечениях же (в ячейках таблицы) указываются те такты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ. В целом таблица определяет действия МТ при всех возможных конфигурациях и тем самым полностью задаёт поведение МТ. Описать алгоритм в виде МТ – значит предъявить такую таблицу.
Слайд 8Программа для машины Тьюринга
Если входное слово пустое, то автомат может смотреть в
Программа для машины Тьюринга
Если входное слово пустое, то автомат может смотреть в

В результате автомат окажется в новой конфигурации. Теперь такие же действия повторяются, но уже для новой конфигурации: в таблице отыскивается ячейка, соответствующая состоянию и символу этой конфигурации, и выполняется такт из этой ячейки. И так далее. Когда завершается выполнение программы? Введём понятие такта останова. Это такт, который ничего не меняет: автомат записывает в видимую клетку тот же символ, что и был в ней раньше, не сдвигается и остается в прежнем состоянии, т.е. это такт S,N,q для конфигурации (S, q). Попав на такт останова, МТ, по определению, останавливается, завершая свою работу.
Правила выполнения программы: К началу выполнения программы машина Тьюринга находится в начальной конфигурации. Эта начальная конфигурация определена следующим образом. Во-первых, на ленте записано входное слово, к которому будет применена программа. Входное слово – это конечная последовательность символов, записанных в соседних клетках ленты. Во-вторых, автомат установлен в состояние q1 (указанное в таблице первым) и размещен под его первым (самым левым) символом входного слова:
Слайд 9Пример
Данная МТ позволяет заменить все «0» в слове на «1» и наоборот.
Пример
Данная МТ позволяет заменить все «0» в слове на «1» и наоборот.

Слово: 100011
Запись в ленту: «Λ q1100011 Λ»
Операции:
Λ q1100011 Λ -- Λ 0q200011 Λ -- Λ 01q10011 Λ -- Λ 011q2011 Λ -- Λ 0111q111 Λ -- Λ 01110 q21 Λ -- Λ 011100 q1 Λ -- Λ 01110 q00Λ
Результат: 011100
Слайд 10Описание алгоритма шифрования методом одноалфавитной подстановки
Есть алфавит, состоящий, к примеру, из символов «АБВГДЕ»
Описание алгоритма шифрования методом одноалфавитной подстановки
Есть алфавит, состоящий, к примеру, из символов «АБВГДЕ»

Слайд 11Реализация алгоритма шифрования методом одноалфавитной подстановки при помощи детерминированной машины Тьюринга .
Постановка
Реализация алгоритма шифрования методом одноалфавитной подстановки при помощи детерминированной машины Тьюринга . Постановка

У нас есть алфавит, состоящий из символов «antrkid». Нам необходимо написать программу для ИМТ, позволяющую зашифровать слово «antarktida» по ключу 1 или 2. В данном примере входящим словом для ИМТ будет являться «1antarktida» или «2antarktida» в зависимости от ключа шифрования. На выходе на ленте мы должны получить только зашифрованное слово («ntrnkirdan» и «trktidkant» для ключей 1 и 2 соответственно). «12antrkid» будет являться множеством допустимых входящих символов.
Теперь определимся с состояниями автомата:
а) q1 — автомат определяет, по какому ключу шифруется слово, и переходит в состояние q2 или q3;
б) q2 — автомат шифрует слово по ключу 1;
в) q3 — автомат шифрует слово по ключу 2.
Проверить работу программы можно в ИМТ, внеся в него следующие команды: 1q1->Bq2R, 2q1->Bq3R, aq2->nq2R, nq2->tq2R, tq2->rq2R, rq2->kq2R, kq2->iq2R, iq2->dq2R, dq2->aq2R, Bq2->BSTOPL, aq3->tq3R, nq3->rq3R, tq3->kq3R, rq3->iq3R, kq3->dq3R, iq3->aq3R, dq3->nq3R, Bq3->BSTOPL.
Слайд 12Описание алгоритма симметричного шифрования методом перестановки.
Данный алгоритм заключается в следующем. У нас есть слово,
Описание алгоритма симметричного шифрования методом перестановки.
Данный алгоритм заключается в следующем. У нас есть слово,

Слайд 13Реализация алгоритма симметричного шифрования методом перестановки при помощи детерминированной машины Тьюринга
Постановка задачи.
Реализация алгоритма симметричного шифрования методом перестановки при помощи детерминированной машины Тьюринга
Постановка задачи.

а) q1 — автомат определяет, какой символ необходимо напечатать, либо прекращает свою работу, если все символы напечатаны (не осталось символов, составляющих ключ);
б) q2–q5 автомат печатает соответствующий символ;
в) q6 — автомат возвращается в начало слова.
При использовании различных ключей, состоящих из символов «1234», будут выдаваться различные зашифрованные слова. Следует отметить, что для реализации шифрования более длинных слов, нужно лишь ввести новые состояния автомата для недостающих символов. А если длина шифруемого слова больше десяти, то ключ следует записывать в системе исчисления, которая позволяет записать каждый номер символа в одной клетке.
Слайд 14Заключение
МТ позволяет в полной мере реализовать простейшие алгоритмы шифрования, однако следует учитывать, что
Заключение
МТ позволяет в полной мере реализовать простейшие алгоритмы шифрования, однако следует учитывать, что

Слайд 15Задача для реализации кодировщика\декодировщика на основе МТ
Программы кодировщика\декодировщика на основе структуры Машины
Задача для реализации кодировщика\декодировщика на основе МТ
Программы кодировщика\декодировщика на основе структуры Машины

Для работы программы нужно:
1. выбрать и ввести режим программы;
2. ввести слово, которое нужно кодировать/декодировать на английском языке;
3. ввести ключ, который имеет входные символы «0», «1», «2», при этом машина должна работать при любом сочетании этих чисел.
Слайд 16Функция Fnull()
Блок-схема
Функция Fnull()
Блок-схема

Слайд 17Функция Fone()
Блок-схема
Функция Fone()
Блок-схема

Слайд 18Функция Ftwo ()
Блок-схема
Функция Ftwo ()
Блок-схема

Слайд 19Функция FNnull()
Блок-схема
Функция FNnull()
Блок-схема

Слайд 20Функция FNone()
Блок-схема
Функция FNone()
Блок-схема

Слайд 21Функция FNtwo ()
Блок-схема
Функция FNtwo ()
Блок-схема

Слайд 22Блок-схема тела программы
Блок-схема тела программы

Слайд 23Результат работы программы
Режим кодирования:
Вводимое слово: Hi, my name is Anya Ashaeva. I
Результат работы программы
Режим кодирования:
Вводимое слово: Hi, my name is Anya Ashaeva. I

Простейший ключ: 0
Результат кодирования: Ij. nz obnf jt Bozb Btibfwb) J mjwf jo uif djuz pg Ojaioz Opwhpspe) Fevdbujpo; OHUV obnfe bgufs Bmfltffw)
Слайд 24Результат работы программы
Режим кодирования:
Вводимое слово: Hi, my name is Anya Ashaeva. I
Результат работы программы
Режим кодирования:
Вводимое слово: Hi, my name is Anya Ashaeva. I

Простейший ключ: 1
Результат кодирования: Kc# bq jybz cl Yjqy Ylkyzay@ C xcaz cj ekz gceq tw Jcvkjq Jtautdtr@ Zrfgyectj^ JUEF jybzr ywezd Yxzmlzza@
Слайд 25Результат работы программы
Режим кодирования:
Вводимое слово: Hi, my name is Anya Ashaeva. I
Результат работы программы
Режим кодирования:
Вводимое слово: Hi, my name is Anya Ashaeva. I

Простейший ключ: 2
Результат кодирования: Uk* xp bvxr kd Vbpv Vduvrfv# K mkfr kb lur sklp jz Bkqubp Bjfwjojg# Rgesvlkjb& BWLE bvxrg vzlro Vmrndrrf#
Слайд 26Результат работы программы
Режим декодирования:
Вводимое слово: Ij. nz obnf jt Bozb Btibfwb) J
Результат работы программы
Режим декодирования:
Вводимое слово: Ij. nz obnf jt Bozb Btibfwb) J

Простейший ключ: 0
Результат декодирования: Hi, my name is Anya Ashaeva. I live in the city of Nizhny Novgorod. Education: NGTU named after Alekseev.
Слайд 27Результат работы программы
Режим декодирования:
Вводимое слово: Kc# bq jybz cl Yjqy Ylkyzay@ C
Результат работы программы
Режим декодирования:
Вводимое слово: Kc# bq jybz cl Yjqy Ylkyzay@ C

Простейший ключ: 1
Результат декодирования: Hi, my name is Anya Ashaeva. I live in the city of Nizhny Novgorod. Education: NGTU named after Alekseev.
Слайд 28Результат работы программы
Режим декодирования:
Вводимое слово: Kc# bq jybz cl Yjqy Ylkyzay@ C
Результат работы программы
Режим декодирования:
Вводимое слово: Kc# bq jybz cl Yjqy Ylkyzay@ C

Простейший ключ: 1
Результат декодирования: Hi, my name is Anya Ashaeva. I live in the city of Nizhny Novgorod. Education: NGTU named after Alekseev.