Теория вычислений

Июль 26, 2022

Главная
Информатика
Теория вычислений

Содержание

2. Глава12: Теория вычислений 12.1 Функции и их вычисление 12.2 Машины Тьюринга 12.3 Универсальные языки программирования 12.4
3. Функции Функция: Соответствие между количеством входных и выходных значений набора двоичных разрядов , так чтоб на
4. Функции (продолжение) Вычисление ФУНКЦИИ: Процесс определения выходной величины функции на основе значения ее входной величины Невычислимая
5. Рисунок 12.1 Попытка отобразить функцию, которая преобразует измерения в ярдах в метры
6. Рисунок 12.2 Компоненты Машины Тьюринга
7. Операции Машины Тьюринга Ввод данных на каждом шаге Состояние Значение по текущей позиции ленты Действия на
8. Рисунок 12.3 Состояние Машины Тьюринга предназначенной для увеличения числа
9. 0- Тезис Черча-Тьюринга Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга
10. Универсальный язык программирования Язык, которым может быть выражено решение любой вычислимой функции Примеры: “Bare Bones” и
11. 0- Язык Bare Bones Bare Bones это простой , но универсальный язык. Операторы clear name; incr
12. Рисунок 12.4 Программа для вычисления X и Y на Bare Bones
13. Рисунок 12.5 Выполнение инструкции «copy Today to Tomorrow» на Bare Bones
14. Проблема остановки Учитывая кодированную версию любой программы, возвращает 1, если программа заканчиваются автоматически, или 0, если
15. Рисунок 12.6 Тестирование программы само завершения
16. Рисунок 12.7 Доказательство неразрешимости проблемы остановки программным путем
17. 0- Сложность задач Время сложности: Количество требуемых для исполнения команд Если не указано иное «сложность» означает
18. Рисунок 12.8 Процедура MergeLists для слияний двух списков
19. Рисунок 12.9 Алгоритмы сортировки слиянием реализованный в виде процедуры MergeSort
20. Рисунок 12.10 Иерархическое представление множества задач порожденных алгоритмом сортировки методом слияния
21. Рисунок 12.11 График основных типов математических функций
22. P против NP Класс P: Задача в классе Θ(f(n)), где f(n) является полиномом Класс NP: Все
23. Рисунок 12.12 Графическое обобщение классификации задач
24. Криптография с использованием открытых ключей Ключ: Значение используемое для шифровке и дешифровке сообщения Открытый ключ: Используется
25. Шифрование сообщения 10111 Шифрование ключей: n = 91 и e = 5 101112 = 2310 23e
26. 0- Дешифровка сообщения 100 Расшифровка ключей: d = 29, n = 91 1002 = 410 4d
27. Рисунок 12.13 Шифрование с использованием открытого ключа
29. Скачать презентацию

Слайд 2

Глава12: Теория вычислений
12.1 Функции и их вычисление
12.2 Машины Тьюринга
12.3 Универсальные языки

программирования
12.4 Невычислимые функции
12.5 Сложность задач
12.6 Криптография с использованием открытых ключей

Слайд 3

Функции
Функция: Соответствие между количеством входных и выходных значений набора двоичных разрядов

, так чтоб на каждое возможное входное значение было назначено выходное .

Слайд 4

Функции (продолжение)
Вычисление ФУНКЦИИ: Процесс определения выходной величины функции на основе значения

ее входной величины
Невычислимая ФУНКЦИЯ: Функция, которая не может быть вычислена по любому алгоритму

Слайд 5

Рисунок 12.1 Попытка отобразить функцию, которая преобразует измерения в ярдах в

метры

Слайд 6

Рисунок 12.2 Компоненты Машины Тьюринга

Слайд 7

Операции Машины Тьюринга
Ввод данных на каждом шаге
Состояние
Значение по текущей позиции ленты
Действия

на каждом шаге
Запись значения в текущую позицию ленты
Чтение шагов /запись заголовков
Смена состояния

Слайд 8

Рисунок 12.3 Состояние Машины Тьюринга предназначенной для увеличения числа

Слайд 9

0-
Тезис Черча-Тьюринга
Любая функция, которая может быть вычислена физическим устройством, может быть

вычислена машиной Тьюринга

Слайд 10

