Методические указания к выполнению контрольных работ по дисциплине "Основы программирования" (стр. 6 из 40)
Формально определим метод вычислений как четверку ( Q, I, W, f ), где Q – это множество, содержащее подмножества I и W, а f – функция, переводящая множество Q в себя. Кроме того, f оставляет неподвижными точки множества W, т.е. f (q) равно q для всех элементов q из множества W. Эти четыре элемента Q, I, W и f представляют соответственно состояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение х из множества I определяет вычисляемую последовательность x0, x1, x2, … следующим образом:
x0 = х и xk+1 = f (xk) для k ³ 0. (1.1)
Говорят, что вычисляемая последовательность заканчивается через k шагов, если k – это наименьшее целое число, для которого xkпринадлежит W, и что она дает выходное значение xk для заданного х. (Заметим, что если xkпринадлежит W, то и xk+1 принадлежит W, так как в этом случае xk+1 = xk). Некоторые вычисляемые последовательности могут никогда не заканчиваться, но алгоритм – это метод вычислений, который заканчивается через конечное число шагов для всех х из I.
Например, алгоритм Е в этих терминах можно формализовать следующим образом. Пусть элементами множества Q будут все величины (n), все упорядоченные пары (m,n) и все упорядоченные четверки (m,n,r,1), (m,n,r,2) и (m,n,p,3), где m, n и р – это целые положительные числа, а r – неотрицательное целое число. Пусть I – это подмножество всех пар (m,n), а W – подмножество всех величин (n). Определим функцию f следующим образом:
(1.2)
Соответствие между данной записью и алгоритмом Е очевидно.
В этой формулировке понятия «алгоритм» не содержится ограничение, касающееся эффективности, о котором упоминалось ранее. Например, Q может быть множеством бесконечных последовательностей, которые нельзя вычислить с помощью карандаша и бумаги, а f может включать операции, которые не всегда возможно выполнить. Если мы хотим ограничить понятие «алгоритм» таким образом, чтобы в нем могли содержаться только элементарные операции, то введем ограничения на элементы Q, I, W и f, например, следующим образом.
Пусть А – это ограниченное множество букв, а L – множество всех строк, определенных на множестве А (т.е. множество всех упорядоченных последовательностей x0, x1, x2, …, где n³0 и xj принадлежит А для 1 £ j £ п. Идея заключается в следующем: закодировать состояния вычисления таким образом, чтобы они были представлены строками из множества L.
Теперь пусть N – целое неотрицательное число, а Q – множество всех пар (s, j), где s принадлежит L, a j – целое число, 0 £ j £ N.
Пусть I – подмножество пар из Q, для которых j=0, а W – подмножество пар из Q, для которых j = N. Если q и s – строки из L, то мы будем говорить, что q входит в s, если s имеет вид aqw, где a и w – некоторые строки.
И в завершение определим функцию f с помощью строк qj, fj и целых чисел aj, bj, 0 £ j £ N, следующим образом:
 , | если qj не входит в s |
 , | если a является самой короткой (1.3) строкой, для которой s = a qj w |
 . |
Метод вычислений, удовлетворяющий этому определению, безусловно, является эффективным. Кроме того, опыт показывает, что в таком виде можно представить любую задачу, которая решается с помощью карандаша и бумаги.
Упражнение 1.1. В тексте показано, как взаимно заменить значения переменных типе помощью символа замены, а именно – полагая t ¬ m, m ¬ п, п ¬ t. Покажите, как в результате ряда замен можно преобразовать четверку переменных (a,b,c,d) в (b,c,d,a). Другими словами, новое значение переменной а должно стать равным первоначальному значению 6 и т.д. Постарайтесь выполнить преобразование с помощью минимального числа замен.
Упражнение 1.2. Докажите, что в начале выполнения шага El m всегда больше п, за исключением, возможно, только первого случая выполнения этого шага.
Упражнение 1.3. Измените алгоритм Е (из соображений эффективности) таким образом, чтобы исключить из него все тривиальные операции замены типа « m ¬ n ». Запишите этот новый алгоритм в стиле алгоритма Е и назовите его алгоритмом F.
Упражнение 1.4. Чему равен наибольший общий делитель чисел 2 166 и 6 099?
Упражнение 1.5. Чему равно T5 (среднее число случаев выполнения шага Е1 при n = 5)?
Упражнение 1.6. Пусть т известно, а n – любое целое положительное число. Пусть Um– среднее число случаев выполнения шага Е1 из алгоритма Е. Покажите, что Umчетко определено. Существует ли какая-либо связь между Umи Tm ?
Упражнение 1.7. Придумайте эффективный формальный алгоритм вычисления наибольшего общего делителя целых положительных чисел т и п, определив соответствующим образом qj, fj, aj, bj(как в формулах (1.3)). Пусть входные данные представлены строкой ambn, т.е. за а, взятым т раз, следует b, взятое n раз. Постарайтесь найти самое простое решение, насколько это возможно.
Указание: воспользуйтесь алгоритмом Е, но вместо деления на шаге El присвойте r ¬ | т - п |, п ¬ min(m, п).
Математические методы, используемые при анализе алгоритмов, имеют свои отличительные особенности. Например, нам довольно часто придется выполнять суммирование конечного числа рациональных чисел или решать рекуррентные уравнения. Подобные темы обычно очень поверхностно освещаются при чтении математических дисциплин, поэтому назначение следующих разделов – не только потренироваться в использовании обозначений, но и проиллюстрировать типы и методы вычислений, которые будут нам особенно необходимы.
Пусть Р(п) – это некоторое утверждение, касающееся целого числа п, например:
«n умножить на (n + 3) – четное число» или «если п ³ 10, то 2n > n3». Предположим, нам нужно доказать, что утверждение Р(п) верно для всех положительных целых чисел п. Существует важный метод доказательства этого факта, который состоит в следующем:
(а) Доказать, что Р(1) верно.
(b) Доказать, что «если Р(1), Р(2), ..., Р(п) справедливы, то Р(п+1) также справедливо»; это доказательство должно иметь силу для любого целого положительного числа п.
Пример 1-2. Нечетные числа в сумме дают квадрат.
В качестве примера рассмотрим следующие известные с древних времен равенства, которые многие исследователи открывали независимо друг от друга:
| 1 = 12, | |
| 1 + 3 = 22, | |
| 1 + 3 + 5 = 32, | (1.4) |
| 1 + 3 + 5 + 7=42, | |
| 1 + 3 + 5 + 7 + 9 = 52. |
В общем виде эти равенства можно записать следующим образом:
1 + 3 + ××× + (2n – 1) = n2 . (1.5)
Обозначим это утверждение как Р(п) и докажем, что оно верно для любого положительного n. Согласно методу, описанному выше, имеем следующее.
(а) «Р(1) верно, так как 1 = 12 »
(b) «Если все утверждения Р(1), ..., Р(п) справедливы, то, в частности, верно и Р(п); следовательно, выполняется соотношение (1.5). Добавляя к обеим частям этого уравнения 2п + 1, получаем:
1 + 3 + ××× + (2п - 1) + (2п + 1) = п 2 + 2 п + 1 = (п + 1)2.
Таким образом, утверждение Р(п + 1) также справедливо».
Этот метод можно считать алгоритмической процедурой доказательства. В самом деле, следующий алгоритм дает доказательство утверждения Р(п) для любого целого положительного п в предположении, что этапы нашего доказательства (а) и (b) уже выполнены.
Алгоритм I (Построить доказательство). Для заданного целого положительного числа n этот алгоритм (рис. 1.2) выдаст доказательство того, что утверждение Р(п) верно.
Действие I 1. Доказать Р(1).
Присвоить k ¬ 1 и в соответствии с п. (а) выдать доказательство утверждения Р(1).
Действие I 2. k = n ?
Если k = n, закончить выполнение алгоритма; требуемое доказательство выдано.
Действие I 3. Доказать P(k + 1).
Согласно п. (b) выдать доказательство того, что «Если все утверждения Р(1), ..., P(k) справедливы, то P(k + 1) также справедливо». Вывести фразу «Мы уже доказали, что если утверждения Р(1), ..., P(k) верны, то верно и P(k+1)».