Zadání projektů pro zimní semestr:

Projekt č. 1:

První program:
Najděte algoritmus pro řešení rovnic lineárních, kvadratických a obecně rovnic třetího řádu metodou půlení intervalu (pozor, tato metoda bude uplatněna pro všechny uvedené typy rovnic bez rozlišení jejich stupně!).
Práce musí obsahovat návrh datových struktur, algoritmus řešení a zdrojový program v Borland Pascalu.

Odlaďte programy od syntaktických, sémantických a běhových chyb.

Metoda půlení intervalu:
Je dána funkce jedné proměnné f(x) na intervalu <a,b>.
Řešením rovnice f(x) = 0 jsou všechny body [x,0], tedy všechny hodnoty na ose x, které lze do rovnice dosadit. Graficky jsou to všechny body, ve kterých funkce f(x) protíná osu x na intervalu <a,b>.
Při výpočtu využíváme toho, že jestliže se obecně na intervalu <m,n> nachází lichý počet řešení (např. jedno), pak platí f(m) * f(n) < 0, protože jedna z těchto funkčních hodnot leží nad osou x (je to kladné číslo) a druhá pod osou x (je to záporné číslo).
Zadává se tedy funkce, interval a dále číslo označované jako epsilon, které představuje délku nejmenšího možného intervalu, na kterém ještě provádíme výpočet.
Samotný výpočet probíhá tak, že u zadaného intervalu vypočteme jeho délku. Jestliže je menší než epsilon (obvykle je to velmi malé číslo, např. 0.005), pak zjistíme pomocí výše uvedeného vztahu, zda se v něm nachází některé řešení a pokud ano, považujeme za toto řešení hodnotu x uprostřed intervalu (tuto hodnotu například můžeme přidat do jakéhosi pole řešení). Jestliže je délka intervalu větší než epsilon, rozpůlíme ho a na obě jeho poloviny rekurzívně uplatňujeme tentýž výpočet.

Poznámky k řešení programů projektu:
Kód vhodně rozdělujte do podprogramů (funkcí, procedur). Každý podprogram by měl sloužit jednomu určitému účelu a podle toho je také pojmenován.
Při generování náhodných čísel používáme funkci random, která předpokládá použití procedury randomize jednou na začátku kódu. Procedura randomize musí být použita opravdu pouze jednou, a to nikoliv v žádné z funkcí, ale v hlavním programu!!!
U druhého programu (zkoušení z matematiky) je vhodné dát žákovi na vědomí okamžitě, že udělal chybu a v čem ta chyba spočívá. Nestačí na konci zkoušení jen vypsat "Nalezeno xxx chyb". Na obrazovku také nevypisujeme operátor DIV, žáci ZŠ absolutně netuší, co to je. Pokud používáme celočíselné dělení, vygenerujeme takové operandy, které vždy dají celočíselný výsledek (např. vygenerujeme nejdřív druhý operand - M, pak vygenerujeme číslo, které bude ve skutečnosti výsledkem výpočtu - N a pak vypočteme M*N = V. Zobrazíme pak zadání V / M = ). Nepoužíváme také příliš velká čísla, aby bylo možné počítat zpaměti.

Projekt č. 2:

První program:
Najděte algoritmus pro řešení základních operací matic. Vytvořte demonstrační program, který bude tyto výpočty testovat.
Práce musí obsahovat návrh datových struktur, algoritmus řešení a zdrojový program v Borland Pascalu.

Odlaďte programy od syntaktických, sémantických a běhových chyb.

Metoda řešení soustavy lineárních rovnic GEM (Gaussova eliminace):
Máme soustavu lineárních rovnic o n neznámých
a_1,1 * x₁ + a_1,2 * x₂ + ... + a_1,n * x_n = b₁
a_2,1 * x₁ + a_2,2 * x₂ + ... + a_2,n * x_n = b₂
...
a_n,1 * x₁ + a_n,2 * x₂ + ... + a_n,n * x_n = b_n

Pak soustavu můžeme přepsat do maticového tvaru:
A_n,n * X = B
kde A je čtvercová matice s rozměry n x n, X a B jsou vektory o délce n prvků.
Ze základní Gaussovy metody je odvozen i postup výpočtu, který se učí již na základních školách:

• Převedeme matici A na trojúhelníkovou matici. Jestliže se na diagonále vyskytne prvek s hodnotou nula, pak vhodně přehodíme řádky, abychom na diagonále dostali nenulový prvek. Jestliže přehazujeme řádky matice A, nesmíme zapomenout udělat totéž ve vektoru B (jinak by nám vyšel špatný výsledek).
• Trojúhelníkovou matici pak řešíme od posledního řádku, kde stačí vypočíst pouze a_n,n * x_n = b_n, při výpočtu každého řádku využíváme výsledků dříve vypočtených následujících řádků, tedy při výpočtu x_i již známe hodnoty proměnných x_i+1, x_i+2, ..., x_n.

Poznámky k řešení programů projektu:
Matici reprezentujeme jako dvourozměrné pole čísel obecně s indexy [1..M, 1..N]. Program testujeme pro nižší hodnoty M a N (doporučujeme pro hodnoty mezi 3 a 5), u operací, kde matice nemusí být čtvercová, volíme pro M a N různé hodnoty (např. u sčítání matic). Větší rozměr matice znamená velkou potřebu paměti a příliš mnoho práce se zadáváním prvků matice.
Jestliže chceme pracovat s reálnými čísly, použijeme místo datového typu real raději datový typ double, výpočty jsou pak přesnější.

Příklady součinu dvou matic:









Počet sloupců první matice musí být shodný s počtem řádků druhé matice, výsledná matice má počet řádků stejný jako první matice a počet sloupců stejný jako druhá matice.

Závěrečný projekt zimního semestru:

První program:
Zpracujte třídicí a vyhledávací algoritmy.
Napište program s procedurami, které v zadaném (setříděném) poli najdou určenou hodnotu pomocí sekvenčního a binárního vyhledávání. Srovnejte rychlost obou metod.
Metody vyzkoušejte na setříděném poli o 10000 prvcích typu word (pole můžete naplnit např. pomocí funkce random - viz dále, a pak setřídit některou z metod použitou v druhém programu).

Druhý program:
Napište program s procedurami, které zadané nesetříděné pole setřídí jednotlivými metodami třídění. Srovnejte rychlost jednotlivých algoritmů, pro testování použijte na rozsáhlém nesetříděném poli prvků typu word.

Práce musí obsahovat návrh datových struktur, algoritmus řešení a zdrojové programy v Borland Pascalu.
Odlaďte programy od syntaktických, sémantických a běhových chyb.

Poznámky k řešení programů projektu: Dejte pozor, abyste netřídili již setříděné pole a aby pro všechny algoritmy byl stejný vstup (tedy aby byly do co největší míry srovnatelné), vygenerujte "vzorové" pole nazvané např. vzor, a před každým voláním jedné procedury třídění načtěte všechny prvky tohoto pole do dalšího, pracovního pole, které již budete třídit (pojmenujte ho např. p).

Naplnění pole náhodnými hodnotami (celými čísly z intervalu 0..65535, rozsah dat. typu word):

• na začátku hlavního programu zavoláme proceduru randomize, která připraví generátor náhodných čísel:
    randomize;
• v cyklu FOR načítáme náhodné hodnoty do prvků pole (jestliže je nazváno vzor):
  const
  MAX = 65535;
for i := 1 to 10000 do
  vzor[i] := random(MAX+1);  { je zde uložena náhodná hodnota z intervalu 0..MAX }

Srovnání rychlosti dvou algoritmů (procedur):
Použijte např. proceduru GetTime(var Hour, Minute, Second, Sec100: word);
Tato procedura vrátí skutečný čas, je v knihovně DOS. Postup pro třídění:

	NactiPole;	{ ze vzorového pole načte hodnoty do pracovního pole }
	GetTime(H,M,S,S100);	{ zjistí přesný čas na začátku třídění }
	t1 := ((H*60 + M)*60 + S)*100 + S100;	{ počet setin sekundy }
	...	{ zde je volána příslušná třídicí procedura }
	GetTime(H,M,S,S100);
	t2 := ((H*60 + M)*60 + S)*100 + S100;
	writeln('Třídění metodou ... trvalo ', t2 - t1, 'setin sekundy');	{ tak dlouho trvalo třídění }
	NactiPole;
	GetTime(H,M,S,S100);	{ zjistí přesný čas na začátku třídění }
	t1 := ((H*60 + M)*60 + S)*100 + S100;	{ počet setin sekundy }
	...	{ zde je volána příslušná třídicí procedura }
	GetTime(H,M,S,S100);
	t2 := ((H*60 + M)*60 + S)*100 + S100;
	writeln('Třídění metodou ... trvalo ', t2 - t1, 'setin sekundy');	{ tak dlouho trvalo třídění }
	atd.