WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Pages:   || 2 |

«Кафедра информатики и методики преподавания математики УТВЕРЖДАЮ Проректор по учебной работе _Г.П.Иванова __200_г. Учебно-методический комплекс по дисциплине Теория ...»

-- [ Страница 1 ] --

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра информатики и методики преподавания математики

УТВЕРЖДАЮ

Проректор по учебной работе

_Г.П.Иванова «_»_200_г.

Учебно-методический комплекс по дисциплине Теория алгоритмов для направления 540200 «Физико-математическое образование»

Профиль «Информатика»

Воронеж – 200_

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра информатики и методики преподавания математики

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

дисциплины «Теория алгоритмов»

для направления 540200 «Физико-математическое образование»

Профиль «Информатика»

Курс обучения Семестр Всего часов по учебному плану: В том числе по формам обучения: очная - лекции - лабораторные работы - самостоятельная работа Формы итогового контроля знаний:

- зачет - экзамен Составитель: доцент Р.Х. Вахитов Программа утверждена на заседании кафедры «_29_»августа2008_г., протокол № Заведующий кафедрой _А.С. Потапов Воронеж

1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Дисциплина «Теория алгоритмов» для направления 540200 «Физикоматематическое образование», профиль «Информатика», относится к циклу общепрофессиональных дисциплин направления – ОПД.Р.04.

В учебных планах направление «Физико-математическое образование»

имеет новый номер после перекодировки:

540200 «Информатика» 050200.03 «Информатика».

Дисциплина «Теория алгоритмов» изучается в 3 семестре.

Понятия алгоритма и вычислимой функции относятся к фундаментальным понятиям информатики и математики. Исследование алгоритмов и вычислимых функций привело к созданию новой дисциплины – теории вычислимости. Первые компьютеры появились в 40-х годах, и их появление стало возможным благодаря достижениям теории вычислимости. Созданная теория NP-полноты имеет большое практическое значение для анализа алгоритмов.

Межпредметные связи: математическая логика, теоретические основы информатики, основы дискретной математики.

Цель – формирование систематизированных знаний в области теории алгоритмов и развитие самостоятельности, элементов поисковой деятельности, творческого подхода к решению теоретико-алгоритмических задач в компьютерных науках.

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

Рассматриваются интуитивные понятия алгоритма, вычислимой функции, разрешимого и перечислимого множеств, а также их формальные уточнения в виде частично рекурсивных функций, машин Тьюринга, машин с неограниченными регистрами, рекурсивных и рекурсивно-перечислимых множеств (предикатов). Изучаются построение рекурсивных функций и предикатов, понятия эффективной нумерации, универсальных функций, примеры невычислимых функций и неразрешимых проблем в математике и информатике, простейшие машины Тьюринга и операции на машинах Тьюринга.

Выполняются лабораторные работы по представлению в системе компьютерной алгебры Mathematica 5.0 частично рекурсивных функций и отношений и составлению программ для вычисления различных одноместных и двухместных функций и отношений на симуляторе машины Тьюринга.

2. ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ

В том числе Всего в трудоемаудиторных 1. Алгоритмы и частично рекурсивные функции и отношения

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

1. Частично рекурсивные функции. Основные требования к алгоритмам. Необходимость уточнения понятия алгоритма. Понятие вычислимой функции. Числовые функции, исходные для построения частично рекурсивных функций. Операторы подстановки, примитивной рекурсии, минимизации. Тезис Черча. Частично рекурсивные функции и рекурсивные предикаты.

Определение примитивно рекурсивных функций. Рекурсивные предикаты (отношения). Ограниченные суммы, произведения, обобщения и подтверждения с ограниченными кванторами, ограниченные -операторы.

2. Машины Тьюринга. Вычислимые по Тьюрингу функции. Тезис Тьюринга. Понятие нумерации множества и эффективно счетного множества. Нумерация машин Тьюринга и ее применение к проблеме остановки.

3. Разрешимые отношения. Определение машины с неограниченными регистрами (МНР) и функции, вычислимой при помощи МНР. Универсальной функции. Применение универсальной функции к проблеме неразрешимости. Теорема о параметризации. Разрешимые и перечислимые множества.

Неразрешимые проблемы. Алгоритмическая сводимость одной проблемы к другой проблеме. Временная сложность машины Тьюринга. Теорема Блюма об ускорении. Классы P и NP.

4. ТЕМАТИКА ЛАБОРАТОРНЫХ ЗАНЯТИЙ

Наименование п/п 1 Частично рекур- Представление примитивно рекурсивных сивные функции и функций в системе Mathematica 5. отношения Представление частично рекурсивных 2 Машины Тьюрин- Знакомство с симулятором машины Тьюга ринга 3 Разрешимые от- Усеченная разность и модуль разности

7. РЕКОМЕНДАЦИИ К САМОСТОЯТЕЛЬНОЙ РАБОТЕ СТУДЕНТОВ

Рекомендации по организации самостоятельной работы студентов:

1) Практические занятия по всем разделам с последующей проверкой домашней работы.

2) Самостоятельное изучение отдельных вопросов, решение задач и доказательство теорем, предлагаемых студентам на лекциях для самостоятельного решения.

На самостоятельную работу выносятся следующие вопросы.

1) Доказательство вычислимости частично рекурсивных функций.

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

3) Проверка изменений конфигураций для всех рассматриваемых программ машин Тьюринга.

4) Применение универсальной функции и теоремы о параметризации к доказательству теорем о неразрешимости проблем 5) Меры сложности

9. ВОПРОСЫ К ЭКЗАМЕНУ

1. Интуитивное определение алгоритма и вычислимой функции 2. Определение и простейшие свойства разрешимых множеств 3. Определение перечислимого множества как образа вычислимой функции и через частичную характеристическую функцию 4. Определение примитивно рекурсивных функций (ПРФ) 5. Определение частично рекурсивных функций 6. Вычислимость частично рекурсивных функций. Тезис Черча 7. Общерекурсивные, но не примитивно рекурсивные функции 8. Применение оператора подстановки для построения ПРФ 9. Применение схемы рекурсии для одноместной функции 10. Применение схемы рекурсии для двухместной функции 11. Усеченная разность и модуль разности как ПРФ 12. Отношения равенства и неравенства примитивно рекурсивны 13. Отношения порядка примитивно рекурсивны 14. Разрешимые отношения (рекурсивные предикаты) 15. Ограниченные суммы как операторы для построения ПРФ 16. Ограниченные произведения как операторы для построения ПРФ 17. Обобщение и подтверждение с ограниченными кванторами 18. Построение ПРФ с помощью ограниченного -оператора 19. Функции, задаваемые по кусочной схеме 20. Команды, конфигурации и программы машины Тьюринга 21. Функции, вычислимые по Тьюрингу. Тезис Тьюринга 22. Нумерация множества упорядоченных пар натуральных чисел 23. Применение нумерации машин Тьюринга к проблеме остановки 24. Существование функции, невычислимой по Тьюрингу 25. Машины с неограниченными регистрами (МНР) 26. Определение и примеры МНР вычислимых функций 27. Определение и примеры универсальных функций 28. Универсальная функция для класса всех ПРФ 29. Применение универсальной функции к неразрешимым проблемам 30. Теорема о параметризации (с неформальным доказательством) 31. Разрешимые и неразрешимые отношения (проблемы) 32. Алгоритмическая сводимость одной проблемы к другой 33. Теорема Райса 34. Временная сложность машины Тьюринга. Аксиомы Блюма 35. Верхняя граница меры сложности 36. Теорема Блюма об ускорении 37. Недетерминированные машины Тьюринга и классы NP.

38. Взаимоотношения между классами P и NP

10. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1. Основная литература 1. Матрос Д.Ш., Поднебесова Г.Б. Теория алгоритмов. – М.: БИНОМ, Лаборатория знаний, 2008. – 208 с.

2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Академия, 2007. – 304 с.

3. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. – 448 с.

4. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. - М.: Инфра-М, 2008. – 224 с.

2. Дополнительная литература 1. Мальцев А.И. Алгоритмы и рекурсивные функции. – М. Наука, 1986. – 2. Фалевич Б.Я. Теория алгоритмов. – М.: Машиностроение, 2008. – 160 с.

3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983. – 256 с.

4. Мирзоев В.Н. Теория алгоритмов (теория вычислимых функций). – Воронеж, 2004. – 74 с.

5. Кормен Е., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. М., «Вильямс». – 2005. – 1296 с.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра информатики и методики преподавания математики Комплект учебно-методических материалов к учебной дисциплине:

КОНСПЕКТ ЛЕКЦИЙ

для направления 540200 «Физико-математическое образование»

Вахитов Р.Х, доцент, кандидат физико-математических наук, доцент

ТЕМА: СЧЕТНЫЕ МНОЖЕСТВА. ОПРЕДЕЛЕНИЕ АЛГОРИТМА

Основные вопросы, рассматриваемые на лекции:

1. Счетные множества 2. Интуитивное понятие алгоритма 3. Определение эффективно вычислимой функции 4. Необходимость уточнения понятия алгоритма и вычислимой функции Краткое содержание лекционного материала Множество V называется n-элементным, если множество первых n натуральных чисел {1,…,n} взаимно однозначно отображается на множество V.

Множество V называется счетным, если множество всех натуральных чисел N взаимно однозначно отображается на множество V.

Множество V называется конечным, если V= (т.е. 0-элементное) или оно n-элементное для некоторого натурального числа n.

Множество V называется бесконечным, если оно не является конечным.

Множество V называется несчетным, если оно бесконечно и не счетное. Например, множества N, Z, Q – счетные, а множества R, C – несчетные.

В теории множеств доказываются следующие утверждения:

(1) бесконечное подмножество счетного множества – счетное множество;

(2) множество V { 1, 2, …, n } всех последовательностей конечной длины элементов счетного множества V есть счетное множество;

(3) объединение счетного множества счетных множеств есть счетное множество;

(4) множество V N всех счетных последовательностей элементов счетного множества V есть несчетное множество.

Алфавит A – это конечный список символов. Слово в алфавите A – это конечная последовательность символов алфавита A.

В силу (2), множество An всех слов длины n в алфавите A, – счетное.

В силу (2) и (3), множество A* всех слов в алфавите A, – счетное.

Пусть U и V – счетные множества, а M – множество всех отображений f:UV, определяемых каким-либо конечным списком слов в алфавите A. Тогда, в силу (1), (2) и (3), множество M счетное.

В силу (4), множество V U всех отображений f :UV несчетное.

Множество M счетное, а множество V U несчетное. Отсюда следует, что существуют отображения счетного множества в счетное же множество, которые нельзя определить никаким конечным списком слов.

Основные черты (или основные требования к определению) интуитивного понятия алгоритма: массовость, определенность, дискретность, детерминированность, направленность. Примеры алгоритмов: арифметические действия над числами в десятичной записи; алгоритм Евклида нахождения НОД двух чисел. Эффективно вычислимые и вычислимые функции. Необходимость уточнения понятия алгоритма: 1) для решения задач неразрешимости; 2) для изучения теоретических вопросов информатики.

Строгие определения понятия алгоритма (машины Тьюринга, нормальные алгорифмы Маркова, частично рекурсивные функции и т.д.) найдены, изучены и успешно применяются в математике и информатике.

ТЕМА: ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ

Основные вопросы, рассматриваемые на лекции:

1. Функции, исходные для построения частично рекурсивных функций 2. Оператор подстановки, или суперпозиции 3. Оператор примитивной рекурсии 4. Оператор минимизации, или -оператор 5. Определение частично рекурсивной функции Краткое содержание лекционного материала Функции, исходные в построении частично рекурсивных функций:

• одноместная нулевая функция o(x)=0;

• одноместная функция прибавления единицы, или следования, s(x)=x+1;

• n-местные функции выбора координаты, или проекции (n0, i=1,…,n), I i (x 1,..., x n )=x i. В частности, I1 ( x) = x – тождественная функция.

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

• двухместный оператор примитивной рекурсии R;

• одноместный оператор минимизации M (или -оператор).

Говорят, что функция h получена из функций f и m функций g1, …, gm h(x 1,..., x n )=f(g 1 (x 1,...,x n ),…, g m (x 1,...,x n )) для всех x 1,..., x n N (m1, n0).

Когда определено значение функции h(x 1,..., x n )?

Если m=1, то h=S 2 (f,g) является обычной композицией функций g и f.

Говорят, что функция h получена из функций f и g при помощи оператора примитивной рекурсии R и пишут h=R(f,g), если:

для всех x 1,…,x n 1,yN (n1). При n=1 f является константой.

Когда определено значение функции h(x 1,…,x n 1,y)?

Пусть функция f(x 1,…,x n 1,y) удовлетворяет условию "либо значение f(x 1,…,x n 1,y) не определено для всех y, либо найдется число y0, такое, что значение f(x 1,…,x n 1,y) определено для всех yy0 и равно x n для y=y0".

Запись y[f(x 1,…,x n 1,y)=x n ] означает "наименьшее y, такое, что f(x 1,…,x n 1,y) определено и равно x n ".

Говорят, что функция g получена из функции f при помощи оператора минимизации M и пишут g=M(f), если g(x 1,…,x n )=y[f(x 1,…,x n 1,y)=x n ] для всех x 1,…,x n,yN (n1).

Когда определено значение функции g(x 1,…,x n )?

Если n=1, f – биекция, то g=f 1 является функцией, обратной к f.

Заметим, что операторам примитивной рекурсии и минимизации в программировании соответствуют циклы типа for ("для") и while ("пока").

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

1) функции o, s, I i f частично рекурсивны;

2) если функции f, g1, …, gm частично рекурсивны, то функция h=S (f,g 1,…,g m ) тоже частично рекурсивна;

3) если функции f, g частично рекурсивны, то функция h=R(f,g) тоже частично рекурсивна;

4) если функции f частично рекурсивна, то функция g=M(f) тоже частично рекурсивна.

Используя интуитивное определение алгоритма, доказывается Теорема 1. Любая частично рекурсивная функция вычислима.

Утверждение, обратное к теореме 1, не является теоремой и даже аксиомой, а является непреложным фактом (законом) практики.

Тезис Чёрча. Любая вычислимая функция частично рекурсивна.

Аргументы в пользу тезиса Черча: 1) все известные нам вычислимые функции оказываются частично рекурсивными: 2) все уточнения понятия алгоритма приводят к одному и тому же классу вычислимых функций, например, классы частично рекурсивных и вычислимых по Тьюрингу функций равны; 3) машины Тьюринга послужили прообразом первых электронновычислительных машин; 4) замена вычислимых функций частично рекурсивными функциями позволяет решать задачи неразрешимости и различные теоретические вопросы компьютерных наук.

Частично рекурсивные функции, вообще говоря, не всюду определенны, например, функция x1 частично рекурсивна: y[sy=x]=y[y+1=x]=x1, но не определена при x=0.

ТЕМА: ПРИМИТИВНО РЕКУРСИВНЫЕ ФУНКЦИИ И ОТНОШЕНИЯ

Основные вопросы, рассматриваемые на лекции:

1. Определение примитивно рекурсивных функций (ПРФ) 2. Применение оператора подстановки для построения ПРФ 3. Схема примитивной рекурсии для одноместной функции 4. Схема примитивной рекурсии для двухместной функции 5. Усеченная разность и модуль разности Краткое содержание лекционного материала Числовая функция называется примитивно рекурсивной функцией, если построена строго по следующим правилам:

1) функции o, s, I i f частично рекурсивны;

2) если функции f, g1, …, gm частично рекурсивны, то функция h=S (f,g 1,…,g m ) тоже частично рекурсивна;

3) если функции f, g частично рекурсивны, то функция h=R(f,g) тоже частично рекурсивна.

Используя интуитивное определение алгоритма, доказывается Теорема 2. Любая частично рекурсивная функция всюду определенна и вычислима.

Утверждение, обратное к теореме 2, неверно: т.н. функция Аккермана частично рекурсивна и всюду определена, но не примитивно рекурсивна.

При помощи оператора подстановки доказывается, что постоянные функции примитивно рекурсивны. Доказательство приведем, без потери общности, на примере функции f ( x,y)=3: f ( x,y)=ssoI 1 ( x,y).

Еще одно применение оператора подстановки: если функция получена из ПРФ перестановкой, повторением или удалением аргументов, то тоже будет ПРФ. Доказательство приведем, без потери общности, на примере функции g(x,y,z)=f ( y,x,z), где f ( x,y,z) есть ПРФ: g=S 4 (f,I 2,I 3,I 1 ).

Приведем схему примитивной рекурсии для одноместной функции:

При помощи этой схемы доказываем, что функции – сигнум sg и антисигнум s g являются ПРФ. Например, сигнум sg – ПРФ:

Приведем схему примитивной рекурсии для двухместной функции:

При помощи этой схемы доказываем, что сложение x+y, умножение xy и возведение в степень x y – ПРФ. Например, функция f + (x,y)=x+y – ПРФ:

Вычитание не всюду определенная функция. Рассматриваются следующие две ПРФ: усеченная разность x y = x y, если x y, иначе усеченная разность считается, равной 0, и модуль разности. При помощи оператора примитивной рекурсии последовательно доказывается, что x 1 и x y ПРФ. Модуль разности тоже ПРФ, так как | x y |= ( x y ) + ( y x).

ТЕМА: ПРИМИТИВНО РЕКУРСИВНЫЕ ПРЕДИКАТЫ

Основные вопросы, рассматриваемые на лекции:

1. Рекурсивные предикаты и операции над ними 2. Определение примитивно рекурсивных отношений 3. Отношения равенства и неравенств (,, ,, ) Предикат – это математическое предложение, которое при замене переменных их значениями принимает истинностное значение. Логические операции над предикатами определяются также как и над высказываниями.

Какие бы числовые значения из N не принимали переменные x1, …, xn отрицание (¬ P)( x1,..., xn ) истинно предикат P ( x1,..., xn ) истинен, дизъюнкция ( P Q)( x1,..., xn ) истинна хотя бы один из предикатов P( x1,..., xn ) и Q( x1,..., xn ) истинен, конъюнкция ( P Q)( x1,..., xn ) истинна одновременно оба предиката P( x1,..., xn ) и Q( x1,..., xn ) истинны.

Теорема 3. Если предикаты P и Q примитивно рекурсивны, то предикаты ¬ P, P Q и P Q тоже примитивно рекурсивны.

Доказательство. Из условия следует, что характеристические функции P и Q примитивно рекурсивны. Представим характеристические функции ¬P, PQ и PQ в виде примитивно рекурсивных функций:

характеристической функцией отношения P(x 1,…,x n ), x 1,…,x n N.

Предикат (отношение) P(x 1,…,x n ) называется примитивно рекурсивным, если примитивно рекурсивна его характеристическая функция.

Полное и пустое отношения P = N n и P = примитивно рекурсивны, так как их характеристические функции N n = 1 и = 0 – постоянные.

Теорема 4. Отношения равенства и порядка примитивно рекурсивны.

Доказательство. Вначале установим связь операций усеченной разности и модуля разности с отношениями равенства и порядка:

Затем представим характеристические функции отношений равенства, неравенства и четырех порядков в виде примитивно рекурсивных функций:

Пример. Отношение примитивно рекурсивно, так как характеристическая функция выражается через ПРФ антисигнума и усеченной разности при помощи оператора подстановки, поэтому примитивно рекурсивна.

ТЕМА: ОГРАНИЧЕННЫЕ СУММЫ, ПРОИЗВЕДЕНИЯ И КВАНТОРЫ

Основные вопросы, рассматриваемые на лекции:

1. Ограниченные суммы примитивно рекурсивны 2. Ограниченные произведения примитивно рекурсивны 3. Формулы подтверждения с ограниченными кванторами существования 4. Формулы обобщения с ограниченными кванторами существования 5. Ограниченные операторы минимизации Краткое содержание лекционного материала Мы рассмотрим новые операторы построения ПРФ.

Применяя оператор подстановки, можно доказать, что суммы и произведения не только двух слагаемых, но и конечного числа слагаемых, примитивно рекурсивны. Кроме конечных сумм и произведений, в математике встречаются также ограниченные суммы и произведения Пример. Последовательность a n является функцией f(n) от натуральноv от натурального аргумента v. Обозначим эту функцию f (v). Заметим, что мы имеем дело с неким оператором с аргументом f и значением f (у нас нет необходимости обозначать этот оператор).

Теорема 5. Пусть f(x 1,…,x n,y) – примитивно рекурсивная функция.

Тогда также примитивно рекурсивны следующие функции:

Доказательство. Применим рекурсию (параметры опустим) для f:

Действительно, f (u,v+1)=f(u)+…+f(v)=f (u,v)+f(v), если uv1, т.е.

uv, или s g (u v) = 1. Аналогично применим рекурсию для f:

Далее рассмотрим формулы с ограниченными кванторами.

Допустим, что на множестве N определено (m+1)-местное отношение P(x 1,…,x m,y). Для краткости опустим параметры x 1,…,x m N. Напомним:

подтверждение yP(y) истинно, если истинно P(y) хотя бы при одном значении y, и ложно, если ложно P(y) для всех значений y;

обобщение yP(y) истинно, если истинно P(y) для всех значений y, и ложно, если ложно P(y) хотя бы при одном значении y.

Навешивание кванторов на примитивно рекурсивные отношения, вообще говоря, не приводит к примитивно рекурсивным отношениям.

Рассмотрим подтверждение и обобщение с ограниченными кванторами. Если P(x 1,…,x m,y) – (m+1)-местный предикат, то определим следующие два (m+2)-местных предиката (с временным обозначением E и A):

Для краткости, без потери общности, предположим, что m=0.

Теорема 6. Если P(y) –примитивно рекурсивное отношение, то отношения E(u,v) и A(u,v) тоже примитивно рекурсивны.

Доказательство. Характеристическая функция P (y) примитивно рекурсивна по условию. Характеристические функции E (u,v) и A (u,v) можно представить в виде примитивно рекурсивных функций:

В силу теоремы 4, функции E (u,v) и A (u,v) являются ПРФ.

Оператор минимизации y[…] не сохраняет примитивную рекурсивность функций. Определим так называемый ограниченный оператор минимизации y y z […], который сохраняет примитивную рекурсивность функций.

определено и не больше z; иначе y y z [f(x 1,…,x n 1,y)=x n ] равно z.

Теорема 7. Пусть примитивно рекурсивная функция f(x 1,…,x n 1,y), такая, что либо значение f(x 1,…,x n 1,y) не определено для всех y, либо найдется число y0, такое, что значение f(x 1,…,x n 1,y) определено для всех yy0 и равно x n для y=y0. Тогда функция g(x 1,…,x n 1,z)=y y z [f(x 1,…,x n 1,y)=x n ] тоже примитивно рекурсивна.

Доказательство. Мы, без потери общности, опускаем параметры (n=1, x n =x). Предположим, что f(0)x, f(1)x, …, f(y 0 1)x, f(y 0 )=x, где 0y 0 z.

Тогда sg|f(0)x|+sg|f(0)x|sg|f(1)x|+…+sg|f(0)x|…sg|f(y 0 1)x|+… +sg|f(0)x|…sg|f(y 0 )x|+…+sg|f(0)x|…sg|f(z)x|=1+11+…+1... 1 +… +1... 1 0+…+1... 1 0…=1 + 1 24 1 +0+…+0=y0 (где равно 0 или 1).

ТЕМА: МАШИНЫ ТЬЮРИНГА. ВЫЧИСЛИМОСТЬ ПО ТЬЮРИНГУ

1. Устройство машины Тьюринга 2. Команды машины Тьюринга 3. Работа машины Тьюринга 4. Вычислимые по Тьюрингу функции. Тезис Тьюринга 5. Примеры вычислимых по Тьюрингу функций 6. Синтез машин Тьюринга 7. Частичная рекурсивность вычислимых по Тьюрингу функций Краткое содержание лекционного материала Алан Тьюринг в 1936 году с целью точного определения понятия алгоритма придумал абстрактную вычислительную машину, которую впоследствии назвали машиной Тьюринга.

Устройство машины Тьюринга:

1) лента, разделенная на ячейки и бесконечная в обе стороны;

2) «вычислитель», который обозревает некоторую ячейку, считывает символ с ячейки, стирает этот символ и вписывает новый символ в ячейку, затем перемещается на одну ячейку влево или вправо;

3) конечный список внутренних состояний Q = {q0, q1,..., qm } с начальным состоянием q1 и заключительным состоянием q0 ;

4) конечный список внешних символов V = {v0, v1,..., vn } – символов ячеек v1,..., vn и символа v0, обозначающего пустую ячейку;

5) программа – список команд вида qi v j vk ql, qi v j Lql или qi v j Rql, причем, каждой паре qi v j соответствует не более одной пары vk ql, Lql или Rql (где i, l = 0,1,..., m, j, k = 0,1,..., n, i 0, а L, R – дополнительные символы, обозначающие перемещение вычислителя на одну ячейку влево или вправо).

В любой момент времени заполнено конечное число ячеек ленты.

Пусть s1 – крайний левый и s2 – крайний правый символ на ленте. Тогда последовательность символов ленты s1...s2 называется машинным.

Программа машины Тьюринга – это список команд, т.е. четверок вида qiajakql, qiajLql или qiajRql, где i,j,k,lN, i0, причем, каждой паре qiaj соответствует не более одной пары akql, Lql или Rql.

Конфигурация машины Тьюринга – это слово машины Тьюринга, дополненное в любом месте одним из символов qi, причем, слева и справа может быть дописано любое число символов пустой клетки a0. Смысл конфигурации s1...qisj...s2 в том, что в данный момент времени машина находиться в состоянии qi и обозревает клетку с символом sj. При этом машина выполняет команду, начинающуюся с пары qisj, и переходит к следующей конфигурации, согласно следующим правилам:

Рассмотрим следующий двухэлементный список внешних символов:

Q = {q0, q1 } = {_,1}. Представим натуральное число k как слово, состоящее из k + 1 единиц: k = 1k +1 = 1...1. Числовая n -местная функция f ( x1,..., xn ) назыk + вается вычислимой по Тьюрингу, если существует машина Тьюринга, которая конфигурацию q1 1x1 +1 _..._ 1xn +1 преобразует в конфигурацию с машинным словом 1y+1, если функция f ( x1,..., xn ) определена и равна y, и останавливается не в заключительном состоянии (нет команды для очередной конфигурации!) или не останавливается, если функция f ( x1,..., xn ) не определена.

Нетрудно убедиться, что для машины Тьюринга выполняются все требования, предъявляемые к интуитивному понятию алгоритма. Отсюда и из определения вычислимой функции следует следующее утверждение:

() функция, вычислимая по Тьюрингу, является вычислимой.

Обратное утверждение называется тезисом Тьюринга:

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

Тезис Тьюринга не доказывается, а принимается как закон науки. Перечислим аргументы в его пользу: 1) все известные вычислимые функции оказываются вычислимыми по Тьюрингу; 2) все методы построения вычислимых функций оказываются пригодными для построения функций, вычислимых по Тьюрингу; 3) машина Тьюринга была прообразом первых электронно-вычислительных машин; 4) машина Тьюринга существенно используется в теоретических исследованиях по теории алгоритмов.

Приведем примеры вычисления функций на машинах Тьюринга.

1) Функция следования s ( x) = x + 1 вычислима по Тьюрингу. Вот подходящая программа машины Тьюринга: q1 1Lq1 ; q1 _1q0. Если на входе дано x = 3, то изменения конфигурации следующие: q1 1111 q1 _1111 q0 11111.

2) Нулевая функция o( x) = 0 вычислима по Тьюрингу. Пишем программу: q1 1_ q2 ; q2 _ Rq0 ; q1 _1q0. Изменения конфигурации ( x = 3 ):

3) Функция проекции I kn ( x1,..., xn ) = xk, где 1 k n, вычислима по Тьюрингу. Составим программу функции I kn в случае n = 2, k = 1, то есть функции I12 ( x1, x2 ) = x1 : q1 1Rq1 ; q1 _ Rq2 ; q21_ q3 ; q3 _ Rq2 ; q2 _ _ q0. Изменения конфигурации выглядят следующим образом ( x = 2, y = 1 ):

Предположим, что машины T и U имеют общий внешний алфавит A и их внутренние состояния q1, …, qi, q00 и qi + 1, …, qn, q0 соответственно. Тогда произведением TU машин T и U называется машина с внешним алфавитом A и с внутренними состояниями q1, …, qi, qi + 1, …, qn, q0, при условии, что в командах T символ q00 заменяется на qi + 1. На ленте мы располагаем "память", и поэтому должны следить за тем, чтобы работа T и U не затрагивала те участки ленты, в которых располагается "память".

Синтез машин Тьюринга позволяет доказывать, операторы подстановки, примитивной рекурсии и минимизации вычислимые по Тьюрингу функции преобразуют вычислимые же по Тьюрингу функции. Отсюда следует, что частично рекурсивные функции вычислимы по Тьюрингу.

ТЕМА: ФУНКЦИИ, ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ

Основные вопросы, рассматриваемые на лекции:

1. Одноместные функции, вычислимые по Тьюрингу 2. Двухместные функции, вычислимые по Тьюрингу 3. Функции, определяемые по кусочной схеме Краткое содержание лекционного материала Функция f:N 0 n N 0 с областью определения DN 0 n называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел x 1,x 2,…,x n N начальную конфигурацию q11x1 +1 _ 1x 2 +1 _... _ 1 n преобразует в заключительную конфигурациюq01y+1, если (x 1,x 2,…,x n )D и y=f(x 1,x 2,…,x n ), и не выдает никакого результата, если (x 1,x 2,…,x n )D.

В частности, одноместная функция f:N 0 N 0 с областью определения DN 0 называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел xN начальную конфигурацию q11x +1 преобразует в заключительную конфигурациюq01y+1, если xD и y=f(x), и не выдает никакого результата, если xD.

1) Программа Тьюринга для функции s:

Преобразования конфигурации при x=2 (и y=3): q1111, q1_111, q01111.

2) Программа Тьюринга для функции o:

Преобразования конфигурации при x=2 (и y=0):

Двухместная функция f:N 0 N 0 N 0 с областью определения DN 0 N называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел x,yN начальную конфигурацию q11x +1 _1y +1 преобразует в заключительную конфигурациюq01z+1, если (x,y)D и z=f(x,y), и не выдает никакого результата, если (x,y)D.

1) Программа машины Тьюринга для функции I 1 2 :

Преобразования конфигурации для I 1 2 при x=2, y=1, z =2:

q1111_11, 111q1_11, 111_q211, 111_ _ _q2, 111_ _ _q0.

2) Программа машины Тьюринга для функции o2:

Преобразования конфигурации для o2 при x=2, y=1, z =0:

q1111_11, _ _ _q1_11, _ _ _ _q211, _ _ _ _ _ _q2, q0_1.

3) Программа машины Тьюринга для функции z =x+y:

Преобразования конфигурации для z =x+y при x=2, y=1, z =3:

q1111_11, 111q1_11, 1111q211, 111111q2, 11111q31, 1111q41_, 111q01_ _.

Пусть заданы одноместные функции f 1 (x),…,f m (x) и одноместные предикаты (предложения) P 1 (x),…,P m (x), причем, для всех xN 0 ровно одно из высказываний P 1 (x), …, P m (x) истинно. Говорят, что одноместная функция g(x) определена кусочной схемой (или перебором случаев), если для всех xN 0.

1) Программа машины Тьюринга для функции sg:

Преобразования конфигурации: если x=0, y=0, то q11, 1q2, 1q0;

если x=1, y=1, то q111, 1q21, 11q3, 11q0;

если x=3, y=1, то q11111, 1q2111, 11q311, 11_ _q3, 11_ _q0.

2) Программа машины Тьюринга для функции Правый столбец задает цикл длины 2, пересчитывающий счетные единицы. При этом считывающая головка стирает все счетные единицы и останавливается перед пустой ячейкой: в состоянии q2, если счетных единиц было нечетно, и в состоянии q1, если счетных единиц было четно. Левый столбец определяет соответствующие состояниям q2 и q1 ответы на ленте.

Преобразования конфигурации для четных чисел: если x=4, y=0, то q111111, _q21111, _ _q1111, _ _ _q211, _ _ _ _q11, _ _ _ _ _q2, _ _ _ _ _q01.

Преобразования конфигурации для нечетных чисел: если x=3, y=1, то q11111, _q2111, _ _q111, _ _ _q21, _ _ _ _q1, _ _ _q2_1, _ _ _q011.

ТЕМА: НУМЕРАЦИЯ МАШИН ТЬЮРИНГА. ПРОБЛЕМА ОСТАНОВКИ

Основные вопросы, рассматриваемые на лекции:

1. Нумерация с повторениями и без повторений 2. Счетные и эффективно счетные множества 3. Нумерация декартова квадрата множества натуральных чисел 4. Нумерация машин Тьюринга и вычислимых по Тьюрингу функций 5. Проблемы самоприменимости и остановки Краткое содержание лекционного материала Отображение f:AN называется нумерацией (или перечислением) множества A, если f – сюръекция, т.е. aA nN f(a)=n. Само множество A при этом может быть задано перечислением элементов:

A={a 0,a 1,…,a n,…}, где a=a n, если f(a)=n. Вообще говоря, нумерация множества A является нумерацией с повторениями. Нумерация f:AN называется нумерацией без повторения, если также f – инъекция, т.е. a,bA [(f(a)=f(b)a=b] (то есть f будет биекцией, или взаимно однозначным отображением множества A на N).

Множество A называется счетным, если существует биекция f:AN.

Заметим, что при этом обратная функция f 1 :NA тоже биекция.

Счетное множество A называется эффективно счетным, если существует биекция f:AN, такая, что обе функции f и f 1 являются вычислимыми.

Теорема 8. Существуют биекция C : N N N и функции L : N N и R : N N, которые ПРФ, и такие, что C ( L(n), R(n)) = n для всех n N.

Доказательство. Построим нумерацию Кантора множества N N.

Строка, начинающаяся с пары (0, x + y ), содержит x + y + 1 пар. Первые

Чтобы показать, что соответствия L(n) = x и R (n) = y являются функциями, причем, примитивно рекурсивными, мы обозначим: k = x + y. Тогда из равенства шее число l, такое, что Теперь мы последовательно построим следующие ПРФ:

Покажем, что C биекция. Пусть C ( x1, y1 ) = C ( x2, y2 ) = n. Тогда по определению понятия функции получим, что x1 = x2 = L(n) и y1 = y2 = R (n).

Рассмотрим все машины Тьюринга с одним и тем же (конечным или счетным) внешним алфавитом A и такие, что их внутренние состояния принадлежат одному и тому же счетному множеству. Без доказательства приведем следующее утверждение: множество всех указанных машин эффективно счетное. Пусть T0, T1, … – нумерация машин Тьюринга с внешним алфавитом A и с множеством внутренних состояний. Тогда машина Ti вычисляет некоторую n-местную функцию ni, iN, так, что: ni(x1,…,xn)=y, если машина Ti начальную конфигурацию q1 1x1 +1 _..._1xn +1 преобразует в заключительную конфигурацию q01y+1; иначе ni(x1,…,xn) не определено.

При n=1 обозначим ni=1i через i.

Ясно, что n0, n1, … – нумерация (с повторениями) всех n-местных вычислимых по Тьюрингу функций.

Пусть T0, T1, … – нумерация машин Тьюринга с алфавитом {0,1}.

Машина Tn называется самоприменимой, если машина Tn при применении к числу n останавливается.

Проблема самоприменимости. Существует ли вычислимая по Тьюрингу функция s(n), такая, что s(n)=1, если машина Tn самоприменима, и s(n)=0, если машина Tn несамоприменима.

Теорема 9. Проблема самоприменимости неразрешима.

Доказательство. Допустим, что существует машина S, которая вычисляет функцию s(n). Рассмотрим машину S, отличающуюся от машины S дополнительным состоянием q0, которое будет и новым заключительным состоянием, а также отличающуюся от машины S двумя дополнительными командами q011q0 и q000q0.Если машина Tn самоприменима, то машина S при применении к числу n не останавливается (бесконечно переходит с 1 на 1).

Если машина Tn не самоприменима, то машина S при применении к числу n останавливается (и выдает результат 0). Значит, при применении к числу n машина Tn останавливается тогда и только тогда, когда машина S не останавливается. Машина S совпадает с некоторой машиной Ti, iN. Является ли машина S=Ti самоприменимой? Мы не можем ответить ни да, ни нет, так как при применении к числу i получается, что машина S=Ti и останавливается, и не останавливается. Значит, машины S и S не существуют.

Проблема остановки. Существует ли машина Тьюринга T, которая вычисляет функцию t(m,n), такую, что t(m,n)=1, если машина Tm при применении к числу n останавливается, и t(m,n)=0, если машина Tn при применении к числу n не останавливается.

Теорема 10. Проблема остановки неразрешима.

Доказательство. Если функция t(m,n) вычислима, то функция s(n)=t(n,n) тоже вычислима, что противоречит теореме 9.

ТЕМА: ФУНКЦИИ, НЕВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ

Основные вопросы, рассматриваемые на лекции:

1. Диагональный метод построения невычислимых функций 2. Метод «усердного бобра», или соревнование машин Тьюринга 3. Примеры составления программ машин Тьюринга Краткое содержание лекционного материала Используя нумерацию машин Тьюринга T0, T1, … и нумерацию функций вычислимых по Тьюрингу n0, n1, …, построим двумя способами числовые функции, невычислимые по Тьюрингу. В силу тезиса Черча невычислимые по Тьюрингу функции будут невычислимыми.

Теорема 11. Существует невычислимая k-местная числовая функция.

Доказательство. Определим функцию k (x,x1,…,xk1) следующим образом: k (x,x1,…,xk1)= xk (x,x1,…,xk1)+1, если xk (x,x1,…,xk1) определено, и k (x,x1,…,xk1)=0, если xk (x,x1,…,xk1) не определено.

Функция k отлична от всех функций xk, xN. Значит, функция k не является функцией, вычислимой по Тьюрингу.

Рассмотрим еще один метод построения невычислимых функций, известный в литературе также как метод «усердного бобра».

Для каждой машины Тьюринга Mi, iN, определим продуктивность p(Mi) машины Mi следующим образом:

p(Mi)= i1 (0), если i1 (0) определено;

p(Mi)=0, если i1 (0) не определено.

Далее определим функцию p(n), nN. Число p(n) равно продуктивности самой продуктивной машины Тьюринга с n состояниями (не считая q0).

Теорема 12 (Тибор Радо, 1962 г.). Функция p(n) невычислимая.

Доказательство. 1) p(n+1)p(n). Действительно, если T – самая продуктивная машина с n состояниями, то машина T, отличающаяся от машины T дополнительным (и новым заключительным) состоянием q0, а также отличающаяся от машины T двумя дополнительными командами q001q0 и q01Lq0.

Машина T имеет n+1 состояний и продуктивность p(n)+1, а продуктивность самой продуктивной машины с n+1 состояниями будет не меньше продуктивности машины T: p(n+1)p(n)+1p(n).

2) Если mn, то p(m)p(n) (так как отношение порядка транзитивно).

3) Если ¬p(m)p(n), то ¬mn (по правилу контрапозиции).

4) Если p(m)p(n), то mn (так как отношение порядка линейно).

5) Легко увидеть, что существует машина Tn с n состояниями, продуктивность которой равна n.

6) Допустим, что машина S с k состояниями вычисляет функцию p(n).

Тогда продуктивность машины TnSS, с n+2k состояниями, полученной соединением трех машин Tn, S и S, равна p(p(n)). Так как продуктивность самой продуктивной машины с n+2k состояниями не меньше продуктивности машины TnSS, то p(n+2k)p(p(n)).

7) Из пунктов 6) и 4) следует, что n+2kp(n). Это неравенство справедливо для любого nN, поэтому верно, что n+2k+11p(n+11).

8) Ранее была построена машина T с n+11 состояниями и с продуктивностью 2n. Так как продуктивность самой продуктивной машины с n+11 состояниями не меньше продуктивности машины T, то p(n+11)2n.

9) Из пунктов 7) и 8) следует, что n+2k+112n.

10) Сократив на n, получим: 2k+11n. Полученное неравенство неверно для всех n, начиная с n=2k+12. Следовательно, не существует машины Тьюринга S, вычисляющей функцию p(n).

ТЕМА: МАШИНЫ С НЕОГРАНИЧЕННЫМИ РЕГИСТРАМИ

Основные вопросы, рассматриваемые на лекции:

1. Устройство машин с неограниченными регистрами (МНР) 2. Программа и выполнение команд МНР 3. Конфигурации и примеры программ МНР 4. Избыточность команды переадресации Краткое содержание лекционного материала В 1963 г. Шепердсон и Стерджис рассмотрели идеализированный компьютер – машину с неограниченными регистрами (МНР).

МНР – это лента, бесконечная в одну сторону и разбитая на ячейки, которые называются регистрами и обозначаются R 1,R 2,… Каждый регистр содержит некоторое неотрицательное целое число. Содержимое регистра R n обозначается r n, причем, только в конечном числе регистров r n 0.

Программа МНР – это конечный список команд I 1,I 2,…,I s 4-х видов:

команда обнуления Z(n) (по этой команде r n :=0), команда прибавления единицы S(n) (по этой команде r n :=r n +1), команда переадресации T(m,n) (по этой команде r n :=r m ), команда условного перехода J(m,n,q).

Работа МНР начинается с выполнения команды I 1. Допустим, что МНР выполняет команду I k, k=1,2,…,s. Если I k одна из трех т.н. арифметических команд Z(n), S(n) или T(m,n), то МНР меняет соответствующим образом содержимое регистра R n и переходит к следующей команде I k + 1. Если же I k =J(m,n,q), то МНР при r n =r m переходит к команде I q и при r n r m переходит к следующей команде I k + 1. МНР останавливается тогда, когда нет команды для выполнения.

Конфигурацией МНР называется слово, составленное из символов на регистрах ленты, включая все ненулевые символы.

Функция f(x 1,…,x n ) называется вычислимой МНР, если существует МНР, которая, начиная работу с конфигурацией x 1 …x n 000…, останавливается с конфигурацией y…, если f(x 1,…,x n ) определено и равно y, и не останавливается, если f(x 1,…,x n ) не определенно.

Пример 1. Программа МНР для вычисления функции f(x,y)=5:

Пример 2. Программа МНР для вычисления функции сигнума sg(x):

Пример 3. Программа МНР для вычисления сложения x+y:

Пример 4. Программа МНР для вычисления функции выбора координаты I 4 ( x 1, x 2, x 3, x 4, x 5 ) = x 4 :

Пример 5. Команда T(m,n) избыточная. Эту команду можно заменить следующей программой, составленной из других команд:

ТЕМА: УНИВЕРСАЛЬНЫЕ ФУНЦИИ. ТЕОРЕМА О ПАРАМЕТРИЗАЦИИ

1. Определение универсальной функции 2. Универсальная функция для класса всех ЧРФ 3. Универсальная функция для класса всех ПРФ не является ПРФ 4. Применение универсальной функции к проблеме неразрешимости 5. Теорема о параметризации Сечением (n+1)-местной функции f по (первой) переменной x называется n-местная функция f x, xN, такая, что для всех t 1,…,t n N Существует ли программа, которая вычисляла бы все функции? В некотором смысле такие программы существуют.

(n+1)-местная функция u называется универсальной для класса C, состоящего из некоторых вычислимых n-местных функций, если:

Иначе говоря, класс C будет задано перечислением функций вида u x :

Существует вычислимая универсальная функция для класса всех вычислимых n-местных функций.

Теорема 13. Пусть функция определена следующим образом:

где x,t 1,…,t n N. Тогда – вычислимая универсальная функция для класса всех вычислимых на МНР n-местных функций.

(Неформальное) доказательство. Дано: x,t 1,…,t n N. Декодируем номер x, т.е. найдем МНР T x с номером x. Затем T x должно вычислить (1).

Вычислимые универсальные функции не всегда существуют.

Теорема 14. Не существует примитивно рекурсивной (общерекурсивной) универсальной функции для класса всех n-местных примитивно рекурсивных (общерекурсивных) функций.

Доказательство. Допустим, что существует примитивно рекурсивная универсальная функции u(x,t 1,…,t n ) для класса всех n-местных примитивно рекурсивных функций. Тогда определим новую n-местную функцию следующим образом: для всех x,t 1,…,t n N Функция g примитивно рекурсивна, но отлична от каждой n-местной примитивно рекурсивной функции u x. Получается противоречие.

Следовательно, не существует примитивно рекурсивной универсальной функции для класса всех n-местных примитивно рекурсивных функций.

Следующую теорему мы приводим без доказательства: существует общерекурсивная универсальная функция для класса всех n-местных примитивно рекурсивных функций.

Отсюда и из теоремы 14 следует, что существует n-местная общерекурсивная, но не примитивно рекурсивная, функция.

Применим универсальную функцию = 2 из теоремы 13 к решению проблемы разрешимости " x всюду определено".

Теорема 15. Пусть для всех xN отношение P(x) определено как отношение " x всюду определено". Тогда отношение P(x) неразрешимо.

Доказательство. Допустим, что отношение P разрешимо, т.е. его характеристическая функция P частично рекурсивна.

Определим новую числовую функцию: для всех xN Функция g(x) частично рекурсивна: g(x)=((x,x)+1)sg P.

Вычислимая функция g совпадает с одним из сечений : xN…g= x.

Функция g= x всюду определенная, поэтому, в частности, P (x)=1, и g(x)= x (x)+1. Получается противоречие: x (x)= x (x)+1.

Следовательно, отношение P неразрешимо.

Каждое из сечений f x, xN, вычислимой двухместной функции f является также вычислимой (одноместной) функцией. Значит, существует номер iN, такой, что f x = i. Следующая теорема показывает, что номер i можно эффективно вычислить по x. Эта теорема называется теоремой о параметризации (или простой формой s-m-n-теоремы).

Теорема 16. Пусть f(x,t) – вычислимая функция. Тогда существует всюду определенная вычислимая функция k(x), такая, что f x = k ( x ).

(Неформальное) доказательство. Пусть МНР T a с программой F вычисляет функцию f. Определим МНР с новой программой:

Пусть y – номер этой программы в эффективной нумерации программ МНР, т.е. построили МНР T y. Определим: y=k(x). Эта функция по построению эффективно вычислима. f(x,t)= y(t)= k ( x ) (t).

ТЕМА: РАЗРЕШИМЫЕ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

Основные вопросы, рассматриваемые на лекции:

1. Определение разрешимых множеств (отношений, предикатов) 2. Простейшие свойства разрешимых множеств 3. Определение перечислимых множеств 4. Основные свойства перечислимых множеств Краткое содержание лекционного материала Определение разрешимого множества и простейшие свойства, доказываемые с помощью интуитивного понятия алгоритма.

Характеристической функцией множества A N называется функция Аналогично определяются характеристические функции R отношения R(x)N n и P предиката P(x), где x= (x 1,…,x n )N n – числовой вектор.

Множество A N называется разрешимым, если его характеристическая функция A является вычислимой. Иначе говоря, множество A N разрешимо, если существует алгоритм, который для всех x N на вопрос «Верно ли, что x A ? » за конечное число шагов выдает ответ «Да», если x A, или ответ «Нет», если x A.

Используя интуитивное определение вычислимой функции (алгоритма), можно доказать следующие свойства разрешимых множеств.

1) Пустое множество и само множество N – разрешимые множества, поскольку = 0 и N = 1 (постоянные функции) – вычислимые функции.

2) Конечное множество A разрешимо: характеристическая функция A равна 0 за исключением конечного числа точек, поэтому вычислима.

3) Дополнение A разрешимого множества A (до множества N ) – разрешимое множество. Действительно, если функция A вычислима, то функция A ( x ) = 1 A ( x ) тоже вычислима.

4) Объединение A B двух разрешимых множеств A и B – разрешимое множество. Действительно, если функции A и B вычислимые, то функция A B (x)= A (x)+ B (x) A (x) B (x) тоже вычислима.

5) Пересечение A B двух разрешимых множеств A и B – разрешимое множество. Действительно, если функции A и B вычислимые, то функция A B (x)= A (x) B (x) тоже вычислима.

Определение перечислимого множества и основные свойства, доказываемые с помощью интуитивного понятия алгоритма.

Множество A N называется перечислимым, если существует вычислимая функция f : N N, такая, что множество A является областью значений функции f, т.е. A = f ( N ) = { f ( n ) | n N }. Также говорят, что множество A перечислимо при помощи функции f.

Используя интуитивное определение вычислимой функции (алгоритма), можно доказать следующие свойства перечислимых множеств.

1) Множества и N перечислимы, поскольку – образ нигде не определенной функции, а N – образ тождественной функции f ( n ) = n.

2) Конечное множество перечислимо, так как является областью значений функции, определенной на конечном множестве точек.

Дополнение A перечислимого множества A, вообще говоря, не является перечислимым множеством.

3) Если множество A разрешимо, то A и его дополнение A – перечислимые множества. Определим функции f и g следующим образом:

4) Объединение A B двух перечислимых множеств A и B – перечислимое множество. Пусть функции f и g вычислимы, A = f ( N ), B = g ( N ). Тогда определим функцию h следующим образом:

h ( 2 m ) = f ( m ), если f ( m ) определено, иначе h ( 2 m ) не определено;

h(2m+1)=g(m), если g(m) определено, иначе h(2m+1) не определено.

5) Пересечение A B двух перечислимых множеств A и B – перечислимое множество. Пусть функции f и g вычислимы, A = f ( N ), B= g ( N ). Тогда вначале определим функцию h : N N N следующим образом:

h ( m, n ) не определено. Функция h вычислима и A B = h ( N N ).

Затем определим вычислимую функцию p : N N N, такую, что NN=p(N):

Композиция функций p и h – вычислимая функция и A B = h ( p ( N ) ).

Частичной характеристической функцией множества A N называется функция A: N N, такая, что A( x ) = 1 для x A и A( x ) неопределенно для x A. Например, ( x ) неопределенно для всех x N.

6) Если функция A вычислима, то множество A N перечислимо.

Действительно, функция f, такая, что f ( n) = n, если A( x ) = 1, иначе f ( n) не определено, – вычислима и A = f ( N ).

ТЕМА: СВОЙСТВА ПЕРЕЧИСЛИМЫХ МНОЖЕСТВ

Основные вопросы, рассматриваемые на лекции:

1. Теоремы о перечислимых множествах, доказываемые с помощью свойства пошагового выполнения алгоритма 2. Теорема о частично характеристических функциях 3. Теорема Поста 4. Теорема о графике вычислимой функции Мы рассмотрим теоремы перечислимых множеств, доказываемых с помощью свойство пошагового выполнения алгоритма: при применении к любому объекту алгоритм или не останавливается, или останавливается в конечное число шагов.

1) Множество A N перечислимо тогда и только тогда, когда его частичная характеристическая функция A вычислима.

Докажем, что если множество A N перечислимо, то функция A вычислима. Пусть функция f вычислима, A = f ( N ). Тогда построим алгоритм вычисления функции A( x ) следующим образом:

(i) выполняется не более чем по n шагов для вычисления каждого из значений f ( k ), k n ;

(ii) если найдется такое число k, что f ( k )= x, то A( x )= 1;

(iii) иначе пункты (i) - (ii) выполняются для числа n + 1.

Если этот процесс продолжается бесконечно, то A( x ) не определено.

Таким образом, перечислимое множество можно определить следующим образом. Множество A N перечислимо, если существует алгоритм, который для всех x N на вопрос «Верно ли, что x A ? » за конечное число шагов выдает ответ «Да», если x A, и не выдает никакого ответа, если x A.

2) (теорема Поста). Множество A N разрешимо тогда и только тогда, когда множества A и A перечислимы. Докажем, что если множества A и A перечислимы, то множество A разрешимо. Пусть функции f и g вычислимы, A = f ( N ), A= g ( N ). Тогда построим алгоритм вычисления функции A ( x ):

(i) выполняется не более чем по n шагов для вычисления каждого из (ii) если найдется такое число k, что f ( k )= x, то A ( x )= 1;

(iii) если найдется такое число k, что g ( k )= x, то A ( x )= 0;

(iv) иначе пункты (i) - (iii) выполняются для числа n + 1.

Построенный алгоритм правильный: так как A A= N, то найдется такое k, что f ( k )= x или найдется такое l, что g ( l )= x ; так как A A=, то будет Графиком функции f называется множество f = { ( x, f ( x ) ) | x N}.

3) (теорема о графике вычислимой функции). График f функции f есть перечислимое множество тогда и только тогда, когда функция f вычислима.

Если функция f вычислима, то f – перечислимое множество: функция Докажем теперь, что если f – перечислимое множество, то функция f вычислима. Пусть g : N N N, g ( N ) = f. Построим алгоритм для вычисления функция f ( x ) следующим образом:

(i) выполняется не более чем по n шагов для вычисления каждого из значений g(k ), k n ;

(iii) иначе пункты (i) - (ii) выполняются для числа n + 1.

Этот процесс либо останавливается с результатом y = f ( x ) в случае, когда f ( x ) определено, либо продолжается бесконечно в случае, когда f ( x ) не определено. Значит, построенный алгоритм вычисляет функцию f ( x ).

4) Множество A N перечислимо тогда и только тогда, когда множество A является областью определения некоторой вычислимой функции f, т.е.

A =D f = { x N | f ( x ) определено}.

Докажем, что если A перечислимо, то A является областью вычислимой функции. Пусть функция f вычислима, A = f ( N ). Тогда построим алгоритм вычисления функции g(y) следующим образом:

(i) выполняется не более чем по n шагов для вычисления каждого из значений f ( x ), x n ;

(ii) если найдется такое число x, что f ( x )= y, то g(y)= x ;

(iii) иначе пункты (i) - (ii) выполняются для числа n + 1.

Если этот процесс продолжается бесконечно, то g(y) не определено.

Функция g вычислима и A =D g.

Пусть теперь g – вычислимая функция и A =D g. Тогда построим алгоритм вычисления функции h(x,n) следующим образом:

(i) выполняется не более чем по n шагов для вычисления каждого из значений g(y), y n ;

(ii) если найдется такое число x, что g(y)= x, и h(x,k)y для всех k n, то h(x,k)= y ;

(iii) иначе пункты (i) - (ii) выполняются для числа n + 1.

Функция h(x,n) вычислима и A = h ( N N ). Используя функцию какуюлибо вычислимую функцию p : N N N, получим A = f ( N ) = p ( h ( N ) ).

5) Множество A перечислимо тогда и только тогда, когда множество A является областью значений всюду определенной вычислимой функции.

Пусть функция f вычислима, A = f ( N ). Надо определить всюду определенную вычислимую функцию g, такую, что A = g ( N ). Предположим, что A N, и A. Заметим, что нельзя просто определить g ( n )= a, если f ( n )= a, и g ( n ) =, если f ( n ) не определено. Алгоритм будет работать бесконечно, а мы запишем результат? Построим алгоритм вычисления функции g(x):

(i) выполняется не более чем по n шагов для вычисления каждого из значений f(k), k n ;

(ii) если найдется такое число k, что f ( k ) = a, и g(k)a для всех k n, то g(n)= a ; иначе принимается g(n)=.

Функция g всюду определенна, вычислима и A = g( N ).

Двухместным отношением на множестве N называется любое множество упорядоченных пар чисел (x,y): R={(x,y)|x,yN}. Вместо (x,y)R пишут R(x,y) (и говорят, что отношение R(x,y) истинно).

Отношение R(x,y) называется разрешимым, если вычислима его характеристическая функция R : N N N, такая, что R ( x,y) = 1, если R(x,y) истинно, и R ( x,y) = 0, если R(x,y) ложно.

Первой и второй проекциями отношения R(x,y) называются множества 6) Множество A N перечислимо тогда и только тогда, когда является (первой или второй) проекцией некоторого разрешимого отношения. Иначе говоря, множество A N перечислимо тогда и только тогда, когда существует отношение R(x,y), такое, что n A ( y N ) R ( n, y ) для всех nN (или Докажем, что если отношение R(x,y) разрешимо (даже, если перечислимо), то его проекция 1 есть перечислимое множество. Пусть функция f вычислима, R= f ( N ). Тогда функция g, такая, что g(n)= x, если f ( n ) = ( x, y ), и g(n) не определено, если f ( n ) не определено, – вычислима и 1 = f ( N ).

Докажем, что если множество A перечислимо, то A есть проекция некоторого разрешимого отношения R(x,n). Пусть функция f вычислима, A = f ( N ). Построим алгоритм для вычисления R ( x,n):

(i) выполняется не более чем по n шагов для вычисления каждого из значений f(k), k n ;

Функция R всюду определенна, вычислима и A = 1.

№ 1. Рассмотрим некоторую функцию f : U V. Образом множества A U называется множество f ( A ) = { f ( x ) | x A }, а прообразом множества B V – множество f 1(B ) = { x U | f ( x ) определено и xB}. В частности, образ множества U есть область значений функции f, а прообраз множества V – область определения функции f. Теперь, допустим, что f : N N – вычислимая функция, A,BN – перечислимые множества. Доказать, что образ f ( A ) множества A и прообраз f 1(B ) множества B – тоже перечислимые множества.

№ 2. Функция f : N N называется не строго возрастающей, если для всех x,yN из xy следует, что f ( x)f ( y). Доказать, что непустое множество AN разрешимо тогда и только тогда, когда оно перечислимо помощи всюду определенной не строго возрастающей функции.

№ 3. Пусть A,BN – перечислимые множества, но непересекающиеся, т.е. AB. Доказать, что существует перечислимые множества AA, BB, такие, что AB= и AB=AB.

№ 4. Доказать, что любое бесконечное перечислимое множество включает в себя бесконечное разрешимое множество.

№ 5. Доказать, что для любой вычислимой функции f : N N существует вычислимая функция g : N N, такая, что g( f ( x)) = x для всех xN, для которых f ( x) определено.

№ 6. Диофантово уравнение – это уравнение P(x 1,…,x n )=0, где P(x 1,…,x n ) – многочлен с целыми коэффициентами. Пусть A – множество диофантовых уравнений, имеющих целые решения. Множество A неразрешимо (так называемая «10-я проблема Гильберта», ее решил Ю.В. Матиясевич в 1970 г.). Доказать, что множество A перечислимо.

ТЕМА: СВОДИМОСТЬ ПРОБЛЕМ

Основные вопросы, рассматриваемые на лекции:

1. Разрешимые и неразрешимые проблемы 2. Сведение одной проблемы к другой проблеме 3. Проблема остановки для ЧРФ 4. Лемма о сведении проблемы P(x,x) к проблеме P(x,y).

5. Лемма о сведении проблемы P(k(x)) к проблеме P(x) Краткое содержание лекционного материала Говорят, что проблема P(x 1,…,x n ), x 1,…,x n N, неразрешима, если отношение P(x 1,…,x n ) неразрешимо. Сводимость проблем используется при доказательстве неразрешимости проблем следующим образом. Если проблема Q(x 1,…,x n ) сводится к проблеме P(x 1,…,x n ) и проблема Q(x 1,…,x n ) неразрешима, то проблема P(x 1,…,x n ) тоже неразрешима.

Пусть P(x 1,…,x n ), Q(x 1,…,x n ) – два отношения, x 1,…,x n N. Говорят, что проблема Q(x 1,…,x n ) сводится к проблеме P(x 1,…,x n ), если из разрешимости отношения P(x 1,…,x n ) следует разрешимость отношения Q(x 1,…,x n ).

Лемма 1. Проблема Q(x)P(x,x) сводится к проблеме P(x,y).

Доказательство. Пусть отношение P(x,y) разрешимо, т.е. характеристическая функция P (x,y) рекурсивна. Тогда Q (x)= P (x,x)= S 3 ( Q, I1, I1 ) (x), т.е. характеристическая функция Q (x) рекурсивна, а отношение Q(x) разрешимо. Значит, проблема Q(x) сводится к проблеме P(x,y).

Алгоритм вычисления частично рекурсивной функции f для каждого входа x либо не останавливается ( f(x) не определено), либо останавливается с результатом f(x) ( f(x) определено).

Теорема 17. Проблема (самоприменимости для частично рекурсивных функций) Q(x)« x (x) определено» неразрешима.

Доказательство. Предположим, что отношение Q(x) разрешимо, т.е.

характеристическая функция Q (x) рекурсивна. Тогда функция Q (x) частично рекурсивна. Значит, Q = n для некоторого индекса nN. Тогда:

если n (n) определено, то Q (n)=1, x (n)=1, n (n) не определено;

если n (n) не определено, то Q (n)=0, x (n)=0, n (n) определено.

Получается противоречие. Значит, проблема Q(x) неразрешима.

Теорема 18. Проблема (остановки для частично рекурсивных функций) P(x,y)« x (y) определено» неразрешима.

Доказательство. Применим лемму 1 к теореме 17.

Таким образом, теоремы 17 и 18 показывают, что невозможно написать программу, которая для каждой вычислимой функции f и для каждого числа x определяла бы – значение функции f(x) определено или нет, равно 0 или нет.

Теорема 19. Проблемы « x (x)=0» и « x (y)=0» неразрешимы.

Доказательство. Пусть Q(x)« x (x)=0» и P(x,y)« x (y)=0» Предположим, что Q(x) разрешимо, т.е. характеристическая функция Q (x) рекурсивна. Значит, Q = n для некоторого индекса nN. Тогда:

Получается противоречие. Значит, проблема Q(x) неразрешима.

В силу леммы 1, проблема P(x,y) тоже неразрешима.

Лемма 2. Пусть k(x) – всюду определенная рекурсивная функция. Тогда проблема Q(x)P(k(x)) сводится к проблеме P(x).

Доказательство. Пусть отношение P(x) разрешимо, т.е. характеристическая функция P (x) рекурсивна. Тогда Q (x)= P (k(x)), т.е. характеристическая функция Q (x) рекурсивна, а отношение Q(x) разрешимо. Значит, проблема Q(x) сводится к проблеме P(x).

Теорема 20. Проблема « x – всюду определенная функция» неразрешима.

Доказательство. Пусть P(x)« x – всюду определенная функция».

Рассмотрим функцию f(x,y)= x (x), x,yN. Функция f(x,y) частично рекурсивна, так как f(x,y)= S 3 (U, I12, I12 ) (x,y), где U(x,y)= x (y) – частично рекурсивная универсальная функция для всех одноместных частично рекурсивных функций. По теореме о параметризации f(x,y)= k ( x ) (y) для некоторой всюду определенной рекурсивной функции k(x).

Если x (x) определено, то f(x,y) определено для всех yN, k ( x ) (y) определено для всех yN, функция k ( x ) всюду определенная.

Если x (x) не определено, то f(x,y) не определено для всех yN, k ( x ) (y) не определено для всех yN, функция k ( x ) нигде не определенная.

Значит, x (x) определено функция k ( x ) всюду определенная.

Отсюда следует, проблемы « x (x) определено» и P(k(x)) одновременно разрешимы или неразрешимы. В силу теоремы 17, проблема P(k(x)) неразрешима. В силу леммы 2, проблема P(x) неразрешима.

Теорема 21. Проблема « x =o» неразрешима.

Доказательство. Пусть P(x)« x =o». Рассмотрим частично рекурсивную функцию f(x,y)=o( x (x)), x,yN. Вновь по теореме о параметризации f(x,y)= k ( x ) (y) для некоторой всюду определенной рекурсивной функции k(x).

Если всюду x (x) определено, то f(x,y)=0 для всех yN, k ( x ) (y)= для всех yN, функция k ( x ) совпадает с нулевой функцией o.

Если всюду x (x) не определено, то f(x,y) не определено для всех yN, k ( x ) (y) не определено для всех yN, в частности, k ( x ) o.

Значит, x (x) определено k ( x ) =o. Отсюда, в силу теоремы 14, следует, что проблема P(k(x)) неразрешима. Отсюда, в силу леммы 2, следует, что проблема P(x) неразрешима.

ТЕМА: ТЕОРЕМА РАЙСА. ЗАДАЧИ НА НЕРАЗРЕШИМОСТЬ ПРОБЛЕМ

Основные вопросы, рассматриваемые на лекции:

1. Теорема Райса 2. Неразрешимость проблемы о равенстве двух вычислимых функций 3. Другие задачи на неразрешимость проблем Краткое содержание лекционного материала Оказывается не существует программы, эффективная процедуры для решения следующего вопроса:обладает ли данная вычислимая функция некоторым нетривиальным свойством или нет?

Теорема 22 (Райс). Пусть W – множество всех частично рекурсивных одноместных функций, AW. Тогда проблема « x A» неразрешима.

Доказательство. Пусть f – нигде не определенная функция, и допустим, что fA (если fA, то рассмотрим проблему « x A »). Так как A, то i A для некоторого индекса iN. Определим новую функцию f(x,y) следующим образом: f(x,y)= i (y) sg x (x) для всех yN. По теореме о параметризации f(x,y)= k ( x ) (y) для некоторой всюду определенной рекурсивной функции k(x).

Если x (x) определено, то f(x,y)= i (y) для всех yN, k ( x ) A.

Если x (x) не определено, то f(x,y) нигде не определено, k ( x ) =fA.

Значит, x (x) определено k ( x ) A. Отсюда, в силу теоремы 1, леммы 2, следует, что проблема « x A» неразрешима.

Если fA, то f A. Так как A W, то аналогично доказывается, что проблема « x A » неразрешима. x A x A. Пусть 1 и 2 – характеристические функции отношений x A и x A. Так как 2= sg 1, то проблема x A сводится к проблеме x A.

Таким образом, теоремы 20-22 показывают, что невозможно написать программу, которая для каждой вычислимой функции определяла бы – является ли эта функция всюду определенной или нулевой, обладает ли какимлибо нетривиальным свойством вычислимых функций.

Теорема 23. Проблема « x = y » неразрешима.

Доказательство. Пусть P(x)« x =o», Q(x,y)« x = y », и i =o для некоторого индекса iN. Тогда P (x)= S 3 ( Q, I1, o) (x), значит, проблема P(x) сводится к проблеме Q(x,y). Отсюда, в силу теоремы 17, следует, что проблема Q(x,y) неразрешима.

Таким образом, теорема 23 показывает, что невозможно написать программу, которая для любых двух вычислимых функций определяла бы – равны эти функции или нет.

Задачи для самостоятельного решения. Докажите, что 1) i =o для некоторого индекса iN;