Универсальный язык программирования
Язык, которым может быть выражено решение любой вычислимой функции
Примеры:

“Bare Bones” и самые популярные языки программирования

Слайд 11

0-
Язык Bare Bones
Bare Bones это простой , но универсальный язык.
Операторы
clear name;
incr

name;
decr name;
while name not 0 do; … end;

Слайд 12

Рисунок 12.4 Программа для вычисления X и Y на Bare Bones

Слайд 13

Рисунок 12.5 Выполнение инструкции «copy Today to Tomorrow» на Bare Bones

Слайд 14

Проблема остановки
Учитывая кодированную версию любой программы, возвращает 1, если программа заканчиваются

автоматически, или 0, если программа не является таковой.

Слайд 15

Рисунок 12.6 Тестирование программы само завершения

Слайд 16

Рисунок 12.7 Доказательство неразрешимости проблемы остановки программным путем

Слайд 17

0-
Сложность задач
Время сложности: Количество требуемых для исполнения команд
Если не указано иное

«сложность» означает «время сложности»
Если алгоритм класса 0(lgn) более эффективен, чем алгоритм класса 0(n), то алгоритм класса 0(n) является более сложным, чем алгоритм класса 0(lgn).
То, что задача принадлежит к классу O(f(n)), равносильно утверждению о существовании ее решения (не обязательно лучшего), сложность которого равна 0(f(n)).

Слайд 18

Рисунок 12.8 Процедура MergeLists для слияний двух списков

Слайд 19

Рисунок 12.9 Алгоритмы сортировки слиянием реализованный в виде процедуры MergeSort

Слайд 20

Рисунок 12.10 Иерархическое представление множества задач порожденных алгоритмом сортировки методом слияния

Слайд 21

Рисунок 12.11 График основных типов математических функций

Слайд 22

P против NP
Класс P: Задача в классе Θ(f(n)), где f(n) является

полиномом
Класс NP: Все задачи могут быть решены в недетерминированным алгоритмом в полиноминальное время
Недетерминированный алгоритм = “алгоритм”, шаги которого не могут быть однозначно и полностью определены состоянием процесса
Больше ли класс NP чем класс P в настоящее время неизвестно

Слайд 23

Рисунок 12.12 Графическое обобщение классификации задач

Слайд 24

Криптография с использованием открытых ключей
Ключ: Значение используемое для шифровке и дешифровке

сообщения
Открытый ключ: Используется для шифровки сообщений
Секретный ключ: Используется для дешифровки сообщения
RSA: Популярный криптографический алгоритм с открытым ключом
Опирается на (предполагаемую) неподатливость проблемы разложения больших чисел на множители

Слайд 25

Шифрование сообщения 10111
Шифрование ключей: n = 91 и e = 5
101112

= 2310
23e = 235 = 6,436,343
6,436,343 ÷ 91 имеет остаток от 4
410 = 1002
Таким образом, зашифрованная версия 10111 равняется100.

Слайд 26

0-
Дешифровка сообщения 100
Расшифровка ключей: d = 29, n = 91
1002 =

410
4d = 429 = 288,230,376,151,711,744
288,230,376,151,711,744 ÷ 91 имеет остаток 23
2310 = 101112
Таким образом расшифрованная версия 100 является 10111.

Слайд 27

Теория вычислений

Содержание

Глава12: Теория вычислений12.1 Функции и их вычисление12.2 Машины Тьюринга12.3 Универсальные языки

ФункцииФункция: Соответствие между количеством входных и выходных значений набора двоичных разрядов

Функции (продолжение)Вычисление ФУНКЦИИ: Процесс определения выходной величины функции на основе значения

Рисунок 12.1 Попытка отобразить функцию, которая преобразует измерения в ярдах в

Рисунок 12.2 Компоненты Машины Тьюринга

Операции Машины ТьюрингаВвод данных на каждом шагеСостояниеЗначение по текущей позиции лентыДействия

Рисунок 12.3 Состояние Машины Тьюринга предназначенной для увеличения числа

0-Тезис Черча-ТьюрингаЛюбая функция, которая может быть вычислена физическим устройством, может быть

Универсальный язык программированияЯзык, которым может быть выражено решение любой вычислимой функцииПримеры:

0-Язык Bare BonesBare Bones это простой , но универсальный язык.Операторыclear name;incr