Рабочая программа по дисциплине «теория сложности алгоритмов и вычислений» для специальности 010200 Прикладная математика и информатика Форма обучения: очная icon

Рабочая программа по дисциплине «теория сложности алгоритмов и вычислений» для специальности 010200 Прикладная математика и информатика Форма обучения: очная


Смотрите также:
Программа обучения студентов (Syllabus) по дисциплине «Теория алгоритмов» для специальности...
Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика...
Рабочая программа по курсу “Теория компиляции.” ( наименование дисциплины по учебному плану )...
Программа дисциплины дс. 11...
Программа дисциплины дс...
Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика (по...
Рабочая программа по курсу “Дискретная математика” ( наименование дисциплины по учебному плану )...
Методические указания по выполнению курсовых проектов...
Рабочая программа по дисциплине «Методы и средства защиты компьютерной информации» для...
Рабочая программа по дисциплине «Теория вычислительных процессов» для направления 010500...
Рабочая программа По дисциплине “Методы оптимизации Для направления 010500 «Прикладная...
Программа подготовки бакалавров...



Загрузка...
скачать
Федеральное агентство по образованию


ГОУ ВПО «Удмуртский государственный университет»


факультет Информационных технологий и

вычислительной техники


кафедра Теоретических основ информатики


РАБОЧАЯ ПРОГРАММА


по дисциплине


«ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ И ВЫЧИСЛЕНИЙ»


для специальности


010200 Прикладная математика и информатика


Форма обучения: очная



Курс

4

Семестр

8

Всего часов

90

Всего аудиторных часов

48

Лекции, час.

32

Лабораторные занятия, час.

16

Самостоятельная работа, час.

42

Экзамен, номера семестров

8

Зачет, номера семестров

-

Другие виды контроля:

дом. задание, семестр



-




Ижевск

2009

Рабочая программа составлена на основании ГОС ВПО специальности 010200 «Прикладная математика и информатика» (квалификация – математик, системный программист), утвержденного в 2000 г.


Составитель рабочей программы

д.ф-м.н., профессор ________________ А.П.Бельтюков


Рабочая программа утверждена на заседании кафедры

«___» ______________ 2009 г.


Заведующий кафедрой ___________________ А.П.Бельтюков

д.ф-м.н., профессор


Одобрено методической комиссией

«___» _______________ 2009 г.


Председатель методической комиссии ______________________В.И.Родионов


Декан факультета _____________________В.И.Родионов


Рекомендации Computing Curricula 2001: Computer Science


Темы


Основы анализа алгоритмов

Распределенные алгоритмы

Основы теории вычислимости

Классы сложности P и NP

Теория автоматов

Углубленный анализ алгоритмов

Параллельные алгоритмы


Введение


Теория алгоритмов и сложности является основой информатики и

программной инженерии. Фактическая производительность

программной системы зависит от двух факторов: (1) применяемых в

ней алгоритмов и (2) эффективности реализации на различных

уровнях. Поэтому разработка хорошего алгоритма имеет решающее

значение для любой программной системы. Кроме того, изучение

алгоритмов позволяет более глубоко вникнуть в задачу и может

подсказать методы решения, не зависящие от языка

программирования, парадигмы программирования, аппаратного

обеспечения и других аспектов реализации.


Важной основной частью знаний в области информатики является

способность выбрать алгоритм, подходящий для решения данной

задачи, или доказать, что такого алгоритма не существует. Эта

способность основывается на знании класса алгоритмов, которые

предназначены для решения определенного набора известных задач,

понимании их сильных и слабых сторон, применимости различных

алгоритмов в данном контексте. Эффективность является важнейшим

вопросом в данной области



  1. Требования

государственного образовательного стандарта (ГОС)

по специальности 010200 – Прикладная математика и информатика


Индекс

Наименование дисциплины

Всего часов

ОПД.В.02.2
^

Теория СЛОЖНОСТИ АЛГОРИТМОВ и вычислений


Требования федерального компонента отсутствуют.

Требования вузовского компонента:

классическая теория (идеальной) вычислимости,

теория сложности вычислений,

теория сложности алгоритмов (дескриптивной сложности),

структурная теория сложности (одновременный учет

ограничений, рассматриваемых в разделах теория сложности вычислений и теория сложности алгоритмов).

90 час.


Курс входит в раздел: национально-региональный (вузовский) компонент


  1. ^ Принципы построения


Традиционно результаты данной науки относятся к следующим

разделам:


(1) классическая теория (идеальной) вычислимости,

(2) теория сложности вычислений,

(3) теория сложности алгоритмов (дескриптивной сложности),

(4) структурная теория сложности (одновременный учет

ограничений, рассматриваемых в разделах (2) и (3)).


Непосредственно наиболее близок к практике раздел (4).

Более того, все классические результаты предыдущих разделов

в настоящее время нетрудно трансформировать в результаты

раздела (4). Классические результаты необходимо, тем не менее,

изучать, во-первых, с целью получения общей культуры в знании

данного вопроса и его истории, во-вторых, - потому что

результаты первых разделов проще для изложения и могут быть

использованы для постепенного перехода к более сложным

вопросам. Однако, стоит подчеркнуть, что некоторые факты,

изучаемые в первых разделах носят неадекватный характер с точки

зрения практического применения. Наиболее яркие примеры этого:


- идеальная вычислимость ничего не говорит о практической

вычислимости, например, разрешимость множества истинных формул

ограниченной арифметики на поверку означает, что в настоящее

время мы обладаем разрешающим алгоритмом, даже не являющимся

элементарным по Кальмару, а выполнение его для некоторых формул,

запись которых, например, в системе TeX, занимает всего 1000

байт, параллельно на всех компьютерах, имеющихся сейчас в мире,

займет время, гораздо большее, чем время, прошедшее с

гипотетического "Большого взрыва" при образовании наблюдаемой

Вселенной;


- идеальная невычислимость может также означать только

отсутствие алгоритма, охватывающего все математически идеальное

бесконечное множество возможных аргументов функции, тогда как на

практике нужно вычислять определенную функцию только для

относительно небольших значений аргумента (хотя практически

идеальная невычислимость может быть и полезна: она

предотвращает появление совсем уж некорректных постановок

задач);


- асимптотический характер большинства традиционных сложностных

результатов также неадекватен: асимптотически время работы

n(log_2 n)^2 считается хуже, чем время работы 10000 n log_2 n,

но те длины входных данных (n), при которых первое время

действительно становится хуже, неосуществимы в наблюдаемой

нами части Вселенной с помощью известных нам физических

эффектов; и наоборот, время работы 1.0001^{n^0.0001} с точки

зрения асимптотики должно считаться очень плохим: почти

экспоненциальным, но реальный его рост начинается также с

совершенно неосуществимых n: больше 10000^{10000};


- традиционные модели вычислимости: машины Тьюринга, нормальные

алгоритмы и т.п., - очень далеки от практики, когда речь

заходит о конкретных (не асимптотических и даже иногда -

асимптотических) сложностных характеристиках вычислений;

относительно адекватной в этом отношении является модель РАМ.


Можно привести и массу других замечаний в этом же роде. Все это

говорит о том, что следует пересмотреть традиции преподавания

теории алгоритмов и сложности.


Предлагается сделать следующее.


Во-первых, надо взять три вида базовых моделей вычислений (три

вида нужны для иллюстрации тезиса Черча):


- равнодоступные адресные машины с сохраняемой в памяти

программой (РАСП), кроме всего прочего, это еще и математически

точная иллюстрация архитектуры Фон-Неймана (можно ее развить и

до параллельной архитектуры ПРАСП, что сейчас актуально);

иллюстрация методов программирования на такой модели заодно

является и экскурсом в историю информатики; для изучения

сложностных ограничений вычислимости изучается практически

точная модель семейств реальных компьютеров с сокращенным

набором команд: ограниченные РАСП (и ПРАСП) - ОРАСП (и ОПРАСП),

на которые накладываются ограничения по используемым

диапазонам адресов и чисел вообще; эти модели очень удобны для

того, чтобы приводить примеры практической относительной

неразрешимости, когда даются задачи, которые в идеале, вообще

говоря, можно решить алгоритмически, но для некоторых конкретных

сложностных ограничений они становятся неразрешимыми;


- для иллюстрации свойств замкнутости классов (ограниченной)

вычислимости удобно в качестве примера модели привести

определение вычислимости на основе идеального языка; лучше

всего для этой цели подходят идеализированные подмножества

реальных наиболее традиционных алгоритмических языков,

например, pascal и C (можно подобрать даже подходящее

"семантическое пересечение" этих языков); заодно это помогает

студентам понять, что представляет собой "ядро" этих языков,

избавившись от вторичных деталей; наиболее удачными

представляются чисто арифметические языки (работающие с

натуральными или целыми числами) и "структурные" языки,

работающие с бинарными деревьями или термами; возможно и

наложение сложностных ограничений на используемые данные;

арифметический язык удобно использовать для построения

ИНТЕРПРЕТАТОРА (универсального алгоритма) для РАСП (ОРАСП) и

эта конструкция удобно с самого начала излагается в сложностной

форме; меры сложности для этой модели - более грубые, чем для

РАСП, но легче поддаются оценке;


- в любом случае необходимы модели, основанные на рекурсивных

схемах: числовых, словарных и структурных (на термах); эти

модели - наиболее традиционные математические конструкции (с

точки зрения остальной математики); кроме того, с точки зрения

иллюстрации тезиса Черча, рекурсивые схемы могут

проиллюстрировать алгоритмы преобразования программ на

идеальных алгоритмических языках в программы РАСП; это также

является иллюстрацией понятия компилятора и одним из его

простейших примеров; рекурсивные схемы удобно определить так,

что они окажутся в результате сужением идеального

алгоритмического языка (который должен содержать подпрограммы,

в том числе и рекурсивные); семантика идеального

алгоритмического языка также удобно определяется через рекурсию

(возможно и преобразование - компиляция идеальных программ в

рекурсивные схемы).


В качестве вспомогательных моделей вычислимости с

ограниченной сложностью берутся модели, основанные на схемах из

логических элементов и на конечных автоматах (модель конечных

автоматов полезна в виду ее широкой известности и практического

использования многих связанных с ней понятий). Модели на схемах

из логических элементов нужны для получения конкретных примеров

задач большой сложности.


Во-вторых, излагаемые результаты должны сразу даваться и в

конкретном сложностном варианте, как можно более близком к

практике. Например, приводится не просто пример неразрешимого

множества, а излагается способ определения множеств,

неразрешимых при заданных сложностных ограничениях (и

разрешимых при других - более слабых ограничениях). При этом,

если быть ближе к практике, то фактически получается некоторое

комбинированное ограничение на размер программы, размер

используемой памяти и время работы. Надо подчеркнуть при этом,

что есть некоторый разрыв между нижними теоретическими

границами сложности и верхними практическими, более того, мы не

знаем, что будет происходить при ослаблении только ОДНОГО

ограничения - мы знаем, лишь, что если одновременно ослабить

ВСЕ (хотя и относительно немного), то задача из разряда

неразрешимых перейдет в разряд разрешимых.


В-третьих нужно с крайней осторожностью относиться к полным

задачам классов, для которых достаточно эффективные

универсальные разрешающие процедуры неизвестны: таким, как

NP-полные проблемы. Для многих из NP-полных задач известны

очень сложные сводимости к ним классически трудных задач. В

подобных случаях нужно анализировать не асимптотическую

сложность сводимости, а конкретные относительные границы

сложности вычислений: сводимость может быть настолько сложной,

что окажется бесполезной с практической точки зрения. С другой

стороны, иногда сама формулировка задачи в этом случае

оказывается непрактичной: например, задача о рюкзаке с

"суперастрономической" точностью. Следует заметить, что

результаты об относительной неразрешимости, хотя и в любом

случае негативны, но могут обладать "здоровым" и "нездоровым"

негативизмом. В первом случае мы строго обосновали конкретные

ограничения, во втором - ссылаемся на то, что задачу никто

еще не решил. От вторых формулировок следует избавляться,

заменяя их на относительные оценки сложности.



  1. ^ Цели курса


Общие требования к курсам по теории алгоритмов и сложности

для специалистов по информатике

(разработаны на основе кн.: "Рекомендации по преподаванию

информатики в университетах" / Пер. с англ., С.-Петербург:

Изд-во СПбГУ, 2002)


Основная цель преподавания Теории алгоритмов и сложности для

будущих специалистов по информатике - дать им инструмент для

установления границ, при переходе за которые формулировки

задач по программированию становятся некорректными: задачи

становятся или неразрешимыми даже в принципе (в идеале), или

неразрешимыми с учетом конкретной возможности использования

вычислительных ресурсов. В свете этого некоторые традиции в

изложении этой науки в академической литературе нуждаются в

пересмотре для того, чтобы излагаемые результаты

формулировались в виде пригодном для их практического

применения без приложения дополнительных теоретических усилий.



  1. ^ Учебно-тематический план





Тема


^ Количество часов

Лекц

Лаб.

Сам

1

Математическая логика и теория алгоритмов

2

1

3

2

Виды алгоритмов

2

1

3

3

Магазинные автоматы. Нормальные алгоритмы. Регистровые машины

2

1

3

4

Равнодоступные адресные машины (РАМ)

2

1

3

5

Примитивно рекурсивные, частично-рекурсивные и общерекурсивные функции

2

1

3

6

Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов

2

1

3

7

Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса.

2

1

3

8

Программа машины Джонса как структура данных

2

1

3

9

Разрешимые и неразрешимые множества.

Перечислимые и неперечислимые множества

2

1

3

10

Элементарные по Кальмару функции

2

1

3

11

Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности

2

1

3

12

Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи

2

1

3

13

On-line - вычисления, вычисления в реальное время

2

1

3

14

Автоматные вычисления. Регулярные множества

2

1

3

15

Регулярность автоматных и автоматность регулярных множеств

2

1

3

16

Связь логики и вычислимости

2

1

3


































  1. ^ Содержание лекционных занятий


Лекция 1. Математическая логика и теория алгоритмов


Виды алгоритмов:

машины Тьюринга: многоленточные, многоголовочные машины,

многомерные ленты, квазибесконечномерность лент*),

