Программа обучения студентов (Syllabus) по дисциплине «Теория алгоритмов» для специальности 050111 «Информатика» форма обучения очная Всего 2 кредитов icon

Программа обучения студентов (Syllabus) по дисциплине «Теория алгоритмов» для специальности 050111 «Информатика» форма обучения очная Всего 2 кредитов


Смотрите также:
Программа обучения студентов ( Syllabus ) по дисциплине Современные методы проектирования баз...
Программа обучения студентов (Syllabus) по дисциплине Криптографические методы з ащиты...
Программа обучения студентов (Syllabus) по дисциплине: Судебная экспертология и теория судебных...
Программа обучения студентов (Syllabus) по дисциплине Защита информации для специальности...
Программа обучения студентов ( Syllabus ) по дисциплине «Вариационное исчисление и методы...
Программа обучения студентов (Syllabus) по дисциплине Экспертиза промышленных товаров для...
Программа обучения студентов (Syllabus) по дисциплине «Структурная ботаника» для специальности...
Программа обучения студентов ( Syllabus ) по дисциплине: Менеджмент изменений для специальности:...
Программа обучения студентов ( Syllabus ) по дисциплине: Основы логопедии наименование...
Программа обучения студентов (Syllabus) по дисциплине «ботаника» для специальности 050113...
Программа обучения студентов ( Syllabus ) по дисциплине: Судебно-психологическая экспертиза...
Программа обучения студентов ( Syllabus ) по дисциплине: психология несовершеннолетних девиантов...



Загрузка...
скачать
1.2. ПРОГРАММА ДИСЦИПЛИНЫ ДЛЯ СТУДЕНТА (SILLABUS)


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

ВОСТОЧНО-КАЗАХСТАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. С.АМАНЖОЛОВА


«Утверждена»

На заседании Методического Совета ФМФиТ

Председатель______Рамазанова Г

«____»______________ 2009г.


ПРОГРАММА ОБУЧЕНИЯ СТУДЕНТОВ


(Syllabus)


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

для специальности 050111 – «Информатика»

форма обучения очная


Всего 2 кредитов

Курс 3

Семестр 6

Лекций 15 часов

Лабораторные работы 30 часов

Количество рубежных контролей (РК) 2

СРСП (аудиторных) 15 часов

СРС – 30 часов

Экзамен 6 семестр

Общая трудоемкость 90 часов


Усть-Каменогорск, 2009

Силлабус составлен на основании государственного общеобязательного стандарта, типового учебного плана и типовой программы по дисциплине «Теория алгоритмов» для специальности 050111- «Информатика», разработанной на кафедре


Силлабус обсужден и рекомендован на заседании кафедры

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

Протокол № ____ от «__» ____________ 2009 г.


Заведующий кафедрой ______________ ^ Ж.З Жантасова


Одобрен методическим советом Факультета математики, физики и технологий

Протокол № ____ от «__» ____________ 2009 г.


Председатель _____________ Рамазанова Г

1. Общие сведения:

1.1 Название и код дисциплины: «Теория алгоритмов», TA-4316

1.2 Данные о преподавателе: Кабланбекова Б.А.старший преподаватель кафедры ММиКТ

1.3 Контактная информация: режим пребывания на кафедре, понеделник-пятница 08.00- 17.00 раб.т. 47-78-44. Место проведения занятий: ВКГУ, корпус №7, ул. Ворошилова, 148

1.4 Дата: 2009-2010 учебный год, 6 семестр.

Количество кредитов 2

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

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

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



  1. Описание курса.

Научить студентов использовать свои знания, полученные при изучении курсов алгебры, математического анализа, математической логики и дискретной математики и кодировать программные языки высокого уровня, машину Шенфилда, последовательные пределы и практиковаться по универсальным функциям создать программы – основная цель и обязанность предмета.


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

Постреквезиты: программирование 2, 3. Программирование в Visual FoxPro, Delphi, VisualBasic, C++.


3. ^ Краткая содержания курса

История развития теория алгоритмов. Частично рекурсивные функции Машина Шёнфильда. Понятия макроса.

Цель: Ознакомить студентов про понятия теории алгоритма и сотавит программу для них.

Задача: С помощью базовые операции, примитивный операции, операция суперпозиция и минимизации решить задачу.

