🗊Презентация Теория вычислений

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Теория вычислений, слайд №1Теория вычислений, слайд №2Теория вычислений, слайд №3Теория вычислений, слайд №4Теория вычислений, слайд №5Теория вычислений, слайд №6Теория вычислений, слайд №7Теория вычислений, слайд №8Теория вычислений, слайд №9Теория вычислений, слайд №10Теория вычислений, слайд №11Теория вычислений, слайд №12Теория вычислений, слайд №13Теория вычислений, слайд №14Теория вычислений, слайд №15Теория вычислений, слайд №16Теория вычислений, слайд №17Теория вычислений, слайд №18Теория вычислений, слайд №19Теория вычислений, слайд №20Теория вычислений, слайд №21Теория вычислений, слайд №22Теория вычислений, слайд №23Теория вычислений, слайд №24Теория вычислений, слайд №25Теория вычислений, слайд №26Теория вычислений, слайд №27Теория вычислений, слайд №28
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория вычислений. Доклад-сообщение содержит 28 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Введение в компьютерные науки ЛЕКТОР К.Т.Н. МОХОВ В. А. ГЛАВА 12. ТЕОРИЯ ВЫЧИСЛЕНИЙ
Описание слайда:
Введение в компьютерные науки ЛЕКТОР К.Т.Н. МОХОВ В. А. ГЛАВА 12. ТЕОРИЯ ВЫЧИСЛЕНИЙ

Слайд 2


Глава12: Теория вычислений 12.1 Функции и их вычисление 12.2 Машины Тьюринга 12.3 Универсальные языки программирования 12.4 Невычислимые функции 12.5 Сложность задач 12.6 Криптография с использованием открытых ключей
Описание слайда:
Глава12: Теория вычислений 12.1 Функции и их вычисление 12.2 Машины Тьюринга 12.3 Универсальные языки программирования 12.4 Невычислимые функции 12.5 Сложность задач 12.6 Криптография с использованием открытых ключей

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


Язык Bare Bones Bare Bones это простой , но универсальный язык. Операторы clear name; incr name; decr name; while name not 0 do; … end;
Описание слайда:
Язык Bare Bones Bare Bones это простой , но универсальный язык. Операторы clear name; incr name; decr name; while name not 0 do; … end;

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


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

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


Шифрование сообщения 10111 Шифрование ключей: n = 91 и e = 5 101112 = 2310 23e = 235 = 6,436,343 6,436,343 ÷ 91 имеет остаток от 4 410 = 1002 Таким образом, зашифрованная версия 10111 равняется100.
Описание слайда:
Шифрование сообщения 10111 Шифрование ключей: n = 91 и e = 5 101112 = 2310 23e = 235 = 6,436,343 6,436,343 ÷ 91 имеет остаток от 4 410 = 1002 Таким образом, зашифрованная версия 10111 равняется100.

Слайд 26


Дешифровка сообщения 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.
Описание слайда:
Дешифровка сообщения 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.13 Шифрование с использованием открытого ключа
Описание слайда:
Рисунок 12.13 Шифрование с использованием открытого ключа

Слайд 28


Рисунок 12.14 Установка системы шифрования открытого ключа RSA
Описание слайда:
Рисунок 12.14 Установка системы шифрования открытого ключа RSA

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию