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

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

Доказательная алгоритмика

Глава 6

Печальное известие! В алгоритмах для задач 12 и 13, приведённых в главе 5, были найдены ошибки!
Ведь при выполнении алгоритма-12 из главы 5 получится так, что элемент С, состоящий только из значения А, будет добавлен count(B) раз, а при выполнении алгоритма-13 из главы 5 получится так, что элемент С, состоящий только из значения В, будет добавлен count(А) раз. А правильно – только по 1 разу.
И обнаружены эти ошибки были совершенно неожиданно, когда я вдруг (подсознательно, и это главный момент) сопоставил результат выполнения алгоритмов этих задач, приведённых в главе 5, с отображением этих результатов, приведённых в одном из источников, откуда я взял описание сути этих алгоритмов http://pionick.net/examples/mysql_join

После чего сообразил, что правильный алгоритм для задачи 12 таков:

for i=1 to count(A) do
d=0
for j=1 to count(B) do
if A(i,’col2’)=B(j,’col1’) then
add(C,A(i,’col1’),B(j,’col2’))
d=1
endif
endfor
if d=0 then
add(C,A(i,’col1’))
endfor

Рис.22. Правильный алгоритм для задачи 12

А для задачи 13:

for j=1 to count(B) do
d=0
for i=1 to count(A) do
if A(i,’col2’)=B(j,’col1’) then
add(C,A(i,’col1’),B(j,’col2’))
d=1
endif
endfor
if d=0 then
add(C,,B(i,’col2’))
endfor

Рис.23. Правильный алгоритм для задачи 13

А для задачи 14?
Ведь в этом случае, если не нашлось (подходящей) строки, то дописывать строку без указания значения другого массива придётся как для массива А, так и для массива В. Но как это сделать в одном алгоритме, если реализовать это (ввиду разного порядка циклов) по В возможно только в алгоритме-13, а по А – только в алгоритме 12?
Как соединить эти 2 последовательности прохода циклов в одном алгоритме? Только следующим способом:
1)проходим по двойному циклу и в специальном списке D – запоминаем i и j, сооветствующие друг другу.(а также в список С – заносим соответствующие значения из массивов А и В)
2)проходим список D тем же двойным циклом, и если для текущего i не нашлось в нём ни одного j, то добавляем в список С элемент c текущим значением А и пустым значением В, а если для текущего j не нашлось в нём ни одного i, то добавляем в список С элемент c текущим значением B и пустым значением A (стоп, но в этом случае придётся построить проход циклов от j  к i. А поэтому понятно, что проходить список D нужно дважды: сначала от i к j, затем от j  к i. А в целом и все трижды, с учетом самого 1-го прохода)

На псевдокоде это записывается так:

for i=1 to count(A) do
for j=1 to count(B) do
if A(i,’col2’)=B(j,’col1’) then
add(C,A(i,’col1’),B(j,’col2’))
add(D,i,j)
endif

k=0
for i=1 to count(A) do
d=0
for j=1 to count(B) do
k=k+1
if D(k,‘1’)=i  then
d=1
break
endif
endfor
if d=0 then
add(C,A(i,’col1’))
endfor

k=0
for j=1 to count(B) do
d=0
for i=1 to count(A) do
k=k+1
if D(k,‘2’)=j  then
d=1
break
endif
endfor
if d=0 then
add(C,,B(i,’col2’))
endfor

Рис.24. Правильный алгоритм для задачи 14

Есть и другой способ (и он, наверно, лучше):
1)проходя двойным циклом списки А и В, запоминать те i, для которых не нашлось ни одного j, а также те j, для которых не нашлось в нём ни одного i (стоп, но ведь для вычленения 2-го опять-таки потребуется проход по циклам в противоположном порядке. Поэтому способ 1 всё-таки лучше)
2)потом, проходя по полученным спискам i и j, соответственно дописывать в список С элемент c текущим значением А и пустым значением В и элемент c текущим значением B и пустым значением A

