1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375)
Текст из файла
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮНОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТМеханико-математический факультетН. Т. КогабаевЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВУчебное пособиеНовосибирск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 , . . .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
