Лекции по информатике (1113418), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

3.Совокупность возможных промежуточных результатов - SuWuV;

4.Правила непосредственной переработки (действия) - правила подстановки, порядок их применения и порядок просмотра слова;

5.Правило начала - всегда с первого правила и начала слова;

6.Правило окончания - терминальные парвила и неприменимость ни одного из правил;

7.Правило извлечения результата - преобразованное слово.

Сложность измеряется в количестве примененных правил подстановки. Рассматриваются примеры НАМ:

1.U(n) = n+1;

S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; W=S; V={*, +};

*0 -> 0*

*1 -> 1*

...

*9 -> 9*

* -> +

0+ -> +0

1+ -> +1

...

9+ -> +9

+ -> 1

-> *

2.U( <n в ун. записи> ) = <n-1 в ун. записи>;

| |-> (Первый штрих в записи числа исчезает)

3.U( <n в ун. записи> ) = n;(строится как композиция НАМ), n>=1

1) Поставить 0 слева от слова

2) Удалить '|'

3) Увеличить число на 1

4) Если нет '|', то стоп

иначе к шагу 2

0| -> 1

1| -> 2

2| -> 3

...

8| -> 9

9| -> |0

| -> 1

4.МТ для вычисления НОД.

Во всех примерах подсчитывается сложность. Подчеркивается свойство НАМ - композиция нескольких НАМ в одну.Заканчиваетя рассмотрение НАМ формулировкой тезиса Маркова. Обращается внимание на равномощность МТ и НАМ в смысле мн-ва алгоритмов, которые можно описать с помощью этих А.с.

Тезис Маркова: Для любой интуитивно вычислимой функции существует НАМ, ее вычисляющий.

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

На примере МТ и НАМ была показана возможность строить А из других А. Возникает вопрос: является ли этот принцип композиции универсальным. Другими словами можно ли аккумулировать знания в форме А, так чтобы на их основе строить другие А.

Эта проблема рассматривается на примере МТ. Вводятся четыре операции

° - последовательной композиции;

N - параллельной композиции;

if_then_else- разветвление;

while_do - цикл.

Доказывается четыре теоремы о том, что если есть МТ1 и МТ2 , то существует регулярная процедура построения МТ, эквивалентной последовательной и параллельной композации МТ1 и МТ2 ; если есть распознающий алгоритм F, то можно построить МТ реализующую if F then МТ1 else МТ2 ; МТ реализующую while F do МТ1.

Теорема 1.

Для любых МТ A и B можно эффективно построить МТ, С(p)=A(p)°B. (Для любого p из области применимости A)

Док-во

Алфавит полученной МТ ести об'единение алфавитов исходных МТ.

'!' в МТ A , заменим на переход в начальное состояние B.

Правило паралелльной композиции

Паралелльная композиция A||B

A(P||R)°B = B(P||R)°A = B(P) || A(R)

Теорема 2

Для любых МТ A и B можно эффективно построить МТ, С(P||R)=A(P) || B(R).

МТ с полулентой не слабее МТ с полной лентой.

Разветвление алгоритма

Ф(р) = 1, если условие выполнено

0, в противном случае

=> Ф - распознающий алгоритм.

Теорема 3

Для любых МТ A, B и распознающей Ф с одинаковым алфавитом можно эффективно построить МТ, С(P) = A(P), если Ф(р)=1

B(P), в противном случае.

Повторное применение А

Теорема 4

Для любой МТ A и распознающей Ф можно эффективно построить МТ, С(P) = { повторяй A, пока Ф }

Теорема

Любая МТ может быть построена с помощью опраций последовательной и паралелльной композиций, условной и циклической конструкций.

Выводы :

. Алгоритм - конструктинвый объект;

. Алгоритм можно строить из других алгоритмов;

. °, N, if_then_else, while_do - универсальный набор действий по управлению вычислительным процессом.

Вопросы :

1. Что такое правило подстановки?

2. Зависит ли резельтат от порядка следования правил в НАМ?

3. Что происходит когда не применимо ни одно правило подстановки?

4. Что утверждает тезис Маркова?

5. Что означает равномощность А.с.?

6. Что такое А.с.?

7. Можно ло доказать тезис Маркова?

8. Семантика операции °?

9. Семантика операции N?

10.Семантика операции if_then_else?

11.Семантика операции while_do?

Лекция 4.

Существование универсальных вычислителей.

Алгоритмические проблемы и взаимосвязь алгоритмических систем.

1. Существование универсальных вычислителей.

Рассматривается проблема: А - описание, определенного множества последовательностей действий, из фиксированного множества действий. Для каждого А нужен свий исполнитель или же можно построить один способный выполять все алгоритмы в данной А.с.?

Эта проблема рассматривается для А.с. - МТ. Сначала рассматривается алгоритм подражения в интуитивной форме. Требуется построить МТ:

исходные данные - функциональная схема другой МТ и данные для нее.

результат - результат, который выдала бы задаваемая МТ при работе.

Затем показывается, что для того чтобы преобразовать этот интуитвный А в форму МТ надо решить две проблемы:

- как задать функциональную схему МТ в линейной форме?

- так как произвольная МТ может иметь произвольный алфавит, то какой алфавит будет у универсальной МТ (УМТ)?

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

1. Запишем МТ пятерками вида A 0 1 Л Q

2. Проблема кодировки. Пример кодировки :

Л 101

Н 1001

П 10001

S1 100001 Q1 1000001

S2 10000001 Q2 100000001

S3 1000000001 Q3 10000000001

... ...

2. Алгоритмические проблемы и взаимосвязь А.с.

Рассматривается понятие Алгоритмической проблемы. Приводятся примеры 10-ой проблемы Гильберта как неразрешимой А.п.

Дано: правила подстановки, слова W и S.

?Можно ли преобразовать W->S с помощью данных правил подстановаки?

Ответ: Нельзя.

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

Теорема: Распознавание самоприменимости неразрешимо.

Доказательство:

Допустим, что существует А, распознающий самоприменимость

А(U) = b, если U самоприменим

c, в противном случае.

=> можно из А построить B(U), который не останавливается, если U самоприменим и останавливается, выдавая c в противном случае.

Рассмотрим B(B):

- если B(B)=c => B остановился => самоприменим. Но в то же время он несамоприменим. Противоречие.

- если B(B) не остановился => B несамоприменим. Но в то же время он самоприменим. Противоречие.

=> Теорема доказана.

В связи с неразрешимостью А.п. рассматривается проблема: Не может ли оказаться так, что А.п. неразрешимая в одной А.с. окажется разрешимой в другой А.п.?

На примере МТ и НАМ доказывается что для равномощных А.с. если А.п. неразрешима в одной А.с., то она не разрешима и в другой.

Две А.с. - равномощны если они описывают одни и теже классы А.

Доказываются две теоремы:

1. Для любой МТ существует эффективная процедура построения эквивалентного НАМ.

2. Для любого НАМ существует эффективная процедура построения эквивалентной МТ.

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

Выводы :

. Для любой А.с. существует универсальный исполнитель, который есть интерпритатор множества действий заданной А.с.;

. В силу тезиса Тьюринга любой А реализуем в терминах действий последовательной, паралелльной композаций, выбора и цикла и базового набора действий;

. Проблема применимости не применима;

. Если А.п. не разрешима, то она не разрешима в любой равномощной А.с.;

. МТ и НАМ равномощны.

Вопросы :

1. Что такое интерпритация?

2. Что такое кодирование?

3. В чем проблема линеаризации Ф.с. для МТ?

4. Что такое универсальный исполнитель:

- он может исполнять заданный А в любой А.с.?

- он может исполнять любой А, выразимый в даннолй А.с.?

5. Как решается проблема произвольности алфавита в УМТ?

6. Что такое А.п.?

7. Самоприменимость - что это такое?

8. А.п. самоприменимости разрешима?

9. В МТ А не закончен если нет применимого правила, в НАМ в этом случае А - закончен. Как это несоответсвие реашется при доказательстве сводимости МТ к НАМ и наоборот?

10. Что означает запись:

Если F (*P) то M (1NQ*a R)°U °U иначе U °U °U ?

Лекция 5

Язык программирования Pascal

Введение

Язык программирования - формальная алгоритмическая система, ориентированная на практическую реализацию А на ЭВМ. Именно на практическую реализацию, а не изучение, как в случае МТ и НАМ.

На беглом review алгоритмов нахождения НОД и определения четности числа (b=2) в интуитивной форме обсуждаются основные понятия :

точка управления;

данные - константы и переменные;

выражения - правила вычисления значений;

действия - над данными по изменению значения; изменение положения точки управления.

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

Язык программирования - формальная система обозначений для описания А в виде текста, пригодного для восприятия автоматом.

Вводятся понятия алфавита, синтаксиса и семантики, синтаксической диаграммы. (Основной источник Абрамов, Трифонов, Трифонова Введение в Паскаль.)

Концепция данных в Pascal.

Обсуждаются понятия значение, константа и переменная.

Значение - это имя специального вида, изображение этого значения.

Константа - программный объект, имеющий уникальное имя и постоянное значение, которое нельзя изменить в ходе работы программы. Константа характеризуется именем и значением.

Рассматривается СД для константы.

Семантика константы: фиксирование значение, доступное через имя. Имя не может быть использовано для изменения значения. Допустимые значения : число, символ, строка.

Описание констант в разделе констант (CONST).

Переменная - программный объект, имеющий уникальное имя и способное принимать значения ТОЛЬКО из множества значений, фиксированного для данного имени.

Семантика:

1.В каждый момент переменная может принимать только одно значение;

2.Может хранить значение из строго фиксированного множества;

3.При размещении новго значения - старое теряется;

4.Копировать текущее значение можно сколько угодно;

5.Доступ к значению только через имя;

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

Переменная характеризуется - именем, через которое осуществляется доступ к ее текущему значению; множеством допустимых значений называемым типом переменной.

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

Вводится иерархия типов в Pascal. Последовательно обсуждаются элементы этой иерархии.

Система типов в Pascal

Основные Производные

Скалярные Ссылочные

Стандартные Определенные

Тип Integer

Этот тип рассматривается как тройка

({подмн-во целых чисел},{+,-,*,div,mod},{>,succ,pred}) т.е. множество объектов, множество операций (алгебраических) над объектами, отношение упорядочения на множестве объектов.

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

maxint: AieInteger (i є maxint);

minint: AieInteger (i Є minint);

Иногда minint = -maxint Конкретное значение констант определяется реализацией.

Формулируется свойство:

Ax,y,z: |x+y| <maxint . |y+z| < maxint 6 (x+y)+z = x+(y+z)

Пример

(60+50) + (-40) ; 60+ (50+(-40))

Все операции выполняются точно.

Дополнительные функции: abs, sqr,succ,pred.

Тип Char = ({мн-во символов},{},{<,succ,pred})

Еще раз подчеркиывается отличие имени от значения: О - имя, 'О'- значение.

Стандартный набор мн-ва символов: - A - Z; - 0 - 9; - ;.:!?'eol и д.р.

Выводы :

1. Программа - А описанный для его выполнения автоматом специального вида, называемого компьютер;

2. Язык программирования - формальная система обозначений для описания А, в форме пригодной для восприятия автоматом;

3.Язык программирования - А.с., ориентированная на практически эффективную реализацию А и где испонитель есть автомат специального вида - компьютер;

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

5. Синтаксис Я.п. - формальные правила описания вышеперечисленных концепций в Я.п.

6. Семантика Я.п. - точное значение этих концепций.

Вопросы:

Характеристики

Список файлов лекций