ленты с неевклидовой топологией*), древовидные ленты,

эластичные ленты - К-алгоритмы*).


*) - дополнительные вопросы


Структура одноленточной одноголовочной (классической)

машины Тьюринга (МТ):

1) ленточный алфавит: конечное множество "букв" Б=

{б[0],б[1],...,б[d]}, нумерация букв ленточного алфавита

(буквы как натуральные числа): б[i]=i;

2) пробел: элемент ленточного алфавита - пустая буква " "=б[0];

3) алфавит (множество) состояний: конечное множество Q=

{q[0],q[1],...,q[n]}, состояния как натуральные числа q[i]=i;

4) начальное состояние: элемент множества состояний q[1]=1;

5) заключительное состояние: элемент множества состояний q[0]=0;

6) алфавит сдвигов Д={l,s,r};

7) "сдвиг на одну ячейку влево": l;

8) "сдвиг на одну ячейку вправо": r;

9) "отсутствие сдвига": s;

10) функция перехода ф, отображающая Б*(Q\q[0]) в Б*Q*Д,

таблица функции перехода.


Работа одноленточной двусторонней одноголовочной МТ:

1) входние слово: w[1]w[2]...w[n], w - отображение 1..n в Б;

2) моменты времени: N={0,1,2,...} - натуральные числа;

3) номера ячеек Z={...,-2,-1,0,1,2,...} - целые числа;

4) содержимое ленты: л - отображение N*Z в Б;

5) начальное содержимое ленты: л[0,i]=б[0] при i=0,-1,-2,... и i=n+1,n+1,...

л[i]=w[i] при i=1,2,...n.

6) результат: слово, записанное справа от головки до первого пробела

в конце работы.


Пример программы (таблицы функции перехода) сложения в "палочковой"

(монадической) системе счисления:

----------------

| | | + | |

---|---|---|---|

1 | 2r| 0r| 0s|

---|---|---|---|

2 ||2r||3l| 3l|

---|---|---|---|

3 ||3l|+3l| 0r|

----------------


Протокол работы этой МТ на входном слове "||+|||":

||+|||

1

|+|||

2

|+|||

2

|||||

2

|||||

2

|||||

0


Контрольный вопрос

Что делает следующая машина Тьюринга:


----------------

| a | b | |

---|---|---|---|

1 | 2r| 0r| 0s|

---|---|---|---|

2 |a2r|b2r| 3l|

---|---|---|---|

3 | 4l|a5l| 0s|

---|---|---|---|

4 |a4l|b4l| 1r|

---|---|---|---|

5 |a5l|b5l| 0r|

----------------


Протокол aaba ?

Результат abaa , aba ?


^ Лекция 2. Виды алгоритмов


Алгоритмы Колмогорова-Успенского.

К-алгоритм - частный случай КУ-алгоритма.

Многомагазинный автомат.


Алгоритм как математическая конструкция.

U - множество конструктивных объектов.

T - конечное множество их локальных преобразований

T - подмножество отображений из U в U.

C - множество признаков C - подмножество отображений из U в {0,1}.

Пусть i,f,o:T, c:C, x:I.

Тогда (i,f,c,o)(x)=(y:=i(x);while(c(y))y:=f(y);o(y))

т.е.

(i,f,c,o)(x)=o(f*(min({j=1,..,N-1|c(f*j(i(x))=1})))


Рассмотрим случай, когда конструктивные объекты - деревья/

скобочные структуры.

Локальные преобразования скобочных структур.


Контрольные вопросы


Пусть К-алгоритм f=

(

qa - aaq

qb - bq

q. - qq.

aqq - qqa

bqq - qqbb

.qq - .

).

Чему равно f(abba)?

Что делает этот алгоритм в общем случае?

Напишите алгоритм, удваивающий число в монадической системе

счисления.


^ Лекция 3. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины


Правила (подстановки) магазинных автоматов:

a1,a2,...,an - w1,w2,...,wn

(ai - не более, чем однобуквенные слова).


Нормальные алгоритмы (НА) Маркова.

Нормальны алгоритм - последовательности (подстановок) вида

f=(u[1] - e[1] v[1];

u[2] - e[2] v[2];

...

u[n] - e[n] v[n])

где v[i], u[i] принадлежат Б* - слова в алфавите Б, e[i]=. или

пустое слово

(".", "-", ";" не принадлежит Б). Применение алгоритма f к

слову w состоит в замене w на слово xv[i]y, при наименьшем i,

для которого слово w представимо в виде xu[i]y. При этом для

данного i длина слова x также берется наименьшей. Если e[i]

пусто, то процесс на этом заканчивается, иначе - продолжается

снова по этому же правилу (находится наименьшее i, а для него -

наименьшее x, при которых уже вновь полученное слово представимо

в виде xu[i]y, и производится соответствующая замена u[i] на

v[i] и т.д.).


Пример. Алгоритм вычисления модуля разности в монадической системе

счисления (заменяет слово x*y, где слова x и y состоят из m и n

палочек соответственно, на слово, содержащее из |m-n| палочек,

то есть слово вида xy*y - на x, а слово вида x*xy - на y, где

x,y:{|}* ):

absdiff=(|*| - *; * -.).


Протокол работы алгоритма absdiff на слове ||||*||:

||||*|| - |||*| - ||* - ||.


Протокол работы алгоритма absdiff на слове ||*||||:

||*|||| - |*||| - *|| - ||.


Регистровые машины. Определение. Примеры.


Контрольный вопрос:

Напишите НА, складывающий любое количество натуральных чисел в монадической системе счисления.


^ Лекция 4. Равнодоступные адресные машины (РАМ)


Структура РАМ:

Входной поток: x[1],x[2],... (входные данные)

Указатель входного потока: i

(Возможное видоизменение: размер входного потока: n: x[1],...,x[n].)

Начальное значение указателя входного потока: 1

Текущее значение входного потока (входное значение): x[i]

Выходной поток: y[1],y[2],... (ячейки для выхоых данных)

Указатель выходного потока: j

Начальное значение указателя выходного потока: 1

Текущее значение выходного потока (выводимое значение): y[j]

Оперативная память: r[0],r[1],r[2],... (регистры)

Аккумулятор (сумматор): r[0]

Программа: 1: I[1];

2: I[2];

...

(команды)

Начальное содержимое памяти: нули

Структура команды: код_операции модификатор операнд

Коды операций:

LOAD - загрузка сумматора,

STORE - запоминание сумматора,

ADD - сложение,

SUBT - вычитание,

JGTZ - переход по положительному значению,

READ - чтение,

WRITE - запись,

HALT - остановка.

Коды дополнительных операций:

JUMP - переход,

JZERO - переход по нулю,

MULT - умножение,

DIV - деление.

Машины с умножением: MRAM

Модификаторы: =, пробел, *

Операнд: числовая константа

(Основной) Тип данных: натуральные числа

(Вариант - работа с целыми числами и др.)


Система команд РАМ:


Команда Комментарий


LOAD = a r[0]:=a

LOAD a r[0]:=r[a]

LOAD * a r[0]:=r[r[a]]

STORE a r[a]:=r[0]

STORE * a r[r[a]]:=r[0]

ADD = a r[0]:=r[0]+a

ADD a r[0]:=r[0]+r[a]

ADD * a r[0]:=r[0]+r[r[a]]

SUBT = a r[0]:=r[0]-.a

где x-.y = max{0,x-y}, если работаем с натуральными числами

SUBT a r[0]:=r[0]-.r[a]

SUBT * a r[0]:=r[0]-.r[r[a]]

(MULT = a r[0]:=r[0]*a

MULT a r[0]:=r[0]*r[a]

MULT * a r[0]:=r[0]*r[r[a]]

DIV = a r[0]:=r[0]/.a

где x/.y - целая часть частного от деления x на y и 0, если y=0

DIV a r[0]:=r[0]/.r[a]

DIV * a r[0]:=r[0]/.r[r[a]]

JUMP m go to m

JZERO m if r[0]=0 then go to m

)

JGTZ m if r[0] > 0 then go to m

READ a r[a]:=x[i];i:=i+1

READ * a r[r[a]]:=x[i];i:=i+1

(возможное видоизменение команды READ:

READ m if i > n then go to m; r[0]:=x[i]; i:=i+1)

WRITE = a y[j]:=a;j:=j+1

WRITE a y[j]:=r[a];j:=j+1

WRITE * a y[j]:=r[r[a]];j:=j+1

HALT остановка, используется при работе в режиме offline,

операнд отсутствует, в режиме online остановка происходит при исчерпании

данных во время выполнения операции READ - при i, большем n.


Примеры РАМ-программ


1. Сложение 2-х чисел: y[1]=x[1]+x[2]:


1: READ 1

2: READ 0

3: ADD 1

4: WRITE 0

5: HALT


2. Сложение n=x[1] чисел: y[1]=x[2]+x[3]+...+x[1+x[1]]:


READ 1

loop: JZERO out

READ 0

ADD 2

STORE 2

JUMP loop

out: WRITE 2

HALT


3. Инверсия (выдача в обратном порядке) n чисел:

y[1]=x[1+x[1]],

y[2]=x[x[1]],

...,

y[i]=x[2+x[1]-i]

...,

y[x[1]]=x[2]:


LOAD = 3

STORE 2

READ 1

LOAD 1

loop: JZERO out

READ * 2

LOAD 2

ADD = 1

STORE 2

LOAD 1

SUBT = 1

STORE 1

JUMP loop

out: LOAD 2

SUBT = 1

STORE 2

SUBT = 2

JZERO end

^ WRITE * 2

JUMP out

end: HALT


Контрольный вопрос

Пусть f=

(

READ 0

STORE 1

READ 0

ADD 1

MULT 1

WRITE 0

HALT

).

Чему равно f(2,2), f(5,8), f(x,y) (написать выражение)?


РАМ с хранимой программой.


^ 5. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции


Базисные функции (B):

I[n,k](x[1],...,x[n])=x[k] при k=1,...,n (другая запись Ink);

Z(x)=0 (другая запись Z=O или Z=0);

S(x)=x+1;


Операторы над (частичными натуральнозначными) функциями

(натуральных аргументов):


суперпозиция o: при любых m-местной f, n-местных g,

натуральных векторах X

fo(g[1],...,g[m])(X)=f(g[1](X),...,g[m](X)), где (X)=(x[1],...,x[n])

(n-мерный натуральный вектор),

если правая часть равенства неопределена, то левая также неопределена,

другая запись: fo(G)=f(G);


(примитивная) рекурсия R: при любых n-местной g, n+2-местной h

f=gRh - n+1-местная функция, это равенство означает, что при

любых n-мерных натуральных векторах X и при любом натуральном y

выполнены два следующих равенства:

f(X,0)=g(X)

f(X,y+1)=h(X,y,f(X,y))

(если правая часть неопределена, то левая также неопределена);

другая запись: f=R(g,h);


операция нахождения наименьшего корня (операция минимизации) mu:

для любой n+1-местной функции M(f) -

Mf(X)=min{y|f(X,y)=0}

(если правая часть неопределена, то левая также неопределена)


Примитивно рекурсивные функции (ПРФ) как замыкание множества B

относительно операций о и R.


Примеры ПРФ:

+: x+0=x

x+(y+1)=S(x+y)

+=R(I11,S(I33))

*: x0=0

x(y+1)=xy+x

*=R(Z,+(I33,I31))

**: x**0=1

x**(y+1)=(x**y)x

**=R(S(Z),*(I33,I11))

***: x***0=1

x***(y+1)=x**(x***y)

***=R(S(Z),**(I31,I33))


Пример не ПРФ:

обозначения:

S(x)=A(0,x,y),

x+y=A(1,x,y),

xy=A(2,x,y),

x**y=A(3,x,y),

x***y=A(4,x,y) (операция "тетрация"),

При n, большем 1

A(n+1,x,0)=1;

A(n+1,x,y+1)=A(n,x,A(n+1,x,y))

A - пример не ПРФ.


Примеры ПРФ:


Pd2(x,0)=0

Pd2(x,y+1)=y

Pd(x)=Pd2(x,x)

Pd=R(Z,I32)(I11)

Pd(x)=max{0,x-1}


x-.0=x

x-.(y+1)=Pd(x-.y)

-.=R(I11,Pd(I33))


if0(x1,x2,0)=x1

if0(x1,x2,y+1)=x2

if0=R(I21,I42)

if0(x,y,z)=if z=0 then x else y


Остаток от деления:

dom(x,0) = 0

dom(x,y+1) = if x-.S(dom(x,y))=0 then 0 else S(dom(x,y))

x mod y = dom(y,x)

mod=R(Z,if0(Z(I33),S(I33),-.(I31,S(I33))))(I22,I21),

при этом определении x mod 0 = 0.


Целая часть частного:

vid(x,0) = 0

vid(x,y+1) = if dom(x,S(y))=0 then S(vid(x,y)) else vid(x,y)

x div y = vid(y,x)

div=R(Z,if0(S(I33)),I33,dom(I31,S(I32)))))(I22,I21),

при этом определении x div 0 = x.


Целая часть корня (степени x):

root(x,0) = 0

root(x,y+1) = if S(root(x,y))**x-.y=0 then root(x,y) else S(root(x,y))

root=R(Z,if0(I33,S(I33),-.(**(S(I33),I31),I32)))


Целая часть квадратного корня:

sqrt(x) = root(2,x)

sqrt=root(S(S(Z)),I11)


Частично-рекурсивные функции (ЧРФ) как замыкание множества B

относительно операций o, R и M.


Общерекурсивные функции (ОРФ) как множество всех всюду определенных

ЧРФ. Функция A - пример ОРФ, не являющейся ПРФ.


Контрольный вопрос


f1(x,0)=0

f1(x,y+1)=y


f1=R(Z,I32)


f2(x,0)=x

f2(x,y+1)=f1(x,f2(x,y))


f2=R(I11,f1(I31,I33))


f2(2,1)=?, f2(1,2)=?


f3=R(I11,R(Z,I32)(I31,I33))


f3(3,2)=?, f3(3,3)=?


Вычислить


f=M(I21-'I22) (M=mu=minroot)

f(0),f(1),f(100),f(x) (выражение)


^ Лекция 6. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов


Частичная рекурсивность вычислимых функций


Теорема о частичной рекурсивности функций,

вычислимых

- многомагазинными автоматами

- (К-алгоритмами, машинами Тьюринга)

- нормальными алгоритмами Маркова.


Части доказательства:

Взаимно однозначное соответствие между словами алфавита Б

и натуральными числами (d-адическая система счисления)

Примитивная рекурсивность функции конкатенации чисел в

d-адической системе счисления.

Примитивная рекурсивность функции выполнения подстановки НА.

Примитивная рекурсивность функции выполнения y подстановок.

Частичная рекурсивность функции подсчета числа шагов НА.

Примитивная рекурсивность функции кодирования и декодирования

чисел в алфавите.


Одновременная рекурсия. **)


Функция, нумерующая пары **)

C(x,y)=(x+y+1)(x+y)/2+x+1

(l,r) - обратная вектор-функция.


Двухмагазинный автомат **)

(n,r,d)

n:N, (1..n-1)=S - символы магазинного алфавита

r:N, (0..r-1)=Q - состояния, 0 - заключительное, 1 - начальное.

d - функция перехода

d отображает n*n*(1..r) в n*n*r

yields(x)=(x,,1)

step(w,v,q)=(w.a',v.b',q')

где d(last(w), last(v),q)=(a',b',q'),

last()=0, last(wa)=a, wa.0=w, w.a=wa, (a:S,w:S*),

end(w,v,q)=(q=0)

.

c3(x,y,z)=c(c(x,y),z)

l3[1](u)=l(l(u))

l3[2](u)=r(l(u))

l3[3](u)=r(u)

.

f - функция протокола автомата (n,r,d):

f(x,0)=c3(x,0,1)

f(x,i+1)=c3(w.a',v.b',q')

=c3(.(l3[1](x),d[1](last(l3[1](x)),last(l3[2](x)),l3[3](x))),

.(l3[2](x),d[2](last(l3[1](x)),last(l3[2](x)),l3[3](x))),

d[3](last(l3[1](x)),last(l3[2](x)),l3[3](x)))

.

g - функция выхода автомата (n,r,d)

g(x)=f(x,min{i|l33(f(x,i))=0})

.

.(x,y)=if(y,trunc(x),dx+y)

trunc(x)=if(x mod d, [x/d]-1, [x/d])

d[i](x,y,z)=d(x,y,z)[i]

last(x)=if(x,0,if(x mod d, d, x mod d))

.

Если d - параметр, то d[i](a,b,q) заменить на

appl[i](d,a,b,q)=l[3,i](proj(proj(proj(d,a),b),q))

proj(D,i)=(l(D)/r(D)**i)mod r(D)


^ Лекция 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса.


Запись на предельно упрощенном рефале

запись УА для НА. Программа НА вида

x[1] - e[1] y[1]

...

x[n] - e[n] y[n]

кодируется выражением

(((x[1])(e[1])y[1])...((x[n])(e[n])y[n]),

где x[i], y[i] - слова в рабочем алфавите алгоритма,

e[i]=. или e[i] пусто.

Например, алгоритм

|*| - *

* -.

кодируется выражением

((('|*|')()'*')(('*')('.')))


Программа на упрощенном рефале:


U((p((u)(e)v)q)x u y)=V((e)(p((u)(e)v)q)x v y);

U((p)x)=x;

V(()z)=U(z);

V(('.')(p)x)=x.


Машины Джонса (дополнительный вопрос).

Универсальная машина Джонса.

Команды

x:=E [v:=E]

if E1=E2 then S1 else S2

while E1#E2 do S

Выражения (E1.E2), nil, x, lE, rE.


Лекция 8. Программа машины Джонса как структура данных

Элементы программы машины Джонса как структуры данных:

(':='.E), ('.'.(E1.E2)), ('l'.E), ('r'.E),

('if'.((E1.E2).(S1.S2))), ('nil'.nil)

('while'.((E1.E2).S)).


Контрольный вопрос:


Напишите программу, выполняющую преобразование

(nil.(nil. ... (nil.(E1.E2))...)) в (E1.E2)


Лекция 9. Разрешимые и неразрешимые множества.

Перечислимые и неперечислимые множества


Определение класса разрешимых множеств


Множество разрешимо в том и только в том случае, когда его

характеристическая функция вычислима. X - характеристическая

функция множества M элементов пространства U, если X отображает

U в {0,1} и для любого x из U равенство X(x)=1 эквивалентно

принадлежности элемента x множеству M. (Примечание: в качестве

пространства U можно брать, например, множество натуральных

чисел, множество слов в конечном алфавите, множество конечных

последовательностей натуральных чисел, множество бинарных

конечных деревьев (или n-арных конечных деревьев или конечных

упорядовеннных деревьев), термов в конечном функциональном

базисе и т.д.).


Свойства разрешимых множеств


- Пустое множество разрешимо.

- Пространство U разрешимо.

- Любое конечное множество разрешимо.

- Пересечение любого конечного числа разрешимых множеств

разрешимо.

- Объединение любого конечного числа разрешимых множеств

разрешимо.

- Разность двух разрешимых множеств разрешима.

- Пример неразрешимого множества - область определения

универсального алгоритма.


Определение класса перечислимых множеств


Перечислимыми множествами называются области определения

вычислимых функций.


Свойства класса перечислимых множеств


- Класс перечислимых множеств совпадает с классом множеств

значений вычислимых функций.

- Все разрешимые множества перечислимы.

- Пересечение любого конечного числа перечислимых множеств

перечислимо.

- Объединение любого конечного числа перечислимых множеств

перечислимо.

- Если дополнение перечислимого множества перечислимо, то это

множество разрешимо.

- Следствие: дополнение области определения универсального

алгоритма не перечислимо.


Контрольный вопрос:

выделите перечислимые и разрешимые множества среди следующих

множеств:

1) множество программ, не применимых к пустому слову,

2) - -, применимых ...,

3) множество (p,n,x), для которых p не останавливается за n

шагов на x,

4) - -, - - - останавливается - - - - пустом слове,

