Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
Практическая работа №11. Решение задач по составлению сложных алгоритмических структурЗадача перемножения длинных целых чисел без знака Длинные целые числа используются в арифметике высокой точности (Д. Кнут. Т. 2), криптографическом кодировании сообщений (шифровании). При этом длина чисел (т.е. количество цифр в записи числа) можетдостигать нескольких сотен и более. Арифметические операции (сложение,вычитание, умножение, деление) над длинными числами не могут выполняться компьютером за один шаг. Любая такая операция должна реализовываться специально написанной процедурой. Представление длинных целых чисел Наиболее естественным является простое расширение стандартного формата: если для записи числа требуется n цифр, то память для них выделяется в виде непрерывной области соответствующего размера. Предположим, что перемножается два числа U = unun-1un-2 ... u3u2u1 и V= vnvn-1vn-2 ... v3v2v1. Результат имеет суммарную длину W = wnwn-1wn-2 ...w3w2w1. Числа записаны в позиционной системе счисления с основанием(базой) b: 0 <= ui, vi, wi < b. При этом индекс единица соответствует младшей цифре в записи числа. Алгоритм умножения 1 (классический) Этот алгоритм работает подобно тому, как производится умножение на бумаге. Числа представлены массивами цифр. Основание системы счисления b может быть как двоичным, b = 2, так и сколь угодно большим, например, занимающим машинное слово. Важно, чтобы перемножить или сложить цифры можно было одной машинной операцией (или малым их числом). Для представления цифр процедура использует некоторый тип Digit. procedure SimpleMultiplication (U, V: superlongpositive; var W: superlongpositive; n, m: integer); var i, j: integer; S: DoubleDigit; {Место для формирования двух цифр.} C: Digit; {Разряд переноса.} begin for i := 1 to n do W[i] := 0; {Подготовка места для результата.} for j := 1 to m do {Пo цифрам числа V.} begin С := 0; {Сначала переноса нет.} for i := 1 to n do {Пo цифрам числа U.} begin S := U[i]*V[j]+W[i+j-1]+C; W[i+j-1] := S mod P; {Временное значение очередной цифры.} С := S div P; {Формирование разряда переноса.} end; W[j + n] := С; {Старшая цифра частичного произведения.} end; end; Непосредственно видно, что сложность этого алгоритма равна O(nm) или в случае сомножителей одинаковой длины - O(n2). Алгоритм умножения 2 (оптимизированный по времени) Разделим задачу на подзадачи, разделив запись каждого из сомножителей на две части: U= U2U1, V=V2V1. При n-разрядных сомножителях длины Ui, Vi будут равны n/2. Индексу 1 соответствует младшая половина, а индексу 2 - старшая. Иначе можно записать U = U200..00 + U1 = U2bn/2 +U1. Произведение UV = (U2bn/2 + U1)(V2bn/2 + V1) = UVbn + U2V1bn/2 +U1V2bn/2 + U1V1. Вычисление произведения предлагаемым способом требует четырех умножений чисел половинной длины, трех сложений и трех умножений на величину bq. Умножения на степень b равносильны сдвигу и требуют времени O(n). То же можно сказать о сложности аддитивных операций. Четырех умножений чисел оказывается слишком много: log24 = 2, сложность рекурсивного алгоритма будет равна O(n2). Но можно немного преобразовать расчетную формулу: UV = U2V2(bn + bn/2) + (U2 - U1)(V1-V2)bn/2 + U1V1(bn/2+1) Она содержит только три умножения. Очевидный алгоритм, строя- щийся по этой формуле, описывается уравнением для функции сложности: Т(n) = 3Т(n/2) + bn , его решение Т(n) = O(nlog3) = O(n1,58), что значительно лучше классического алгоритма. Возведение целого числа без знака в положительную целую степень Вычисление у = хn для вещественных x и n не представляет никакого труда: y = en*ln(x). Но для целых чисел этот способ неприменим, поскольку вычисления экспоненты и логарифма на цифровой вычислительной машине принципиально являются приближенными и не будут давать целочисленный результат. Не поможет здесь и округление, так как крайне трудно достоверно вычислить величину ошибки при приближенных расчетах, следовательно, не известно ни в какую сторону округлять, ни является ли истинным результатом ближайшее целое или ошибка составляет несколько единиц. Особенно важна эта проблема для длинных целых x и больших n, что встречается в некоторых критических приложениях, например, в шифровании информации. Правильный результат будет получен, если реализуем возведение в степень через целочисленное умножение. Решение "в лоб" – перемножение n экземпляров x, на что требуется (n-1) операция умножения. Более остроумный метод состоит в том, чтобы на каждом шаге вычислений активно использовать достижения предыдущих шагов. Пусть, например, требуется вычислить x 1024. 1024. На каждом шаге получается очередная степень x, которая на следующем шаге умножается сама на себя, т. е. предыдущее значение возводится в квадрат. Результат, таким образом, достигается за десять шагов. Этот метод хорош, если n равно степени двойки. Его сложность равна log n умножений. Для других показателей он требует видоизменения. Пусть, например, требуется вычислить х 1023. Очевидным подходом является достижение за девять умножений значения х 512 и перемножение еще за девять операций всех ранее найденных степеней: 1023 = 1 + 2 + 4 + 8 + ... + 256 + 512. Интересно, что для меньшей степени (1023 < 1024) требуется на восемь умножений больше! Для произвольного n можно использовать так называемый бинарный метод. Представим n его двоичной записью. Читая запись слева направо, начиная с первой значащей цифры (единицы), будем производить следующие действия: первую единицу игнорируем; переменной y присваиваем начальное значение, равное x; далее в цикле пока не закончились цифры умножаем y на себя, а если очередная цифра равна единице, то дополнительно умножаем y на x. По окончании цикла в y находится значение xn. Эти действия можно описать следующей процедурой. procedure BinaryMethod (x, n: integer; var у: integer); var В: integer; begin у:= x; В:= NextBit(n); while В = 0 do В:= NextBit(n); {В B - первая единица.} В:= NextBit(n); while not Eon(n) do {Пока не закончилась запись числа n.} begin у:= у*у; if В = 1 then у:= у*х; end; end; Сложность процедуры зависит от количества единиц l(n) в записи числа n и может быть определена формулой: Т(n) = log n + l(n)-1. Минимальная сложность получается для степеней двойки, n = 2m-1, l(n)=1. Максимальная сложность - для чисел n = 2m-1: l(n) = log2(n+l). Что общего между рассмотренными методами оптимизации алгорит- мов? Стандартные алгоритмы решения задач перемножения матриц, длинных чисел, возведения в степень сводили задачу к длинной последовательности однородных подзадач малого размера. Эта последовательность записывалась в виде итеративного алгоритма, складывающего простым (стандартным) образом общее решение из решений независимых малых подзадач. Малые подзадачи отличаются по своей постановке от исходной задачи. Оптимизированные алгоритмы делят задачу на малое число подзадач относительно большого размера (но, разумеется, меньшего, чем исходная задача). Подзадачи являются уменьшенными копиями исходной задачи, поэтому алгоритм удобно сформулировать в рекурсивной форме. Однако не всегда этот подход приводит к желаемому ускорению. Часто требуется некий нестандартный, усложненный метод соединения подзадач, позволяющий обойтись меньшим их числом. При этом подзадачи оказываются зависимыми. Эти рассуждения не претендуют на точность, но, вероятно, способны указать верный путь при оптимизации алгоритмов для других задач. Ярким примером является алгоритм быстрой сортировки Э.Хоара. ЗАДАЧИ Задача 1 Уровень 1. Рассмотрим алгоритм нахождения НОД, построенный на основе метода вычитаний с таким уточнением: “На каждом шаге алгоритма из наибольшего числа набора вычитается следующее по величине или равное”. а) Примените этот алгоритм к набору из примера: {72; 84; 132; 144}. б) Приведите пример набора из четырех различных чисел, для которого этот алгоритм является лучшим из всех алгоритмов, основанных на методе вычитаний. в) Приведите пример набора из четырех различных чисел, для которого этот алгоритм не является лучшим. Задача 2 Предложите алгоритм выбора пар для вычитания, обеспечивающий возможно меньшее число шагов в обсуждаемом методе нахождения НОД. Уровень 1. Опишите алгоритм. Продемонстрируйте его работу для набора чисел из пункта в задачи 1. Уровень 2. Напишите программу, которая по заданному набору из n чисел определяет последовательность выбора пар, приводящую к результату за возможно меньшее число шагов. Формат ввода: Количество чисел n Ј 10 1-е число набора 2-е число набора ... n-е число набора Формат вывода: Количество операций т Номер 1-го уменьшаемого Номер 1-го вычитаемого Номер 2-го уменьшаемого Номер 2-го вычитаемого ... Номер m-го уменьшаемого Номер m-гo вычитаемого Пример:
Задача 3 Уровень 1. Ваш знакомый живет в стандартном двенадцатиэтажном доме в квартире 87. На каком этаже может располагаться его квартира? (На лестничной площадке одно и то же число квартир.) Вообще, как быстро определить, может ли квартира с данным номером находиться на данном этаже? Задача 4 Уровень 1. Язык племени мумбу-юмбу состоит из шестибуквенных слов, составленных из букв {А, Б, В, Г, Д, Е, Ж, З, И, К}. В Оксфорде издан полный словарь слов этого языка (упорядоченных по алфавиту): АААААА, АААААБ, АААААВ … КККККИ, КККККК. На каждой странице словаря помещается 15 слов. На каких страницах и в каких строках находятся слова ДЕКАДА и ЗАБАВА? Задача 5 Найдите цифру с номером n в последовательности 01234567891011121314151617181920... записанных подряд натуральных чисел. Уровень 1. Опишите алгоритм. Найдите цифру с номером 1999. Уровень 2. Напишите программу. Формат ввода: Число п < 1 000 000 Формат вывода: Цифра с номером n Пример Ввод: 31 Вывод: 2 Задача 6 Для любого натурального числа алгоритм совершает следующие операции: отделяет от числа первую цифру и прибавляет ее к числу из оставшихся цифр. Процесс оканчивается тогда, когда в числе остается одна цифра. Например: 123456 ® 23457 ® 3459 ® 462 ® 66 ® 12 ® 3. Уровень 1. Определить результат работы алгоритма для чисел вида при различных значениях n. Уровень 2. Напишите программу, которая выдает все промежуточные результаты для чисел из не более чем 50 цифр. Формат ввода: Количество цифр заданного числа 1-я цифра 2-я цифра … п-я цифра. Формат вывода: Первый промежуточный результат Второй промежуточный результат … Итоговая цифра. Задача 7 Известно, что любую дробь , где а и b — натуральные числа, можно представить в виде цепной дроби. Уровень 1. Опишите алгоритм. Представьте в виде цепной дроби . Уровень 2. Напишите программу, которая по данным числам a и b представляет дробь в виде цепной дроби (a, b < 1 000 000). Формат ввода: Число а Число b Формат вывода: Количество числителей п Число с0 Число с1 … Число сn Пример Ввод: 5 9 Вывод: 3 0 1 1 4 Задача 8 Уровень 1. Пусть большее из чисел набора {а, b} равно 1999. Какое максимальное число шагов может сделать алгоритм Евклида с делением для такого набора в худшем случае? Каким при этом будет второе число набора? Приведите пример такого числа. Сколько таких чисел? Уровень 2. Придумайте алгоритм для нахождения по числу а (а < 1 000 000) всех чисел b, меньших а и таких, для которых алгоритм Евклида делает максимальное число шагов. Формат ввода: Число а Формат вывода: Число шагов Количество п различных значений b 1-е значение b 2-е значение b … п-е значение b Задача 9 Уровень 1. Обобщить алгоритм Евклида с делением на 2 и вычитанием для наборов из более чем двух чисел. Применить обобщенный алгоритм к набору {72; 84; 132; 144}. Уровень 2. Доказать, что если одно из чисел а, b четное, а другое нечетное, то следующее преобразование сохраняет множество общих делителей а и b: ЕСЛИ ровно одно из чисел а, b четное ТО поделить его на 2 ИНАЧЕ заменить большее из чисел а, b их разностью Задача 10 Есть несколько ведер с различными емкостями. Разрешается этими ведрами добавлять или вычерпывать воду из бочки. Сначала бочка пуста. Уровень 1. Необходимо налить в бочку 1 литр воды, имея в распоряжении ведра емкостью 17, 32 и 45 литров. Как это сделать поскорее (за возможно меньшее количество переливаний)? Сколько при этом будет перелито воды? Можно ли выполнить эту работу, чтобы общее количество перелитой воды было еще меньше? Уровень 2. Написать программу, которая выдает последовательность действий для наливания в бочку а (a < 1 000 000) литров воды. Формат ввода: Число ведер п Ј 10 Емкость 1-го ведра Емкость 2-го ведра … Емкость п-го ведра Нужное число литров а Формат вывода: НЕЛЬЗЯ или Число операций т 1-я операция 2-я операция … m-я операция Каждая операция представляет собой + номер ведра (долить в бочку) или — номер ведра (вычерпать из бочки) Пример
Задача 11 Уровень 1. Из кучки камней двое играющих по очереди берут 1, 2 или 3 камня. Проигрывает тот, кто берет последний камень. Предположим, что всего камней N. Кто из игроков имеет выигрышную стратегию? Опишите ее. А если выигрывает взявший последний камень? Задача 12 Уровень 1. Алиса, попав в cтрану чудес, забыла таблицу умножения. Она говорит: “семью семь будет ... пятнадцать, девятью девять будет ... тринадцать”. Определите, в какой модульной арифметике такие правила умножения справедливы. Сколько всего таких арифметик? Уровень 2. Напишите программу, которая по введенным примерам таблицы умножения определяет, существует ли модульная арифметика, в которых эти примеры имеют место. Чем больше таких модулей найдет ваша программа и чем быстрее она это сделает, тем лучше. Формат ввода: Число равенств п Ј 10 1-е равенство 2-е равенство … п-е равенство Каждое равенство имеет вид число1 * число2 = число3 Формат вывода: Число найденных модулей т 1-й модуль 2-й модуль…n-й модуль Пример
Задача 13 По заданным остаткам а, b по простому модулю р найти а/b (в решении этой задачи пригодится представление наибольшего общего делителя суммой чисел, кратных числам набора). Уровень 1. Опишите алгоритм. Найдите 17/23 по модулю 239. Уровень 2. Напишите программу вычисления частного а/b (а, b, р < 1 000 000). Формат ввода: Модуль р Число а Число b Формат вывода: Число a/b (по модулю p) Пример
Практическая работа №12. Составление программ для машины ТьюрингаЦель работы: Формирование представления учащихся об универсальном исполнителе алгоритмов. Получение навыков построения программ для машины Тьюринга. В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга. Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи. Что собой представляет машина Тьюринга? Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице. Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие: Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ. Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова. Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа. Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия: Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой). Передвигаться на одну ячейку влево или вправо. Менять свое внутреннее состояние. Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния). Пример работы машины Тьюринга Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова. Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).  Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):  Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние q2 (команды которого совпадают с командами q1 предыдущей программы). Пример Пример. Требуется построить машину Тьюринга, которая прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанных в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа. Решение. Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для данной машины Тьюринга может выглядеть так:  В этой машине Тьюринга q1 — состояние изменения цифры, q0 — состояние останова. Если в состоянии ql автомат видит цифру 0..8, то он заменяет ее на 1..9 соответственно и переходит в состояние q0, т.е. машина останавливается. Если же он видит цифру 9, то заменяет ее на 0, сдвигается влево, оставаясь в состоянии ql. Так продолжается до тех пор, пока автомат не встретит цифру меньше 9. Если же все цифры были равны 9, то он заменит их нулями, запишет 0 на месте старшей цифры, сдвинется влево и в пустой клетке запишет 1. Затем перейдет в состояние q0, т.е. остановится. Задание 1. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. 2. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. 3. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. Дополнительные задания 1. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. 2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. 3. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. |