Кодирование машины Шёнфильда и конечных последовательностях. Теорема Клини о нормальной форме. Лемма о кусочной рекурсии. С помощью предикатов и регистров составить программу и решить задачу для доказателстве последовательности и лемму.


^ 4. Календарно-тематический план распределения часов по видам занятий с указанием недели, темы.

4.1 Лекции:


^ Наимен. модуля и шифр

Наименование изучаемых вопросов

Кол-во часов

Распред. по неделям

Литература №

Примечание

1

2

3

4

5

6

Модуль 1

1.История развития теория алгоритмов.

Введение. Поверхностное изучение история развития ЭВМ и теории алгоритмов.

1



1

1-3





2. Базовые алгоритмические конструкции.

Команды алгоритма.

Способы записи алгоритма

2

2-3

1-3




3.Методы сортировок и поиска данных

Методы сортировок (обмена и выбора).

Методы поиска данных.

2

4-5







4.Рекурсивные функции

Базовые операции, примитивный операции, операция суперпозиция и минимизация.

2

6-7

1-3




5.Модели вычислений

Автомат Неймана

2

8-9

1-3




6.Машина Шенфильда

На машине Шенфильда составить программу и вычислить.

2

10-11

1-3




7.Сложность алгоритма

Машины РАМ и РАМ*.

Оценки сложности алгоритмов

2

12-13

1-3




8.Методы повышения эффективности алгоритмов

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


2

14-15

1-3




Всего




15

15









^ 4.2 Лабораторные занятия:


Тема

Наименование изучаемых вопросов

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

Распределение по неделям

Литература №

Форма контроля

Примечание

1

2

3

4

5

6

7

1.История развития теория алгоритмов.


Введение. Поверхностное изучение история развития ЭВМ и теории алгоритмов.

2

1

1-4







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

Базовые операции, примитивный операции, операция суперпозиция и минимизация.

2

2

1-4

Решить задачу. Доказать.




3.Машина Тьюринга

На машине Тьюринга составить программу и вычислить.

2

3

1-4

Составить программу




4.Формальные грамматики и языки

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

2

4

1-4

Составить программу




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


Предикаты, регистры и составить программу.

2

5

1-4

Составить программу




6. Равнодоступ-ная адресная машина (РАМ) с хранимой программой.


Машина с произвольным доступом к памяти и возможностью модификаций команд (РАМ*)

2

6

1-4

Составить программу





7. Полиномиаль-ные и экспоненциаль-ные алгоритмы. Трудноразрешимые задачи


Полиномиальные и экспоненциаль-ные алгоритмы

2

7

1-4

Составить программу Доказать.




8. Примитивно-рекурсивные функции и базис Клини. Примитивная рекурсивность суммы и факториала

Теорема Клини о нормальной форме и ее последствия.



2

8

1-4

Составить программу Доказать.




9. Теоремы Шеннона

2 теоремы Шеннона. Эквивалентность машин

Общая идея построения


2

9

5-6

Составить программу Доказать




10. Алгоритмы и структуры данных

Структуры данных: простые и сложные

3

10

6-7

Составить программу Доказать




11. Списки, очереди, стеки


Применение списка, очереди, стеки

данных в алгоритмах

2

11

1-5

Составить программу Доказать




12. Представление множеств.

Применение статических, полустатических структур данных

2

12

2-6

Составить программу Доказать




13. Графы и их представление

Применение динамических структур данных

3

13

2-6

Составить программу Доказать




14. Деревья и их представление


Применение деревьев и их представление

2

14

2-6

Составить программу Доказать




Всего:




30

15











^ 5. График подготовки материалов для подготовки к занятиям

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

№ п/п


Темы занятий

Задания на СРС

Цель и содержание занятий

Рекомен-дуемая литерату-ра

Форма контроля

Макс

балл , %

1

История развития теория алгоритмов.

Алгоритмы циклических структур с использованием массивов


1.Разработать алгоритм умножения матрицы на вектор.

2.Разработать алгоритм умножения матрицы на матрицу.

3.Разработать алгоритм транспонирования матрицы.

4.Разработать алгоритм, реализующий операцию объединения следующих двух

множеств:

A = {a1, a2, . . ., ak} и

B= {b1, b2, ... , bn}

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


1-4

Составить программу

10%

2

Функции и процедуры.


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

2. Составьте программу нахождения наименьшего натурального N-значного числа Х (X>=10), равного утроенному произведению своих цифр.

3. Дано натуральное число. Определите, сколько четных цифр используется в записи этого числа.

4. Дана последовательность К чисел. Определите, сколько чисел этой последовательности содержит в своей записи все цифры больше некоторого числа n введенного с клавиатуры.

5. Для последовательности вводимых с клавиатуры чисел, выведите суммы цифр каждого введенного числа. Признак конца ввода - число -1.

Использование процедур и функции.

1-4

Составить программу

10%

3

Рекурсивные функции.

Составьте программу

a) нахождения n-го члена геометрической прогрессии,

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

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

г) нахождения n-го члена ряда Фибоначчи.


Использование рекурсии в программах.

1-4

Составить программу

10%

9

Всего:

30 часов










30%


6. График самостоятельной работы студентов с преподавателем:

№ п/п


Темы занятий

Задания на СРСП

Цель и содержание занятий

Рекомен-дуемая литература

Форма

контроля

Макс

балл

1

Циклы и

виды циклов.

.


1. Определите члены последовательность Фибоначчи.

2. Найдите максимальный элемент в одномерном массиве.

3. Составьте алгоритм вычисления суммы .

Указание. Обозначьте и используйте соотношения



4. Вычислите



5. Определите n–й член последовательности, в которой каждый следующий член равен сумме обратных величин всех предыдущих

Составление программ циклических структур

1-4

Соста-вить прог-рамму

5%

2

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

1. Определите n–й член последовательности, в которой каждый следующий член равен сумме квадратов всех предыдущих.

2. При положительном а решением уравнения х=х/2+а/(2х) служит х=. Рекуррентное соотношение

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

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



4. Составьте алгоритм, вычисляющий n–й член последовательности, заданной соотношениями:

5. Составить рекурсивную программу ввода с клавиатуры последовательности чисел (окончание ввода - 0) и вывода ее на экран в обратном порядке.

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

Составление программ с помощью рекурсии

1-4

Соста-вить прог-рамму

5%

3

Примитивная рекурсия

1.Дано множество слов одинаковой длины, причем первые два слова выделены.

2. Построить цепь от первого выделенного слова ко второму так, чтобы все слова этой цепи были только из заданного множества. Соседние слова построенной цепи должны отличаться

только одной буквой.

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

4. Грани кубика разбиты на клетки 5х5. Каждая из клеток выкрашена в белый или синий цвет. Переход из клетки в клетку допускается только через общую сторону при условии совпадения цветов этих клеток. Построить маршрут перехода из одной заданной клетки в другую заданную клетку этого же цвета.

5. Имеется клетчатая ткань размером NxN клеток. Разрезать ее на M квадратных частей,

не нарушая целостности клеток.

Составление алгоритмов с примитивной рекурсией

1-4

Составить алгоритм

5%

9

Всего:

15 часов










15%



7. Литература