Есть, правда, способ оптимизировать алгоритм на рис.24. А именно, объединив 2 первых двойных цикла и убрав массив D. (т.к. проще работать с предикатом A(i,’col2’)=B(j,’col1’)) Вот что получится:

for i=1 to count(A) do
d=0
for j=1 to count(B) do
if A(i,’col2’)=B(j,’col1’) then
add(C,A(i,’col1’),B(j,’col2’))
d=1
endif
if d=0 then
add(C,A(i,’col1’))
endfor

for j=1 to count(B) do
d=0
for i=1 to count(A) do
if A(i,’col2’)=B(j,’col1’) then
d=1
if d=0 then
add(C,,B(i,’col2’))
endfor

Рис.25. Правильный алгоритм №2 для задачи 14

Но в чём же дело? Почему была допущена ошибка? Неправильно написано предформальное описание? (Его роль, кстати, должна сводиться к тому, что «тянуть» к содержательной стороне задачи (предохраняя таким образом от чрезмерной (сначала) формализованности) То есть это промежучное звено между естественно-текстовым описанием и формально-текстовым.
Где же ошибка? По-видимому, я неправильно понял смысл ключевого слова LEFT OUTER JOIN. И брал я этот смысл вот отсюда:
«внешние соединения (outer joins) позволяют нам включить в результат запроса все строки из одной таблицы и соответствующие им строки из другой таблицы.»
http://articles.org.ru/cn/showdetail.php?cid=7163
А также отсюда:
«В случае с LEFT JOIN из главной таблицы будут выбраны все записи, даже если в присоединяемой таблице нет совпадений, то есть условие condition не будет учитывать присоединяемую (правую) таблицу.»
http://pionick.net/examples/mysql_join

На самом же деле смысл ключевого слова LEFT OUTER JOIN формулируется так: сначала в результирующую таблицу попадают строки, являющиеся сочетаниями данных исходных таблиц для тех строк левой таблицы, для которых нашлись соответствующие строки из правой таблицы, а потом к ним дописываются строки с данными из левой таблицы, для которых не нашлись соответствующие строки из правой таблицы.
(вот как бывает, когда учебники по языкам программирования пишут не программисты)

Начнём с задачи 12
И действительно, предформальное описание её алгоритма было таким:
1.Список С получится при обходе всех сочетаний элемента A(i)  списка А c элементом B(j) списка B
2.Значение элемента списка С(i,j) получится как сочетание значения колонки1 и значения колонки2.
3.Элемент списка С(i,j)  получится как новый элемент списка С
4.Значение колонки 1 элемента списка С(i,j)   получится как значение колонки col1 элемента A(i) 
5.Значение колонки 2 элемента списка С(i,j)   получится как значения колонки col2 элемента B(j), удовлетворяющего предикату f(i,j)
6.Предикат f(i,j) получится как A(i,’col2’)=B(j,’col1’)

Так и есть! Ошибка в предформальном описании.(и как раз по вышеизложенной причине)
На самом же деле правильно так:
1.Список С получится при обходе всех сочетаний элемента A(i)  списка А c элементом B(j) списка B
2.Значение элемента списка С(i,j) получится как альтернатива1 или альтернатива2.
3.Альтернатива1 получится как сочетание значения колонки1 и значения колонки2, удовлетворяющего предикату f(i,j)
4.Предикат f(i,j) получится как A(i,’col2’)=B(j,’col1’)
5.Альтернатива2 получится как сочетание значения колонки1, удовлетворяющего предикату d(i)
6.Предикат d(i) получится при обходе списка А по i=1.. count(A)
7. Предикат d(i) (состояние j) получится как d(i) (состояние j-1) and f(i,j)

Ну вот, когда знаешь правильный смысл слова, тогда и предформальные описания (его концепта) получаются правильные! А за ними и формальные.

Исправление ошибок в предформальных описаниях алгоритмов для задач 13 и 14 предоставляю читателю.