5) - (p,n), - - - не останавливается ...,

6) - -, - - - останавливается ...,

7) - программ, не останавливающихся за 1000000 шагов на пустом слове,

8) - -, останавливающихся ...,

9) можно ли определить, выполняется ли когда-либо некоторая команда

в программе.


Иерархия Клини-Мостовского


^ Лекция 10. Элементарные по Кальмару функции


Определение, свойства и примеры функций, множеств и отношений, элементарных по Кальиару.


Контрольный вопрос:

Элементарна ли по Кальмару характеристическая функция

множества совершенных чисел?


^ Лекция 11. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности


Определение, свойства и примеры классов функций, множеств и отношений, основанных на ограниченной рекурсии.

Контрольный вопрос:


Определить с помощью ограниченной рекурсии функцию


f(x,y,z) = [x/y**z]


Классы функций и предикатов ограниченной вычислительной сложности


Если Compl - мера сложности какой-то модели вычислений, а Bounds

- класс верхних границ сложности для этой меры сложности, то

сложностным классом BoundCompl называется класс множеств, для

которых существуют разрешающие алгоритмы на данной модели

вычислений удовлетворяющие некоторым границам из Bound для меры

сложности Compl.


Примеры Compl:

- Space - требуемый объем памяти (например в битах),

- Time - требуемое время вычисления (например, в тактах

процессора),


Функции класса Bound, как правило - функции длины записи

аргумента вычисляемой (характеристической) функции.


Примеры Bound:

- Log - логарифмические функции (натуральнозначные приближения,

объем памяти, занимаемой аргументом не считается, требуется

произвольный (прямой) доступ к элементам аргумента),

- Lin - линейные функуции,

- Poly - многочлены,

- Exp - показательные функции.


Примеры сложностных классов:

- P=PolyTime

- PSPACE=PolySpace


Известные соотношения между некоторыми сложностными классами

(теоремы):

- LogSpace - подмножество P (строгость включения неизвестна),

- LogSpace - строгое подмножество LinSpace (иерархия),

- P не равно LinSpace (детали не известны),

- P - строгое подмножество ExpSpace (иерархия),

- LinSpace - подмножество ExpTime (строгость включения

неизвестна),

- LinSpace - строгое подмножество PSPACE (иерархия),

- ExpTime - подмножество ExpSpace (строгость включения

неизвестна),

- ExpTime не равно PSPACE (детали неизвестны),

- PSPACE - строгое подмножество ExpSpace (иерархия).


^ Лекция 12. Методы оценки сложности вычислений и алгоритмов.

Доказуемо трудные задачи. Полные переборные задачи


В качестве доказуемо трудных задач рассматриваются задачи

установления принадлежности произвольного элемента заданному

множеству, то есть задачи вычисления характеристических функций

этих множеств. Доказуемая трудность такой задачи есть доказуемая

трудность соответствующего множества.


Множество называется доказуемо трудным относительно сложностного

класса C, если можно доказать что это множество не принадлежит

классу C.


Примеры доказуемо трудных задач относительно класса P:

- ограниченная арифметика Беннета (арифметика в сигнатуре:

- переменные x[i],

- 0, 1,

- +, *, =, меньше, &, или,

- для всех ..., меньших ..., выполнено ...

- для некоторых ..., меньших ..., выполнено ...)


- ограниченная теория слов в конечном алфавите (теория Смульяна:

то же, что и в предыдущем случае, но константы - алфавит, а

единственная операция - сцепление слов, вместо "меньше" -

"короче"),


- теория логических функций (переменные и константы для

логических значений и n-местных логических функций, применения

функций к формулам, кванторы по логическим значениям и

функциям).


Полные переборные задачи


Классом переборных задач называется класс NP?, определенный

ниже.


Множество M принадлежит NP, если найдется такое множество M' из

класса P и такой многочлен p, что принадлежносто произвольного

элемента x длины n множеству M эквивалентна существованию такого

y длины p(n), что xy принадлежит M'.


Пусть A - некоторое множество слов. Вычислительной машиной с

оракулом A называется вычислительная машина РАМ с дополнительной

командой TEST(A) a, которая проверяет за 1 шаг, принадлежит ли

содержимое ячейки a множеству A, помещая результат в виде

значения соответствующей характеристической функции в сумматор.

Аналог класса P, определенный с помощью такой машины

обозначается через P[A]. Если A принадлежит NP и NP=P[A], то A

называется NP-полным или полной переборной задачей. Пример

полной переборной задачи - множество выполнимых

пропозициональных формул. Полные переборные задачи также

образуют класс трудных задач.


Контрольный вопрос:


Какова временная сложность (простая и взвешенная)

и зонная (лог. взвеш., макс. сумма длин ячеек)