2) проблема входа « x (c) не определено» неразрешима (c – константа);

3) проблема выхода «nN x (n)=c» неразрешима (c – константа);

4) проблема « x – нигде не определенная функция» неразрешима;

5) проблема « x – постоянная функция» неразрешима;

6) проблема « x = c » неразрешима (c – константа);

7) проблема « x – сюръекция» неразрешима;

8) проблема « x – инъекция» неразрешима;

9) проблема «nN x (n)=y» неразрешима;

10) проблема «m,nN x (m)= y (n)» неразрешима;

11) проблема «область определения x бесконечна» неразрешима;

12) проблема «множество значений x бесконечно» неразрешима.

ТЕМА: МЕРЫ СЛОЖНОСТИ ФУНКЦИЙ

Основные вопросы, рассматриваемые на лекции:

1. Временная и емкостная сложность машин Тьюринга 2. Абстрактная мера сложности 3. Верхняя граница сложности алгоритмов 4. Теорема об ускорении Блюма Краткое содержание лекционного материала Каждая машина Тьюринга Ti с номером i вычисляет для каждого числа n0 функцию in от n переменных с номером i. Временной сложностью машины Ti называется функция tin, равная числу шагов машины Ti, сделанных при вычислении функции in (функция tin не определена тогда и только тогда, когда функция in не определена). Емкостной сложностью машины Ti называется функция sin, равная числу ячеек ленты машины Ti посещаемых в процессе вычисления функции in (функция sin также не определена тогда и только тогда, когда функция in не определена).

Семейство функций {tin} называется абстрактной мерой сложности семейства функций {in}, если выполнены следующие аксиомы Блюма:

1) для каждого номера i функция tin не определена тогда и только тогда, когда функция in не определена;

2) для каждого номера i график (tin) функции tin является разрешимым множеством (определение: i n ={(x 1,…,x n,y)|y=t i n (x 1,…,x n ,y)}).

Заметим, что график (fin) (вычислимой) функции fin является только перечислимым множеством. Напомним, что множество ANn является перечислимым (разрешимым), если существует алгоритм, который для каждого числового вектора x=(x1,…,xn) на вопрос "xA?" отвечает положительно, если xA, и не отвечает (отвечает отрицательно), если xA.

Временная и емкостная сложности машин Тьюринга являются абстрактными мерами сложности (удовлетворяют аксиомам Блюма).

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

Приведем некоторые теоремы о машинно-независимой сложности.

Вопрос о верхней границе сложности: существует ли вычислимая всюду определенная функция h(x), такая, что для любой вычислимой функции f(x) найдется машина Тьюринга Ti, вычисляющая функцию i(x)=f(x), для которой t i (x)h(x). Значения f(x) не могут быть сколь угодно большими. Иначе на запись ответа потребуется больше шагов машины Ti, чем h(x)).

Приведем без доказательства теоремы о верхней границе сложности.

Теорема 24. Для всякой общерекурсивной функция h(x) существует общерекурсивная функция f(x) со значениями 0,1, которая вычисляется машиной Тьюринга Ti, так, что t i (x)h(x) для всех xx0 для некоторого числа x0.

Это значит, верхняя граница меры сложности может быть больше почти всюду любой общерекурсивной функции.

Теорема 25. (теорема Блюма об ускорении). Для всякой общерекурсивной функция r(x) существует общерекурсивная функция f(x) со значениями 0,1, которая вычисляется машиной Тьюринга Ti, и для которой найдется машина Тьюринга Tj, вычисляющая тоже функцию f(x), такая, что r(t j (x))t i (x) для всех xx0 для некоторого числа x0.

Если r(x)=2x, то запись 2(t j (x))t i (x) означает, что мера сложности уменьшена в 2 раза.

ТЕМА: ЯЗЫКИ И ГРАММАТИКИ. ИЕРАРХИЯ ХОМСКОГО

Основные вопросы, рассматриваемые на лекции:

1. Слова в данном алфавите. Пустое слово. Конкатенация слов 2. Определения языка в данном алфавите 3. Определение грамматики. Грамматики типа 0,1,2, Краткое содержание лекционного материала Алфавит A – это конечное непустое множество символов.

Конечная последовательность символов u=u1…um, где u1…umA, mN, называется словом в алфавите A (или словом над алфавитом A). При этом число m называется длиной слова u и обозначается |u|.

Слово длины 0 называется пустым словом и обозначается.

Два слова u=u1…um и v=v1…vn, где u 1,…,u m,v 1,…,v n A, могут быть соединены в одно слово uv=u1…umv1…vn (конкатенация слов u и v).

Через A обозначается множество всех слов в алфавите A. Через A+ обозначается множество всех слов длины m0 в алфавите A.

Конкатенацию двух слов можно рассматривать как бинарную операцию uv=uv в множестве A. Алгебраическая система (A,,) является моноидом, а именно обладает следующими свойствами:

1) операция ассоциативна, т.е. (uv)w=u(vw) для всех u,v,wA;

2) элемент является единицей операции, т.е. u=u=u для всех uA.

(Формальный) язык L в алфавите A – это произвольное подмножество множества A, т.е. LA.

Грамматика – это четверка =(A N,A T,P,S), состоящая из двух непересекающихся алфавитов A N и A T, множества правил P и символа SA N. Символы алфавитов A N и A T называются соответственно нетерминалами и терминалами (иначе, вспомогательными и основными символами). Символ S называется стартовым. Правила грамматики являются упорядоченными парами (u,v) слов в алфавите AB и обозначаются uv.

Пусть,,u,v(A N A T ). Говорят, что слово непосредственно выводится из слова, и пишут |= (или |=), если =u, =v, uv – правило из P. Говорят, что слово выводится из слова, если существует последовательность слов, 1, …, k, слов в алфавите AB, такая, что |=1, 1|=2, …, k1|=k, k|=.

Грамматика порождает язык L=L(), если L={wA|w выводится из S}. Две грамматики 1 и 2 называются эквивалентными, если L(1)=L(2).

В 1957 г. Ноам Хомский предложил следующую классификацию грамматик (и порождаемых ими языков): грамматики типа 0, 1, 2, 3.

Грамматика типа 0 (неограниченная) – это грамматика, в которой каждое правило uv из P никакими условиями не ограничивается.

Грамматика типа 1 (контекстно-зависимая) – это грамматика, определяемая правилами вида Сw, где,,w(A N A T ), СA N, w, или, эквивалентным образом, правилами вида uv, для которых |u||v|.

Грамматика типа 2 (контекстно-свободная) – это грамматика, которая определяется такими же правилами, что и контекстно-зависимая грамматика, но без контекстов и, т.е. правилами вида Сw, где w(A N A T ) +, СA N.

Грамматика типа 3 (или регулярная грамматика) – это грамматика, определяемая правилами вида СaD, Сa, где aA T, С,DA N.

ТЕМА: КЛАССЫ СЛОЖНОСТИ P И NP

Основные вопросы, рассматриваемые на лекции:

1. Асимптоптические оценки функций 2. Класс P задач, решаемых за полиномиальное время 3. Примеры задач, решаемых и не решаемых за полиномиальное время 4. Класс NP. Взаимосвязь классов P и NP Краткое содержание лекционного материала Говорят, что функция g (n) является асимптотически точной оценкой функции f (n), и пишут f (n) = ( g (n)), если Говорят, что функция g (n) является асимптотически верхней оценкой функции f (n), и пишут f (n) = ( g (n)), если Говорят, что функция g (n) является асимптотически точной нижней оценкой функции f (n), и пишут f (n) = ( g (n)), если Говорят, что функция f (n) асимптотически меньше функции g (n), и пишут f (n) = ( g (n)), если Говорят, что функция f (n) асимптотически больше функции g (n), и пишут f (n) = ( g (n)), если Пусть tT (n) = max tT ( x) - временная сложность решения задачи, заx|= n писанной в виде строки x длины n символов машиной T по худшему случаю. Говорят, что машина T решает задачу за полиномиальное время, если tT (n) = O ( p (n)) для некоторого полинома p (n). В проивном случае говорят, что машина T решает задачу за экспоненциальное время.

Класс P - это класс задач, решаемых за полиномиальное время.

Нахождение эйлеровости графа осуществляется алгоритмом сложности O(n 2 ). Тривиальное нахождение гамильтоности графа осуществляется за n!

шагов. Полиномиального алгоритма для этой задачи неизвестно.

В настоящее время неизвестно алгоритма полиномиальной сложности для нахождения выполнимости формул КНФ (конъюнктивной нормальной формы). Тривиальный алгоритм – это перебор 2 n наборов значений.