Основная литература:



  1. Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов: Учебное пособие. Улан-Удэ: Изд-во ВСГТУ, 2000.

  2. Мальцев А.И. Алгоритмы и рекурсивные функции. –М., Наука 1986.

  3. Колмогоров А.Н. и Успенский В.А. К определению алгоритма. – УМН, Барздинь Я.М. Об одном классе машин Тьюринг. – Алгебра и логика, 1962.

  4. Глушков В.М. Теория алгоритмов. – Киев, 1961.

  5. Детловс В.К. Нормальные алгоритмы и рекурсивные функции. – ДАН СССР, 1953

  6. Нагорный Н.М. К усилению теоремы приведения теории нормальных алгоритмов. – ДАН СССР, 1953.

  7. Новиков П.С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп. – АН СССР, 1955.

  8. А.А.Марков Теория алгорифмов М.Л. Изд-во АН СССР, 1954, 374с., 1984, 432 с.

  9. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов. М. Мир, 1979. 536 с.

  10. Проблемы математической логики (сб.). Под ред. Козмидиади и др. М. Мир 1970, 432 с.

  11. Э.Мендельсон. Введение в математическую логику. (Гл. 5.) M. 1971, 1976, 1984. 320 с.

  12. С.К.Клини. Математическая логика. (Гл. V). М. Мир, 1973. 480с.

  13. Ю.Л.Ершов, Е.А.Палютин. Математическая логика. (Гл. 7). М. "Наука" 1971. 320 с.

  14. Р.Смальян. Теория формальных систем. (Гл. I, II.) М. Наука, 1981, 207 с.

  15. Дж.Шенфилд. Математическая логика. (Гл. 6-7.) М. Наука, 1975. 527 с.

  16. С.К.Клини. Введение в метаматематику. М "Иностраниздат", 1957, 526 с.

  17. Н.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Ч 3. Вычислимые функции. M. МЦНМО 1999. 126с.

  18. К.А.Гоуд. Доказательства как описания вычислений. В кн. "Математическая логика в программировании". Под ред. М.В.Захарьящева и Ю.И.Янова. М. 1991. С. 311-330. (407 с.)

  19. В.Г.Карпов, В.А.Мощенский Математическая логика и дискретная математика, Минск "Высшая школа", 1977. 254 с.

  20. А.Н.Колмогоров, Драгалин Математическая логика, дополнительные главы, М МГУ, 1984. 120 с.

  21. А.Н.Колмогоров, Драгалин Введение в математическую логику, М. МГУ. 1982.

  22. Н.К.Косовский Основы теории элементарных алгоритмов, Л. ЛГУ, 1987. 132 с.

  23. С.Л.Эдельман Математическая логика, М. Высшая школа. 1975. 176с. 

  24. Дж.Булос,Р.Джефри. Вычислимость и логика, М. Мир. 1994. 396с. 

  25. Котов В.М., Соболевская Е.П. Структуры данных и алгоритмы: теория и практика.  Мн.: БГУ. 2004.  252 с.

  26. Ковалев М.Я., Котов В.М.,Лепин В.В. Теория алгоритмов. Часть 2. Приближенные алгоритмы. – Мн.: БГУ, 2003. – 147 с.

  27. Котов В.М., Пилипчук Л.А., Соболевская Е.П. Теория алгоритмов. Ч.1.  Мн.: БГУ. 2001.  192 с.

  28. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.  М.: МЦНМО, 1999.  960 с., 263 ил.



Дополнительная литература:

  1. Поляков Е.А. Алгебры рекурсивных функций. – Алгебра и логика, 1964.

  2. Пост Э. Конечные комбинаторные процессы. М.: Наука, 1979.

  3. Трахтенброт Б.А. Алгоритмы и машинное решение задач. –М.: Физматгиз, 1960.

  4. Иринчеев А.А., Мангадаев А.М., Паскаль в примерах. - Улан-Удэ: Изд-во ВСГТУ, 2004.

  5. В.В. Васильев, Л.В. Хливненко, Pascal. Файлы,2007.

  6. Математическая логика. Под ред. А.А.Столяра. Гл. А.4, Б.3. М. 1971. 

  7. Вирт Н.  Алгоритмы и структуры данных.  СПб.: Невский Диалект, 2001. 352с.

  8. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.  М.: Наука, 1990. 383с.

  9. Котов В.М.  Алгоритмы для задач разбиения и упаковки. Научное издание.  Мн.: БГУ. 2001.  97 с.

  10. Липский В.  Комбинаторика для программистов.  М.: Мир,1988.  214 с.

  11. Пападдимитриу Х.,Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.  М.: Мир,1971.  512с.

  12. Рейнгольд Э., Нивергельт Ю., Део Н.  Комбинаторные алгоритмы теория и практика.  М.: Мир, 1980.  476 c.

  13. Mark Allen Weiss. Data structures and algorithm analysis.  Benjamin/Cummings Publishing Company, 1992.  455 p.

  14. C. Shaffer. A Practical Introduction to Data Structure and Algorithm Analysis.  London: Prentice Hall International, 1997.  494 p.




  1. Информация по оценке



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

Оценка по буквенной системе

Баллы

%-ное содержание

Оценка по традиционной системе

A

4,0

95-100

Отлично

A-

3,67

90-94

B+

3,33

85-89

Хорошо

B

3,0

80-84

B-

2,67

75-79

C+

2,33

70-74

Удовлетворительно

C

2,0

65-69

C-

1,67

60-64

D+

1,33

55-59

D

1,0

50-54

F

0

0-49

Неудовлетворительно



«Рейтинг-шкала»

^ Форма контроля

Баллы

Лекция

20

Практические зан./семинарские зан./ лабораторные работы

25

Самостоятельные работы студента с преподавателем

30

Самостоятельные работы студента

25

Рейтинг 1

100

Лекция

20

Практические зан./семинарские зан./ лабораторные работы

25

Самостоятельные работы студента с преподавателем

30

Самостоятельные работы студента

25

Рейтинг 2

100

Экзамен

100

Всего

300


б) Итоговая оценка по дисциплине в процентном содержании определяется:



где: Р1 – процентное содержание оценки первого рейтинга;

Р2 – процентное содержание оценки второго рейтинга;

Э – процентное содержание экзаменационной оценки.


^ 9. Политика выставления баллов

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

- текущего контроля (проводится еженедельно)

- рубежного контроля (на 7,14 неделях)

- итогового контроля (проводится один раз в конце периода, т.е. экзамен).

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

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

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


^ 6. Политика выставления баллов

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


По дисциплине всего:

15-лекции

30 - лабораторных

15 - СРСП

30 – СРС

Макс. балл: за 90 часов - 200


По 1-рейтингу:

8-лекции

15- лабораторных

7- СРСП

15 СРС

Макс. балл по 1-рейтингу: за 44 часа – 100


По 2-рейтингу:

8-лекции

15- лабораторных

8- СРСП

15 СРС

Макс. балл по 2-рейтингу: за 46 часов – 100


Распределение процентов1-рейтинга по неделям:


Вид

контроля

1нед

2нед

3нед

4нед

5нед

6нед

7нед

Всего

Лекции

За посещение

Устный опрос

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

3

1

1

20%



Лабораторные работы

За посещение лабораторных

Защита лабораторных

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

8

1

1

25%

СРСП

Выполнение домашних заданий

Реферат




5



2

2

1

2

2

1

2

2

1

2

2

1

2

2

1

30%

СРС

Коллоквиум

Семестровое задание

1

1

1

1

1

1

1

1

1

1

1

1

3

1

1

3

1

1

3

1

1

25%

ИТОГО по 1-рейтингу

7,5

12,5

12,5

12,5

15

15

25

100%



^ Распределение процентов 2-рейтинга по неделям:


Вид

контроля

8

9

10

11

12

13

14

15

Всего

Лекции

За посещение

Устный опрос

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

0,5

1

1

20%



Лабораторные работы

За посещение лабораторных

Защита лабораторных

0,5

1

1

1

1

1

1

1

1

1,5

1

1

1,5

1

1

1

1

1

0,5

1

1

0,5

1

1

25%

СРСП

Выполнение домашних заданий

Реферат




0,5



2,5

2

1

2,5

1

1

2

1

1

2

1

1

2

1

1

2

1

1

30%

СРС

Коллоквиум

Семестровое задание

1

1

0,5

1

1

0,5

1

0,5

0,5

1

1

1

3

1

1

3

1

1

3

1

1

3

1

1

25%

ИТОГО по 2-рейтингу

7,5

8,5

13

13,5

15

14,5

14

14

100%

^ ИТОГОВЫЙ РЕЙТИНГ

15

21

25,5

26

30

29,5

39

14

200%


Всего по предмету: (100+100)/2*0,6+ Оценка экз.*0,4=100


^ 10. Политика курса

  1. Не опаздывать на занятия.

  2. Не разговаривать во время занятий.

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

  4. Пропущенные занятия отрабатывать в определенное преподавателем время.

  5. Отключить сотовый телефон.

  6. В случае невыполнения заданий итоговая оценка снижается.

  7. Своевременно и старательно выполнять домашние задания.

  8. Быть пунктуальным и обязательным.

  9. Быть терпимым, открытым и доброжелательным к сокурсникам и преподавателям.

^ 11. Перечень вопросов и тем по формам контроля


10.1 Экзаменационные вопросы по курсу

  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. Доказать: если отношение вычислима , то вычислима отношение P().

30. Теорема Клини о нормальной форме.

31. Доказать вычислимость отношение х=.

32. Универсальный вычислимый функций.

33. Доказать, если - вычислимое отношение, то вычислимо также отношение <.







Скачать 305.21 Kb.
оставить комментарий
Дата20.07.2012
Размер305.21 Kb.
ТипПрограмма, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх