Доказательная алгоритмика. Глава 4

начало http://www.proza.ru/2015/07/16/1738
назад http://www.proza.ru/2015/07/17/1295

Решим алгоритмическую задачу 5:
Построить список b индексов элементов списка а, значение которых равно значению l.(оператор SELECT, ключевое слово WHERE)

Создаём предформальное описание алгоритма:
1.Строим список b индексов элементов списка а, значение которых равно значению l, обходя список а.
2.Элемент списка b получится как как элемент a(k) списка a, удовлетворящий предикату a(k)=l
На псевдокоде это запишется так:

For k=1 to count(a) do
If a(k)=l then add(b,k)

Рис.11. Алгоритм для задачи 5

Этот алгоритм уже использовался нами, как часть алгоритма №2 для задачи 3.
Попробуем свои силы в разработке более сложных алгоритмов.

Задача 6: удалить из списка а все элементы, значение которых равно l. (предполагая при этом, что описание метода удалитьэлемент для типа «список» не предзадано)(оператор DELETE, ключевое слово WHERE)

Предформальное описание
1.Список а, из которого удалены все элементы, значение которых равно l (состояние 2), получится из списка а (состояние1) при обходе списка b.
2.Список а (состояние 1) получится как список а (состояние 0), из которого удалены все элементы.
3.Список b получится при обходе списка а (состояние 0).
4.Элемент b(k) списка b получится как элемент a(k) списка а (состояние 0), не удовлетворяющий предикату a(k)=l.
5.Элемент a(k) списка а, из которого удалены все элементы, значение которых равно l (состояние 2), получится как элемент b(k) списка b.
В этом описании у нас присутствует новый элемент: понятие состояние объекта. А именно, если в процессе выполнения алгоритма состояние какого-нибудь объекта изменяется, то мы должны указать, над объектом в каком состоянии производится данная операция. Исключение составляет случай сборки (множественного) объекта в цикле.(Если в теле цикла он упоминается 1 раз)

Собираем теперь из предформального описания формальное (то есть запись на псевдокоде) Здесь немного поинтереснее это делается (потому что список а - в 3-х разных состояниях,а также одновременно с движением рассуждения на следующий слой (1->5, 3->4, ) есть продолжение движения в этом же слое(1->2, 1->3))
В итоге получится следующая запись на псевдокоде (слева я поставил номера утверждений предформального описания, соответствующих текущим строкам записи на псевдокоде):

3)for k=1 to count(a) do
4)if not(a(k)=l) then add(b,a(k))
2)clear(a)
1)for k=1 to count(b) do
5)add(a,b(k))

Рис.12. Алгоритм для задачи 6.

Объясню теперь, как такая последовательность получилась. Ставим 1) сначала на 1-ое место. (потому что других вариантов нет). Ставим 2) на место непосредственно перед 1) (так как 2) - подчинено 1) на том же слое). Ставим 3) на место непосредственно перед 1) (так как 2) - подчинено 1) на том же слое). Но тут возникает коллизия: поскольку и 2) и 3) – должны занять место непосредственно перед 1)(и такой вариант допустим,  и при реализации (одним исполнителем) он он означает индифферентность порядка выполнения этих операций. А при выполнени 2-мя исполнителями – параллельное их выполнение.), то нет ли дополнительной информации о порядке (между собой) шагов 2) и 3)?
Есть, и она содержится в шаге 1, а именно в упоминании в нём, что список а (состояние 2) – получается из списка а (состояние 1) Вот почему реализацию шага 3 – ставим после реализации шага 2.
Ну а шаги 4 и 5 (то есть в переходом на следующий слой) – ставим непосредственно после шагов, их вызвавших (соответственно 3 и 1)

Решим теперь задачу 7:
Упорядочить список a по возрастанию значений его элементов (то есть получить список b, который является списком а, упорядоченным по значению его элемента)(ключевое слово ORDER BY)

Предформальное описание
1.список b элементов списка а, упорядоченных по возрастанию значений элементов списка а, получится при обходе списка а по i=1..n
2.элемент b(i) списка b элементов списка а, упорядоченного по возрастанию значений элементов списка а, получится как минимальное значение элементов подножества a(i,n)
3.минимальное значение min элементов подножества a(i,n), получится при обходе списка а по k=i..n
4.min (состояние k-i+1) получится как значение элемента a(k) списка а, удовлетворяющее предикату f(k-i+1)
5.предикат f(k-i+1) получится как a(k)<min(состояние k-i) (и это верно в том числе и для min=undef (неопределённое значение))
6.min(состояние 0) получится как clear(min) (очистка значения min)

Переходим на псевдокод:

n=count(a)
1)for i=1 to n do
6)clear(min)
3)for k=i to n do
5)if a(k)<min then
4)min=a(k)
endif
endfor
2)b(i)=min
Endfor

Рис.13. Алгоритм для задачи 7.

Задача 8:
Получить список b, содержащий только 1 элемент из списка а, имеющеий данное значение.(ключевое слово UNIQUE, в некоторых реализациях - ключевое слово DISTINCT):

Предформальное описание:
1.Список b, содержащий только 1 элемент из списка а, имеющий данное значение, получится при обходе списка с по i=1..count(c)
2.Список с получится как упорядоченный по возрастанию список а (см. алгоритм задачи 7)
3.Элемент b(k) cписка b, содержащий только 1 элемент из списка а, имеющий данное значение, получится как элемент c(i) списка с, удовлетворяющий предикату f(i)
(отмена)4.Предикат f(i) получится как c(i)>cc
5.значение сс получится как с(i), удовлетворяющее предикату f(i)
6.см. 4.

Что же при переходе на псевдокод? (клянусь, в этот раз я не получал предформальное описание из описания на псевдокоде. Хотя определённая алгоритмическая идея была, не скрою. Но что в этом плохого? Просто создание предформальной записи (на каждом шагу) заставляет задумываться и контролировать рассуждение.)

2)с=sort(a,up) (см. алгоритм задачи 7, он встроен сюда, как процедура)
1)for i=1 to count(c) do
6)if c(i)>cc then
3)add(b,c(i))
5)cc=c(i)
engif

Рис.14. Алгоритм для задачи 8.

Разберём теперь, как (по каким правилам) получается из предформального описания запись на псевдокоде. Главный принцип здесь такой: то (высказывание), что стоит позже (относительно данного) в предформальном описании, будет стоять раньше (относительно данного) в записи на псевдокоде.
Поэтому 2 – стоит позже 1, в итоговой записи.
Но тут опять коллизия: 1 и на 2 и на 3 – ссылается. Поэтому что раньше?  Конечно, 2, потому что это – движение в том же слое, а 3- переход на следующий слой. (правило тут такое: сначала реализуем переход по данному слою, потом – по следующему (-вытекающему)
Поэтому в итоге порядок такой: 2, 1, 3.
Но поскольку 3 - ссылается на 4, а 4 – заменён на 6 (в результате несвоевременного расположения), то  итоге порядок такой: 2, 1, 6, 3.
А поскольку на 6 ссылается также и 5, то 6 должен стоять (непосредственно) как перед 3, так и перед 5. Что же разрешит эту коллизию? (что же раньше, 3 или 5, стоит после 6?) Ничто, поэтому здесь и тот и этот порядок (5 и 6) правильны.
А кроме того, поскольку 5 и 6 стоят под одним предикатом, я объединил их под ним.

Задача 9:
Вычислить сумму значений элементов подмножества a(kb,ke) списка а (агрегатная функция SUM)

Предформальное описание:
1.Сумма s значений элементов подмножества a(kb,ke) списка а получится при обходе списка a по i=kb..ke
2.s(состояние i-kb+1) получится как s(состояние i-kb)+a(i) (в применяемой здесь арифметике для упрощения описания алгоритмов принято, что undef+b=b, где undef – переменная, имеющая неопределённое значение.)

Описание на псевдокоде

1)for i=kb to ke do
2)s=s+a(i)

Рис.15. Алгоритм для задачи 9

вперёд http://www.proza.ru/2015/07/22/1695