1610906280-c80d8404f2eaa01776b47d41b0f18e85 (Когабаев Лекции)

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮНОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТМеханико-математический факультетН. Т. КогабаевЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВУчебное пособиеНовосибирск2009УДК 510.5(075)ББК В12я73-1К 570Когабаев Н. Т. Лекции по теории алгоритмов: Учеб. пособие / Новосиб. гос.ун-т. Новосибирск, 2009. 107 с.ISBN 978-5-94356-799-5В настоящем учебном пособии изложены математические основы теории алгоритмов. Пособие отражает содержание лекций основного курса «Теория алгоритмов»,прочитанных автором для студентов 1-го курса механико-математического факультета НГУ и охватывает материал из нескольких областей математики, так или иначесвязанных с понятием алгоритма: теория автоматов и регулярных языков, машиныТьюринга и Шёнфилда, нормальные алгорифмы Маркова, классическая теория вычислимости, теория нумераций, теория сложности вычислений.Предназначено для студентов 1-го курса механико-математического факультетаНГУ, изучающих курс «Теория алгоритмов», а также для всех желающих познакомиться с основами упомянутых в пособии математических теорий.Рецензентканд.

физ.-мат. наук В. Н. ВласовИздание подготовлено в рамках выполнения инновационно-образовательной программы «Инновационные образовательные программы и технологии, реализуемыена принципах партнерства классического университета, науки, бизнеса и государства» национального проекта «Образование».ISBN 978-5-94356-799-5c Новосибирский государственный°университет, 2009c° Когабаев Н. Т., 2009ОглавлениеГлава I.

Предварительные сведения§ 1. Некоторые аксиомы теории множеств . . . . . . . . . . . . . . . . . . . .§ 2. Алфавиты и формальные языки . . . . . . . . . . . . . . . . . . . . . . .§ 3. Интуитивные свойства алгоритмов . . . . . . . . . . . . .

. . . . . . . .Глава II. Конечные автоматы и формальные§ 4. Детерминированные конечные автоматы .§ 5. Недетерминированные конечные автоматы§ 6. Свойства автоматных языков . . . . . . .§ 7. Регулярные языки . . . . . . . . . . . . . .§ 8. Определение формальных грамматик . . .§ 9. Свойства формальных грамматик . . . . .грамматики. . . . . . . . .. . . . . . . . ..

. . . . . . . .. . . . . . . . .. . . . . . . . .. . . . . . . . ...........................................4479......12121518232730Глава III. Формализации понятия вычислимой функции§ 10. Машины Шёнфилда . . . . . . . . . . . . . . . . . . . . .§ 11. Частично рекурсивные функции . . .

. . . . . . . . . . .§ 12. Рекурсивность некоторых функций и отношений . . . .§ 13. Кодирование машин Шёнфилда . . . . . . . . . . . . . .§ 14. Машины Шёнфилда vs Частично рекурсивные функции§ 15. Машины Тьюринга . . . . . . . . . . . . . . . .

. . . . .§ 16. Нормальные алгорифмы Маркова . . . . . . . . . . . . .§ 17. Тезис Чёрча . . . . . . . . . . . . . . . . . . . . . . . . .........................................................................343439424854596466Глава IV. Теория вычислимости§ 18. Теорема о неподвижной точке . . . . . . . . . .

.§ 19. Нумерации и алгоритмические проблемы . . . . .§ 20. Вычислимо перечислимые множества . . . . . . .§ 21. Универсальные функции . . . . . . . . . . . . . .§ 22. Единственность сильно универсальной функции.............................................686871758184.....888889939799Глава V. Теория сложности алгоритмов§ 23. О вычислительной сложности . . .

. . . .§ 24. Недетерминированные машины Тьюринга§ 25. Классы P и NP . . . . . . . . . . . . . . . .§ 26. NP-полные проблемы . . . . . . . . . . . .§ 27. Теорема Кука . . . . . . . . . . . . . . . . .Список литературы....................................................................................................106Глава IПредварительные сведения§ 1.Некоторые аксиомы теории множествВсе объекты, изучаемые в данном курсе, являются множествами. Множествами являются символы, алфавиты и языки. Множествами являются числа, кортежи и последовательности. Множествами являются предикаты, функции и операторы.

Дажеавтоматы, машины и алгоритмы, изучению которых посвящен настоящий курс, являются множествами.Для работы с множествами и формализации определенных понятий нам потребуются некоторые аксиомы теории множеств Цермело-Френкеля ZF. Теория ZF является формальной (синтаксической) теорией в языке с одним символом двухместногопредиката ∈ и символом равенства ≈. Однако мы будем формулировать понятияи аксиомы данной теории на естественном (общематематическом) языке. Подобная«нестрогость» не должна пугать читателя, поскольку при желании все формулировки можно «перевести» на формальный язык ZF, но в рамках данного курса в этомнет необходимости. Для более глубокого и подробного ознакомления с системой ZFможно порекомендовать книги [2], [3].Понятия множества и отношения принадлежности ∈ являются неопределяемыми через другие математические объекты. Неформально множество — это некоторая совокупность объектов A, отношение x ∈ A означает, что объект x являетсяэлементом совокупности A.

