Теоретическая информатика, Громкович Ю.

Теоретическая информатика, Громкович Ю.
 
  Этот учебник является введением в теоретическую информатику. При этом основное внимание в нём уделено разработке алгоритмических концепций. Учебник является существенной переработкой предыдущего написанного на немецком языке «Algorithmische Konzepte der Informatik»; on был создан на основе курса лекций, читавшихся автором в Университете Аахена по теоретическим основам информатики. Материал для курса лекций и соответствующих глав учебника был выбран таким образом. чтобы по-возможности соблюсти баланс между классическими основами информатики (сюда относятся теория автоматов, теория вычислимости и NP-полноты) и современными её темами (такими как аппроксимационные и рандомизированные алгоритмы, а также криптография).




Конечные автоматы.
Конечный автомат это самая простая вычислительная модель, рассматриваемая в теоретической информатике; его можно считать моделью специальных программ программ, решающих задачи без использования каких-либо переменных. Конечные автоматы работают в режиме реального времени в том смысле, что входное слово доступно только для чтения, только один раз и только слева направо, а вывод (результат работы) получается сразу после прочтения последнего входного символа.

Основная причина рассмотрения конечных автоматов в этой книге вовсе не введение в теорию автоматов, не изучение её главных результатов. Вместо этого данная глава преследует специальную «дидактическую» цель рассмотрение конечных автоматов даёт очень простой и ясный способ понимания процесса моделирования вычислений вообще. Введение основных понятий теоретической информатики при описании работы конечного автомата конфигурации, шага вычисления, процесса вычисления вообще, детерминизма, недетерминизма, моделирования работы автомата (с помощью другого автомата) даёт читателю интуитивное представление об общих, фундаментальных свойствах этих понятий, а также некоторый опыт работы с ними. А наличие у читателя такой интуиции и такого опыта помогает впоследствии например, упрощает понимание точных определений этих терминов в общих моделях алгоритмических вычислений.

ОГЛАВЛЕНИЕ.
1. Введение.
1.1. Что такое теоретическая информатика?.
1.2. Замечательная теория.
1.3. Студентам.
1.4. Структура книги.
2. Алфавиты, слова, языки, алгоритмические проблемы.
2.1. Цели и задачи главы.
2.2. Алфавиты, слова и языки.
2.3. Алгоритмические проблемы.
2.4. Сложность по Колмогорову.
2.5. Заключение.
3. Конечные автоматы.
3.1. Цели и задачи главы.
3.2. Различные варианты представления конечных автоматов.
3.3. Моделирование конечных автоматов.
3.4. Доказательства неразрешимости.
3.5. Недетерминизм.
3.6. Заключение.
4. Машины Тьюринга.
4.1. Цели и задачи главы.
4.2. Формальная модель машин Тьюринга.
4.3. Многоленточные машины Тьюринга и тезис Чёрча.
4.4. Недетерминированные машины Тьюринга.
4.5. Кодирование машин Тьюринга.
4.6. Заключение.
5. Теория вычислимости.
5.1. Цели и задачи главы.
5.2. Метод диагонализации.
5.3. Метод сводимости.
5.4. Теорем а Райса.
5.5. Проблема соответствий Поста.
5.6. Метод сложности по Колмогорову.
5.7. Заключение.
6. Теория сложности.
6.1. Цели и задачи главы.
6.2. Меры сложности.
6.3. Классы сложности. Класс Р.
6.4. Недетерминированные меры сложности.
6.5. Класс NP и проверка доказательств.
6.6. NP-полнота.
6.7. Заключение.
7. Алгоритмизация труднорешаемых задач.
7.1. Цели и задачи главы.
7.2. Псевдополиномиальные алгоритмы.
7.3. Аппроксимационные алгоритмы.
7.4. Алгоритмы локального поиска.
7.5. Алгоритм имитационной нормализации.
7.6. Заключение.
8. Рандомизация.
8.1. Цели и задачи главы.
8.2. Основы теории вероятностей.
8.3. Рандомизированный протокол связи.
8.4. Избыток свидетельств и проверка простоты числа.
8.5. Дактилоскопия и эквивалентность двух полиномов.
8.6. Заключение.
9. Теория связи и криптография.
9.1. Цели и задачи главы.
9.2. Классические криптографические системы.
9.3. Системы с открытым ключом и RSA-кодирование.
9.4. Цифровая подпись.
9.5. Доказательства с нулевым разглашением.
9.6. Проектирование объединённых сетей.
9.7. Заключение.
Список литературы.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теоретическая информатика, Громкович Ю. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по информатике :: информатика :: компьютеры :: Громкович