Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Введение в компьютерные науки
Содержание
- 1. Введение в компьютерные науки
- 2. Глава12: Теория вычислений12.1 Функции и их вычисление12.2
- 3. ФункцииФункция: Соответствие между количеством входных и выходных
- 4. Функции (продолжение)Вычисление ФУНКЦИИ: Процесс определения выходной величины
- 5. Рисунок 12.1 Попытка отобразить функцию, которая преобразует измерения в ярдах в метры
- 6. Рисунок 12.2 Компоненты Машины Тьюринга
- 7. Операции Машины ТьюрингаВвод данных на каждом шагеСостояниеЗначение
- 8. Рисунок 12.3 Состояние Машины Тьюринга предназначенной для увеличения числа
- 9. 0-Тезис Черча-ТьюрингаЛюбая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга
- 10. Универсальный язык программированияЯзык, которым может быть выражено
- 11. 0-Язык Bare BonesBare Bones это простой ,
- 12. Рисунок 12.4 Программа для вычисления X и Y на Bare Bones
- 13. Рисунок 12.5 Выполнение инструкции «copy Today to Tomorrow» на Bare Bones
- 14. Проблема остановкиУчитывая кодированную версию любой программы, возвращает
- 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: Задача в классе
- 23. Рисунок 12.12 Графическое обобщение классификации задач
- 24. Криптография с использованием открытых ключейКлюч: Значение используемое
- 25. Шифрование сообщения 10111Шифрование ключей: n = 91
- 26. 0-Дешифровка сообщения 100Расшифровка ключей: d = 29,
- 27. Рисунок 12.13 Шифрование с использованием открытого ключа
- 28. Рисунок 12.14 Установка системы шифрования открытого ключа RSA
- 29. Скачать презентанцию
Глава12: Теория вычислений12.1 Функции и их вычисление12.2 Машины Тьюринга12.3 Универсальные языки программирования 12.4 Невычислимые функции12.5 Сложность задач12.6 Криптография с использованием открытых ключей
Слайды и текст этой презентации
Слайд 2Глава12: Теория вычислений
12.1 Функции и их вычисление
12.2 Машины Тьюринга
12.3 Универсальные
языки программирования
12.4 Невычислимые функции
12.5 Сложность задач
12.6 Криптография с использованием
открытых ключей
Слайд 3Функции
Функция: Соответствие между количеством входных и выходных значений набора двоичных
разрядов , так чтоб на каждое возможное входное значение было
назначено выходное .
Слайд 4Функции (продолжение)
Вычисление ФУНКЦИИ: Процесс определения выходной величины функции на основе
значения ее входной величины
Невычислимая ФУНКЦИЯ: Функция, которая не может быть
вычислена по любому алгоритму
Слайд 7Операции Машины Тьюринга
Ввод данных на каждом шаге
Состояние
Значение по текущей позиции
ленты
Действия на каждом шаге
Запись значения в текущую позицию ленты
Чтение шагов
/запись заголовковСмена состояния
Слайд 90-
Тезис Черча-Тьюринга
Любая функция, которая может быть вычислена физическим устройством, может
быть вычислена машиной Тьюринга
Слайд 10Универсальный язык программирования
Язык, которым может быть выражено решение любой вычислимой
функции
Примеры: “Bare Bones” и самые популярные языки программирования
Слайд 110-
Язык Bare Bones
Bare Bones это простой , но универсальный язык.
Операторы
clear
name;
incr name;
decr name;
while name not 0 do; … end;
Слайд 14Проблема остановки
Учитывая кодированную версию любой программы, возвращает 1, если программа
заканчиваются автоматически, или 0, если программа не является таковой.
Слайд 170-
Сложность задач
Время сложности: Количество требуемых для исполнения команд
Если не указано
иное «сложность» означает «время сложности»
Если алгоритм класса 0(lgn) более эффективен,
чем алгоритм класса 0(n), то алгоритм класса 0(n) является более сложным, чем алгоритм класса 0(lgn). То, что задача принадлежит к классу O(f(n)), равносильно утверждению о существовании ее решения (не обязательно лучшего), сложность которого равна 0(f(n)).
Слайд 20Рисунок 12.10 Иерархическое представление множества задач порожденных алгоритмом сортировки методом
слияния
Слайд 22P против NP
Класс P: Задача в классе Q(f(n)), где f(n)
является полиномом
Класс NP: Все задачи могут быть решены в недетерминированным
алгоритмом в полиноминальное времяНедетерминированный алгоритм = “алгоритм”, шаги которого не могут быть однозначно и полностью определены состоянием процесса
Больше ли класс NP чем класс P в настоящее время неизвестно
Слайд 24Криптография с использованием открытых ключей
Ключ: Значение используемое для шифровке и
дешифровке сообщения
Открытый ключ: Используется для шифровки сообщений
Секретный ключ: Используется для
дешифровки сообщенияRSA: Популярный криптографический алгоритм с открытым ключом
Опирается на (предполагаемую) неподатливость проблемы разложения больших чисел на множители
Слайд 25Шифрование сообщения 10111
Шифрование ключей: n = 91 и e =
5
101112 = 2310
23e = 235 = 6,436,343
6,436,343 ÷ 91 имеет
остаток от 4410 = 1002
Таким образом, зашифрованная версия 10111 равняется100.
Слайд 260-
Дешифровка сообщения 100
Расшифровка ключей: d = 29, n = 91
1002
= 410
4d = 429 = 288,230,376,151,711,744
288,230,376,151,711,744 ÷ 91 имеет остаток
232310 = 101112
Таким образом расшифрованная версия 100 является 10111.
