Povinné úlohy k zápočtu I065

• Tyto úlohy musejí povinně vypracovat studenti ze všech cvičebních skupin.
• Obvyklým způsobem je předkládat úlohy ke kontrole přímo na cvičení (není-li uvedeno jinak). Cvičící může určit jiný způsob předávání a kontroly (např. zasílání e-mailem). I při tomto způsobu jsou studenti povinni všechny průběžně vypracovávané úlohy uchovávat pro případnou zpětnou kontrolu až do udělení zápočtu.
• Při kontrole úloh se vždy předkládá přeložitelný zdrojový tvar v jazyce Pascal. Pouze spustitelný soubor (.exe), resp. přeložený kód jednotky nestačí. Kromě toho v některých případech (např. jedná-li se o úkol vytvořit použitelnou jednotku), je součástí řešení úlohy také vytvoření demonstračního programu, který prověřuje fungování dané jednotky.
• Řešení je možné odevzdávat i ve formě programu v C/C++. V takovém případě však upozorněte cvičícího předem, že hodláte používat jiný jazyk než Pascal a nechte si to schválit.

• Korektnost algoritmů a správnost implementace
• Efektivita implementace
• Dodržení termínu odevzdání (jeden týden později -> ztráta poloviny bodů za úlohu)
• Kvalita demonstračního programu/dat

• Detaily hodnocení a počty bodů u jednotlivých úloh stanoví cvičící.
• Cvičící mohou do hodnocení úloh zahrnout další kritéria, se kterými vás předem seznámí.
• Kromě těchto povinných úloh mohou cvičící zadat další úlohy, jež se stanou také součástí hodnocení. Zadání těchto úloh je opět v režii cvičících.
• Níže uvedené názvy souborů jsou pouze orientační, řiďte se pokyny cvičících.
• Stejně tak termíny kontroly mohou být modifikovány podle pokynů cvičících.

Unita na zásobník

Napište unitu implementující ADT zásobník. Zásobník implementujte jako dynamickou datovou strukturu, unita bude obsahovat procedury (funkce) na přidání prvku do zásobníku, na odebrání prvku ze zásobníku vč. testu, zda-li lze něco odebrat, na nahlédnutí na vrchol zásobníku bez odebrání prvku,na test prázdnosti zásobníku a inicializaci zásobníku.
Procedury a funkce pomenujte nejlépe podle pokynů na přednášce.

• uložte do zasobnik.pas
• kontrola příkladu: cvičení následující po zadání

Vyhodnocení aritmetického výrazu

Uživatel zadá aritmetický výraz (jako řetězec) s použitím celých čísel, operátorů + - * / a závorek (). Program tento výraz vyhodnotí a na obrazovku napíše výsledek. Pro vyhodnocení využijte převodu z infixoveho do postfixoveho tvaru. Program bude tedy postupovat ve dvou fázích: vstupní (infixový) tvar -> interní postfixový tvar -> výsledek vyhodnocení
Algoritmus viz přednáška.

• uložte do postfix.pas
• kontrola příkladu: cvičení následující po zadání

Unita na frontu

Frontu implementujte jako dynamickou datovou strukturu, unita bude obsahovat procedury (funkce) na přidání prvku do fronty, na odebrání prvku z fronty vč. testu, zda-li lze něco odebrat, na test prázdnosti fronty a inicializaci fronty. (K této jednotce napište i demo prográmek, který bude názorně demonstrovat použití funkcí a procedur z jednotky.

• uložte do fronta.pas (demo program demof.pas)
• kontrola příkladu: cvičení následující po zadání

Unita na grafy

Napište jednotku na počítačovou reprezentaci grafů, která bude zajišťovat nejdůležitější operace nad grafy. Jednotka bude pracovat s celkem třemi typy grafů: neorientovaný graf, orientovaný graf a neorientovaný ohodnocený graf.

• reprezentace grafu pomocí matice sousednosti
• reprezentace grafu pomocí pole(seznamu) seznamů následníků
• vzájemný převod mezi oběma typy reprezentací
• inicializace prázdného grafu
• načtení grafu ze souboru
• načtení grafu z klávesnice uživatelem
• zápis grafu do souboru
• přidání/odebrání hrany mezi dvěma uzly
• zobrazení grafu v grafickém režimu
• změna barvy uzlu/hrany (pro pozdější zvýrazňování cest v grafech)

• uložte do grafy.pas
• kontrola příkladu: dva týdny po zadání

Ariadna a Minotaurus

• uložte do ariadna.pas
• kontrola příkladu: cvičení následující po zadání

Zjišťování souvislosti grafu (Warshall)

Nalezněte matici souvislosti grafu Warschallovým algoritmem. Na vstupu předpokládejte booleovskou matici sousednosti, na výstupu je rovněž booleovská matice udávající souvislost grafu.

• uložte do warsh1.pas
• kontrola příkladu: cvičení následující po zadání

Zjišťování vzdáleností od daného uzlu (Dijkstra)

Nalezněte nejkratší cesty (vzdálenosti) od zadaného uzlu ke všem ostatním použitím Dijkstrova algoritmu. Nalezené cesty vhodným způsobem vizualizujte.

• uložte do dijkstra.pas
• kontrola příkladu: cvičení následující po zadání

Prohledávání grafu do hloubky (deep-first search)

Pro daný acyklický orientovaný graf G a jeho uzel u jediný, který nemá žádného bezprostředního předchůdce v G, určete vzdálenosti z u do každého uzlu grafu G s využitím prohledávání grafu do hloubky.

• uložte do hloubka.pas
• kontrola příkladu: cvičení následující po zadání

Prohledávání grafu do šířky (breadth-first search)

Pro daný acyklický orientovaný graf jeho uzel u jediný, který nemá žádného bezprostředního předchůdce v G, určete vzdálenosti z u do každého uzlu grafu G s využitím prohledávání grafu do šířky.

• uložte do sirka.pas
• kontrola příkladu: cvičení následující po zadání

Výpočet matice vzdáleností (Warshall)

V daném nezáporně ohodnoceném grafu určete pro každou dvojici uzlů vzdálenost z uzlu i do uzlu j.

• uložte do warsh2.pas
• kontrola příkladu: cvičení následující po zadání

Obchodní cestující

Je dán seznam měst a pro každou dvojici měst je známa jejich vzdálenost. Určete nejkratší (nejlevnější) cestu, procházející všemi městy daného seznamu. Použijte metody heuristického algoritmu.

• uložte do obchod.pas
• kontrola příkladu: cvičení následující po zadání

Pět čísel

Sestavte algoritmus generujicí pětice čísel (zobrazené do kříže) z čísel 1..8, a to tak, že žádné sousední políčka v kříži neobsahují po sobě jdoucí čísla. Použijte backtracking.

• uložte do backtrk.pas
• kontrola příkladu: cvičení následující po zadání

QuickSort

Setřiďte posloupnost 20 čísel vzestupně metodou quicksortu (rekurzivně). Bližší popis zadání viz cvičení.

• uložte do quick.pas
• kontrola příkladu: cvičení následující po zadání