Минимум по специальности 05,13,11

petr1

13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
У кого-нибудь есть бомбы или ссылки на ответы в лит-ре?

petr1

ну где же вы, ВМКашники?

petr1

Вот на эти вопросы нужны ответы или источники ответов.
1. Математические основы программирования
Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции. Эквивалентность данных формальных моделей алгоритмов. Понятие об алгоритмической неразрешимости. Примеры алгоритмически неразрешимых проблем.
Понятие сложности алгоритмов. Классы P и NP. Полиномиальная сводимость задач. Теорема Кука об NP-полноте задачи выполнимости булевой формулы. Примеры NP-полных задач, подходы к их решению. Точные и приближенные комбинаторные алгоритмы.
Примеры эффективных (полиномиальных) алгоритмов: быстрые алгоритмы поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях (поиск в глубину и ширину, о минимальном остове, о кратчайшем пути, о назначениях).
Автоматы. Эксперименты с автоматами. Алгебры регулярных выражений. Теорема Клини о регулярных языках.
Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полной системы. Критерий полноты Поста. Минимизация булевых функций в классах нормальных форм.
Исчисление предикатов первого порядка. Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели. Теорема о полноте исчисления предикатов первого порядка.
Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества. Отношения частичного порядка. Теоретико-множественное и алгебраическое определения решетки, их эквивалентность. Свойства решеток. Булевы решетки. Полные решетки.
Формальные языки и способы их описания. Классификация формальных грамматик. Их использование в лексическом и синтаксическом анализе.
?-исчисление, правила редукции, единственность нормальной формы и правила ее достижения, представление рекурсивных функций.
Основы комбинаторного анализа. Метод производящих функций, метод включений и исключений. Примеры применения.
Коды с исправлением ошибок. Алфавитное кодирование. Методы сжатия информации.
Основы криптографии. Задачи обеспечения конфиденциальности и целостности информации. Теоретико-информационный и теоретико-сложностный подходы к определению криптографической стойкости. Американский стандарт шифрования DES и российский стандарт шифрования данных ГОСТ 28147-89. Системы шифрования с открытым ключом (RSA). Цифровая подпись. Методы генерации и распределения ключей.

976evil

Значительная часть покрывается http://www.ozon.ru/context/detail/id/1279571/
Метод производящих функций — первый том Кнута.
Лямбда-исчисление — Х. Барендрегт (русский перевод есть в электронном виде) http://ec3.images-amazon.com/images/P/0444875085.01._SS500_SCLZZZZZZZ_V1056443904_.jpg

petr1

спасибо
Оставить комментарий
Имя или ник:
Комментарий: