Máme za úkol evidovat údaje ekonomické agendy vysokoškolského pracoviště (katedry). Systém má sloužit jako pomůcka pro evidenci údajů na pracovišti a přenos údajů na fakultu. Celý problém je velmi složitý. Začíná přidělením rozpočtových částek. Přitom je třeba brát vúvahu jejich zdroj. Čerpání (a tedy i rozpočtování) údajů je třeba sledovat odděleně pro jednotlivé zdroje, mezi ně patří zejména provozní prostředky, granty a hospodářské smlouvy.
Čerpání prostředků se pak provádí různými způsoby. Jsou to především objednávky a faktury, cestovné na konference (akce), provozní záloha a další, označené jako ostatní výdaje. Informace o jednotlivých čerpáních se pro jednotlivé druhy čerpání tak výrazně liší, že pro ně byly zvoleny samostatné tabulky, viz obr. 7.
Obr. 7. Datová struktura evidence ekonomické agendy katedry
Vzniká tím však zásadní problém. Tím je celkový tisk přehledu čerpání prostředků. Kjeho provedení je potřeba přenést jednotlivé druhy čerpání do jediné tabulky. Není totiž možno tisknout do jedné tiskové sestavy údaje zněkolika tabulek. Ke složení údajů pak slouží tabulka Celková čerpání. To ovšem znamená, že údaje jsou vzásadě uloženy dvojmo.
Další problém se objevil, když byl systém nainstalován. Pro ochranu přístupu kdatům bylo nutné nainstalovat pro každé pracoviště samostatný systém. Pro sumarizaci údajů za fakultu pak bylo nutno přebírat údaje od jednotlivých pracovišť. Přenos všech údajů podle jednotlivých tabulek se záhy ukázal jako časově neúnosný. Přitom fakulta potřebuje vzásadě jen sumární data za jednotlivé druhy čerpání.
Proto byl systém doplněn další tabulkou Přehledová čerpání, která je naplňována vždy po opuštění formuláře pro editaci údajů jejich sumářem. Na obr. 8. je uvedena struktura dat fakultní aplikace. Všimněte si především tabulky QRozpočet souhrn. Ta je naplňována zdat předzpracovaných dotazem stejného názvu vjednotlivých databázích kateder.
Obr. 8. Datová struktura sumáře údajů za celou fakultu
Celý systém je navržen značně komplikovaně, proto se vsoučasné době pracuje na nové koncepci systému. Pro uložení dat je použita jedna tabulka (vycházející ze současné tabulky Celková čerpání). Záznamy jsou přitom označeny typem čerpání, čímž je zastoupeno jejich dřívější rozdělení do samostatných tabulek. Toto řešení ovšem způsobuje, že v této tabulce má záznam řadu položek, používaných jen u některých typů čerpání.
Samostatným problémem se ukázala evidence provozní zálohy. Na katedře se zapisují jednotlivé účetní doklady (paragony), které se sumarizují a podávají kvyúčtování na ekonomický odbor vysoké školy. Tam je ovšem zaúčtována sumárně, respektive rozdělená podle jednotlivých analytických účtů.
Na obr. 9 vidíme upravenou datovou strukturu evidence ekonomické agendy katedry. Všechny typy čerpání jsou uloženy vjediné tabulce NPolozky. Tvorba celkové sestavy pak nevyžaduje žádné spojování údajů. Přebírání údajů zjednotlivých kateder do fakultní databáze je pak řešen pomocí dotazu, který sumarizuje data u katedry podle požadovaného členění.
Obr. 9. Upravená datová struktura evidence ekonomické agendy katedry
Máme za úkol evidovat závodníky sportovní soutěže, rozdělovat je do jednotlivých utkání, sbírat a tisknout výsledky. Je vcelku nepodstatné o jakou soutěž se jedná. Základní požadavky jsou následující:
Počet závodníků je vždy dělitelný čtyřmi. Soutěž probíhá vněkolika kolech (max. 9). Vkaždém kole soutěží všichni soutěžící a to ve skupinách po čtyřech osobách. Přitom požadujeme, aby se vžádném kole nesetkaly dvě stejné osoby vjedné hře.
Obr. 10. Datová struktura evidence a řízení sportovní soutěže
Jednotlivé hry přitom probíhají na několika hřištích. Požadujeme vytištění pořadí her, tak jak budou po sobě následovat na jednotlivých hřištích, dále pořadí jednotlivých her podle jednotlivých kol, aby se hráči mohli orientovat vjakém pořadí hrají.
Výsledky jednotlivých kol budeme zapisovat ksoutěžícím tak, abychom byli schopni vytisknout pořadí po každém kole (a to i zpětně). Výsledky se přitom počítají jako průměr ze všech kol od prvního až po požadované.
Tato úloha není složitá zhlediska velkého rozsahu zpracovávaných dat, ale zhlediska manipulace snimi. Zjevně nejsložitější problém je rozdělení soutěžících na jednotlivé hry. jedná se o sestavení variací 4 z n bez opakování.
Je zřejmé, že jeden závodník se může setkat maximálně s n-1 soupeři a znich vždy se 3 vkaždém kole. Při podmínce celočíselnosti počtu kol lze určit maximální počet kol
kmax = (n - 1) div 3. (1)
kde je n - počet závodníků.
Odtud např. pro 12 závodníků dostaneme maximální možný počet kol 3 stím, že dva soupeři zůstávají bez kontaktu. Vlastní komplikovanost problému je způsobena požadavkem na jednoznačnost jednotlivých kol. Předpokládejme očíslování soutěžících čísly 1 ÷ 12 a ukažme si rozdělení do jednotlivých kol, viz obr. 11.
Obr. 11. Rozdělení 12 soutěžících do čtveřic
Pro rozdělení druhého kola musíme vzít zkaždé skupiny 1. kola po jednom soutěžícím. Přitom není možno vzít zjedné skupiny dva soutěžící, neboť se již setkali. Jak vidíme zobr. 11, pro 12 soutěžících není možno rozlosovat ani druhé, natož třetí kolo. Současně je zřejmé, že podle požadovaných pravidel je možno druhé kolo rozlosovat až pro 16. soutěžících. Na obr. 12 je pak ukázáno rozdělení soutěžících do prvních tří kol.
Zobr. 11 a 12 vyplývá, že doplňková podmínka způsobuje snížení maximálního počtu kol pod teoretickou hodnotu kmax. Další snížení maximálního počtu kol může být způsobeno algoritmem rozdělování soutěžících do jednotlivých her. Protože se jedná o kombinatorický problém, existuje nebezpečí, že pro větší počet soutěžících a kol bude tvorba kola trvat tak dlouho, že přesáhne reálně dostupný čas řešení, neboť složitost těchto algoritmů je úměrná n!.
Sohledem na uvedené skutečnosti budeme vést další řešení ve dvou částech:
Vytvoření algoritmu na sestavení jednotlivých kol.
Aplikace algoritmu nebo aplikace jím získaných výsledků vúloze.
Obr. 12. Rozdělení 16 soutěžících do čtveřic
Pro rozdělení soutěžících do jednotlivých kol podle dříve uvedených pravidel sestavíme nejprve generující program vjazyku PASCAL. Kuložení informací využijeme datový typ dat. Soutěžící označíme jednoznačně startovním číslem od 1 do n. Čísla soupeřů zjednotlivých kol budeme ukládat do pole souperi. Vpoli rozbeh bude uloženo pořadí soutěžícího vrámci každého kola. Algoritmus bude pracovat metodou prohledávání do hloubky. Vkaždém kole bude hledat postupně prvního soutěžícího (soutěžícího na prvním místě vprvní hře tohoto kola), pak druhého, třetího atd. skontrolou, že nedává dohromady závodníky, kteří spolu již hráli. Pokud není možno najít žádného hráče, vrací se algoritmus kjiž umístěným soutěžícím a hledá jiné. Tak vkaždém kole vyzkouší vnejhorším případě všechny kombinace hráčů a zjistí, že kolo již rozlosovat nelze. Pro úplnou dokonalost by se měl algoritmus vrátit kpředchozímu kolu a pokusit se změnit jeho rozlosování. Tato činnost již do programu nebyla vložena.
Při tvorbě algoritmu byla řešena také otázka rozmístění soutěžících na jednotlivá hřiště, resp. požadavek, aby se soutěžící pokud možno dostávali na různá hřiště. Posledním doplňkem je požadavek, aby pořadí soutěžících na hřišti (dané jejich pořadím při přiřazení na hřiště) bylo rovněž proměnné. Dodatečné požadavky byly řešeny zajištěním změny počátku seznamu soutěžících, ze kterého se soutěžící rozdělují. První rozdělovaný soutěžící se určí ze vztahu:
první = (1 + (kolo - 1) * 4) mod zavodniku (2)
program kroket;
uses crt;
const zavodniku_max =100;
type dat = record
stc : integer;
jmeno: string;
souperi : array [1..27]of integer;
rozbeh : array [1..9] of integer;
nahoda : real;
end;
var data : array [1..100] of dat;
poradi: array [1..100] of integer;
start: array [1..100] of integer;
zavodniku,
max_kol,
nejvetsi_kolo,
max_drah,
max_shoda : integer;
procedure init_data;
{##################}
var I, J: integer;
begin
for I:=1 to zavodniku_max do
with data[I] do
begin
for J:=1 to 27 do
souperi[J]:=0;
for J:=1 to 9 do
rozbeh[J]:=0;
stc:=I;
jmeno:='Jmeno';
nahoda:=RANDOM(1);
end;
end; {procedure init_data}
function losovani_kola(kolo:integer):integer;
{############################################}
var prvni, pozice, zarazka, i, j : integer;
konec : boolean;
s, kontrola_od,kontrola_do,shoda : integer;
function nejblizsi_volny:integer;
{********************************}
var p: integer;
begin
p:=pozice;
repeat
inc(p);
if p>zavodniku then
p:=1;
if p=zarazka then
konec:=true;
until (start[p]=0) or (p=pozice) or konec;
nejblizsi_volny:=p;
end; {function nejblizsi_volny}
function kontrola_shody(kdo,skym:integer):integer;
{************************************************}
var i,st: integer;
begin
st:=0;
if kolo>1 then
for i:=1 to 3+(kolo-2)*3 do
if data[kdo].souperi[i]=skym then
inc(st);
kontrola_shody:=st;
end; {function kontrola_shody}
procedure zarad_soupere(odk,dok:integer);
{***************************************}
var i,j,k:integer;
begin
for i:=odk to dok do
begin
k:=1+(kolo-1)*3;
for j:=odk to dok do
if i<>j then
begin
data[poradi[i]].souperi[k]:=poradi[j];
inc(k);
end;
end;
end; {procedure zarad_soupere}
begin {function losovani_kola}
writeln('start losovani kola ',kolo);
if kolo>nejvetsi_kolo then
max_shoda:=1;
losovani_kola:=1; {losovani probehlo uspesne}
for I:=1 to zavodniku_max do
begin
start[I]:=0;
poradi[i]:=0;
end;
prvni:=(1+(kolo-1)*4);
while prvni>zavodniku do
prvni:=prvni-zavodniku;
pozice:=prvni;
zarazka:=prvni;
i:=1;
poradi[i]:=prvni;
start[pozice]:=1;
inc(i);
while (i<zavodniku+1) and (i>1) do
begin
konec:=false;
kontrola_od:=i-((i-1) mod 4);
kontrola_do:=i;
repeat
s:=nejblizsi_volny {nejblizsi v danem kole nezarazeny
hrac pocinaje za hodnotou pozice}
shoda:=0;
for j:=kontrola_od to kontrola_do-1 do
shoda:=shoda+kontrola_shody(s,poradi[j]);
{hrac S hral s hracem cislo pozice[j]? ano=1, ne=0}
pozice:=s;
until (shoda<=max_shoda) or konec;
if konec then {nelze najit vhodny na teto urovni}
begin
dec(i);
if i>0 then begin
pozice:=poradi[i]; {vytazeni ukazovatka}
if i=1 then
zarazka:=prvni
else
zarazka:=poradi[i-1];
poradi[i]:=0; {vyrazeni z poradi}
for j:=1+(kolo-1)*3 to kolo*3 do {zruseni souperu}
data[pozice].souperi[j]:=0;
start[pozice]:=0; {zruseno zarazeni}
end;
end
else
begin
poradi[i]:=s; {hrac do poradi}
start[s]:=1; {hrac zarazen}
if i mod 4 = 0 then {ukoncena ctverice}
zarad_soupere(i-3,i); {zarazeni souperu}
inc(i); {dalsi pozice}
pozice:=s;
zarazka:=s;
end;
end;
if i<2 then {nepodarilo se vytvorit kolo}
begin
writeln;
writeln('nelze seradit kolo:',kolo:3);
losovani_kola:=0;
end
else
begin {kolo serazeno spravne}
j:=1;
for i:=1 to zavodniku do
begin
data[poradi[i]].rozbeh[kolo]:=j;
inc(j);
end;
end;
end; {procedure_losovani kola}
var f:text;
u,kl:integer;
begin {program kroket}
assign(f,'vystu16.txt'); {nazev vystupniho souboru}
rewrite(f);
init_data;
zavodniku:=16; {pocet zavodniku}
nejvetsi_kolo:=9; {max. rozlosovatelne kolo}
writeln('KROKET, zavodniku ',zavodniku);
max_kol:=(zavodniku-1) div 3;
if max_kol>9 then max_kol:=9;
max_drah:=4;
max_shoda:=0;
writeln(f,'System KROKET pro ',zavodniku,' zavodniku, max. pocet kol ',max_kol);
for kl:=1 to max_kol do
if losovani_kola(kl)=1 then
begin
writeln(f,'rozlosovani kola ',kl:2);
for u:=1 to zavodniku do
write(f,poradi[u]:3);
writeln(f);
end
else
begin
writeln(f,'nelze rozlosovat kolo ',kl:2);
kl:=max_kol;
end;
writeln(f,'Informace o zavodnicich, souperich a rozbezich');
for u:=1 to zavodniku do
with data[u] do
begin
write(f,u:3,' -> ');
for kl:=1 to max_kol*3 do
write(f,souperi[kl]:3);
write(f,' R:');
for kl:=1 to max_kol do
write(f,rozbeh[kl]:3);
writeln(f);
end;
writeln(f);
close(f);
end. {program kroket}
Program pro 16 hráčů vygeneroval následující informace o rozlosování soutěžících. Na výpisu je uvedeno pořadí hráčů vjednotlivých kolech (rozdělením do čtveřic získáme jejich umístění na jednotlivá hřiště). Dále jsou vypsány informace o soupeřích (vždy trojice soupeřů vkaždém kole) a pořadí soutěžícího vkaždém kole.
Jak vidíme pro 16 závodníků vygeneroval algoritmus plných 5 kol, což je také maximální možný počet kol. Pro vyšší počty závodníků se však rozlosované počty kol od teoretického maximálního počtu kol výrazně liší. Tabulka 1 uvádí počty rozlosovaných kol pro počty soutěžících až do 116. Pokud bylo možno rozlosovat více než 9 požadovaných kol, algoritmus se samozřejmě zastavil, neboť již byly vyčerpány paměťové prostory pro uložení informací o soupeřích a pořadí soutěžícího vkole.
System KROKET pro 16 zavodniku, max. pocet kol 5
rozlosovani kola 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
rozlosovani kola 2
5 9 13 1 2 6 10 14 15 3 7 11 12 16 4 8
rozlosovani kola 3
9 14 3 8 10 13 4 7 11 16 1 6 12 15 2 5
rozlosovani kola 4
13 2 8 11 12 14 1 7 9 15 4 6 10 16 3 5
rozlosovani kola 5
1 8 10 15 16 2 7 9 11 14 4 5 6 12 13 3
Informace o zavodnicich, souperich a rozbezich
1 -> 2 3 4 5 9 13 11 16 6 12 14 7 8 10 15 R: 1 4 11 7 1
2 -> 1 3 4 6 10 14 12 15 5 13 8 11 16 7 9 R: 2 5 15 2 6
3 -> 1 2 4 15 7 11 9 14 8 10 16 5 6 12 13 R: 3 10 3 15 16
4 -> 1 2 3 12 16 8 10 13 7 9 15 6 11 14 5 R: 4 15 7 11 11
5 -> 6 7 8 9 13 1 12 15 2 10 16 3 11 14 4 R: 5 1 16 16 12
6 -> 5 7 8 2 10 14 11 16 1 9 15 4 12 13 3 R: 6 6 12 12 13
7 -> 5 6 8 15 3 11 10 13 4 12 14 1 16 2 9 R: 7 11 8 8 7
8 -> 5 6 7 12 16 4 9 14 3 13 2 11 1 10 15 R: 8 16 4 3 2
9 -> 10 11 12 5 13 1 14 3 8 15 4 6 16 2 7 R: 9 2 1 9 8
10 -> 9 11 12 2 6 14 13 4 7 16 3 5 1 8 15 R: 10 7 5 13 3
11 -> 9 10 12 15 3 7 16 1 6 13 2 8 14 4 5 R: 11 12 9 4 9
12 -> 9 10 11 16 4 8 15 2 5 14 1 7 6 13 3 R: 12 13 13 5 14
13 -> 14 15 16 5 9 1 10 4 7 2 8 11 6 12 3 R: 13 3 6 1 15
14 -> 13 15 16 2 6 10 9 3 8 12 1 7 11 4 5 R: 14 8 2 6 10
15 -> 13 14 16 3 7 11 12 2 5 9 4 6 1 8 10 R: 15 9 14 10 4
16 -> 13 14 15 12 4 8 11 1 6 10 3 5 2 7 9 R: 16 14 10 14 5
Tabulka 1. Počty rozlosovaných kol pro různé počty soutěžících
soutěžících |
16 |
20 |
24 |
28 |
32 |
36 |
40 |
44 |
48 |
52 |
56 |
60 |
64 |
kol |
5 |
3 |
4 |
2 |
5 |
6 |
5 |
5 |
6 |
6 |
8 |
9 |
7 |
soutěžících |
68 |
72 |
76 |
80 |
84 |
88 |
92 |
96 |
100 |
104 |
108 |
112 |
116 |
kol |
9 |
9 |
9 |
8 |
9 |
6 |
9 |
9 |
9 |
9 |
9 |
9 |
9 |
Pro vyšší počty soutěžících však prudce roste doba zpracování. To se pro praktické použití nehodí. Proto byly vygenerovány tabulky obsahující údaje pro rozlosování soutěžících vzávislosti na jejich počtu. Byly nazvány KROK16, KROK20 atd. Poté, co je zadán požadavek na rozlosování, zjistí se počet soutěžících, najde požadovaná tabulka a zní použijí připravená data.
Obdobně se řeší požadavek na tvorbu sestavy pro tisk přiřazení soutěžících na hřiště. Do pomocné tabulky se postupně vygenerují záznamy podle pořadí soutěžících vprvním kole, druhém kole, atd. Každý soutěžící je tedy uložen tolikrát, kolik je kol a není problém sestavy vytisknout. Stejným způsobem se řeší požadavek na tisk pořadí. Opět se vypočtené údaje přesunou do pomocné tabulky.