вычисления суммы входных чисел.


^ Лекция 13. On-line - вычисления, вычисления в реальное время


Определение, основные свойства и примеры on-line-вычислений и вычислений в реальное время.


^ Лекция 14. Автоматные вычисления. Регулярные множества


Определение и основные свойства конечных автоматов-распознавателей и конечных преобразователей. Автоматы Мили и Мура. Автоматные множества. Определение класса регулярных множеств.


Контрольный вопрос:


Написать on-line RAM для нахождения НОК чисел

Сложность (простое время)


^ Лекция 15. Регулярность автоматных и автоматность регулярных множеств


Теоремы об автоматности регулярных множеств и регулярности автоматных множеств


Дополнительный вопрос: Классы функций и предикатов, рудиментарные по Р.Смульяну


^ Лекция 16. Связь логики и вычислимости


Традиционные конструктивные логические теории

Пример: формальная конструктивная (интуиционистская) арифметика.

Вычислительная интерпретация логических формул.

Вычислительная интерпретация доказательств.



  1. ^ Программа лабораторных занятий


Занятие 1. Математическая логика и теория алгоритмов.


Построение алгоритмов следующих видов.

Машины Тьюринга: многоленточные, многоголовочные машины,

многомерные ленты, квазибесконечномерность лент*),

ленты с неевклидовой топологией, древовидные ленты,

эластичные ленты - К-алгоритмы.


^ Занятие 2. Виды алгоритмов


Построение алгоритмов следующих видов.

Алгоритмы Колмогорова-Успенского.

К-алгоритм - частный случай КУ-алгоритма.

Многомагазинный автомат.


Занятие 3. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины


Построение магазинных автоматов, НА, РМ.


Занятие 4. Равнодоступные адресные машины (РАМ)


Построение РАМ.

РАМ с хранимой программой.


Занятие 5. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции


Построение ПРФ, ЧРФ и ОРФ.


^ Занятие 6. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов

Построение ПРП, ПРМ и ПРО. Операции над ними.


^ Занятие 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса.


Построение моделей универсальных алгоритмов.


Занятие 8. Программа машины Джонса как структура данных

Построение структур программ машин Джонса.


^ Занятие 9. Разрешимые и неразрешимые множества.

Перечислимые и неперечислимые множества


Выделение примеров разрешимых, неразрешимых, перечислимых и неперечислимых иножеств.


Занятие 10. Элементарные по Кальмару функции


Построение примеров функций, множеств и отношений, элементарных по Кальиару.


^ Занятие 11. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности


Построение примеров функций, множеств и отношений, в классах, основанных на ограниченной рекурсии.


Построение примеров функций, множеств и отношений в классах ограниченной вычислительной сложности


^ Занятие 12. Методы оценки сложности вычислений и алгоритмов.

Доказуемо трудные задачи. Полные переборные задачи


Построение и выделение примеров доказуемо трудных и полных переборных задач.


Занятие 13. On-line - вычисления, вычисления в реальное время


Построение примеров on-line-алгоритмов и алгоритмов, работающих в реальное время.


Занятие 14. Автоматные вычисления. Регулярные множества


Построение примеров конечных автоматов-распознавателей и конечных преобразователей. Построение примеров регулярных множеств.


Занятие 15. Регулярность автоматных и автоматность регулярных множеств


Осуществление переходов между регулярными и автоматными определениями в конкретных случаях.


Занятие 16. Связь логики и вычислимости


Построение конструктивных логических выводов.



  1. ^ Программа самостоятельной работы студента


Самостоятельная работа выполняется в виде заданий к соответствующим лабораторным работам. Задания сдаются раз в 2 недели по следующим неделям:


Неделя 2. Математическая логика и теория алгоритмов. Виды алгоритмов


Неделя 4. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины. Равнодоступные адресные машины (РАМ)


Неделя 6. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов


Неделя 8 Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса. Программа машины Джонса как структура данных

Неделя 10. Разрешимые и неразрешимые множества. Перечислимые и неперечислимые множества. Элементарные по Кальмару функции


Неделя 12. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности. Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи


Неделя 14. On-line - вычисления, вычисления в реальное время. Автоматные вычисления. Регулярные множества


Неделя 16. Регулярность автоматных и автоматность регулярных множеств. Связь логики и вычислимости



  1. Контролирующие материалы


Задания для лабораторных работ


1. Машина Тьюринга с одной одномерной двусторонней лентой и

одной головкой.


2. Машина Тьюринга с одной одномерной односторонней лентой и

одной головкой.


3. Машина Тьюринга с двумя двусторонними одномерными лентами по

одной головке на каждой ленте.


4. Машина Тьюринга с одной двумерной лентой.


5. Двухмагазинный автомат.


6. Нормальный алгоритм Маркова.


7. К-алгоритм.


8. Равнодоступная адресная машина.


9. Равнодоступная адресная машина с сохраняемой программой.


10. Машина Джонса.


11. Частично-рекурсивные функции.


12. Словарные рекурсивные функции.


13. Рекурсивные функции на бинарных деревьях.


14. Рекурсивные функции на термах.


15. Алгоритм Колмогорова-Успенского на бинарных

деревьях.


16. Алгоритм Колмогорова-Успенского на термах.


17. Регистровая (счетчиковая) машина.


18. Машина Тьюринга с лентой в виде бинарного дерева.


19. Двухголовочная машина Тьюринга с лентой в виде бинарного

дерева.


20. Машина Минского (счетчиковая машина).


Пример набора задач к экзамену


1. РАМ для нахождения максимума 100 входных чисел.


2. РАМ для нахождения минимума 400 входных чисел.


3. РАМ для нахождения максимума входных чисел, не превосходящих 200,

(всего дано 500 входных чисел) или выдать 300, если таких чисел нет.


4. РАМ для нахождения минимума входных чисел, не меньших 50,

(всего дано 150 входных чисел) или 0, если таких чисел нет.


5. РАМ для вычисления максимума попарных сумм из 120 входных чисел

(x[1],...,x[120]) x[i]+x[j], меньших 10 при i,j=1,...,120.


6. РАМ для вычисления миниимума попарных сумм из 80 входных чисел

(x[1],...,x[80]) x[i]+x[j], больших 20 при i,j=1,...,80.


7. РАМ для вычисления максимума попарных разностей 40 входных чисел.


8. РАМ для вычисления минимума попарных положительных разностей 60

входных чисел.


9. Машина Тьюринга, распознающая слова длины 3 в алфавите {0,1}

(101 -> 1, 10 -> 0, 1111 - > 0)


10. Машина Тьюринга, распознаюшие слова в алфавите {0,1}, имеющие

более 2-x единиц в своем составе (010 -> 0, 11 -> 0, 1011 -> 1).


11. РАМ для нахождения наименьшего из номеров наибольших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 6).


12. РАМ для нахождения наибольшего из номеров наибольших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 8).


13. РАМ для нахождения наименьшего из номеров наименьших чисел в заданной

последовательности из 10 чисел (3 2 2 3 4 5 7 6 7 4 -> 2).


4. РАМ для нахождения наибольшего из номеров наименьших чисел в заданной

последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 2).


15. Машина Тьюринга для уменьшения числа на 3 в монадической

("палочковой") системе счисления.


16. Машина Тьюринга для увеличения числа на 4 в монадической

("палочковой") системе счисления.


17. Машина Тьюринга для распознавания слова в алфавите {0,1},

состоящего из одних единиц.


18. Машина Тьюринга для распознавания словав алфавите {0,1},

состоящего из одних нулей.


19. РАМ для определения наименьшего положительного натурального

i, при котором x[i]=x[1] по входным числам x[1],...,x[80].


20. РАМ для определения наибольшего натурального i от 0 до 80,

при котором x[i]=x[1] по входным числам x[1],...,x[80].


21. РАМ для нахождения такого наименьшего i, что

x[i]=max{x[1],...,x[70],70} или i=71 по x[1],...,x[70].


22. РАМ для нахождения такого наибольшего i, что

x[i]=min{76,x[1],...,x[75]} или i=0 по x[1],...,x[75].


23. РАМ для вычисления такого наименьшего i (от 1 до 101), что

x[i]=0 или i=101 по входным числам x[1],...,x[100].


24. РАМ для вычисления такого наибольшего i (от 0 до 100), что

x[i]=0 или i=0 по входным числам x[1],...,x[100].


  1. Экзаменационные вопросы


1. Конструктивные логические теории.

2. Вычислительная интерпретация логических формул.

3. Вычислительная интерпретация доказательств.

4. Машины Тьюринга и другие модели вычислений.

5. Машины Джонса.

6. Равнодоступные адресные машины.

7. РАМ с хранимой программой.

8. Примитивно рекурсивные функции.

9. Частично-рекурсивные и общерекурсивные функции.

10. Тезисы Черча, Тьюринга, Маркова.

11. Эквивалентность разных моделей вычислимости.

12. Универсальные алгоритмы.

13. Рекурсивно разрешимые множества, неразрешимые множества.

14. Примитивно рекурсивные множества, отношения, предикаты.

15. Перечислимые множества и неперечислимые множества.

16. Элементарные функции, множества, отношения, предикаты.

17. Классы функция, основанных на ограниченной рекурсии.

18. Классы Гжегорчика и их аналоги.

19. Классы словарных функций.

20. Определение словарных функций с помощью словарной

ограниченной рекурсии.

21. Конечная сложность вычислений (сложность вычислений на

конечных равнодоступных адресных машинах).

22. Алгоритмическая (описательная, дескриптивная) сложность.

23. Алгоритмическое определение случайности.



  1. Список литературы (основная, дополнительная)


Основная литература


1. А.А.Марков Теория алгорифмов М.Л. Изд-во АН СССР, 1954,

374с., 1984, 432 с.


2. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ

вычислительных алгоритмов. М. Мир, 1979. 536 с.


3. Проблемы математической логики (сб.). Под ред. Козмидиади и

др. М. Мир 1970, 432 с.


4. Э.Мендельсон. Введение в математическую логику. (Гл. 5.) M.

1971, 1976, 1984. 320 с.


5. С.К.Клини. Математическая логика. (Гл. V). М. Мир, 1973.

480с.


6. Ю.Л.Ершов, Е.А.Палютин. Математическая логика. (Гл. 7). М.

"Наука" 1971. 320 с.


7. Р.Смальян. Теория формальных систем. (Гл. I, II.) М. Наука,

1981, 207 с.


8. Дж.Шенфилд. Математическая логика. (Гл. 6-7.) М. Наука, 1975.

527 с.


9. С.К.Клини. Введение в метаматематику. М "Иностраниздат",

1957, 526 с.


10. Н.Верещагин, А.Шень. Лекции по математической логике и

теории алгоритмов. Ч 3. Вычислимые функции. M. МЦНМО 1999.

126с.


11. К.А.Гоуд. Доказательства как описания вычислений. В кн.

"Математическая логика в программировании". Под ред.

М.В.Захарьящева и Ю.И.Янова. М. 1991. С. 311-330. (407 с.)


12. А.И.Мальцев Алгоритмы и рекурсивные функции. М Наука 1986.

357с.


13. В.Г.Карпов, В.А.Мощенский Математическая логика и дискретная

математика, Минск "Высшая школа", 1977. 254 с.


14. А.Н.Колмогоров, Драгалин Математическая логика,

дополнительные главы, М МГУ, 1984. 120 с.


15. А.Н.Колмогоров, Драгалин Введение в математическую логику,

М. МГУ. 1982.


16. Н.К.Косовский Основы теории элементарных алгоритмов, Л. ЛГУ,

1987. 132 с.


17. С.Л.Эдельман Математическая логика, М. Высшая школа. 1975.

176с.


18. Дж.Булос,Р.Джефри. Вычислимость и логика, М. Мир. 1994.

396с.


Дополнительная литература


1. Математическая логика. Под ред. А.А.Столяра. Гл. А.4, Б.3. М.

1971.


2. Б.А.Трахтенброт. Алгоритмы и вычислительные автоматы. М.1974.


3. В.А.Успенский, А.Л.Семенов Теория Алгоритмов: основные

открытия и приложения. М., "Н", 1987.


4. Г.Д.Эббинхауз, К.Якобс, Ф.-К.Ман, Г.Хермес Машины Тьюринга и

рекурсивные функции. М.1972


5. Х.Роджерс Теория рекурсивных функций и эффективная

вычислимость, М.1972


6. В.К.Иложарский Математическая логика и алгоритмы, 1970


Приложение 1

Основное оборудование по дисциплине

Перечень основного оборудования в соответствии с ГОС

по дисциплине «Теория сложности алгоритмов и вычислений»

специальности «Прикладная математика и информатика»

Формы обучения «дневная»

2009/2010 год

№ п/п

Наименование оборудования

Кол-во

Примечание (сведения о наличии, необходимости обновления, приобретения)

1

Компьютерный проектор

1

Наличествует 1




Скачать 361.03 Kb.
оставить комментарий
Дата13.10.2011
Размер361.03 Kb.
ТипРабочая программа, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх