More Related Content
What's hot (12)
Viewers also liked (20)
Similar to практика 2 (20)
More from student_kai (20)
практика 2
- 1. Практическое занятие 2 Свойства алгоритмов 1. 2. 3. 4. Теоретические сведения Контрольные вопросы Указания по выполнению заданий Задания
- 2. Теоретические сведения Одной из моделей алгоритмов является операторная схема <U, V, A, R, T>, где U = {S1, …, Sm} – множество операторов Sj, V = {x1, …, xn} – множество переменных xi, A ⊆ V × U – отношение «быть аргументом» (xi A Sj), R ⊆ U × V – отношение «быть результатом» (Sj R xi), T ⊆ U × U – отношение между оператором-предшественником и оператором-преемником (Sj T Sk). Свойство алгоритма – это утверждение о состоянии его переменных. Утверждение о состоянии – это предикат, определенный на множестве состояний W, т.е. отображение множества W в множество BV = {true, false} логических значений.
- 3. Теоретические сведения Обычно важнее всего установить связь между исходным и заключительным состояниями алгоритма. 1. Из единственного входа Sin операторной схемы должна исходить лишь одна дуга ain к некоторому другому оператору, с исполнения которого начинается преобразование состояний. Этой дуге сопоставляется предикат pin, называемый начальным предикатом. 2. Допустимыми начальными состояниями называются такие состояния, вырабатываемые оператором Sin, которые удовлетворяют начальному предикату pin. 3. В выход Sout операторной схемы должна заходить единственная дуга, которой сопоставляется заключительный предикат pout. 4. Пара предикатов (pin, pout) называется спецификацией алгоритма, а доказательство того, что его исполнение, начавшееся в допустимом начальном состоянии, завершается в состоянии, удовлетворяющем предикату pout, – доказательством правильности алгоритма.
- 4. Теоретические сведения 5. p(S) – дизъюнкция предикатов, сопоставленных всем дугам, заходящим в оператор S. Если некоторый оператор Sj начинает исполняться в состоянии w, удовлетворяющем дизъюнкции p(Sj), в результате его исполнения вырабатывается состояние w1 и происходит переход по дуге ai, исходящей из Sj, причем состояние w1 удовлетворяет предикату pi, сопоставленному дуге ai, то данное исполнение оператора S корректно. 6. Предикаты, сопоставляемые дугам, зацикливающим схему, принято называть инвариантами циклов. 7. Суть доказательства свойств алгоритмов состоит в правильном подборе инвариантов циклов. 8. Необходимо доказать завершаемость алгоритма
- 5. Теоретические сведения Один из методов доказательства завершаемости алгоритма заключается в следующем. Пусть для операторной схемы задана предикатная разметка дуг и найдена функция состояния F с целочисленными значениями, такая, что: 1) для каждого оператора S и для каждого состояния w, удовлетворяющего предикату p(S), верно, что F(w1) < F(w), где w1 – состояние, вырабатываемое оператором S в состоянии w; 2) для каждой дуги ai верно, что pi ⊃ F(w) ≥ 0, где w – текущее состояние при прохождении дуги ai; 3) соблюдаются условия корректности операторов по отношению к заданной предикатной разметке. Тогда алгоритм, начинающий работу из допустимого состояния w0, завершается за конечное число шагов. Завершаемость алгоритма вытекает из завершаемости таких частей алгоритма, которые исполняются не более одного раза при любом исполнении алгоритма. Тогда
- 6. Теоретические сведения Предикатная разметка операторной схемы алгоритма слияния двух массивов j n k i a k p6 S1 S4 i a p9 j S7 b S8 p7 p3 m n a p5 b i p1 m p11 c k S5 i j b p10 k k j m p8 p2 S2 S3 p4 S9 S6 p13 i j k p12 c j c S10
- 7. Теоретические сведения p1: m ≥ 0 ∧ n ≥ 0 ∧ m + n ≥ 1 ∧ a1 ≤ a2 ∧ … ∧ am – 1 ≤ am ∧ ∧ b1 ≤ b2 ∧ … ∧ bn – 1 ≤ bn, p2: p1 ∧ i = 1 ∧ j = 1 ∧ k = 1, p12: ai ≤ ai + 1 ∧ … ∧ am – 1 ≤ am ∧ bj ≤ bj + 1 ∧ … ∧ bn – 1 ≤ bn ∧ c1 ≤ c2 ∧ … ∧ck – 2 ≤ ck – 1 ∧ i ≥ 1 ∧ i ≤ m + 1 ∧ j ≥ 1 ∧ j ≤ n + 1 ∧ ∧ (i ≤ m ⊃ ck – 1 ≤ ai) ∧ (j ≤ n ⊃ ck – 1 ≤ bj) ∧ k ≤ m + n, p3: p12 ∧ i ≤ m, p4: p12 ∧ i = m + 1, p5: p12 ∧ i ≤ m ∧ j ≤ n, p6: p12 ∧ i ≤ m ∧ j = n + 1, p7: p4 ∧ ai ≤ bj, p8: p4 ∧ ai > bj, p9 = p10: ai ≤ ai + 1 ∧ … ∧ am – 1 ≤ am ∧ bj ≤ bj + 1 ∧ … ∧ bn – 1 ≤ bn ∧ c1 ≤ c2 ∧ … ∧ ck – 1 ≤ ck ∧ i ≥ 1 ∧ i ≤ m + 1 ∧ j ≥ 1 ∧ j ≤ n + 1 ∧ k = i + j – 2 ∧ ∧ (i ≤ m ⊃ ck ≤ ai) ∧ (j ≤ n ⊃ ck ≤ bj) ∧ k ≤ m + n, p11: ai ≤ ai + 1 ∧ … ∧ am – 1 ≤ am ∧ bj ≤ bj + 1 ∧ … ∧ bn – 1 ≤ bn ∧ c1 ≤ c2 ∧ … ∧ ck – 2 ≤ ck– 1 ∧ i ≥ 1 ∧ i ≤ m + 1 ∧ j ≥ 1 ∧ j ≤ n + 1 ∧ k = i + j – 1 ∧
- 8. Контрольные вопросы 1. 2. 3. 4. 5. Операторная схема. Свойства алгоритма. Утверждение о состоянии. Предикатная разметка дуг операторной схемы. Условия установления связи между исходным и заключительным состояниями алгоритма. 6. Спецификация алгоритма. 7. Корректность исполнения оператора. 8. Инвариант цикла. 9. Завершаемость алгоритма. 10.Поэтапная завершаемость алгоритма.
- 9. Указания по выполнению заданий 1. 2. 3. 4. 5. 6. Получить задание Разработать алгоритм решения задачи. Построить операторную схему. Выполнить предикатную разметку операторной схемы Доказать завершаемость алгоритма Подготовить отчет по выполнению задания. Отчет должен включать задание и описание этапов выполнения задания. 7. Ответить на вопросы по выполнению задания и контрольные вопросы
- 10. Задания 1. Определить длину наибольшей невозрастающей подпоследовательности последовательности чисел, заканчивающейся 0. 2. Определить длину наименьшей невозрастающей подпоследовательности последовательности из 25 чисел. 3. Определить длину наибольшей неубывающей подпоследовательности последовательности из 25 чисел. 4. Отсортировать по убыванию массив из 10 положительных чисел методом последовательного нахождения максимума. 5. Отсортировать по возрастанию массив из 10 целых чисел, не превосходящих по абсолютному значению 100, методом последовательного нахождения минимума. 6. Отсортировать массив из 10 чисел методом пузырька. 7. Определить наибольшую десятичную цифру целого числа. 8. Определить число десятичных цифр целого числа. 9. Переставить элементы массива из 20 чисел в обратном порядке. 10. Найти количество различных чисел среди элементов целочисленного массива из 25 элементов. 11. Выполнить умножение многочленов, степень, которых не выше 10, а целочисленные коэффициенты записаны в двух массивах. 12. Выполнить двоичный поиск в массиве из 30 чисел заданного числа. 13. Найти наибольший общий делитель двух натуральных чисел, используя алгоритм Евклида.