- •Вопрос 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
- •Вопрос 27
- •Вопрос 28
- •Вопрос 29
- •Вопрос 30
- •Вопрос 31
- •Вопрос 32
- •Вопрос 33
- •Вопрос 34
- •.Вопрос 35
- •Вопрос 36
- •Вопрос 37
- •Вопрос 38
- •Вопрос 39
- •Вопрос 40-41
- •Вопрос 42
- •Вопрос 43
- •Вопрос 44
- •Вопрос 45
- •1 Год сек. Тобит – предел Бреммермана
- •Вопрос 46
- •Вопрос 47
- •Вопрос 48
- •7 Неразрешимых проблем:
- •Вопрос 49
- •§5.2 Полиномиальные и экспоненциальные алгоритмы
- •Вопрос 50
Вопрос 15
Алгоритмизация– это процесс построения алгоритма решения задачи, результатом которого является выделение этапов процесса обработки данных, формальная запись содержания этих этапов и определение порядка их выполнения.
Алгоритм, в соответствии с которым решение поставленной задачи сводится к операциям над числами, называется численным, а в соответствии с которым решение сводится к логическим действиями над объектами, называется логическим.
Пример численного алгоритма:
Алгоритм Евклида.
Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя двух заданных целых положительных чисел а и b. Этот алгоритм может быть записан в виде следующей системы последовательных указаний:
1.Обозревай данные числа а и b. Переходи к следующему указанию.
2.Сравни обозреваемые числа (а = b, или а < b, или а > b]. Переходи к следующему указанию.
3.Если обозреваемые числа равны, то каждое из них дает искомый результат. Процесс вычисления остановить. Если нет, переходи к следующему указанию.
4. Если первое обозреваемое число меньше второго, то переставь их местами. Переходи к следующему указанию.
5. Вычитай второе число из первого и обозревай два числа: вычитаемое и остаток. Переходи к указанию 2.
Примером логического алгоритма может служить таблица истинности(задача 1 в индивидуальной работе).
Вопрос 16
Свойства алгоритмов:
Элементарность– получение последующей системы величин из предшествующей должно быть простым и локальным.
Дискретность– это разбиение алгоритма на ряд отдельных законченных действий (шагов).
Детерминированность – любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае.
Направленность– В алгоритме должны быть предусмотрены все возможные пути решения, в том числеальтернативные.
Результативность. Алгоритм через конкретное число шагов для любых исходных данных приводит к конечному результату.
Массовость– один и тот же алгоритм можно использовать с разными исходными данными.
Виды алгоритмов как логико-математических средств, в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
детерминированные;
вероятностные и эвристические.
Детерминированный алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса или задачи, для которых разработан алгоритм.
Эвристический алгоритм - это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий исполнителя. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и опыте решения схожих задач.
Вопрос 17
Калмогоровый объект – математический объект не рассматривающийся безоценочно.
Конструктивный объект – представляет конечное множество элементов связанное некоторым отношением, причем элементы отношения могут быть заранее указанного типа.
Б-комплексы. Конструктивные объекты могут быть преобразованы в комплексы. Б-комплексов если элементы и отношения в виде вершин.
Каждая вершина отмечается буквами некоторого конечного алфавита.пометками могут быть числа натурального ряда, но в любом случае это множество пометок должно быть ограниченно сверху.
Калмогоровский Б-комплекс обладает особым «калмагоровым свойством » для произвольных вершин, все соединения с ней имеют разные пометки, тогда выделив какую либо вершину объявляем ее конечный граф становится.
инициальным и свойства калмагорова
обеспечиваем введение внутри системы координат
Ансамбли – к совместимости некоторых объектов, для которых характерно «стадное» поведение.
Колмогоров комплекс над алфавитом Б это связанный, инициальный неорентированный граф, вершины которого помечены буквами. Конечногоалфовита и которые обладают калмагоровым свойством a,b,a
(Б,К)-комплекс – называется инициальный, конечно ориентированный график и который имеет следующую разметку на своих вершинах и ребрах:
Все вершины намечены буквами из Б
Все исходные ребра намечены числами от 0 до к-1.0…к-1.
(Б.К)-комплекс является конструктивным объектом.
Правило перехода
Буквы алфавита 0…к-1, не ориентируемое ребро заменяется противоположно ориентируемых дуг. Каждому ребру присваивается пометка (число той вершины, к которой направлена дуга).
Ансамбля – более первичное понятие чем понятие конструктивного обекта. Для каждого конечного алфавита Б и для каждого натурального к можно указать следующий основной ансамбль
Ансамбль Б–слов (если Б больше 1-й буквы то он словарный, если Б однобуквенный то такой ансамбль относится к натуральным рядом чисел) – А АА ААА
Ансамбль (Б,К) – деревьев
Ансамбль колмогоровых Б-комплексов
Ансамбль всех таких калмагоровыхБ-комплексов у которых степень каждой вершины превосходит к
Рассмотрим ансамбль Б слов. Между 2 ансамблями существует однородное соответствие (изоморфизм).
Между ансамблями находятся некоторые естественные вложения.