| meno | krúžok | 15.2. | 22.2. | 1.3. | 8.3. | 15.3. | 22.3. | 29.3. veľká noc |
5.4. | 12.4. nahr. 15.4. | 19.4. | 26.4. | 3.5. | 10.5. | 17.5. | suma 8 najlepších | DÚ | spolu (max 40) |
projekt | body za projekt |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Gallik Daniel | 1iai5 | 4 | 2.5 | 2.5 | 4.5 | 3 | 3.5 | 3.5 | 4.5 | 28 | 4 | 32 | ||||||||
| Chromík Štefan | 1iai5 | 4.5 | 4.5 | 5 | 5 | 4.5 | 5 | 28.5 | 2 | 30.5 | ||||||||||
| Jánošík Juraj | 1iai5 | 3.5 | 4.5 | 3 | 3 | 3 | 4 | 3.5 | 3.5 | 28 | 28 | |||||||||
| Jonis Marián | 1iai5 | 4 | 3.5 | 5 | 4.5 | 4 | 4.5 | 3.5 | 5 | 3 | 3.5 | 5 | 5 | 5 | 38 | 3 | 40 | Lekáreň | 10 | |
| Kovan Tomáš | 1iai5 | 3.5 | 2.5 | 4 | 2.5 | 3 | 5 | 2.5 | 2 | 5 | 4 | 29.5 | 29.5 | |||||||
| Vaberer Patrik | 1iai4 | 5 | 5 | 5 | 0 | 2.5 | 4 | 0 | 4 | 2.5 | 4.5 | 5 | 4 | 4.5 | 37 | 3.5 | 40 | Kolporteri | 4 | |
| Vetrík Tomáš | 1iai5 | 4.5 | 4 | 3 | 3.5 | 4.5 | 3.5 | 3.5 | 4.5 | 3 | 3.5 | 3.5 | 4.5 | 32.5 | 32.5 | ZOO | 4 | |||
| Vyslúžil Marián | 1iai5 | 4.5 | 4.5 | 5 | 4 | 4.5 | 4.5 | 5 | 5 | 37 | 4 | 40 | CD Predajňa | 6 |
Reprezentácia grafu obsahuje okrem reprezentácie vrcholov a hrán aj:
type
TGraf = class
... // vasa oblubena reprezentacia grafu
Komponent: array of Integer;
procedure UrobKomponenty;
end;
Metóda UrobKomponenty do poľa Komponent pre každý vrchol grafu zapíše číslo komponentu, v ktorom sa tento vrchol nachádza.
Ak sú dva vrcholy v tom istom komponente, majú v tomto poli rovnaké číslo. Ak je graf súvislý, všetky vrcholy majú hodnotu 1.
Naprogramujte funkciu grafu (function TGraf.PridajMost: Boolean;), ktorá nájde a pridá takú chýbajúcu hranu do grafu, aby klesol počet komponentov.
Ak sa to podarí, vráti true. Ak sa hrana do grafu už pridať nedá, lebo graf je súvislý, vráti false.
Naprogramujte oknovú aplikáciu, ktorá bude vizualizovať vrcholy a hrany grafu na 2d grafickej ploche. Aplikácia musí vedieť minimálne korektne vykresliť nejaký graf s väčším počtom vrcholov (desiatky), či už náhodný, alebo zo súboru. Body navyše budú za možnosť pridávať/uberať do grafu vrcholy, hrany a ohodnotenia a drag'n'drop ovládanie polohy vrcholov, prípadne iné vylepšenia. Posielajte mi skomprimovaný celý projekt.
Vytvorte mini-aplikáciu (grafickú alebo konzolovú) na porovnávanie efektivity rôznych algoritmov usporiadania.
Využite nasledovnú štruktúru procedurálnych typov (ak sa vám nezdá, môžete si ju mierne upraviť):
type TPole = array of TPrvok;
// zaznam o priebehu jedneho behu sortovacieho algoritmu
type TStatistika = record sort: TSort; N, porovnania, vymeny: integer; end;
// porovna prvky na indexoch i,j; vrati true ak su spravne usporiadane(a[i]<a[j]), false ak su v zlom poradi(a[i]>=a[j]). urcuje poradie prvkov
type TPorovnaj = function(var ai,aj: TPrvok; var stat: TStatistika): boolean;
// vymeni prvky na indexoch i,j.
type TVymen = procedure(var pole: TPole; i,j: integer; var stat: TStatistika);
// usporiadaj premennu pole, prvky pritom porovnavaj pomocou funkcie porovnaj a vymienaj pomocou funkcie vymen. statistiku vrat v premennej stat.
type TSort = function(var pole: TPole; porovnaj: TPorovnaj; vymen: TVymen; var stat: TStatistika);
// usporiadaj prvky pola niekolkymi sortami a vrat pole statistik. vsetky sorty budu zacinat z rovnakeho poradia.
function sortBenchmarkTest(var pole: TPole; sort: array of TSort): array of TStatistika;
Pre realizáciu testu využite funckiu sortBenchmarkTest a jej výsledok (počty porovnaní a výmen) prehľadne zobrazte.
Pre minimum treba implementovať aspoň 3 vami zvolené sorty, ktoré sa otestujú na tej istej náhodne generovanej postupnosti.
Funkcie na porovnanie a výmenu prvkov by mali v štatistike počítať, koľkokrát boli vykonanné.
Pre body navyše treba viac sortov, usporiadaní(zostupne, vzostupne, lexikograficky, inak...),
predgenerované zaujímavé postupnosti na testovanie a porovnanie, užívateľskú prístupnosť, a pod.
Príklad s minsortom:
procedure minsort(var pole: TPole; porovnaj: TPorovnaj; vymen: TVymen; var stat: TStatistika);
var i,j,min_j: integer;
begin
stat.N := length(pole); // pocet prvkov
for i:=low(pole) to high(pole)-1 do begin
min_j := i;
for j:=i+1 to high(pole) do
if porovnaj(pole[j],pole[min_j], stat) then // ak j-ty prvok je mensi ako min_j-ty
min_j := j;
vymen(pole, i,j, stat);
end;
end;
function vzostupne(var ai,aj: TPrvok; var stat: TStatistika): boolean;
begin
inc(stat.porovnania);
Result := (ai < aj);
end;
// ak by sme porovnavali datumy, tak napriklad takto
function datumVzostupne(var ai,aj: TPrvok; var stat: TStatistika): boolean;
begin
inc(stat.porovnania);
Result := false;
if (ai.rok < aj.rok) then Result := true
else if (ai.rok = aj.rok) then
if (ai.mesiac < aj.mesiac) then Result := true
else if (ai.mesiac = aj.mesiac) then
if (ai.den < aj.den) then Result := true
end;
// a zavola sa to cca nejako takto
var s: TStat; a: TPole;
//...
minsort(a, @vzostupne, @vymen, s);
write('pocet prvkov: ',s.N,' vymen: ',s.vymeny,' porovnani: ',s.porovnania);
function backtrack(vypisRiesenie: TSpracujRiesenie; moze: TPovolVetvu;...): TRiesenie, ktorá implementuje
všeobecnú schému backtrackového algoritmu (niekoľko ich je v prednáške). Ako parametre dostáva procedúru a funkcie a prípadne doplnkové parametre, ktoré
implementujú kľúčové body schémy pre riešenie konkrétneho problému.Naprogramujte generovanie haldy s daným počtom vrcholov. Halda (angl. heap) je binárny strom, ktorý ma minimálnu možnú hĺbku a všetky listy na najhlbšej úrovni sú "natlačené" vľavo. Na obsahu listov mi nezáleží, ale ideálne by bolo, keby boli po vypísaní inorderom usporiadané. Možno sa oplatí využiť vlastnosť, že plný binárny strom hĺbky H má 2H+1-1 vrcholov. Teda naopak, strom s N vrcholmi má hĺbku minimálne ceil(log2(N+1)-1) kde ceil vráti hornú celú časť, teda zaokrúhlenie nahor. Ľahšie sa to možno predstaví ako log2(najbližšia_väčšia_alebo_rovná_mocnina_dvojky(N+1))-1
Aritmetický binárny strom má v listoch celé čísla a vo vnútorných uzloch má operáciu, kde ľavý a pravý podstrom predstavujú operandy, ktoré treba operáciou skombinovať (sčítať, odčítať, vynásobiť, vydeliť) Ak je operadom operácia, znamenaá to, že je akoby v zátvorke. Náčrt deklarácií pre triedy je nižšie. Takýto strom môžeme zapísať v troch tvaroch, podľa toho, či je operácia pred operandami, medzi operandami, alebo za operandami:
TBinarnyStrom = class
protected
lavy,pravy: TBinarnyStrom;
public
function pravyPodstrom: TBinarnyStrom;
function lavyPodstrom: TBinarnyStrom;
function vyhodnot: integer; virtual; abstract;
end
TZnamienko = class (TBinarnyStrom)
protected
znamienko: char;
public
constructor Create(zn: char);
function vyhodnot: integer; override;
end
TCislo = class (TBinarnyStrom)
protected
hodnota: integer;
public
constructor Create(hod: integer);
function vyhodnot: integer; override;
end
function parsujPreorder(input: string): TBinarnyStrom; // + * 1 2 3 pochopi ako (1 * 2) + 3 0.5 boda
var
start, space: integer;
function parsuj: TBinarnyStrom;
begin
// preskoc medzery
while (space <= length(input)) and (_____________________) do
inc(space);
start := space; // tuto sa bude zacinat slovo
// najdi dalsiu medzeru
while (space <= length(input)) and (_____________________) do
inc(space);
// (space-start) je teraz vlastne dlzka slova
if (space-start=1) and (_____________ in ['+','-','*','/']) then begin
Result := _____________________;
Result.lavy := parsuj; // rekurzivne sparsujeme zvysok stringu - prvy operand
Result.pravy := parsuj; // a potom este dalsi zvysok - druhy operand
end
else
Result := TCislo.Create(_____________________);
end;
begin
start := 1;
space := 1;
Result := parsuj;
end;
function parsujPostorder(input: string): TBinarnyStrom; // 1 2 * 3 + pochopi ako (1 * 2) + 3 1.5 boda
// v zasade v mnohom podobne ako preorder, ale namiesto rekurzie bude mat zasobnik uzlov
// ked je nove nacitane slovo hodnota, prida novy uzol do zasobnika
// ked je nove slovo operator, vyberie a pouzije posledne dva prvky v zasobniku ako operandy operacie a do zasobnika prida takyto zlozeny uzol