Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика
жүктеу/скачать 3,71 Mb.
|
УМКАлгор и стр данн Инеттен (1)
|
структур данных в будущем? 9. В чем заключается идея структурного программирования? 10.В чем состоит отличие структурного программирования от модульного программирования? 11.В чем заключается разница между восходящим и нисходящим проектированием алгоритмов решения сложных задач? 12.Поясните этапы декомпозиция данных в сложных программах.
2. АБСТРАКТНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ МАШИНА ПОСТА Эмиль Пост рассматривает общую проблему (общую задачу), состоящую из множества конкретных проблем (конкретных задач). Решение общей проблемы – такое решение, которое даёт решение каждой конкретную (рис.1).
Рис.1. Общая задача Поста Например, решение уравнения 𝑎𝑥 + 𝑏 = 0 это общая проблема, а решение уравнения 3𝑥 + 9 = 0 – одна из конкретных (частных) проблем. Основные понятия алгоритмического формализма Поста: пространство символов (язык S) в котором задаётся конкретная проблема и получается ответ; набор инструкций (операций) в пространстве символов, задающих как сами операции, так и порядок их выполнения.
Машина Поста состоитиз: бесконечной ленты, поделенной на одинаковые ячейки (секции), ячейка может быть пустой (0 или пустота) или содержать метку (1 или V);
головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также проверять наличие метки, стирать и записывать метку.
15 Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты– информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Конкретная проблема задается «внешней силой» посредством пометки конечного количества ячеек. При этом любая конфигурация начинается и заканчивается помеченным ящиком. Машина работает в единичной системе счисления (0=V; 1=VV; 2=VVV; 3=VVVV), т.е. ноль представляется одним помеченным ящиком, а целое положительное число – помеченными ящиками в количестве на единицу больше его значения. После применения к проблеме набора инструкций решение представляется в виде набора помеченных и непомеченных ячеек, распознаваемое «внешней силой». Пост предложил набор инструкций. Этот набор инструкций является, минимальным набором битовых операций: 1) пометить ячейку, если она пуста; 2) стереть метку, если она есть; 3) переместить головку влево/вправо на 1 ячейку; 4) определить помечена ячейка или нет и, в зависимости от результата, выполнить инструкцию 3; 5) остановиться. Программа представляет собой нумерованную последовательность инструкций, причем переходы в инструкции 3 производятся на указанные в ней номера других инструкций.
МАШИНА ТЬЮРИНГА И АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ Статья «О вычислимых числах в приложении к проблеме разрешения» может считаться одной из основ современной теории алгоритмов. Посвящена проблеме«разрешимости» (Гильберт, 1900г.) – нахождения общего метода для определения выполнимости высказывания на языке формальной логики. Тьюринг показал: 16 этот метод (алгоритм, процедура) может быть выполнен механически, без творческого вмешательства; как эту идею можно воплотить в виде подробной модели вычислительного процесса. Машина Тьюринга – логическая конструкция модели вычислений, в которой алгоритм разбивается на последовательность элементарных шагов.
Машина Тьюрингаявляется расширением модели конечного автомата, который включает в себя потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому/правому соседу. Формально машина Тьюринга может быть описана следующим образом:
конечное множества букв алфавита 𝑆 = {𝑠1 , … , 𝑠𝑛 }; конечное множества состояний 𝑄 = {𝑞1 , … , 𝑞𝑘 }; движения головки 𝐷 = {𝑑1 , 𝑑2 , 𝑑3 }: на ячейку влево, вправо, остаться на месте; набором правил (функций перехода𝛿), по которым работает машина: 𝛿: 𝑞𝑖 𝑠𝑗 → 𝑞𝑚 𝑠𝑛 𝑑𝑘 . Для каждой возможной конфигурации 〈𝑞𝑖 , 𝑠𝑗 〉имеется ровно одно правило. Для заключительного состояния, попав в которое машина останавливается, правил 𝛿нет. один из символов алфавита пустой 𝑒 (принадлежит𝑆); конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины. Конечная проблема задается записью конечного количества символов на ленте.
𝑒 𝒔𝟏 𝒔𝟐 … … 𝒔𝒏 𝑒 Детерминированная машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три вещи: символ, который будет записан на ленте; направление смещения головки по ленте; новое состояние конечного автомата. ВероятностнаямашинаТьюрингапредставляетсобой детерминированную машину Тьюринга, имеющую дополнительно 17 аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту и потом использовать в вычислениях обычным для МТ образом. В случае недетерминированной машины Тьюринга, комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов. НМТ распознаёт, какой из возможных путей приведёт в допускающее состояние двумя способами:
1. Можно считать, что НМТ – «чрезвычайно удачлива»; то есть всегда выбирает переход, который в конечном счете приводит к допускающему состоянию, если такой переход вообще есть. 2. Можно представить, что в случае неоднозначности перехода (текущая комбинация состояния и символа на ленте допускает несколько переходов) НМТ делится на копии, каждая из которых следует за одним из возможных переходов. В отличие от ДМТ, которая имеет единственный «путь вычислений», НМТ имеет «дерево вычислений» (в общем случае — экспоненциальное число путей). Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает. АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ Доказательство алгоритмической неразрешимости некоторой задачи принято сводить к классической задаче – «задаче останова». Теорема. Алгоритмическая неразрешимость. Не существует общего алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных определить, останавливается ли этот алгоритм на этих данных или работает бесконечно. Рис. 2.Алгоритмическая неразрешимость Таким образом, фундаментально алгоритмическая неразрешимость связана сбесконечностьювыполняемыхалгоритмомдействий,т.е. невозможностью предсказать, что для любых исходных данных решение будет получено за конечное количество шагов. 18 ПРИЧИНЫ (СВОДИМЫЕ К ПРОБЛЕМЕ ОСТАНОВА) ВЕДУЩИЕ К АЛГОРИТМИЧЕСКОЙ НЕРАЗРЕШИМОСТИ 1. Отсутствие общего метода решения задачи Проблема 1. Распределение числа 𝑥 в записи числа 𝝅; 𝝅 = 3,141592 … , 𝑓9 (1) = 5. 𝝅 = 48𝑎𝑟𝑐𝑡𝑔(1/18) + 24𝑎𝑟𝑐𝑡𝑔(1/57) − 20𝑎𝑟𝑐𝑡𝑔(1/239). Задача состоит в вычислении функции 𝑓𝑥 (𝑛) для произвольного 𝑛. Проблема 2. Вычисление совершенных чисел; Совершенные числа – это числа, которые равны сумме своих делителей, например: 𝑆(1) = 1 = 1 𝑆(2) = 6 = 1 + 2 + 3 𝑆(3) = 28 = 1 + 2 + 4 + 7 + 14. Задача вычисления 𝑆(𝑛) по произвольно заданному 𝑛. Проблема 3. Десятая проблема Гильберта; Пусть задан многочлен 𝑛 -ой степени с целыми коэффициентами 𝑃𝑛 (х). Существует ли алгоритм, который определяет, имеет ли уравнение 𝑃𝑛 (х) = 0 решение в целых числах? 2. Информационная неопределенность задачи Проблема 4. Позиционирование машины Поста на последнюю помеченную ячейку. Информационная неопределенность – отсутствие информации либо о количестве последовательности ячеек, либо о максимальном расстоянии между ячейками (кортежами) – при наличии такой информации задача становится алгоритмически разрешимой. 3. Логическая неразрешимость (в смысле теоремы Гёделя о неполноте) Проблема 5. Проблема «останова» (см. теорема). Проблема 6. Проблема эквивалентности алгоритмов. По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных. Проблема 7. Проблема тотальности. По произвольному заданному алгоритму определить, будет ли он останавливаться на всех возможных наборах исходных данных. Другая формулировка этой задачи – является ли частичный алгоритм 𝑷 всюду определённым?
19 Контрольные вопросы 1. В чем состоят основные принципы работы машины Поста? 2. В чем состоят основные принципы работы машины Тьюринга? 3. В чем разница между машиной Поста и Тьюринга? 4. Охарактеризуйте виды машин Тьюринга. 5. В чем заключается смысл понятия «алгоритмическая неразрешимость» задачи? 6. Перечислите причины, приводящие к алгоритмической неразрешимости задачи 7. Является ли задача нахождения простых чисел алгоритмически неразрешимой? Дайте подробное пояснения. 8. Приведите примеры алгоритмически неразрешимых проблем. 3. АНАЛИЗ АЛГОРИТМОВ 3.1. СРАВНИТЕЛЬНЫЕ ОЦЕНКИ АЛГОРИТМОВ При использовании алгоритмов для решения практических задач возникает проблема рационального выбора алгоритма (рис. 1). Рис. 1. Проблема рационального выбора алгоритма Решение проблемывыбора связано с построением системы сравнительных оценок, которая в свою очередь существенно зависит от формальной модели алгоритма. Для оперирования с формальной моделью алгоритма рассматривается абстрактная машина, включающая:
20 процессор, поддерживающий адресную память; набор элементарных операций, соотнесенных с языком высокого уровня. Допущения: каждая команда выполняется не более чем за фиксированное время;
исходные данные алгоритма представляются 𝑵машинными словами по 𝛂 битов каждое. На входе алгоритма: 𝐍𝜶 = 𝑵 ∗ 𝜶бит информации Программа, реализующая алгоритм состоит из 𝑴 машинных инструкций по 𝛃 битов:
𝐌𝜷 = 𝑴 ∗ 𝛃бит информации Дополнительные ресурсы абстрактной машины на реализацию алгоритма: 𝑺𝒅 – память для хранения промежуточных результатов; 𝑺𝜸 – память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов). При решении конкретной задачи, заданной 𝑵 + 𝑴 + 𝑺𝒅 + 𝑺𝜸 словами памяти, алгоритм выполняет конечное количество «элементарных» операций абстрактной машины. В связи с этим вводится определение трудоёмкости алгоритма. Под трудоёмкостью алгоритма 𝑭𝒂 (𝒏) для данного конкретного входа;
для решения конкретной проблемы (задачи); в данной формальной системе понимается количество «элементарных» операций (𝑛) , совершаемых алгоритмом. Комплексный анализ алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной машины, требуемых алгоритмом для решения конкретных задач. 𝜑𝐴 = 𝑐1 𝐹 (𝑛) + 𝑐2 𝑁𝑎 + 𝑐3 𝑀𝛽 + 𝑐4 𝑆𝑑 + 𝑐5 𝑆𝛾𝑎
Для различных областей применения веса ресурсов𝐜𝐢 будут различны. 3.2. КЛАССИФИКАЦИЯ АЛГОРИТМОВ ПО ВИДУ ФУНКЦИИ ТРУДОЁМКОСТИ 1.Количественно-зависимые по трудоемкости алгоритмы. Их функция трудоемкости только от размерности входных данных и не зависит от их значений:
21 𝑭𝒂 (𝒏), 𝒏 = 𝒇(𝑵). Пример. Алгоритмы для стандартных операций с массивами и матрицами: умножение матриц, умножение матрицы на вектор и т.д. 2. Параметрически-зависимые по трудоемкости алгоритмы. Их функция трудоемкости определяется конкретными значениями обрабатываемых слов памяти: 𝑭𝒂 (𝒏), 𝒏 = 𝒇(𝒑𝟏 , … , 𝒑𝒊 ). У таких алгоритмов на входе два числовых значения: аргумент функции и точность. Пример. Алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. a) Вычисление 𝑥 𝑘 последовательным умножением: 𝐹 (𝑎, 𝑘) = 𝐹 (𝑘).𝑎𝑎 𝑘𝑛b) Вычисление 𝑒 = ∑(𝑥 /𝑛!), с точностью до ε > 0: 𝐹 = 𝐹𝑎 (𝑥, ε)𝑎
3.Количественно-параметрические по трудоемкости алгоритмы. В большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от их значений: 𝑭𝒂 (𝒏), 𝒏 = 𝒇(𝑵, 𝒑𝟏 , … , 𝒑𝒊 ) Пример. Алгоритмы численных методов, в которых существует параметрически-зависимый цикл по точности и цикл количественно- зависимый по размерности. Среди параметрически-зависимых алгоритмов выделяют группу алгоритмов, для которой количество операций зависит от порядка расположения исходных объектов. Пример. алгоритмы сортировки; алгоритмы поиска минимума/максимума в массиве. 3.3. АСИМПТОТИЧЕСКИЙ АНАЛИЗ ФУНКЦИЙ Цель анализа трудоёмкости алгоритмов – нахождение оптимального алгоритма для решения данной задачи (рис. 2). Критерий оптимальности – количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. 22 Рис. 2. Анализ трудоёмкости алгоритмов 𝑺и Э=→ 𝟏, 𝑺и → 𝒎𝒊𝒏 𝑺и + 𝑺𝒓 𝑺и𝒎𝑺и Э𝒎 ==→ 𝟏
𝑺𝒓⁄𝒎𝑺и + 𝑺𝒓 𝑺и +𝒎
Цель асимптотического анализа - сравнение затрат ресурсов системы различными алгоритмами, предназначенными для решения: одной и той же задачи;
при больших объемах входных данных. Используемая в асимптотическом анализе оценка функции трудоёмкости, называется сложностью алгоритма и позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных. В асимптотическом анализе используются обозначения, позволяющие показать скорость роста функции: 1. ОценкаΘ(тетта) 2. Оценка Ο (О большое) 3. Оценка Ω (Омега)
1. Оценка 𝚯 (тетта) Пусть 𝑓(𝑛) и𝑔(𝑛) – положительные функции положительного аргумента, 𝑛 ∈ ℕ, тогда (рис. 3): 23 Рис. 3. Оценка 𝚯 Обычно говорят, что при этом функция 𝑔(𝑛) является асимптотически точной оценкой функции 𝑓(𝑛) , т.к. по определению функция 𝑓(𝑛) не отличается от функции 𝑔(𝑛) с точностью до постоянного множителя. Примеры.
1) 𝑓 (𝑛) = 4 𝑛2 + 𝑛ln(𝑛) + 174, 𝑓(𝑛) → Θ(𝑛2 ); 2) 𝑓(𝑛) → Θ Следующая запись означает, что 𝑓(𝑛) или равна константе, не равной нулю, или 𝑓(𝑛) ограничена константой на Θ: 𝑓(𝑛) = 7 + 1/𝑛 → Θ. Пример.
1 22𝑐1 𝑛 ≤ 𝑛 − 3𝑛 ≤ 𝑐2 𝑛2 2 1 3 𝑐1 ≤ − ≤ 𝑐2 2 𝑛
Неравенства выполняются, если выбрать: 𝑛 ≥ 7, 𝑐1 ≤ 1/14 𝑛 → ∞, 𝑐2 ≥ 1/2 Таким образом: 21 ( ) 𝑛2 ≤ 𝑛2 /2 − 3𝑛 ≤ ( ) 𝑛2 72 Пример.
𝑐1 𝑛2 ≤ 𝑎𝑛2 + 𝑏𝑛 + 𝑐 ≤ 𝑐2 𝑛2 , 𝑎, 𝑏, 𝑐 > 0, 𝑎𝑛2 ≤ 𝑎𝑛2 + 𝑏𝑛 + 𝑐 ≤ (𝑎 + 𝑏 + 𝑐 )𝑛2 . Для произвольных 𝑎, 𝑏, 𝑐: 𝑐1 = 𝐦𝐢𝐧{𝑎, 𝑎 + 𝑏 + 𝑐}, 𝑐2 = 𝐦𝐚𝐱{𝑎, 𝑎 + 𝑏 + 𝑐} 2. Оценка 𝑶 (О большое) 24 В отличие от оценки 𝚯, оценка 𝑶 требует только, чтобы функция 𝑓(𝑛) не превышала 𝑔(𝑛), начиная с некоторого 𝑛 > 𝑛0 , с точностью до постоянного множителя (рис. 4):
Рис. 4. Оценка 𝚶 Запись 𝑶(𝒈(𝒏)) обозначает класс функций, которые растут не быстрее, чем функция 𝑔(𝑛) с точностью до постоянного множителя, поэтому иногда говорят, что 𝑔(𝑛)мажорирует функцию 𝑓(𝑛). Например, для всех функций: 1 𝑓(𝑛) = ,𝑓(𝑛) = 12,𝑓 (𝑛) = 3𝑛 + 17, 𝑛 𝑓(𝑛) = 𝑛 ∙ ln(𝑛),𝑓(𝑛) = 6𝑛2 + 24𝑛 + 77 будет справедлива оценка 𝑂(𝑛2 ).
3. Оценка𝛀 (Омега) Оценка 𝛀 является оценкой снизу, т.е. определяет класс функций, которые растут не медленнее, чем𝑔(𝑛) с точностью до постоянного множителя (рис. 5):
25 Рис. 5. Оценка 𝛀 Теорема. Для любых двух функций 𝑓(𝑛) и 𝑔(𝑛) соотношение 𝑓(𝑛) = 𝚯(𝑔(𝑛)) выполняется тогда и только тогда, когда 𝑓(𝑛) = 𝐎(𝑔(𝑛)) и 𝑓(𝑛) = 𝛀(𝑔(𝑛))(рис. 6).
Например, запись 𝛀(𝑛 ∙ ln(𝑛)) обозначает класс функций, которые растут не медленнее, чем 𝑔(𝑛) = 𝑛 ∙ ln(𝑛). В этот класс попадают все полиномы степени 𝑛 > 2 и все степенные функции с основанием большим единицы. Есть примеры, когда для пары функций не выполняется ни одно из асимптотических соотношений. Например, 𝒇(𝒏) = 𝒏𝟏+𝐬𝐢𝐧(𝒏) и𝒈(𝒏) = 𝒏. В асимптотическом анализе алгоритмов разработаны специальные методы получения асимптотических оценок, особенно для класса рекурсивных алгоритмов. 𝚯 оценка является предпочтительной. Знание асимптотики поведения функции трудоемкости алгоритма (сложности), дает возможность делать прогнозы по выбору более рационального с этой точки зрения алгоритма для больших размерностей исходных данных.
Рис. 6. а, б, в – графические примеры Θ, O иΩ обозначений. В качестве 𝑛0 используется минимальное возможное значение, т.е. при любом значении 𝑛 > 𝑛0 соответствующая оценка также будет выполниться. 26 3.4. ТРУДОЕМКОСТЬ АЛГОРИТМОВ И ВРЕМЕННЫЕ ОЦЕНКИ Элементарные операции на языке записи алгоритмов При получения функции трудоемкости алгоритма выделяют следующие «элементарные» операции: 1. Простое присваивание: a b; 2. Одномерная индексация a[i] : (адрес (а)+i*[длина элемента]); 3. Арифметические операции: (* ,/,- , +); 4. Операции сравнения: a < b; 5. Логические операции (or, and, not). Из этих операций в анализе исключают команду перехода по адресу, считая ее связанной с операцией сравнения в конструкции ветвления. 1. Конструкция «Следование» Трудоемкость конструкции есть сумма трудоемкостей блоков, следующих друг за другом (рис. 7).
𝐹≪следование≫ = 𝑓1 + ⋯ + 𝑓𝑘 , где 𝑘 – количество блоков. Рис. 7. Конструкция «Следование» 2. Конструкция «Ветвление» Общая трудоемкость конструкции «Ветвление» требует анализа вероятности выполнения переходов на блоки «Then» и «Else» и определяется как (рис. 8): 𝐹≪ветвление≫ = 𝑓𝑡ℎ𝑒𝑛 ∗ 𝑝 + 𝑓𝑒𝑙𝑠𝑒 ∗ (1 − 𝑝) if ( l ) then → 𝒇𝑡ℎ𝑒𝑛 с вероятностью𝒑 else → 𝒇𝑒𝑙𝑠𝑒 с вероятностью𝒑 − 𝟏 Рис. 8. Конструкция «Ветвление» 3. Конструкция «Цикл 1». Количественно-зависимый алгоритм 27 После сведения конструкции к элементарным операциям ее трудоемкость определяется как (рис. 9): 𝐹≪цикл≫ = 1 + 3 ∗ 𝑁 + 𝑁 ∗ 𝑓≪тело цикла≫ fori← 1 𝑡𝑜 𝑵 i←1 end i←i+1 ifi≤ 𝑵
Рис. 9. Конструкция «Цикл 1». Количественно-зависимый алгоритм 4. Конструкция «Цикл2». Количественно-параметрический алгоритм 3.5. ПРИМЕРЫ АНАЛИЗА ПРОСТЫХ АЛГОРИТМОВ Пример 1. Задача суммирования элементов квадратной матрицы Алгоритмвыполняетодинаковое <> количествооперацийпри Sum = 01 фиксированномзначенииn,и, For i = 1 to nn следовательно, является количественно- For j = 1 to nn зависимым. Sum = Sum + A(i, i)4 Применениеметодикианализа Next j конструкции «Цикл 1» дает: Next i Внутренний: 𝒇𝟏 (𝒏) = 𝟏 + 𝟑𝒏 + 𝟒𝒏 Print (Sum) Внешний: 𝒇𝟐 (𝒏) = 𝟏 + 𝟑𝒏 + 𝒏𝒇𝟏 (𝒏)<> Окончательно:
𝑭(𝒏) = 𝟏 + 𝟏 + 𝟑𝒏 + 𝒏(𝟏 + 𝟑𝒏 + 𝟒𝒏) = 𝟐 + 𝟒𝒏 + 𝟕𝒏𝟐 = 𝚯(𝒏𝟐 ) Под 𝒏 понимается линейная размерность матрицы, в то время, как на вход алгоритма подается 𝒏𝟐 значений.
28 Пример 2. Задача поиска максимума в массиве Данныйалгоритмявляется <> количественно-параметрическим, Max = S(1)2 поэтомудляфиксированной For i = 2 to nn-1 размерности исходных данных If Max < S(i)2 (< u S[i]) необходимо проводить анализ для Max = S(i)2 (= u S[i])худшего, лучшего и среднего end ifслучая. Next i Худший случай Print (Max) Максимальноеколичество <> переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна 𝑭(𝒏) = 𝟐 + 𝟏 + 𝟑(𝒏 − 𝟏) + (𝒏 − 𝟏)(𝟐 + 𝟐) = 𝟕𝒏 − 𝟒 → 𝚯(𝒏). жүктеу/скачать 3,71 Mb. Достарыңызбен бөлісу:
|