Мы также будем использовать термины семейство исовокупность для описания некоторых множеств.Определение. Говорят, что множество A является подмножеством множества B,и пишут A ⊆ B, если ∀x(x ∈ A → x ∈ B). Другими словами, A ⊆ B, если каждыйэлемент множества A является элементом множества B.Равенство двух множеств A и B определяется следующей аксиомой.Аксиома экстенсиональности: A = B тогда и только тогда, когда ∀x(x ∈ A ↔x ∈ B). Таким образом, множества A и B равны, если A ⊆ B и B ⊆ A.Следующая естественная аксиома постулирует существование наименьшего повключению множества.Аксиома пустого множества: существует пустое множество ∅, т. е. множество, не содержащее ни одного элемента.Следующие четыре аксиомы позволяют из одних множеств строить другие, болеесложные по своей структуре.Аксиома пары: если A и B — множества, то существует неупорядоченная пара{A, B}, составленная из этих множеств.§ 1.

Некоторые аксиомы теории множеств5Аксиома суммы: если A — множество, то существует множество ∪A = {x |x ∈ y для некоторого y ∈ A}, которое называется объединением множества A.Аксиома степени: если A — множество, то существует множество P (A) = {B |B ⊆ A} всех подмножеств множества A.Аксиома подстановки: если A — множество, а Φ(x, y) — некоторое условие намножества x, y такое, что для любого x существует не более одного y, удовлетворяющего условию Φ(x, y), то существует множество {y | Φ(x, y) для некоторогоx ∈ A}.Например, из аксиомы пустого множества, аксиомы пары и аксиомы суммы следует, что существуют множества ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}} и т. д.

(каждоеследующее состоит из всех предыдущих), эти множества мы будем называть натуральными числами и обозначать их соответственно через 0, 1, 2, 3 и т. д.Заметим, что используя только те пять аксиом «существования», которые сформулированы выше, можно получить лишь конечные множества. В частности, из этихпяти аксиом невозможно вывести, что «совокупность» всех натуральных чисел образует множество.

Для разрешения этого вопроса вводится следующаяАксиома бесконечности: существует множество ω = {0, 1, 2, 3, . . .} всех натуральных чисел.Теперь, располагая каноническим бесконечным множеством ω, можно строитьдругие бесконечные множества. В следующем определении вводятся стандартныетеоретико-множественные операции объединения, пересечения, разности и дополнения (до некоторого множества).Определение. Если A и B — множества, то их объединением называется множествоA ∪ B = {x | x ∈ A или x ∈ B}, пересечением — множество A ∩ B = {x | x ∈ A и x ∈B}, разностью — множество A \ B = {x | x ∈ A и x ∈/ B}.Если рассматриваемые множества являются подмножествами некоторого фиксированного множества U , то можно говорить о дополнении A = U \ A множества A(до множества U ).Объединением семейства множеств A называется множество ∪A = {x | ∃B ∈A(x ∈ B)}.

Пересечением непустого семейства множеств A называется множество∩A = {x | ∀B ∈ A(x ∈ B)}.Из перечисленных выше аксиом следует, что применяя эти операции к множествам, мы снова получаем множества. Например, если A, B — множества, то в силуаксиомы пары существует неупорядоченная пара {A, B}, а в силу аксиомы суммысуществует объединение A ∪ B = ∪{A, B}. Затем, используя аксиому подстановки, заключаем, что существует пересечение A ∩ B = {y | (y ∈ A и y ∈ B и y =x) для некоторого x ∈ A ∪ B}.Аксиома пары постулирует существование множества {a, b}. Однако порядок расположения элементов в паре формально никак не задается, поскольку {a, b} = {b, a}.Более того, если a = b, то пара {a, b} превращается в одноэлементное множество {a}.Чтобы все-таки упорядочить элементы пары, вводится следующееОпределение. Упорядоченной парой элементов a и b называется множество ha, bi ={{a}, {a, b}}.

В упорядоченной паре мы задаем строгий порядок расположения элементов: a — первый, b — второй. Следует различать ha, bi 6= {a, b}!6Глава I. Предварительные сведенияПредложение 1. Для любых элементов a, b, c, d имеет место: ha, bi = hc, di тогдаи только тогда, когда a = c и b = d.Доказательство. Предлагается читателю в качестве упражнения.Определение. Пусть n ∈ ω, n > 1. Упорядоченная n-ка (кортеж длины n) определяется по индукции: ha1 i = a1 , ha1 , . . . , an−1 , an i = hha1 , . .

. , an−1 i, an i.Пустое множество ∅ по определению называем кортежем длины 0.Следствие 2. ha1 , . . . , an i = hb1 , . . . , bn i тогда и только тогда, когда имеет местоa1 = b1 , . . . , an = bn .Доказательство. Следует из предыдущего предложения по индукции.Определение. Декартовым произведением множеств A1 , . . . , An называется множествоA1 × . . . × An = {ha1 , .

. . , an i | a1 ∈ A1 , . . . , an ∈ An }.n-ой декартовой степенью множества A называется множество An = |A × .{z. . × A}.При n = 0 по определению полагаем A0 = {∅}.nОпределение. Любое подмножество R ⊆ A1 × . . . × An называется отношением(предикатом) на множествах A1 , . . . , An . Если hx1 , . . .