Недетерминированная машина Тьюринга (НТМ) имеет дополнительное угадывающее устройство. Вначале угадывается решение, а потом НТМ как машина Тьюринга проверяет, верно ли это решение.

Класс NP - это класс задач, решаемых за полиномиальное время НТМ.

Ясно, что P NP. Скорее всего это включение строгое, но доказательства неизвестно. Если NP, то существует полином p (n), n - размерность задачи, такой, что задача решается детерминированным алгоритмом сложности O(2 p (n ) ).

ТЕМА: NP-ПОЛНЫЕ ЗАДАЧИ

Основные вопросы, рассматриваемые на лекции:

1. Полиномиальная сводимость задач 2. NP-полные задачи 3. Теорема Кука Краткое содержание лекционного материала Пусть 1, 2 задачи распознавания, задаваемые в алфавитах A1, A2 соотвественно. Задача 1 сводится к задаче 2, если существует словарная означает, что x задача из i с ответом «Да», i = 1,2.

Отношение полиномиальной сводимости является рефлексивным, симметричным и транзитивным.

Задача назыается NP-полной, если принадлежит классу NP и любая задача NP полиномиально сводится к задаче Теорема Кука. Задача выполнимости КНФ является NP-полная.

Если NP-полная задача 1 сводится к задаче 2 класса NP, то задача 2 тоже NP-полная.

Примеры. 1) Задача о гамильтоновых циклах NP-полная.

2) Задача о целочисленном рюкзаке тоже NP-полная.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра информатики и методики преподавания математики Комплект учебно-методических материалов к учебной дисциплине:

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ЛАБОРАТОРНЫМ РАБОТАМ

для направления 540200 «Физико-математическое образование»

Вахитов Р.Х, доцент, кандидат физико-математических наук, доцент

ЛАБОРАТОРНАЯ РАБОТА №

Тема: Представление примитивно рекурсивных функций Цель: научиться применять систему компьютерной алгебры Mathematica 5.0 для решения представления примитивно рекурсивных функций.

Задача: Представить функции следования, обнуления, проекции и операторы подстановки, примитивной рекурсии в системе Mathematica 5.0.

Теоретические сведения: Окно слева – «Блокнот» заполняется с клавиатуры: 2+2. Вычисление выполняется нажатием клавиш Enter+Shift. Файлы можно сохранять. При первом сохранении файл именуется.

Окно справа – панель (палитра) математических символов. Для умножения, например, можно использовать знак * с клавиатуры или знак с математической палитры.

Числовая функция f называется примитивно рекурсивной функцией, есn ли f построена за конечное число шагов из функций o, s, I i применением операторов подстановки S и примитивной рекурсии R.

Порядок выполнения работы Нулевую функцию и функцию следования в системе Mathematica 5. можно определить по следующим командам:

Применение оператора подстановки g(f1(x1,…,xm),…,fm(x1,…,xm)) осуществляется следующим образом: g[f1[x1_,…,xm_],…,fm[x1_,…,xm_]].

Пример 1. Определение функции перестановкой аргументов.

I31[x_,y_,z_]:=x;

I32[x_,y_,z_]:=y;

I33[x_,y_,z_]:=z;

g[x_,y_,z_]:=f[I32[x,y,z],I33[x,y,z],I31[x,y,z]];

g[x,y,z] Пример 2. Определение постоянной функции.

h[x_,y_,z_]:=s[s[s[s[s[o[I31[x,y,z]]]]]]];

h[x,y,z] Применение схемы примитивной рекурсии для одноместной функции.

Пример 3. Построение функции – сигнума.

sg[0]=0;

sg[x_]:=s[o[I21[x,sg[x-1]]]];

sg[5] Применение схемы примитивной рекурсии для двухместной функции.

Пример 4. Построение операции сложения.

S[x_,0]:=I1[x];

S[x_,y_]:=s[I33[x,y-1,S[x,y-1]]];

S[4,5] Самостоятельно задание. Представить в системе Mathematica 5.0 построение усеченной разности, модуля разности, характеристических функций отношений равенств, "больше", "не больше".

ЛАБОРАТОРНАЯ РАБОТА №

Тема: Представление частично рекурсивных функций Цель: научиться применять систему компьютерной алгебры Mathematica 5.0 для решения представления частично рекурсивных функций.

Задача: Представить функцию Аккермана и оператор минимизации (на примерах) в системе Mathematica 5.0.

Теоретические сведения: Числовая функция f называется частично рекурсивной функцией, если f построена за конечное число шагов из функций Числовая функция f называется общерекурсивной функцией, если f поn строена за конечное число шагов из функций o, s, I i применением оператоm+ ров S, R и M, причем, оператор минимизации g=Mf применяется тогда и только когда, когда f и g – всюду определенные функции. Примитивно рекурсивные функции общерекурсивны, но, обратное утверждение, вообще говоря, неверно. так называемая функция Аккермана общерекурсивна, но не примитивно рекурсивна.

Функция Аккермана определяется рекурсией по двум аргументам:

Запись y[f(x 1,…,x n 1,y)=x n ] означает "наименьшее y, такое, что f(x 1,…,x n 1,y) определено и равно x n ".

Порядок выполнения работы Функция Аккермана в системе Mathematica 5.0 можно определить по следующей программе:

a[0,y_]:=y+1;

a[x_,0]:=a[x-1,1];

a[x_,y_]:= a[x-1,a[x,y-1]];

В компьютерной системе Mathematica 5.0 с целью представления применения оператора минимизации для построения частично рекурсивных функций используем команду while. Программа x=1; While[P[x],x++]; Print[x] тестирует P[x] для x, и если P[x] истинно, то тестирует P[x] для x+1, если P[x] ложно, то печатает x.

Пример 1. Функция x1=y[s(x)=0].

y=1;

While[s[y]x,y++];

x=12;

Print[y] Пример 2. Функция xy=z[x+z=y].

x=12;

y=15;

z=1;

While[x+zy,z++];

Print[z] Пример 3.Функция y = [ x ] (целая часть квадратного корня).

x = 50;

y = 1;

WhileAy2 x, y++E;

Print@y 1D

ЛАБОРАТОРНАЯ РАБОТА №

Тема: Знакомство с симулятором машины Тьюринга Цель: приобрести навыки обращения с симулятором машины Тьюринга и научиться решать задачи на составление программ машин Тьюринга.

Теоретические сведения: Каждая машина Тьюринга имеет конечное число внутренних состояний q 1, …, q n, q 0 (на симуляторе обозначаются 1,…, n, 0; состояния 1, …, n в программе занимают соответственно 1-ю, …, n-ю строки). Состояние q 1 называется начальным, а состояние q 0 – заключительным. Машина Тьюринга начинает работу с состояния q 1 и останавливается в состоянии q 0. Лента машины Тьюринга потенциально бесконечна в обе стороны и разбита на ячейки. Внешний алфавит A – это конечное непустое множество символов, которые по одному вписываются в ячейки ленты. Один из символов алфавита A должен обозначать пустую ячейку. На симуляторе для обозначения пустой ячейки используется символ _ (нижняя черта).

Мы используем обозначение 1 k для слова на ленте, состоящего из k единиц, причем, справа и слева все ячейки пустые. Неотрицательное целое число nN 0 на ленте записывается как 1 n + 1. (В примерах на симуляторе положительное целое число nN записывается как 1 n ). В каждый момент времени машина находится в некотором состоянии q i, где i=1,2,…,n, и обозревает некоторую ячейку с символом a j A. Команда машины Тьюринга – это упорядоченная пятерка q i a j a k Дq l (q i a j a k Дq l ), где qi, ql – состояния машины, i0, a j,a k A, Д{Л,П,Н}, причем, для каждой пары q i a j определяется не более одной тройки a k Дq l. Поэтому команда можно обозначить q i a j.

Выполнение машиной команды q i a j a k Дq: она, в состоянии q i и при чтении символа a j, заменяет символ a j на символ a k, двигается вдоль ленты на одну ячейку влево (Д=Л) или вправо (Д=П), или остается на месте (Д=Н), и переходит на новое состояние q l.

Программа машины Тьюринга – это множество команд для данного множества состояний q1, q2, …, qn, q0 и данного внешнего алфавита A.

В симуляторе машины Тьюринга программа представлена в виде таблицы: со строками – состояниями и со столбцами – символами. На пересечении строки "qi" и столбца "a j " пишется команда "a k Д q l " (с пробелами!).

Конфигурация машины Тьюринга – это слово _..._s 1 …q i s j …s k _..._, где q i – состояние машины, s 1,…,s k A, s 1 …s k – слово на ленте, s 1,s k _, 1jk, s j – символ, который в данный момент обозревается на ленте.

Задания по знакомству с работой симулятора машины Тьюринга.

1. Добавить 3 ячейки с выбором символа 1; удалить ячейку.

2. Записать на ленте число 5 и пару (3,7).

3. Добавить строку; удалить строку.

4. Добавить столбец с выбором символа 1; удалить столбец.

5. Загрузить программу: умножение. Выполнить: 52.

6. Заменить исходные данные в ленте: добавить ячейку во втором аргументе и удалить ячейку в первом аргументе. Выполнить 43.

7. Загрузить программу: вычитание. Выполнить: 52.

8. Заменить исходные данные в ленте: удалить 3 ячейки в первом аргументе и прибавить 3 ячейки во втором аргументе. Выполнить 25.

ЛАБОРАТОРНАЯ РАБОТА №

Тема: Одноместные функции, вычислимые по Тьюрингу Цель: научиться решать задачи на составление программ машин Тьюринга для вычисления одноместных функций.

Задача: Составьте программу машины Тьюринга для вычисления одноместной функции y=f(x) и напишите пример преобразования начальной конфигурации q11x + 1 в заключительную конфигурацию (q0)1y + 1 (с q0 на любом месте):

1) функция прибавления единицы s(x)=x+1;

3) нулевая функция o(x)=0;

4) функция g(x)=1.

Теоретические сведения: Функция f:N 0 n N 0 с областью определения DN 0 n называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел x 1,x 2,…,x n N начальную конфигурацию q11x1 +1 _ 1x 2 +1 _... _ 1 n преобразует в заключительную конфигурациюq01y+1, если (x 1,x 2,…,x n )D и y=f(x 1,x 2,…,x n ), и не выдает никакого результата, если (x 1,x 2,…,x n )D.

В частности, одноместная функция f:N 0 N 0 с областью определения DN 0 называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел xN начальную конфигурацию q11x +1 преобразует в заключительную конфигурациюq01y+1, если xD и y=f(x), и не выдает никакого результата, если xD.

Порядок выполнения работы 1) Программа Тьюринга для функции s:

Преобразования конфигурации при x=2 (и y=3): q1111, q1_111, q01111.

2) Программа Тьюринга для функции f:

Преобразования конфигурации при x=2 (и y=4):

q1111, q1_111, q2_1111, q011111.

3) Программа Тьюринга для функции o:

Преобразования конфигурации при x=2 (и y=0):

q1111, _ _ _q1_, _ _ _q01.

4) Программа Тьюринга для функции g:

Преобразования конфигурации при x=2 (и y=1):

q1111, _ _ _q1_, _ _ _q2_1, q011.

Самостоятельно выполнить задание для одной из функций вида f(x)=x+k, k=3,4,5,…, и для одной из функций вида g(x)=k, k=2,3,4,…

ЛАБОРАТОРНАЯ РАБОТА №

Тема: Двухместные функции, вычислимые по Тьюрингу Цель: научиться решать задачи на составление программ машин Тьюринга для вычисления двухместных функций.

Задача: Составьте программу машины Тьюринга для вычисления двухместной функции z=f(x,y) и напишите существенно отличающиеся примеры преобразований начальной конфигурации q11x + 1 _1y + 1 в заключительную конфигурацию (q0)1z + 1 (с q0 на любом месте), если даны функции:

1) выбор координаты I 1 2 (x,y)=x и I 2 2 (x,y)=y;

2) f ( x,y)=x+1 и f ( x,y)=y+1;

3) нуль-функция o2(x,y)=0 и f ( x,y)=1;

4) z=x+y+2 и сложение z=x+y;

Теоретические сведения: Двухместная функция f:N 0 N 0 N 0 с областью определения DN 0 N 0 называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел x,yN начальную конфигурацию q11x +1 _1y +1 преобразует в заключительную конфигурациюq01z+1, если (x,y)D и z=f(x,y), и не выдает никакого результата, если (x,y)D.

Порядок выполнения работы 1) Программа машины Тьюринга для функции I 1 2 :

Преобразования конфигурации для I 1 2 при x=2, y=1, z =2:

