введение в теорию сложности

Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» М.Г. АДИГЕЕВ ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ Методические указания для студентов механико-математического факультета Ростов–на–Дону 2004 г. 2 Печатается по решению учебно-методической комиссии механико-математического факультета РГУ от АННОТАЦИЯ В данных методических указаниях изложены основы теории сложности алгоритмов и вычислений. Указания составлены на основе лекций, читаемых автором для студентов механико-математического факультета, специализирующихся по кафедре алгебры и дискретной математики. Методические указания предназначены для студентов отделений «Прикладная математика» и «Защита информации» механико-математического факультета. Автор: Адигеев М.Г. © Адигеев М.Г., 2004 г. 3 ВВЕДЕНИЕ Теория сложности вычислений — бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы. Поэтому знакомство с основами теории сложности, безусловно, полезно любому, кто собирается серьезно заниматься практическим программированием или теоретическими исследованиями. Данные методические указания содержат изложение базовых понятий и основных результатов теории сложности и соответствуют первой части курса лекций, читаемого автором для студентов механико–математического факультета. В будущем планируется выпуск методических указаний по следующим частям (сводимость задач, NP-полнота; вероятностные алгоритмы; приложения в криптографии). 1 CЛОЖНОСТЬ АЛГОРИТМОВ Под