Teoretická informatika
Semestrální práce
Pro získání zápočtu musí být vypracována semestrální práce v odpovídající kvalitě.
Zadání:
- ve dvojicích
- do 4. týdne semestru
- Úkol: Vytvořte konečný automat + program simulující jeho funkci.
- vlastní zadání
- preferované
- konečný automat z reálného světa (min. 6 stavů)
- standardní zadání:
- Automat na výdej jízdenek
- Popište automatovým modelem automat na výdej jízdenek MHD, vstupní písmena jsou mince, stavy automatu jsou hodnoty dosud vhozených mincí. Automat vydá jízdenku(y) ihned jakmile to vložené mince umožní a po jejich vložení uplyne předem zadaná doba, výstupem automatu je dvojice (počet vydaných jízdenek, počet vrácených korun). Jízdenka stojí 8 Kč.
- Jednosměrné nádraží
- Sestrojte konečný automat modelující nádraží o 3 kolejích. Vlaky jezdí pouze jedním směrem. Vstupy budou: příjezd vlaku, odjezd vlaku z 1. koleje, 2. koleje, 3. koleje. Výstupy budou obsazení nádraží a nastavení výhybek.
- Křižovatka U Práce
- Popište konečným automatem přepínání semaforů na křižovatce U Práce. Stavy automatu jsou kombinace barev semaforů. Vstupy udávají signály časovače. Intenzita provozu je v každém směru je jiná (podle zadané křižovatky - v programu bude řešena parametrem). Chodci mají k dispozici "chodecká" tlačítka. V programu není nutná real-time simulace (signály časovače mohou být realizovány např. stiskem klávesy). Při simulaci se bude zobrazovat aktuální čas.
- Stopky na digitálních hodinkách
- Navrhněte konečný automat, kterým by se mohla realizovat funkce stopek na digitálních hodinkách. Stopky je možné ovládat tlačítky A a B. Stopky musí umožňovat následující činnosti: stojí a ukazují nulový čas, běží a ukazují narůstající čas, stojí a ukazují hlavní naměřený čas, běží a ukazují mezičas, stojí a ukazují mezičas. Samozřejmě je možné je také vynulovat.
- Obousměrné nádraží
- Sestrojte konečný automat modelující nádraží o 4 kolejích. 2 koleje v každém směru. Vstupy budou: příjezd vlaku, odjezd vlaku z 1. koleje, 2. koleje, 3. koleje a 4. koleje. Výstupy budou obsazení nádraží a nastavení výhybek.
- Křižovatka u nádraží
- Popište konečným automatem přepínání semaforů na křižovatce u nádraží. Stavy automatu jsou kombinace barev semaforů. Vstupy udávají signály časovače. Intenzita provozu je v každém směru je jiná (podle zadané křižovatky - v programu bude řešena parametrem). Chodci mají k dispozici "chodecká" tlačítka. V programu není nutná real-time simulace (signály časovače mohou být realizovány např. stiskem klávesy). Při simulaci se bude zobrazovat aktuální čas.
- Výhybky
- Vytvořte konečný automat modelující následující situaci. Na jednokolejné trati se mohou setkat dva vlaky jedoucí proti sobě. Z tohoto důvodu je zde kousek trati veden po dvou kolejích (hlavní + pomocná). To znamená, že potřebujeme dvě výhybky. Pokud je na trati pouze jeden vlak, jede po hlavní trati. Vstupy budou tedy příjezdy vlaků a signál časovače. Výstupy budou kombinace výhybek.
- Baseball
- Sestrojte konečný automat modelující půlku směny baseballového utkání. Situace je následující. Útočící tým má již 2 outy. To znamená, že další out znamená konec. Vstupem bude kvalita odpalu (0 = hráč byl „vyoutován“, 1 = hráč doběhl na 1. metu (ostatní se posunuli), podobně kvalita 2 a 3, 4 = hráč doběhl na domácí metu). Stav udává obsazení met. Výstupem bude počet uhraných bodů. Zjednodušení: neuvažujeme outování při hře.
- Pohyb výtahu
- Popište konečným automatem pohyb výtahu v 6-ti podlažním domě. Stav udává patro ve kterém se výtah nachází. Vstupy jsou přivolávající tlačítka a tlačítka uvnitř výtahu. Výtah sbírá lidi cestou dolů.
- Otáčení hřídele
- Sestrojte konečně automatový Mealyho model zařízení určující smysl oráčení hřídele (otočení vlevo či vpravo).
Vstupy jsou x1 a x2 a směr posledního zaznamenaného otočení (y1). Výstupy budou y1 (směr otáčení) a y2 (pokud y2=0
nedošlo k nepřípustné kombinaci podnětu a stavu a y2=1 v opačném případě. Viz obrázek:
- Parkovací automat
- Popište automatovým modelem parkovací automat. Parkování stojí 10 Kč na půl hodiny a 15 Kč na hodinu. Osoba nejprve vhodí do automatu mince a potom stiskne tlačítko 1/2 hod nebo 1 hod. Stavy automatu jsou hodnoty dosud vhozených mincí. Automat vydá parkovací lístek, pokud to vložené mince umožní, a vrátí zbytek vhozených peněz.
- Automat na pití
- Popište konečným automatem automat na pití. Stavem rozumíme částku vhozenou do automatu. Automat vydává 3 druhy pití v hodnotách 10 Kč, 12 Kč a 15 Kč. Vstupem je vhození mince (hodnoty 1,2,5,10,20) + zvolení druhu pití. Automat vrací mince.
- Rozpoznávání vozidel
- Po stejné silnici se pohybuje nákladní auto, osobní auto a motorka konstantní rychlostí. Motorka je kratší než 2m, osobní auto je 2-4m dlouhé a nákladní auto je 4-8m dlouhé (neuvažujeme krajní hodnoty - tzn. 2, 4 a 8m). Použijeme trojici světlo-citlivých prvků vzdálených 2m. Každý z prvků vydává signál, nachází-li se před ním vozidlo. Předpokládáme, že rozteč po sobě jdoucích vozidel není menší než 8m. Úkolem zařízení je rozpoznat, které ze tři vozidel projelo kolem.
- Detekce hokejových off-sidů
- Situace je následující: dva hokejisté si přihrávají puk. Úkolem je detekovat postavení mimo hru na červené čáře a normální postavení mimo hru (na útočné modré). Stavem bude kombinace oblastí, ve které se nachází hráč s pukem a hráč bez puku. Vstupem budou přejezdy hráčů z jednotlivých pásem a přihrávka. Výstup signalizuje, zda se jedná o off-side či ne.
- Automat na sušenky
- Popište konečným automatem automat na sušenky. Stavem rozumíme částku vhozenou do automatu. Automat vydává 3 druhy sušenek v hodnotách 8 Kč, 10 Kč a 14 Kč. Vstupem je vhození mince (hodnoty 1,2,5,10,20) + zvolení druhu sušenky. Automat vrací mince.
- Tenisový zápas
- Simulujte tenisový zápas na jeden set. V případě stavu 6:6 na hry následuje tiebreak, který končí sedmým bodem. Tzn. nejdelší zápas - 7:6 (7:6).
Odevzdání:
- 13. týden semestru (v době posledního cvičení)
- dokument + program (zdrojové kódy + spustitelný soubor)
- části dokumentu
- 1. Titulní strana
- 2. Popis řešeného problému
- 3. Konečný automat
- 4. Krátký popis programu
- 5. Listing programu (jen pokud nebude program příliš dlouhý)
- 6. Závěr
Poslední změna
20. 10. 2003
Josef Steinberger