q1111_11, 111q1_11, 111_q211, 111_ _ _q2, 111_ _ _q0.

Программа машины Тьюринга для функции I 2 2 :

Преобразования конфигурации для I 2 2 при x=2, y=1, z =1:

q1111_11, _ _ _q1_11, _ _ _ _q011.

2) Программа машины Тьюринга для функции f ( x,y)=x+1:

Преобразования конфигурации для f ( x,y)=x+1 при x=2, y=1, z =3:

q1111_11, 111q1_11, 111_q211, 111_ _ _q2, 111_ _ _q3, 11q31_ _ _, 11q31_ _ _, 111q4, 111q4, 1111q0.

Программа машины Тьюринга для функции f ( x,y)=y+1:

Преобразования конфигурации для f ( x,y)=y+1 при x=2, y=1, z =2:

q1111_11, _ _ _q1_11, _ _ q0_111.

3) Программа машины Тьюринга для функции o2:

Преобразования конфигурации для o2 при x=2, y=1, z =0:

q1111_11, _ _ _q1_11, _ _ _ _q211, _ _ _ _ _ _q2, q0_1.

Программа машины Тьюринга функции f ( x,y)=1:

Преобразования конфигурации для f ( x,y)=1 при x=2, y=1, z =1:

q1111_11, _ _ _q1_11, _ _ _ _q211, _ _ _ _ _ _q2, q3_1, q0_11.

4) Программа машины Тьюринга для функции z =x+y+2:



Pages:   || 2 |
 


Похожие работы:

«Государственное образовательное учреждение высшего профессионального образования Российский государственный университет нефти и газа им. И. М. Губкина Департамент оперативного управления реализацией программы НИУ АННОТАЦИЯ 3.3.3/2 Разработка программ магистерской подготовки Автоматизированные системы диспетчерского управления в нефтегазовом комплексе, реализуемой в соответствии с ПНР университета Москва 2011 3 Программа развития государственного образовательного учреждения высшего...»

«Федеральное агентство по образованию АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ГОУ ВПО АмГУ УТВЕРЖДАЮ Зав. кафедрой ОМиИ Г. В. Литовка __2007 г. МАТЕМАТИКА Часть 4 УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ для специальностей: 080109, 080105, 080102, 080507, 080502, 080504, 080111 Составители: Г. Н. Торопчина, Г. П. Вохминцева Благовещенск 2007 г. Печатается по решению редакционно-издательского совета факультета математики и информатики Амурского государственного университета Г. Н. Торопчина, Г.П....»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Тверской государственный университет Факультет прикладной математики и кибернетики УТВЕРЖДАЮ Руководитель направления подготовки магистров _С.М.Дудаков 23марта2012 г. Учебно-методический комплекс по дисциплине Методы математического моделирования для магистров 1 курс, 1, 2 семестр Направление подготовки 0104000- прикладная математика и информатика...»

«Акт контроля за деятельностью ГБУК Белгородская государственная универсальная научная библиотека по итогам плановой проверки, проведенной лицами, уполномоченными на проведение проверки Настоящий акт составлен в том, что комиссией в составе представителей управления культуры Белгородской области: Андросовой Н.О., заместителя начальника управления культуры области - начальника отдела развития социально-культурной деятельности, библиотечного дела и взаимодействия с органами местного...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ СОГЛАСОВАНО: УТВЕРЖДАЮ: Первый Заместитель Министра Заместитель Министра Российской Федерации по связи образования Российской Федерации и информатизации В.Д. Шадриков Ю.А. Павленко 10.03.2000 г. 23.02.2000 г. Регистрационный номер 19тех/маг ГОСУДАРСТВЕННЫЙ ОБРАЗОВАТЕЛЬНЫЙ СТАНДАРТ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Направление 210400 Телекоммуникации Степень (квалификация) - магистр техники и технологии Вводится с момента утверждения Москва 2000...»

«Министерство образования и наук и Российской Федерации Федеральное агентство по образованию Российская академия наук Государственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет) Российский фонд фундаментальных исследований ТРУДЫ 49-Й НАУЧНОЙ КОНФЕРЕНЦИИ МФТИ СОВРЕМЕННЫЕ ПРОБЛЕМЫ ФУНДАМЕНТАЛЬНЫХ И ПРИКЛАДНЫХ НАУК Часть VII УПРАВЛЕНИЕ И ПРИКЛАДНАЯ МТЕМАТИКА 24–25 ноября 2006 года Москва – Долгопрудный 49-я...»

«Аннотация специальности 031201 Теория и методика преподавания иностранных языков и культур Квалификация выпускника: специалист (лингвист, преподаватель двух иностранных языков) Введена в действие в 2000 г., приказ Минобразования РФ № 686. Нормативный срок освоения программы – 5 лет. Программа включает дисциплины федерального компонента, регионального компонента, дисциплин по выбору студента и факультативных дисциплин. Программа предусматривает итоговую государственную аттестацию на основе...»

«  Древние языки и культуры  Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики Евразийский открытый институт В.М. Заболотный ДРЕВНИЕ ЯЗЫКИ  И КУЛЬТУРЫ  Учебно-методический комплекс Москва, 2009 1   Древние языки и культуры  УДК 81 ББК 81 З 125 Научный редактор: д.ф.н., проф. С.С. Хромов Заболотный, В.М. ДРЕВНИЕ ЯЗЫКИ И КУЛЬТУРЫ. – М.: Изд. центр З 125 ЕАОИ, 2009. – 308 с. ISBN 978-5-374-00262-1 УДК ББК © Заболотный В.М., ©...»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ СИСТЕМ ИНФОРМАТИКИ ИМ. А.П. ЕРШОВА НАУЧНЫЙ СОВЕТ ПО МУЗЕЯМ И.А. Крайнева, Н.А. Черемных Путь программиста Ответственный редактор доктор физико-математических наук, профессор А. Г. Марчук Новосибирск 2011 УДК 007(092) ББК 32.81 Е 80 Путь программиста / И.А Крайнева., Н.А. Черемных. Новосибирск: Нонпарель, 2011. 222 с. ISBN 978-5-93089-033-4 Биография выдающегося ученого, математика, программиста, создателя Сибирской школы программирования...»

«Учебно – методический комплекс “Охрана труда” 1. Учебная программа, для Белорусского государственного университета по всем специальностям факультета прикладной математики и информатики. 2. Примерный тематический план. 3. Программа курса “Охрана труда” для студентов 5-ого курса ФПМИ. 4. Содержание лекционного курса “Охрана труда”. 5. Курс лекций “Охрана труда”. 6. Темы рефератов по курсу “Охрана труда”. 7. Темы рефератов(дополнение к основным темам по курсу “Охрана труда”). 8. Дополнительные...»

«Информатика. 11 класс. Вариант ИНФ10101 2 Инструкция по выполнению работы Тренировочная работа № 1 На выполнение работы по информатике и ИКТ отводится 235 минут. Работа состоит из 3 частей, содержащих 32 задания. Рекомендуем не более по ИНФОРМАТИКЕ 1,5 часов (90 минут) отвести на выполнение заданий частей 1 и 2, а остальное время – на часть 3. 8 октября 2013 года Часть 1 содержит 13 заданий (А1–А13). К каждому заданию даётся четыре варианта ответа, из которых только один правильный 11 класс...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Кемеровский государственный университет Факультет гуманитарный Кафедра иностранных языков УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Б1. Б2 Иностранный язык (английский) (код и название дисциплины по учебному плану направления) Для направления 010400.62 Прикладная математика и информатика (код и название направления) Цикл дисциплин учебного...»

«МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ проект УТВЕРЖДАЮ: Заместитель Министра образования Российской Федерации В.Д. Шадриков “”_2000 г. Номер Государственной регистрации ГОСУДАРСТВЕННЫЙ ОБРАЗОВАТЕЛЬНЫЙ СТАНДАРТ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ по специальности: 351700 - ИНФОРМАЦИОННО-КОММУНИКАТИВНЫЕ СИСТЕМЫ В ГЕОГРАФИИ Квалификация: Геоинформатик Вводится с момента утверждения Москва, 2000 г. 1. ОБЩАЯ ХАРАКТЕРИСТИКА СПЕЦИАЛЬНОСТИ 351700 -...»

«Министерство Образования Российской Федерации Международный образовательный консорциум Открытое образование Московский государственный университет экономики, статистики и информатики АНО Евразийский открытый институт О.А. Кудинов Конституционное право зарубежных стран Учебно-практическое пособие Москва – 2003 УДК 342 ББК 67.99 К 65 Кудинов О.А. КОНСТИТУЦИОННОЕ ПРАВО ЗАРУБЕЖНЫХ СТРАН: Учебнопрактическое пособие / Московский государственный университет экономики, статистики и информатики. - М.:...»

«Применение информационных технологий при создании школьной газеты Волынская Маргарита Николаевна, учитель информатики МОУ Мошинская общеобразовательная школа Ревенко Ирина Валентиновна, учитель русского языка и литературы МОУ Мошинская общеобразовательная школа Список ИПМ: ИПМ 1. Теоретическая интерпретация ИПМ 2. Этапы работы над выпуском школьной газеты ИПМ 3. Развитие базовых и дополнительных знаний, умений и навыков во время работы в издательских системах ИПМ 4. Тематическое планирование и...»

«СОДЕРЖАНИЕ Определение ООП.. 1 4 Характеристика профессиональной деятельности выпускника ООП 2 бакалавриата по направлению подготовки 230700.62 – Прикладная информатика.. 7 Компетенции выпускника ООП бакалавриата, формируемые 3 в результате освоения данной ООП ВПО. 9 Документы, регламентирующие содержание и организацию образовательного процесса при реализации ООП бакалавриата по направлению подготовки 230700.62 – Прикладная информатика. 12 Фактическое ресурсное обеспечение ООП бакалавриата...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное образовательное учреждение высшего профессионального образования КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ УТВЕРЖДАЮ Декан факультета прикладной информатики профессор _ С.А. Курносов 29 06 2012 г. РАБОЧАЯ ПРОГРАММА дисциплины: Информационная безопасность и защита информации для специальности 230201.65 - Информационные системы технологии Факультет Прикладной информатики Ведущая кафедра Компьютерных технологий...»

«Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ РУКОВОДЯЩИЙ РД ПГУТИ ДОКУМЕНТ 2.64.7-2013 Система управления качеством образования ПОРЯДОК ПЕРЕВОДА, ОТЧИСЛЕНИЯ И ВОССТАНОВЛЕНИЯ СТУДЕНТОВ В ПГУТИ Положение Самара 2013 РД ПГУТИ 2.64.7 – 2013 ПОРЯДОК ПЕРЕВОДА, ОТЧИСЛЕНИЯ И ВОССТАНОВЛЕНИЯ СТУДЕНТОВ В ПГУТИ Положение Предисловие 1 РАЗРАБОТАН Отделом качества образования ПГУТИ...»

«РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. А.И. ГЕРЦЕНА ДИСТАНЦИОННОЕ ОБУЧЕНИЕ РУКОВОДСТВО ПРЕПОДАВАТЕЛЮ MOODLE РЕСУРСНОИНФОРМАЦИОННЫЙ ОТДЕЛ Санкт-Петербург 2009 УПРАВЛЕНИЕ ИНФОРМАТИЗАЦИИ РЕСУРСНО-ИНФОРМАЦИОННЫЙ ОТДЕЛ 2 УПРАВЛЕНИЕ ИНФОРМАТИЗАЦИИ РЕСУРСНО-ИНФОРМАЦИОННЫЙ ОТДЕЛ СОДЕРЖАНИЕ ВВЕДЕНИЕ РЕГИСТРАЦИЯ ПОДТВЕРЖДЕНИЕ РЕГИСТРАЦИИ АВТОРИЗАЦИЯ ДОБАВЛЕНИЕ КУРСА ДОБАВЛЕНИЕ РЕСУРСА ДОБАВЛЕНИЕ ЭЛЕМЕНТА КУРСА Добавление теста Добавление форума...»

«СБОРНИК РАБОЧИХ ПРОГРАММ Профиль бакалавриата : Математическое и программное обеспечение вычислительных машин и компьютерных сетей Содержание Страница Б.1.1 Иностранный язык 2 Б.1.2 История 18 Б.1.3 Философия 36 Б.1.4 Экономика 47 Б.1.5 Социология 57 Б.1.6 Культурология 71 Б.1.7 Правоведение 83 Б.1.8.1 Политология 89 Б.1.8.2 Мировые цивилизации, философии и культуры Б.2.1 Алгебра и геометрия Б.2.2 Математический анализ Б.2.3 Комплексный анализ Б.2.4 Функциональный анализ Б.2.5, Б.2.12 Физика...»














 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.