 |
Операторные схемы Ляпунова
|
|
|
|
Вопрос 1
Применение теории алгоритмов Во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают практически во всех разделах математики. В математической логике для каждой теории формулируется проблема решения множества всех истинных или доводочные утверждений этой теории относительно множества всех ее предложений (теории подразделяются на разрешимые и неразрешимые в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Черч установил неразрешимость проблемы разрешимости для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А.Тарском, А. И. Мальцеву и др.. Неразрешимые алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп; первые примеры полугрупп с неразрешимой проблемой тождества были изобретены в 1947 г. независимо А. А. Марковым и Э. Постом, а пример группы с неразрешимой проблемой тождества - в 1952 г. П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 г. А. А. Марковым); в теории чисел (проблема решения 'язностидиофантовых уравнений, неразрешимость которого была установлена в 1970 г. Ю. В. Матиясевичем) и в др.. разделам математики.
Теория алгоритмов тесно связана: 1) с математической логикой, поскольку в терминах алгоритмов может быть изложено одно из центральных понятий математической логики - понятие исчисления (и поэтому, напр., Геделя теорема о неполноте формальных систем может быть получена как следствие теорем А. т.) 2) с основами математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного (в частности, А. т. дает аппарат, необходимый для разработки конструктивного направления в математике); в 1965 г. А. Н. Колмогоров предложил использовать А. т. для обоснования теории информации, 3) с кибернетикой, в которой важное место занимает изучение алгоритмов управления. А. т. образует теоретический фундамент для ряда вопросов вычислительной математики.
|
|
|
Области применения –
1) внутри математики (логика, алгебра, геометрия)
2) Связанные с созданием ЭВМ (схемотехника, алгоритмы, цифровые автоматы)
3) Не математические области (лингвистика, философия, экономика)
Теория алгоритмов – раздел матиматики в котором изучают теоритические возможности эффективных процессов вычислений и их приложений.
Алгоритм – совокупность правил обладающих свойствами –
1) Массовости
2) Детерминированности
3) Результативности
4) Элементарности
Вопрос 2
Первое правило – при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Второе правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти. В школьной “теории алгоритмов” эти два правила не рассматриваются. В то же время практическая работа с алгоритмами (программирование) начинается именно с реализации этих правил.
|
|
|
В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Бейсик не все переменные описываются, обычно описываются только массивы. Но все равно при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и отводит память под соответствующие переменные.
Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.
Четвертое правило – детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки. Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
Вопрос 3
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
|
|
|
· Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
· Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
· Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
· Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
· Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.
· Результативность — завершение алгоритма определёнными результатами.
· Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
· Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.
Вопрос 4
Точная формулировка рассматривается Колмогоровым: «Мы отправляемся от следующих наглядных представлений об алгоритмах:
1) Алгоритм Г, применённый ко всякому «условию» («начальному состоянию») А из некоторого множества S («области применимости» алгоритма Г), даёт «решение» («заключительное состояние) В.
|
|
|
2) Алгоритмический процесс расчленяется на отдельные шаги заранее ограниченного сложности; каждый шаг состоит в «непосредственной переработке» возникшего к этому шагу состояния S в состояние S*=ΩГ(S).
3) Процесс переработки <...> продолжается до тех пор, пока либо не произойдёт безрезультатная остановка <...>, либо не появится сигнал о получении «решения». При этом не исключается возможность неограниченного продолжения процесса <...>
. 4) Непосредственная переработка S в S*=ΩГ(S) производится лишь на основании информации о виде заранее ограниченной «активной части» состояния S и затрагивает лишь эту активную часть» [Колмогоров, 1953].
Эта формулировка достаточно общая и включает в себя формальное понятие машины Тьюринга, Поста и многие другие известные формальные задания. Формулировка Колмогорова содержит две существенные идеи: итеративность алгоритмического процесса и локальность каждого отдельного шага. Для того же, чтобы задать вычислительную модель необходимо конкретизировать понятия «состояние», «непосредственная переработка», «активная часть», «сигнал о решении». В [Колмогоров, 1953] предложена общая схема такой конкретизации. Эта схема может рассматриваться как адекватная формализация точного понятия алгоритма. Здесь, при работе с моделями с нелокальным преобразованием информации нудно разбить нелокальные шаги на локальные, — и мы видим замечательную параллель одного известного метода, изложенного ещё Декартом: «Сложную задачу разбивай на простые». Только в случае алгоритма эти простые задачи должны решаться однотипно.
Вопрос 5
В современной математике алгоритмами принято называть конструктивно задаваемые соответствия между словами в абстрактных алфавитах. Это определение, в свою очередь, использует два понятия – понятие абстрактного алфавита и слов в таком алфавите.
Абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или символами данного алфавита. Иными словами алфавит - это конечное множество различимых символов (слово "абстрактный" для краткости здесь и далее опускается). Алфавит, как и любое другое множество, может быть задан перечислением его элементов. Например, алфавит A есть A={a, b, c}, алфавит B есть B={x, y}.
Под словом или строкой в алфавите понимают любую конечную последовательность символов. В последовательности (цепочке) между символами стоит операция сцепки, т.е. менять местами символы в последовательности нельзя. Например, в алфавите А словами являются любые последовательности: a, ac, cb, acb, bb, а в алфавите B: x, y, yx, xx и т. п.
|
|
|
Число символов в слове называется длиной этого слова. Так слова в алфавите А, приведенные в примере, имеют длину соответственно 1, 2, 2, 3, 2. Различают также пустые слова, не содержащие ни одного символа. Слово р называется подсловом слова q, если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое. Очевидно, что такое понятие слова будет отличаться от аналогичного в разговорных языках. Здесь под словом можно понимать любую последовательность символов, даже бессмысленную.
При расширении алфавита понятие слова может существенно меняться. Так, например, в алфавите A={0,1,2,3,4,5,6,7,8,9} цепочка символов 69+73 представляет собой два слова, соединенные знаком суммы, а в алфавите В={+,0,1,2,3,4,5,6,7,8,9} это будет одно слово.
Алфавитным оператором или алфавитным отображением называется всякое соответствие между словами некоторого алфавита и словами в том же самом или в каком-либо другом фиксированном алфавите. Первый называется входным, а второй – выходным алфавитом данного оператора. В случае совпадения входного и выходного алфавитов говорят, что алфавитный оператор задан в соответствующем алфавите.
Пусть заданы слова в алфавитах X и Y и заданы соответствия между этими словами. Если xi – слово в алфавите X, а yj – слово в алфавите Y, то алфавитный оператор Гxi=yj преобразует входное слово xi в выходное слово yj. Символ Г в алфавитном операторе означает отображение.
Различают однозначные и многозначные алфавитные операторы. Под однозначным алфавитным оператором понимается такой алфавитный оператор, который каждому входному слову ставит в соответствие не более одного выходного слова.
Совокупность всех слов, на которых алфавитный оператор определен, называется областью его определения. Алфавитный оператор, не сопоставляющий данному входному слову ai никакого выходного слова bj (в том числе и пустого), на этом слове не определен.
Вопрос 6
Кодирование — это процесс преобразования одной формы представления информации с целью обеспечения удобства ее хранения и передачи.. Для формирования сообщений, содержащих информацию, используется большое число разнообразных знаков (например, буквы). При необходимости передать или хранить очень большое число различных сообщений используется язык с иерархической структурой, который позволяет строить знаки различного рода (например, буква – слово – предложение – абзац – страница – раздел – книга и т.д.). Низшим рангом являются символы. Если число символов ограничено, то их совокупность называют алфавитом. В цифровых системах алфавит состоит из двух символов. Слово является следующим рангом и т.д. Комбинирование символов используемого алфавита для построения элементов сообщения по определенным правилам называется кодированием. Обратная операция переданных сигналов называется декодированием.
Код принимаемого языка определяется алфавитом символов и правилами их комбинирования, т.е. правилами построения знаков различного ранга. Число символов в алфавите называется основанием кода. Знаки второго ранга называются кодовыми словами. Если все кодовые слова имеют одинаковое число символов, то код называется равномерным, в противном случае код называется неравномерным.
Кодирующим отображением Г называется отображение множества слов в некотором алфавите в множество слов в этом же или другом алфавите. Входное множество символов называется входным, выходное — выходным. Применение кодирующего отображения Г к слову, представленному во входном алфавите называется кодированием, а само правило кодирования Г-входом.
Рассмотрим пример кодирующего отображения. Заданы алфавиты:
А = {р, r, s, t) — входной;
В = (а, b, с, d, f, g, h, m, n, q) — выходной; отображения символов А символами В (рис. 3).
Для построения искомого кодирующего отображения достаточно заменить все символы
любого слова ai в алфавите А соответствующими кодами алфавита В.
Пусть задано слово а = sstr, тогда Га = fghfghabcdmn. Полученное таким образом слово в
алфавите В называется кодом исходного слова а.
Для обратимости кодирования должны выполняться два следующих условия:
1) Коды разных символов должны быть различны;
2) Код любого символа алфавита А не может совпадать ни с одним из начальных отрезков слов других слов этого алфавита.
Следует отметить, что второе условие выполняется в том случае, если коды всех символов исходного алфавита А имеют одинаковую длину.
Вопрос 7
1. Постановка задачи.(техническое задание). Входные данные, требования на сам алгоритм
2. Построение модели.
3. Разработка алгоритма.
4. Проверка правильности алгоритма, верификация, валидация
5. Реализация алгоритма.(выбор среды, языка программирования)
6. Анализ алгоритма и его сложности.
7. Проверка программы.
8. Составление документации.
Вопрос 8
1.Графический.
Для составления алгоритма в виде блок-схемы применяются следующие основные графические изображения.
Достоинства:
1. обмен методами решения между специалистами
2. облегчается работа по составлению машиннойпроги
3. возможность отдельно программировать каждый блок
4.облегачается чтение и понимание
5. уменьшается количество ошибок.
Недостатки:
1. невозможность использовать при автоматизированном программировании
2. не устанавливается определенная степень детализации
2. Операторный способ
А) ванхао
Операторный алгоритм Ван-Хао задается последовательностью команд специального вида: каждая команда имеет определенный номер и содержит указания какую операцию следует выполнить над заданным объектом и команду с каким номером следует далее выполнять над результатлм данной операции.
Общий вид:
I:
| W | a | b |
I – номер команды
W- элементарная операция над объектом
a,b - номера некоторых команд.
Выполнить команду I над числом Х в операторном алгоритме – значит найти число W(X) и далее перейти к выполнению над W(X) команды с номером a. Если же W(X) не определено, то перейти к выполнению над числом Х команды с номером b.
Кроме обычных команд существует заключительная команда вида:
I:
| стоп |
Если в процессе выполнения алгоритма не возникает указания назаключительный оператор, то результатом переработки Х будет “неопределенное значение”.
Если функция W всюду определена, то символ b не оказывает влияния на процесс вычислений и поэтому команда имеет вид:
I:
| W | a |
Говорят, что операторный алгоритм А с программой (Х) вычисляет частичную функцию f(x), если алгоритм А перерабатывает каждое натуральное число Х в f(x).
В частности, если f(x) неопределена, то процесс переработки Х должен быть бесконечным. Природа функций, вычислимых посредством операторных алгоритмов Ван-Хао зависит от того, какие функции Wi входят в записи команд. Имеет место следующая теорема:
Для того, чтобы частичная функция f(x) была вычислимой с помощью алгоритма, программа которого содержит лишь ч.р.ф. Wi(x) с рекурсивной областью определенности, необходимо и достаточно, чтобы f(x) была частично рекурсивной.
Б) Ляпунов
Используют пять типов операторов
1. Арифметические – для записи арфиметических действий, A,B,C
2. Проверка логического условия P,Q
3. Операторы переадресации. Служат для изменения различных параметров
F(i) – оператор инкремента(i:=i+1)
F (в минус 1) (i)- декремент (i:=i-1)
4. Оператор переноса. Служит для переноса одного параметра на место другого
5. Операторы формирования. Переносят запасенные приказы в определенные места алгоритма
Сомножитель стоящий слева передает управление сомножителю справа.
Если передачи управления нет, то ставят точку с запятой
S – конец строки
Если присутствует логический оператор, то управление передается стоящему справа, если не выполняется то оператору к которому идет стрелка идущая сверху.
Работа алгоритма заканчивается либо когда отработал оператор S, либо когда нет такого элемента схемы который должен работать
Достоинства:
1. Допускает эквивалентное преобразование
2. Компактность записи
Недостатки:
1. Необходимо расписывать все обозначения
2. Малая наглядность
3. Словесный способ.
Содержание каждого шага записывают на естественном языке в повелительном наклонении в безличной форму с обязательным указанием номера очередного шага. (ввести значение х, перейти к шагу..)
Достоинства:
Понятность даже не специалистам
Недостатки:
Языковой барьер, низкая наглядность, не компактно.
Вопрос 9
графический способ записи алгоритма
Достоинства:
1. Обеспечивается обмен методами решения между специалистами, использующие разные ЭВМ
2. Облегчается работа по составлению машинной программы
3. Создается возможность отдельно программировать каждый блок
4. Облегчается чтение и понимание программы
5. Уменьшается количество ошибок при программировании и упрощается проверка и отладка готовых программ
Недостатки:
1. Невозможность использовать при автоматизированном программировании
2. Не устанавливается определенная степень детализации
Блок-схемный способ может быть рекомендован в качестве предварительного этапа.
Вопрос 10
Операторные схемы Ван Хао
| ω | α | β |
Используются приказы спец вида i:
Где i-номер приказа, ω-элементарная |, α и β-номера очередных приказов
| ω | α |
Выполнить приказ i над числом x- значит найти число ω(х) и если результат определен, то перейти к приказу с номером α, в противном случае к приказу с номером β. Если ω(х)-всюду определенная функция, то приказы имеют вид i:
| ω | α |
Приказ вида, который выполняется над некоторым числом дает результат вычислений j: Программой операторного алгоритма называется последовательность приказа вида:
| ωi | αi | βi |
i:
| ωi+j | αi+j | βi+j |
i+1:
| ω s | α s | β s |
s:
s+1: СТОП
если в результате выполнения алгоритма не возникают пары, указывающие назаключительный оператор, то результатом переработки неопределенное значение.
Теорема1: для того чтобы частичная функция была вычислимой с помощью операторного алгоритма программа которого содержит лишь частично рекурсивную функцию ωi(х) с рекурсивной областью определенности необходимо и достаточно, чтобы f(x) была частично рекурсивной.
Теорема Минского: для каждой частично-рекурсивной функции f(x) существует операторный алгоритм, программа которого состоит из приказов вида и которая для любого х перабатывает слово 2х=>2f(x):
| ω | α | β |
i:
j: СТОП
Вопрос 11
операторные схемы Ляпунова
Схема алгоритма, составленная из арифметических операторов и логических условий называется логическая схема алгоритма. В операторных схемах используются 5 операторов:
1. Арифметические операторы (А, В, С, …, А1, В1, С1,…)
2. Операторы проверки логических условий (P, Q) p(x>y)
3. Операторы переадресации-служат для изменения адресов приказов, для изменения различных параметров, для восстановления ранее измененных значений. Типичным представителем служит F(i)->i:=i+1
Fn(i)->i:=i+1+1+1… (nраз)
F-1(i)->i:=i-1
F-n(i)->i:=i-1-1-1… (nраз)
4. Оператор переноса-служит для переноса одного параметра на место другого [a->b]
5. Оператор формирования-переносят некоторые заранее запасенные приказы в определенные места алгоритма
Последовательное выполнение нескольких операторов обозначается как произведение, сомножитель, стоящий слева передает управление сомножителю, стоящему справа.
Если такой передачи управления нет, то ставится; в конце строки записывается S
Если нужно выделить группу операторов, то ставят {}
Если в строке символов присутствует логический оператор то при выполнении условия передача управления осуществляется оператору, стоящему справа, а если не выполняется, то оператору к которому ведет стрелка, идущая сверху.
Разрывы стрелок 
-начало 
-конец
Работа алгоритма заканчивается либо когда последний из отработавших операторов-это S, либо когда не оказывается такого элемента схемы, который должен был бы работать.
Достоинства:
1. Допускает эквивалентные преобразования
2. Компактность записи
Недостатки:
1. Необходимость расписывать все обозначения
2. Малая наглядность по сравнению с графическим способом
Вопрос 12
словесная форма записи алгоритмов
Алгоритм разделяется на ряд элементарных операций, содержание каждого шага записывается на естественном языке в повелительном наклонении в безличной форме с обязательным указанным номера очередного шага.
Достоинства: понятность, доступность
Вопрос 13
Эти правила применимы для любых алгоритмов, но наиболее полезны они при составлении достаточно сложных и объемных алгоритмов.
Главные из этих правил следующие:
1. При составлении алгоритма необходимо пользоваться способом последовательной (поэтапной) детализации.
2. Алгоритм должен строиться по модульному принципу.
3. Схема алгоритма должна доставляться на базе ограниченного числа типовых(стандартных) структур.
1.Способ последовательной детализации
предполагает получение алгоритма в виде многоэтапного, процесса, в котором на каждом из этапов составляется алгоритм или отдельные его части с различной степенью детализации.
Укрупненная схема алгоритма составляется укрупненный алгоритм с малой степенью детализации. На последующих этапах степень детализации увеличивается. Особенно это относится к отдельным частям алгоритма.
2.алгоритм по модульному принципу
предполагает его построение в виде отдельных, относительно независимых частей (модулей). В состав модуля включаются части алгоритма, удовлетворяющие следующим требованиям: функциональной законченности, минимальной связности и представимости в форме схемы с одним входом и одним выходом.
Требование функциональной законченности означает, что в состав модуля должна включаться некоторая законченная в смысловом и функциональном отношении часть общего алгоритма. Выделение таких частей позволяет проводить их параллельную разработку и допускает относительно простой контроль правильности их составления. При обнаружении ошибок полной замене или коррекции может подлежать содержание только «неисправного» модуля, а не всего алгоритма.
Требование минимальной связности означает формирование модулей так, чтобы они использовали минимальное число общих переменных. Учет этого требования позволяет строить наглядные и легко «читаемые» алгоритмы, а также выполнять их проверку в автономном режиме.
Представление модуля схемы, имеющей один вход и один выход, так же как и требование минимальной связности, обеспечивает улучшение наглядности и «читаемости» алгоритма. В таких алгоритмах легко прослеживаются причинно-следственные связи отдельных частей.
3.Правило составления схем алгоритмов на базе ограниченного числа типовых структур, имеющих один вход и один выход, обусловлено стремлением обеспечить обозримость и проверяемость алгоритма. Сложные структуры алгоритмов или их частей могут быть изображены с помощью трех типовых структур
обработки данных, имеющих один вход и один выход. При этом алгоритмы сложной структуры также будут иметь один вход и один выход.
Вопрос 14
К типовым структурам относятся:
1) неразветвленная (линейная) структура обработки данных – набор инструкций, выполняемых последовательно во времени друг за другом.
2) разветвленные нециклические структуры – алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
3) разветвленные циклические структуры – алгоритм, предусматривающий повторения одного и того же действия над новыми исходными данными. Необходимо заметить, что циклический алгоритм легко реализуется посредством двух ранее рассмотренных типов алгоритмов.
Вопрос 15
Алгоритмизация – это процесс построения алгоритма решения задачи, результатом которого является выделение этапов процесса обработки данных, формальная запись содержания этих этапов и определение порядка их выполнения.
Алгоритм, в соответствии с которым решение поставленной задачи сводится к операциям над числами, называется численным, а в соответствии с которым решение сводится к логическим действиями над объектами, называется логическим.
Пример численного алгоритма:
Алгоритм Евклида.
Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя двух заданных целых положительных чисел а и b. Этот алгоритм может быть записан в виде следующей системы последовательных указаний:
1.Обозревай данные числа а и b. Переходи к следующему указанию.
2.Сравни обозреваемые числа (а = b, или а < b, или а > b]. Переходи к следующему указанию.
3.Если обозреваемые числа равны, то каждое из них дает искомый результат. Процесс вычисления остановить. Если нет, переходи к следующему указанию.
4. Если первое обозреваемое число меньше второго, то переставь их местами. Переходи к следующему указанию.
5. Вычитай второе число из первого и обозревай два числа: вычитаемое и остаток. Переходи к указанию 2.
Примером логического алгоритма может служить таблица истинности(задача 1 в индивидуальной работе).
Вопрос 16
Свойства алгоритмов:
Элементарность – получение последующей системы величин из предшествующей должно быть простым и локальным.
Дискретность – это разбиение алгоритма на ряд отдельных законченных действий (шагов).
Детерминированность – любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае.
Направленность – В алгоритме должны быть предусмотрены все возможные пути решения, в том числеальтернативные.
Результативность. Алгоритм через конкретное число шагов для любых исходных данных приводит к конечному результату.
Массовость – один и тот же алгоритм можно использовать с разными исходными данными.
Виды алгоритмов как логико-математических средств, в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
· детерминированные;
· вероятностные и эвристические.
Детерминированный алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса или задачи, для которых разработан алгоритм.
Эвристический алгоритм - это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий исполнителя. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и опыте решения схожих задач.
Вопрос 17
Калмогоровый объект – математический объект не рассматривающийся безоценочно.
Конструктивный объект – представляет конечное множество элементов связанное некоторым отношением, причем элементы отношения могут быть заранее указанного типа.
Б-комплексы. Конструктивные объекты могут быть преобразованы в комплексы. Б-комплексов если элементы и отношения в виде вершин.
Каждая вершина отмечается буквами некоторого конечного алфавита.пометками могут быть числа натурального ряда, но в любом случае это множество пометок должно быть ограниченно сверху.
Калмогоровский Б-комплекс обладает особым «калмагоровым свойством» для произвольных вершин, все соединения с ней имеют разные пометки, тогда выделив какую либо вершину объявляем ее конечный граф становится.
инициальным и свойства калмагорова
обеспечиваем введение внутри системы координат
Ансамбли – к совместимости некоторых объектов, для которых характерно «стадное» поведение.
Колмогоров комплекс над алфавитом Б это связанный, инициальный неорентированный граф, вершины которого помечены буквами. Конечногоалфовита и которые обладают калмагоровым свойством a,b,a
(Б,К)-комплекс – называется инициальный, конечно ориентированный график и который имеет следующую разметку на своих вершинах и ребрах:
1) Все вершины намечены буквами из Б
2) Все исходные ребра намечены числами от 0 до к-1.0…к-1.
(Б.К)-комплекс является конструктивным объектом.
Правило перехода
Буквы алфавита 0…к-1, не ориентируемое ребро заменяется противоположно ориентируемых дуг. Каждому ребру присваивается пометка (число той вершины, к которой направлена дуга).
Ансамбля – более первичное понятие чем понятие конструктивного обекта. Для каждого конечного алфавита Б и для каждого натурального к можно указать следующий основной ансамбль
1) Ансамбль Б–слов (если Б больше 1-й буквы то он словарный, если Б однобуквенный то такой ансамбль относится к натуральным рядом чисел) – А АА ААА
2) Ансамбль (Б,К) – деревьев
3) Ансамбль колмогоровых Б-комплексов
4) Ансамбль всех таких калмагоровыхБ-комплексов у которых степень каждой вершины превосходит к 
5) Рассмотрим ансамбль Б слов. Между 2 ансамблями существует однородное соответствие (изоморфизм).
Между ансамблями находятся некоторые естественные вложения.
Вопрос 18
Общее понятие исчисления (дедуктивная система)
Исчисления представляют собой список разрешительных правил – называются предупреждающими правилами или правилами вывода
Эти правила разрешают переходить от одних конструктивных правил к другим в рамках ансамбля. Подобно таму как алгоритм задает алгоритмический или вычислительный процесс исчисление задает исчислительный процесс (порождающий). Разбивается на шаги, каждый шаг состоит из полученного нового конструктивного объекта из уже полученного.
Объекты к которым применяются правила называются посылками.
Функциональное отличие алгоритма от исчисления.
Применение одного и того же правила к одним и тем же посылкам может давать разные результаты.
Для каждого правила число посылок фиксировано если все эти числа ориентированы числом (к) то исчисление называется посылочными.
Если объект B получается из объектов (a1;a2;…;aB.) применяем одно из разрешительных правил исчисления, и если (a1;a2;…;aK.) является допустимым объектом, то и B является допустимым объектом.
Начало индукции обеспечивает нуль посылочных правил (из ничего)
Объекты некоторого ансамбля W с которыми работает исчисление называется рабочей средой исчисления.и все состояния исчисляемого процесса должны лежать в W.
Вопрос 19
Разрешимое множество
Множество разрешимо если содержится в некотором ансамбле и для него существует разрешающий алгоритм.(U)
U – разрешающий алгоритм для подмножества А, ансамбля х, Если множество допустимых входов совпадает с Х, и U отвечает на вопрос (xЄХ) ЄА.
Множество разрешимо тогда и только тогда, когда его проблемма разрешения решима.
Объединение, пересечение и т.п Разрешимых множеств – разрешимы, конечное множество разрешимо, Критерии разрешимости множества заключаются в том, что множество A в ансамбле Х разрешимо тогда и только тогда, когда
А Є Gen(X) (множество породимо)
А Є х \ Gen(X) (дополнение породимо)
Функция вычислима тогда и только тогда, когда она рассматривается как множество пар =>породима. Два любых породимых бесконечных множества изоморфны.
Перечислимые множества.
Множество натуральных чисел называется перечислимым, если оно перечисляется некоторым алгоритмом, то есть если существует алгоритм, который печатает (в произвольном порядке и с произвольными промежутками времени) все элементы этого множества и только их.
Такой алгоритм не имеет входа; напечатав несколько чисел, он может надолго задуматься и следующее число напечатать после большого перерыв
|
|
|
