E-Book Overview
М.: Институт системного программирования РАН, 2012. – 8 с.
В основу настоящей программы положены следующие дисциплины: математические основы программирования; вычислительные машины, системы и сети; языки и системы программирования; технология разработки программного обеспечения; операционные системы; методы хранения и доступа к данным, организация баз данных и знаний; защита данных и программных систем. Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по управлению, вычислительной технике и информатике при участии Московского государственного университета им. М.В. Ломоносова, Московского авиационного института (государственного технического университета), Московского государственного энергетического института (технического университета) и Института системного программирования РАН.Содержание: Математические основы программирования. Вычислительные машины, системы и сети. Языки и системы программирования. Технология разработки программного обеспечения. Операционные системы. Методы хранения данных и доступа к ним. Организация баз данных и знаний. Защита данных и программных систем.
E-Book Content
РОССИЙСКАЯ АКАДЕМИЯ НАУК Федеральное государственное бюджетное учреждение науки Институт системного программирования Российской академии наук
«УТВЕРЖДАЮ» Директор ИСП РАН академик РАН, д.ф.-м.н., профессор ______________ В.П.Иванников «___»__________________ 2012 г.
ПРОГРАММА-МИНИМУМ кандидатского экзамена по специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» по физико-математическим и техническим наукам
Москва 2012
2
Введение В основу настоящей программы положены следующие дисциплины: математические основы программирования; вычислительные машины, системы и сети; языки и системы программирования; технология разработки программного обеспечения; операционные системы; методы хранения и доступа к данным, организация баз данных и знаний; защита данных и программных систем. Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по управлению, вычислительной технике и информатике при участии Московского государственного университета им. М.В. Ломоносова, Московского авиационного института (государственного технического университета), Московского государственного энергетического института (технического университета) и Института системного программирования РАН.
1. Математические основы программирования Понятие алгоритма и его уточнения: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции. Эквивалентность данных формальных моделей алгоритмов. Понятие об алгоритмической неразрешимости. Примеры алгоритмически неразрешимых проблем. Понятие сложности алгоритмов. Классы P и NP. Полиномиальная сводимость задач. Теорема Кука об NP-полноте задачи выполнимости булевой формулы. Примеры NPполных задач, подходы к их решению. Точные и приближенные комбинаторные алгоритмы. Примеры эффективных (полиномиальных) алгоритмов: быстрые алгоритмы поиска и сортировки; полиномиальные алгоритмы для задач на графах и сетях (поиск в глубину и ширину, о минимальном остове, о кратчайшем пути, о назначениях). Автоматы. Эксперименты с автоматами. Алгебры регулярных выражений. Теорема Клини о регулярных языках. Алгебра логики. Булевы функции, канонические формы задания булевых функций. Понятие полной системы. Критерий полноты Поста. Минимизация булевых функций в классах нормальных форм. Исчисление предикатов первого порядка. Понятие интерпретации. Выполнимость и общезначимость формулы первого порядка. Понятие модели. Теорема о полноте исчисления предикатов первого порядка. Отношения и функции. Отношение эквивалентности и разбиения. Фактор множества