Základy programování - kontrolní otázky Vyjmenujte etapy programátorské práce a stručně je charakterizujte. formulace úlohy - pochopení zadání analýza úlohy - řešitelnost, představa o řešení návrh řešení - rozklad na podproblémy a řešení sestavení algoritmu řešení - zápis algoritmu pomocí vývojových diagramů kódování programu - zápis algoritmů v programovacím jazyku odladění - testování správné funkčnosti optimalizace - vylepšování programu Co je to algoritmus? Algoritmus je konečná, uspořádaná množina úplně definovaných pravidel pro vyřešení nějakého problému. Charakterizujte strategie řešení problémů na počítačích. Řešení problémů probíhá na základě dvou základních principů: Dekompozice (metoda shora dolů) - chápe složité problémy jako kolekci jednodušších problémů Abstrakce (metoda zdola nahoru) - ignorováním detailů zjednodušíme složitý problém Jak je definován algoritmický problém? Je to problém charakterizovaný vstupními a výstupními proměnnými, vstupní a výstupní podmínkou. Co je datová abstrakce? Je to proces získání popisu reality pomocí údajů (dat). S daty lze manipulovat bez znalosti jejich vnitřní implementace. Datová abstrakce spočívá v mapování objektů reálného světa do počítačového systému. Vysvětlete vlastnosti algoritmů. konečnost (rezultativnost) - má zaručit vyřešení úlohy po konečném počtu kroků hromadnost - jedním algoritmem lze řešit celou třídu úloh stejného druhu determinovanost - algoritmus je zadaný ve formě konečného počtu jednoznačných pravidel efektivnost - na správný průběh programu nemá žádný vliv, zajišťuje pouze, aby program trval co nejkratší dobu Co jsou vývojové diagramy a k čemu slouží? Zobrazují posloupnost operací v programu, které se mají provádět v průběhu transformace vstupních dat na data výstupní. Slouží ke grafickému vyjádření algoritmu. Obsahují symboly (pro vlastní operace zpracování včetně symbolů definujících stanovený tok, který má být dodržen při zachování logických podmínek), symboly spojení (indikují tok řízení) a zvláštní symboly (pro usnadnění čtení a zápisu vývojového diagramu). Vysvětlete co je syntaxe a sémantika programovacích jazyků. Syntaxe je soubor pravidel udávající přípustné konstrukce programů. Popisuje formální strukturu programu. Definuje klíčová slova, identifikátory, čísla a další programové entity a určuje způsob, jak je lze kombinovat. Sémantika určuje logický význam jednotlivých výrazů jazyka. Co je BNF, EBNF? Metajazykové symboly. Backus Naurova Forma (BNF) se používá pro popis syntaxe a parametrů programů ovládaných z příkazového řádku. Součástí BNF jsou metajazykové symboly. EBNF (rozšíření BNF) zjednodušuje zápis, ale nezvyšuje vyjadřovací schopnosti. Co je syntaktický diagram, z čeho se skládá a k čemu slouží? Používá se pro grafický popis syntaxe jazyka. Skládá se z terminálního symbolu (znak, slovo zapsáno v kroužku nebo oválu) a nonterminálního symbolu (znak, slovo zapsáno v obdélníku). Proč je důležitá strukturalizace v programování? Aby bylo možné lépe testovat programy na chyby. Musíme se ale zaměřit na vnitřní strukturu. Co jsou jazyky nižší úrovně a jazyky vyšší úrovně. Jaký je mezi nimi rozdíl? Jazyky nižší úrovně: - strojový kód, jazyk symbolických adres - např. Assembler Jazyky vyšší úrovně: - přístup kompilační, interpretační - např. jazyk C Jazyky vyšší úrovně mají možnost vyšší úrovně abstrakce.
Jaký je rozdíl mezi kompilátorem a interpretem? Kompilátor je překladač, který přeloží celý kód ze zdrojové formy do jazyka stroje najednou, kdežto interpret (Awk, Perl) neprovádí přímý překlad do jazyka stroje. Vysvětlete von Neumannův princip počítače. Principem je řídící a aritmetická jednotka, vstupní a výstupní jednotky, paměť (data i instrukce sdílí tutéž paměť). Jaký je vztah mezi strojem, jazykem a programem? Stroj (resp. jazyk stroje), programovací jazyk a program představují tři na sobě závislé vrstvy. Každá vrstva využívá služeb vrstvy podřízené. Programovací jazyky proto představují přirozené a žádoucí rozšíření možností stroje. Vyjmenujte programovací paradigmata a stručně je charakterizujte. naivní paradigma (typické pro laiky a začátečníky) - vyznačuje se nekoncepčností a chaotičností procedurální paradigma (klasické, imperativní) - průběh výpočtu je dán sekvencí po sobě jdoucích instrukcí funkcionální paradigma - průběh výpočtu je založen na postupném aplikování funkcí objektově orientované paradigma - průběh výpočtu je určen posíláním zpráv mezi jednotlivými objekty logické paradigma - průběh výpočtu je založen na metodě unifikace a zpětného řetězení paralelní paradigma - dekompozice algoritmu na paralelní úlohy, které mohou být souběžně zpracovávány Čím je určen datový typ? Je určen názvem (logical, Boolean, int, real, float, den, pohlaví), množinou hodnot (kterých mohou nabývat konstanty, proměnné, výrazy, funkce určitého typu), množinou operací (každý operátor nebo funkce předpokládá operandy stanoveného typu a dává výsledek stanoveného typu) a množinou atributů (které vlastnosti objektů daného typu jsou programově dosažitelné). Uveďte rozdělení datových typů. (zde jsou popsané typy v Pascalu) Rozdělují se na jednoduché (real, ordinální), strukturované (pole, záznam, množina a soubor) a ukazatel. Vysvětlete použití specifikátoru typu signed a unsigned. Signed je znaménkový a unsigned je neznaménkový typ. Rozdíl je v rozsahu čísla. Jak překladač rozliší typ konstanty (literálu)? Konstanty jsou symboly, reprezentující neměnnou číselnou nebo jinou hodnotu, překladač jazyka jim přiřadí typ, který této hodnotě odpovídá. Uveďte druhy operátorů. Ekvivalence, přiřazení a transformační operátory. K čemu slouží operátor sizeof? Používá se ke zjištění, kolik prostoru zabírá konkrétní datový typ. Jak probíhá vyhodnocení výrazů? Priorita operátorů udává, v jakém pořadí se budou vyhodnocovat jednotlivé podvýrazy. Priorita všech operátorů je přesně specifikována. Pořadí vyhodnocení výrazu lze, podle potřeby, měnit pomocí závorek. Jaký je obecný formát programu v jazyce C? Skládá se ze vstupních a výstupních parametrů, jména funkce a datového typu, jehož hodnotu funkce vrací. Co je deklarace funkce, kde se uvádí? Deklarace funkce (prototyp) se uvádí před jejím použitím a před tím než je definována. Skládá se z návratového typu, jména funkce a seznamu parametrů (jsou uvedené v závorce). Ukončuje se středníkem. Co to je prototyp funkce? Používá se v hlavičkových souborech a u funkcí, které je potřeba používat dříve, než je známa jejich implementace. Co je definice funkce? Je to implementace funkce a stejně jako deklarace funkce se skládá z návratového typu, jména funkce a seznamu parametrů (jsou uvedeny v závorce), ale neukončuje se středníkem, následují složené závorky, ve kterých je seznam příkazů (jednotlivé příkazy se oddělují středníkem). Jak se definuje funkce, která nevrací hodnotu? Pokud funkci definujeme dříve než je použita, pak funkce nevrací hodnotu.
K čemu slouží parametry funkce, kde se deklarují? Parametry určují, co bude funkce vykonávat. Deklarují se za definici funkce ve složených závorkách a jednotlivé parametry se zakončují středníkem. Kde a kdy se používají argumenty funkce? Aby mohla funkce převzít argumenty, musí být deklarovány speciální proměnné pro příjem těchto argumentů. Nazývají se formální parametry funkce. Deklarují se v závorkách následujících za jménem funkce. Uveďte rozdíl mezi globální a lokální proměnnou. Globální proměnné slouží pro celý program, kdežto lokální proměnné pouze pro potřeby určitých funkcí. Co se rozumí pojmem zastínění proměnné? Pokud například lokální proměnná stejného jména jako globální proměnná zastíní ve svém rozsahu viditelnosti tuto globální proměnnou. Podobně to platí i pro lokální identifikátory ve vnořených blocích. Jaká je struktura složeného příkazu? Vzniká uzavřením více příkazů do složených závorek. Jaké jsou druhy podmíněných příkazů, uveďte jejich rozdíl. if - pokud je podmínka splněna, provede se příkaz if-else - pokud je podmínka splněna provede se příkaz, pokud není, provede se příkaz uvedený za else switch - slouží ke větvení výpočtu podle hodnoty celočíselného výrazu, tzn. že můžeme definovat libovolný počet bloků příkazů, jejichž provedení je podmíněno hodnotou výrazu Uveďte druhy cyklů a v čem se jednotlivé cykly liší? for - známe předem počet opakování, ale lze použít i jindy/jinak while - nemusí proběhnout ani 1x, neznáme předem počet opakování, ale lze použít i jindy/jinak do-while - proběhne minimálně 1x, neznáme předem počet opakování, ale lze použít i jindy/jinak Uveďte jednotlivé příkazy skoku, a kde se používají. break - při vnořování cyklů ukončí jen nejbližší cyklus, ve kterém je použit continue - vynutí si nové vyhodnocení podmínky cyklu, přeskočí se všechny příkazy mezi ním a koncem těla cyklu return - ukončí provádění funkce, která tento příkaz obsahuje, ve funkci main ukončí celý program goto - pokud nastane fatální chyba, vyskočí z hluboko zanořené části programu Co je ukazatel? Je to proměnná, která obsahuje paměťovou adresu. Jeho hodnota říká, kde je uložen nějaký objekt. Součástí deklarace ukazatele je i informace o typu dat, která jsou na získané adrese očekávána. Typ ukazatele může být odvozen z libovolného typu datového objektu (int, float, char,…), funkčního typu a z neúplného typu. Jaké jsou ukazatelové operátory a jaká je jejich funkce? referenční - vrací adresu proměnné operandu dereferenční - vrací hodnotu uloženou na adrese operandu Vysvětlete, co je nulový ukazatel a k čemu slouží. Je to prázdný ukazatel, jehož význam je nulový. Používá se k označení, že ukazatel neukazuje nikam. Charakterizujte statickou alokaci paměti. Při této alokaci je nutné znát už v době překladu velikost dat, která budou takto alokována. Data jsou pak alokována v datové oblasti programu. Skutečná alokace paměti se provádí během zavádění programu do paměti. Charakterizujte dynamickou alokaci paměti. Do prostoru zásobníku se ukládají veškeré lokální proměnné a parametry funkcí. Při každém zavolání funkce se automaticky vyhradí prostor pro lokální proměnné a parametry, takže programátor se o to nemusí vůbec starat. Tato paměť se automaticky uvolní v okamžiku ukončení funkce. Co je pole? Pole je kolekce proměnných stejného typu, které mohou být označovány společným jménem. K prvkům pole přistupujeme prostřednictvím identifikátoru pole a indexu. Jak se provede kopie jednoho pole do jiného pole? V jazyce C nelze přiřadit jedno celé pole jinému poli. Chceme-li zkopírovat hodnoty všech prvků jednoho pole do jiného pole, pak to musíme udělat samostatným kopírováním jednotlivých prvků.
Jaké jsou možnosti předávání argumentů funkcím? Rozlišujeme dva druhy předávání argumentů funkcím. Jde o předávání hodnotou a o předávání odkazem. Jejich použití se liší v tom, co se děje s argumentem při zavolání podprogramu. Jaká je výhoda použití ukazatelů místo indexování polí? Pro použití ukazatelové aritmetiky pro přístup k prvkům vícerozměrného pole se musí vypočítat pozice prvku v poli. Pro výběr prvku pomocí indexů pole to překladač dělá automaticky. Jaký je vzájemný vztah polí a ukazatelů? Při dynamické alokaci vlastně vyhradíme místo pro prvky pole a k nim pak přistupujeme pomocí ukazatele na první prvek (resp. tento ukazatel ukazuje na začátek alokované paměti). Proto můžeme i k jednotlivým prvkům přistupovat pomocí ukazatele. Např. ke třetímu prvku pole přistoupíme takto: "*(pole + 2)". Je jedno, jakého je ukazatel typu, vždy budeme přičtením jedničky ukazovat na další prvek a ne na adresu o 1 vyšší. Proč lze při deklaraci vícerozměrného pole s inicializátorem nebo jako parametru funkce vynechat nejlevější rozměr pole? Plyne to ze způsobu uložení vícerozměrných polí v paměti. Tam se (např. pro dvourozměrné pole) ukládají postupně jednotlivé řádky (paměť počítače je totiž lineární, nemůžeme si tam nacpat čtvereček). Nejlevější rozměr pole se dá dopočítat Proč nelze při deklaraci pole jako globální proměnné použít pro specifikaci jeho rozměrů proměnné? Pokud je pole deklarováno na globální úrovni, lze pro specifikaci velikosti použít výhradně konstanty zapsané pomocí literálů nebo definované pomocí klauzule #define. Lze v nějakém případě použít při deklaraci pole proměnné pro specifikaci jeho rozměrů. Pokud ano, které to jsou a proč je to v těchto případech možné? Velikost statického pole musí být známa již v době překladu. V definici pole lze použít jen přímé hodnoty nebo preprocesorové (symbolické) konstanty (např. #define POCETPRVKU 100), nikoliv konstantní proměnné (tj. při použití specifikátoru const) jejichž hodnoty nejsou při překladu známy. Existuje nějaké principiální omezení jazyka C, které mu znemožňuje automaticky hlídat meze polí? Jazyk C nekontroluje žádné meze indexů pole, toto si musí programátor ošetřit sám. K čemu slouží klíčové slovo typedef? Je určeno pro vytvoření nového označení určitého datového typu. Používá se pro zvýšení přehlednosti programu. K čemu v jazyce C slouží datový typ enum? Nazývá se výčet a slouží k definování sady pojmenovaných celočíselných konstant. Tyto konstanty lze pak použít všude, kde lze zadat celé číslo a jsou typu int. Co je datový typ struktura? Struktura je odvozený datový typ charakteristický tím, že na rozdíl od pole může obsahovat datové položky různých typů. Říkáme, že jde o heterogenní datový typ. Je následující zápis v pořádku? Proč? typedef balance float; Není, protože balance není žádný typ. Správně by to mělo být typedef float balance. Co dělají funkce fprintf() a fscanf()? Používají se pro formátovaný vstup ze souboru a formátovaný výstup do souboru. Jsou analogické k funkcím scanf(), printf() určeným pro formátovaný standardní vstup a výstup. Proč vrací funkce getc() hodnotu typu int, i když umí číst pouze osmibitové znaky? Funkce pracuje s datovým typem int, aby bylo možné detekovat konec souboru (EOF). Proč bychom se měli vyvarovat používání funkce gets()? Protože nelze omezit počet znaků načítaných ze vstupu. Pokud je na vstupu delší řádek než řetězec, který jsme alokovali, dojde k nelegálnímu zápisu do paměti (překročení rozsahu pole). Jaký je hlavní rozdíl mezi textovým a binárním souborem? V textovém souboru lze knihovními funkcemi vytvářet a rozeznávat textové řádky nezávisle na operačním systému. Binární soubor není funkcemi čtení a zápisu tímto způsobem nijak ovlivňován.
Čím se liší standardní vstup a výstup od jiných textových souborů? U standardního vstupu a výstupu jde o virtuální soubory, protože existují pouze v operační paměti a nikoliv fyzicky na disku. Jakým způsobem lze při čtení souboru detekovat jeho konec? K detekci konce souboru je určena symbolická konstanta EOF. O tom, jakým způsobem operační systém rozpozná konec souboru, rozhoduje použitý systém souborů. Kde v souboru lze nalézt znak EOF? Na konci souboru. Jak je definován rekurentní vztah? Je to funkce, která volá sama sebe, dokud není splněná nějaká ukončovací podmínka. Vysvětlete postup řešení problémů, které jsou definované rekurentním vztahem. Jestliže podmínky požadované hodnoty vyjádříme pomocí predikátu B(Y) (podmínky, které závisí na aktuální hodnotě Y), můžeme algoritmus realizující rekurentní vztah Yi+1 = F(Yi) napsat takto: 1. Y = y0 2. while (¬B(Y)) { Y=F(Y) } Co je to algoritmické schéma. Je to algoritmická konstrukce, ve které symboly proměnných, funkcí a predikátů nejsou interpretované. Jakým způsobem se dosahuje zadané přesnosti výpočtu u problémů zadaných rekurentním vztahem? Značíme ji eps. Je dána buď dosaženou hodnotou částečné sumy, nebo posledním sčítancem. Proč většinou pomocí iteračních výpočtů nedosahujeme absolutně přesných výsledků? Protože jednak jsme omezeni limity hardwaru (ani typ double nemusí být dostatečně přesný ke zobrazení absolutního výsledku) a dále také proto, že některé iterační algoritmy výsledek např. funkce pouze aproximují (tj. limitně se k němu blíží). Často se také musíme spokojit jen s přibližnou přesností, protože výpočet by jinak trval příliš dlouho. Může dojít k zacyklení iteračního výpočtu u problémů zadaných rekurentním vztahem? Pokud ano, uveďte možné příčiny. Může, například špatnou podmínkou. Co to je heuristika a k čemu se používá? Je to obecné označení pro všechna opatření, která vedou ke snížení náročnosti výpočtu a ke zvýšení efektivity. Používá se ke snížení náročnosti výpočtu, a ke zvýšení efektivity. V čem se liší rekurze a iterace? Rekurze je programovací technika, která se používá tam, kde lze tentýž postup řešení aplikovat na každou podúlohu. Musí obsahovat ukončovací podmínku. Každou rekurzi lze nahradit iterací (a naopak). Rekurze je zobecněná iterace. Podmínka ukončení se může vyskytovat v rekurzivní definici kdekoli. Iterace je cyklus, kde je sekvence příkazů vykonávaná opakovaně na základě testu podmínky. Ukončení podmínky je nezbytné, jinak by vzniknul nekonečný cyklus. Může se objevit na začátku nebo na konci cyklu. Iterace bývá efektivnější, rekurzi lze popsat průzračnějším algoritmem. Proč bývají iterační algoritmy bezpečnější než rekurzívní? Nehrozí „přetečení“ zásobníku a následná havárie programu. Rekurzivní algoritmy jsou náročnější na paměť. V čem tkví nebezpečí při používání rekurzívních algoritmů? Hrozí přetečení zásobníku (v závislosti na podmínce ukončení rekurze, počet volání funkce, atd.). Jaký je rozdíl mezi přímou a nepřímou rekurzí? Přímá rekurze - funkce A má ve svém těle opět příkaz volání funkce A nepřímá rekurze (vzájemná, zprostředkovaná) - funkce A volá B, B volá C a C volá A K čemu slouží analýza složitosti algoritmů? Je to systematické zkoumání ceny výpočtu měřené v časových jednotkách, v provedených operacích nebo v množství požadované paměti. Provádí se za účelem porovnání algoritmů a/nebo porovnání implementací nezávislých na prováděcí platformě. Složitost závisí na velikosti vstupních dat.
Jaké jsou základní typy složitosti? Maximální - určuje funkci, která je vždy větší nebo rovna skutečné složitosti, skutečná složitost se k ní zdola asymptoticky blíží, je to horní mez složitosti, složitost pro nejhorší vstup, např. řazení obráceně seřazené posloupnosti minimální - určuje funkci, která je vždy menší nebo rovna skutečné složitosti, skutečná složitost se k ní shora asymptoticky blíží, je to dolní mez složitosti, složitost pro nejlepší vstup, např. řazení již seřazené posloupnosti průměrná - očekávaná složitost pro běžný vstup - vypočteno na základě pravděpodobnosti výskytu určitých vstupních dat a odpovídajících složitostí Jakým způsobem se zjišťuje složitost algoritmů? Exaktně - k dispozici je několik aparátů (matematické stroje - Turingův stroj) neformálně - analýzou programu Jaké jsou typické řády složitosti? Konstantní, lineární, logaritmická, kvadratická, kubická a exponenciální. Jak se změní časová složitost u jednotlivých řádů složitosti, kdy velikost řešeného problému (N) zdvojnásobíme? Ο(1) - konstantní Ο(N) - lineární (když se N zdvojnásobí, délka běhu se také zdvojnásobí) Ο(log N) - logaritmická (když se N zdvojnásobí, délka běhu se zvýší o konstantu) Ο(NlogN) - když se N zdvojnásobí, délka běhu se také více než zdvojnásobí Ο(N2) - kvadratická (dvojnásobně vnořený cyklus, když se N zdvojnásobí, délka běhu vzroste 4 krát) Ο(N3) - kubická (trojnásobně vnořený cyklus, když se N zdvojnásobí, délka běhu vzroste 8 krát) Ο(2N) - exponenciální (když se N zdvojnásobí, délka běhu vzroste s druhou mocninou) Jaký je zásadní rozdíl mezi vektorem a polem? Datový typ pole má v programovacích jazycích obecnější použití nežli jen ve významu vektoru. Skutečný význam použitého pole závisí na povaze úlohy a interpretaci. Pole znaků takto například můžeme považovat za textový řetězec, pole čísel můžeme interpretovat jako obecnou posloupnost nebo v jiné úloze jako vektor popisující vztahy v N-rozměrném prostoru. Jaký je rozdíl mezi skalárním a vektorovým součinem dvou vektorů? Lze sčítat vektory různých délek? Skalární součin dá číslo, vektorový součin dá vektor. Vektory různých délek sčítat nelze. Jaká omezení klademe na vektory a matice při násobení konstantou? Žádná. K čemu slouží algoritmus nazývaný Eratostenovo síto? Vysvětlete stručně jeho princip. Eratostenovo síto slouží ke hledání prvočísel. Má dva algoritmy - jeden využívá pole a druhý množinu. Pole - zinicializujeme pole, kdy každému prvku přiřadíme jeden bit (na začátku bude mít hodnotu 1). Najdeme číslo 2, označíme násobky dvou a přiřadíme jim hodnotu bitu 0 (není prvočíslo), totéž provedeme pro násobky 3, 5, 7,… dokud není P větší než odmocnina z N. Množina - zvolíme množinu zvanou síto a naplníme ji celými čísly z intervalu 2..n/2+1. Prvky množiny reprezentují lichá čísla (obecně prvek x reprezentuje číslo 2x–1). ► Vybereme nejmenší číslo ze síta (je to prvočíslo). Vybrané číslo zahrneme do množiny prvočísel. Ze síta odstraníme toto číslo a také všechny jeho násobky. ◄ (Úkony uvedené v šipkách opakujeme tak dlouho, dokud není síto prázdné.) Jaká omezení klademe na matice při jejich sčítání a násobení? U sčítání matic je důležité, aby matice měly stejné rozměry, jinak je nelze sečíst. Pro násobení matic je nutné, aby se počet řádků první matice rovnal počtu sloupců druhé matice a počet sloupců první matice se rovnal počtu řádků druhé matice, jinak tyto matice nelze vynásobit. Která z verzí algoritmu pro reverzi řetězce (nebo pole) je efektivnější? Proč? Reverze řetězce se provádí dvěma způsoby - rekurzivně nebo pomocí cyklu. Efektivnější je to provádět pomocí cyklu, kdy se provede záměna prvního a posledního, druhého a předposledního, atd., znaku v řetězci. Protože každé vyvolání rekurzivní procedury či funkce totiž vyžaduje provedení určitých pomocných akcí (např. vymezení paměťového místa pro lokální proměnné), což prodlužuje dobu výpočtu. Uveďte klasifikaci vyhledávacích algoritmů. Ne každý vyhledávací algoritmus se hodí pro všechny typy prohledávaných dat. Klasifikace těchto algoritmů podle různých kritérií zjednoduší volbu vhodného algoritmu pro konkrétní data. Rozlišujeme klasifikaci podle místa uložení dat, principu, práce s klíči, jednorozměrné a vícerozměrné vyhledávání a složeného klíče.
Vysvětlete princip sekvenčního vyhledávání v poli (v poli se zarážkou, v seřazeném poli, v seřazeném poli se zarážkou). Principem je sekvenční procházení všech hodnot až do nalezení hledané hodnoty nebo dosažení konce dat. V poli se zarážkou - pole vytvoříme o jeden prvek delší a na konec se vloží hledaný klíč (zarážka), cyklus skončí buď až na zarážce (neúspěšné vyhledání) nebo dříve (úspěšné vyhledání). V seřazeném poli - pole je seřazené, při vkládání a rušení prvku nutno zachovat uspořádanost, do určitého počtu nových prvků je lepší přidávat na konec a neuspořádanou část projít sekvenčně; efektivnější řešení V seřazeném poli se zarážkou - kombinace předchozích dvou řešení Vysvětlete princip binárního vyhledávání. Vyhledávaný klíč se porovná s klíčem položky, která je umístěna v polovině vyhledávaného pole. Dojde-li ke shodě, končí vyhledávání úspěšně. Je-li vyhledávaný klíč menší, postupuje se porovnáváním prostředního prvku v levé polovině původního pole, je-li vyhledávaný klíč větší, v pravé polovině původního pole. Vyhledávání končí neúspěchem v případě, že prohledávaná část pole je prázdná (její levý index je větší než pravý). Co jsou tabulky s rozptýlenými položkami? Vysvětlete princip použití tabulek s rozptýlenými položkami pro vyhledávání údajů. Tabulky s přímým přístupem (Hash-table) s adresovacím klíčem jsou ideálními strukturami. Je-li známa množina všech klíčů K = {K1,... Kn}, které se budou vkládat do vyhledávací tabulky, a je-li možné nalézt jednoznačnou mapovací funkci f(Ki) = i, (i = 1,2,...,n) pro všechny prvky množiny K, je možné vytvořit tabulku s rozptýlenými položkami. Tuto tabulku tvoří pole, v němž položka s klíčem Ki bude uložena na indexu i daného pole. Vysvětlete, co znamená, když metoda řazení je: sekvenční, přirozená, stabilní, pracuje in situ. Sekvenčnost je vlastnost, která vyjadřuje, že řadící algoritmus pracuje se vstupními údaji i s datovými meziprodukty v tom pořadí v jakém jsou lineárně uspořádány v datové struktuře. Přirozenost řazení je vlastnost algoritmu, která vyjadřuje, že doba potřebná k řazení již seřazené množiny údajů je menší než doba pro seřazení náhodně uspořádané množiny a ta je menší než doba pro seřazení opačně seřazené množiny údajů. Stabilita vyjadřuje, že algoritmus zachovává relativní uspořádání duplicitních klíčů souboru se shodnými klíči. Je nutná tam, kde se vyžaduje, aby se při řazení údajů podle klíče s vyšší prioritou neporušilo pořadí údajů se shodnými klíči vyšší priority, získané předcházejícím řazením množiny podle klíčů s nižší prioritou. In situ je metoda kdy se pracuje přímo v místě uložení řazených dat a nepotřebuje se žádný (nebo jen minimální) přídavný prostor. Toto je zajímavé z hlediska prostorové složitosti. Jaká je obvyklá maximální časová složitost metod řazení? Kvadratická - O(N2). Vysvětlete princip řazení podle více klíčů K řešení vedou dva přístupy: 1. Vytvoření složené relace uspořádání, která může mít tvar funkce, ve které se budou postupně srovnávat klíče se snižující se prioritou. Dojde-li k nerovnosti u klíčů vyšší priority, je relace rozhodnuta. Jinak se postupuje k porovnání klíčů s nižší prioritou. Pomocí takové relace lze seřadit osoby podle stáří v jednom řazení. Funguje i pro nestabilní řadící metody. 2. Postupné řazení podle jednotlivých klíčů se dosáhne téhož seřazení, bude-li se postupovat v řazení od nižší priority klíče k vyšší prioritě. To znamená, že seznam osob podle stáří získáme, budeme-li daný soubor postupně řadit podle klíče DEN, pak podle klíče MESIC, a nakonec podle klíče ROK. Řadící metoda musí být stabilní! Nevýhodou je, že musí být použito víceprůchodové řešení, které je neefektivní. Vysvětlete princip řazení bez přesunu položek. Porovnají se dvě položky a dojde k výměně dvou položek. Proč je řadící metoda selection-sort nestabilní? Vysvětlete metodu řazení založenou na principu přímého výběru (Straight selection-sort). Uveďte její vlastnosti. Pole je rozděleno na seřazenou část a neseřazenou část. V neseřazené části se nalezne minimum a vymění se s prvkem bezprostředně následujícím za seřazenou částí a tento prvek se do ní zahrne. Toto opakujeme tak dlouho, dokud neseřazená část obsahuje více než jeden prvek. Jinak algoritmus končí. Vysvětlete metodu bublinového řazení (Bubble-sort). Uveďte její vlastnosti. Posloupnost rozdělíme na dvě části, seřazenou a neseřazenou. Seřazená část je prázdná. Postupně porovnáme všechny sousední prvky v neseřazené části, a pokud nejsou v požadovaném pořadí, prohodíme je. Toto opakujeme tak dlouho, dokud neseřazená část obsahuje více než jeden prvek. Jinak algoritmus končí.
Vysvětlete metodu řazení založenou na principu vkládání (Insert-sort). Uveďte její vlastnosti. Pole je rozděleno na seřazenou a neseřazenou část. V seřazené části se nalezne pozice, na kterou přijde vložit první prvek z neseřazené části a od této pozice až do konce seřazené části se prvky odsunou. Toto opakujeme tak dlouho, dokud neseřazená část obsahuje nějaký prvek. Jinak algoritmus končí. Jaké jsou základní výhody a nevýhody dynamických datových struktur? Výhodou okamžitý přístup k libovolnému prvku přes index a nevýhodou je pevná velikost. Popište princip abstraktního datového typu seznam. Uveďte příklady reálného využití. Seznam je zadán ukazatelem na první/poslední prvek. Aktuální stav seznamu je zpravidla určen ukazatelem na prvek, se kterým se právě pracuje (aktivní prvek, vybraný prvek). Lineární seznam se v praxi používá spíše jako pomocná datová struktura (např. koncept indexsekvenčního pole). Pokud potřebujeme přístup doprostřed seznamu, je nalistování požadovaného prvku velmi časově náročná operace. Popište princip abstraktního datového typu zásobník. Uveďte příklady reálného využití. Jsou zde definovány dvě základní operace - push (uloží nový prvek na vrchol zásobníku) a pop (odebere prvek z vrcholu zásobníku a vrátí jeho hodnotu). Této struktuře se někdy říká LIFO (Last In, First Out). Princip použití je, že prvek, který jsme vložili na vrchol jako poslední, bude při výběru pomocí operace Pop zpracován jako první. Tato struktura se tedy hodí na zpracování dat, které potřebujeme zpracovávat v opačném pořadí, než jsme je načetli. Hlavní oblastí využití této struktury jsou iterační algoritmy nahrazující rekurzi. Popište princip abstraktního datového typu fronta. Uveďte příklady reálného využití. Fronta má svůj počátek i konec. Operace, které se nad frontou provádějí, jsou vložení prvku na konec fronty (odpovídá počátečnímu prvku seznamu) a výběr prvku ze začátku fronty (odpovídá koncovému prvku seznamu). Této struktuře se říká FIFO (First In, First Out), tedy prvek, který jsme vložili do fronty jako první, bude z fronty také jako první vybrán. Tato struktura se tedy hodí pro úlohy, kde potřebujeme zachovat pořadí příchozích prvků. Typickou příkladem použití fronty je program, který zpracovává data v pořadí, v jakém přicházejí, ale není schopen je zpracovat dostatečně rychle. Ukládáním takovýchto dat do fronty zajistíme plynulé zpracovávání. Popište princip abstraktního datového typu hashovací tabulka. Uveďte příklady reálného využití. Hashovaní tabulka je hybridní datovou strukturou vytvořenou kombinací pole a spojového seznamu. Hlavním použitím hashovací tabulky je ukládání dat, která jdou vyhledávat podle klíče. Všude, kde jsou klasické způsoby vyhledávání nevhodné (pomalé, různá doba vyhledání pro různá data, atd.), používají se hashovací tabulky. Data v nich nejsou seřazena podle klíčů, ale jejich umístění je dáno hashovací funkcí. To je funkce, která poměrně rychlým výpočtem určí z hodnoty klíče index hledaného prvku v tabulce. Tato struktura najde využití především u databází, ale také u některých souborových systémů (např. na pevném disku počítače). Popište princip abstraktního datového typu strom. Uveďte příklady reálného využití. Strom je nelineární struktura. Prvek stromu (uzel) je v podstatě shodný s prvkem obousměrně vázaného seznamu. Ukazatele odkazují na levý a pravý podstrom. U stromu rozlišujeme dva významné typy prvků kořenový prvek „root“ (prvek, z něhož se lze dostat ke kterémukoli jinému prvku stromu) a listy (koncové prvky, které neobsahují žádný podstrom). Pokud má každý prvek pouze dva podstromy, mluvíme o binárním stromu, pokud jich má více, mluvíme obecně o n-árních stromech. Operace nad stromem jako je vkládání nebo rušení prvku jsou složitější než u seznamu, protože strom je potřeba udržovat v konzistentním stavu. Využití je například jako překladače počítačových jazyků a různé analyzátory zdrojového kódu. Co je to invariant algoritmu? Lze se s ním setkat při programování v jazyce C? Pokud ano, k čemu se využívá? V jazyce C se s ním setkat lze. Invariant je tvrzení, které musí být správné vždy, když program prochází kontrolním bodem, i v cyklu. Tato tvrzení zůstávají v platnosti bez ohledu na to, kolikrát byly dosaženy. Rozlišujeme dva významné invarianty - vstupní invariant (specifikace množiny vstupů I) a výstupní invariant (výstup vyhovuje R). Nalezení invariantů je dostatečným důkazem částečné správnosti. Jaký je rozdíl mezi syntaktickou a sémantickou chybou v programu? Syntaktické chyby jsou chyby, které se projeví při překladu programu, kdežto sémantické chyby se projeví až při běhu programu jeho chybnou funkcí nebo havárií. Co to je instrumentace programu? Je to doplnění zejména kontrolních tisků. Instrumentace programů je vhodná zejména tehdy, jestliže není k dispozici vhodný ladící program, resp. při ověřování programu provozem. K čemu slouží v jazyce C makro assert? Toto makro používáme pouze ve fázi testování programu. Pokud v této fázi dojde k chybě, makro assert program ukončí a na výstup vypíše, na kterém řádku došlo k porušení testovací podmínky.
Co to je verifikace a k čemu se používá? Je to proces formálního dokazování toho, že počítačový program dělá přesně to, co je uvedeno ve specifikaci programu, která udává co má program realizovat. Verifikace programu se zabývá podáním formálního důkazu správnosti algoritmu a skládá se z důkazu konečnosti a důkazu zachování invariantů. Jaký je rozdíl mezi částečnou a úplnou správností algoritmu? Stručně popište. Částečná správnost - jestliže X ∈ I , pak skončí-li algoritmus, je výsledek vždy správný, znamená to, že algoritmus nemusí skončit na všech korektních vstupech v reálném čase. Úplná správnost - jestliže je algoritmus částečně správný a skončí pro libovolné X ∈ I , pak je úplně správný. Co je Hornerovo schéma? Vysvětlete princip implementace funkce pro výpočet hodnoty polynomu pomocí Hornerova schématu. Je to efektivní algoritmus snižující na minimum počet násobení. Polynom stupně N tak může být vyhodnocen jen užitím N-1 operací násobení a N operací sčítání. Hornerův algoritmus je přímý, optimální, lineární algoritmus založený na využití závorek. Vysvětlete algoritmus pro hledání kořene rovnice metodou půlení intervalu. Polohu kořene zjišťujeme rozpůlením intervalu
a zjištěním, ve které části kořen leží. Zmenšený interval, v němž leží kořen, lze dále rozpůlit a tak zvyšovat přesnost výpočtu. Střed posledního sestrojeného intervalu lze považovat za aproximaci kořene řešené rovnice. Z tohoto postupu je patrné, že čím více kroků provedeme, tím přesnější dostaneme výsledek. Vysvětlete algoritmus pro výpočet integrálu obdélníkovou metodou. Rozdělíme danou plochu na obdélníky, kde n je počet dílčích intervalů a n+1 značí počet souřadnic x v intervalu . Vysvětlete algoritmus pro výpočet integrálu lichoběžníkovou metodou. Přesnější integraci funkce f(x) získáme použitím lichoběžníků, kterými aproximujeme danou funkci. Vysvětlete algoritmus pro výpočet integrálu Simpsonovou metodou. Při konstantní hodnotě šířky dílčích intervalů se velmi často kvůli přesnosti používá Simpsonova metoda, při které je nezbytné dodržet podmínku, že počet dílčích intervalů musí být sudé číslo. Při této metodě se vždy tři sousední body na křivce f(x) aproximují vhodnou parabolou. Charakterizujte modulární technologii výstavby programů. Modularita je vyšší stupeň strukturovaného programování. Významně podporuje dekompozici řešení problému. Modul tvoří samostatnou ucelenou jednotku, kterou lze samostatně kompilovat a opakovaně využívat. Účelem je zvýšení srozumitelnosti, spolehlivosti, udržovatelnosti, modifikovatelnosti a uplatnění principu skládání programových systémů z menších částí (stavebnice). Umožňuje spolupráci více programátorů na velkých projektech. Vhodně navržené moduly lze použít opakovaně v mnoha programech. Výsledkem jsou nižší výrobní a provozní náklady programů. Co je programový modul a z čeho se skládá? Programový modul obsahuje funkce, datové typy, konstanty a proměnné. Je to úsek programu, který je uložen v souboru a v okamžiku sestavování celého programu jej lze již velmi snadno a rychle připojit k výslednému kódu. Při opravách zdrojových textů stačí přeložit pouze ten modul, v němž došlo ke změnám, a celý program pouze znovu sestavit. Jakým způsobem podporuje modulární výstavbu programů jazyk C? Jazyk C podporuje modulární výstavbu programů formou vytváření zdrojových (*.c) a hlavičkových (*.h) souborů. Zdrojové soubory obsahují implementace veřejných a privátních funkcí a definice globálních proměnných. V hlavičkovém souboru nesmí být žádné definice (typu vymezení paměti pro proměnné, definice funkcí nebo inicializace sdílených proměnných). Jaký je doporučený obsah hlavičkových souborů? Dokumentační část, definice symbolických konstant (symbolické konstanty, o kterých se předpokládá, že budou využívány i v jiných modulech), definice maker s parametry (makra, o kterých se předpokládá, že budou využívána i v jiných modulech), definice exportovaných globálních typů (nové datové typy využitelné i v jiných modulech definujeme zásadně pomocí typedef), deklarace veřejných exportovaných globálních a konstantních proměnných příslušného (.c) modulu (jsou zde označeny jako externí - jejich definice, či inicializace musí být provedena ve zdrojovém souboru odpovídajícího modulu) a funkční prototypy exportovaných globálních funkcí příslušného zdrojového souboru (.c) modulu.
