1
Struktura osobn´ıho poˇ c´ıtaˇ ce
Zakreslete z´ akladn´ı sch´ema poˇc´ıtaˇce podle Johna von Neumanna. Popiˇste z´ akladn´ı strukturu osobn´ıho poˇc´ıtaˇce. Vysvˇetlete funkci a popiˇste parametry jednotliv´ ych komponent poˇc´ıtaˇce a perifern´ıch zaˇr´ızen´ı.
2
Programov´ e vybaven´ı poˇ c´ıtaˇ ce, operaˇ cn´ı syst´ emy
Popiˇste u ´ˇcel a fungov´ an´ı operaˇcn´ıho syst´emu. Struˇcnˇe se zmiˇ nte o operaˇcn´ıch syst´emech, se kter´ ymi jste se setkali bˇehem sv´eho studia. Popiˇste nˇekter´e skupiny program˚ u pro kancel´aˇrsk´e u ´ˇcely a pro nˇekter´e odborn´e u ´lohy. Zmiˇ nte se o modern´ıch metod´ ach poskytov´ an´ı software jako sluˇzby. Vysvˇetlete, co jsou to softwarov´e licence, vyjmenujte a charakterizujte nˇekter´e z nich.
3
Poˇ c´ıtaˇ cov´ e s´ıtˇ e
Vysvˇetlete, co je to poˇc´ıtaˇcov´ a s´ıt’. Popiˇste bˇeˇznˇe pouˇz´ıvan´e s´ıt’ov´e prvky a s´ıt’ov´e vrstvy, ve kter´ ych pracuj´ı. Vysvˇetlete, co je to pods´ıt’ a jak´ y je jej´ı v´ yznam pˇri smˇerov´an´ı paketu. Popiˇste a zd˚ uvodnˇete, jak a z jak´ ych prvk˚ u byste vytvoˇrili lok´aln´ı s´ıt’ pro mal´ y podnik.
4
Internet
Vysvˇetlete, co je to internet. Popiˇste zp˚ usoby pˇripojen´ı k internetu. Charakterizujte s´ıt’ov´e sluˇzby a protokoly, kter´e jsou kl´ıˇcov´e pro chod internetu. Popiˇste v´ yznam technologie NAT (network address translation) a protokolu IP verze 6 pro fungov´ an´ı internetu. Charakterizujte sluˇzby d˚ uleˇzit´e pro bˇeˇzn´eho uˇzivatele internetu, jako je Worldwide Web, e-mail, VPN atp. Vysvˇetlete principy jejich funkce.
5
ˇ ıseln´ C´ e soustavy
Popiˇste obecn´ y z´ apis cel´eho ˇc´ısla. Porovnejte z´apis ˇc´ısel v r˚ uzn´ ych ˇc´ıseln´ ych soustav´ach (des´ıtkov´ a, dvojkov´ a, osmiˇckov´ a, ˇsestn´ actkov´ a) Popiˇste form´ aty ˇc´ısel, se kter´ ymi pracuj´ı procesory a bˇeˇznˇe pouˇz´ıvan´e typy ˇc´ısel v nˇekter´ ych programovac´ıch jazyc´ıch. Zmiˇ nte se o jejich v´ yhod´ach a nev´ yhod´ach pro r˚ uzn´e u ´ˇcely. Zapiˇste ve zvolen´em programovac´ım jazyce funkci, kter´a jako vstupn´ı parametr dostane pole se z´ apisem ˇc´ısla ve dvojkov´e soustavˇe a vyp´ıˇse ho jako ˇc´ıslo zapsan´e v soustavˇe des´ıtkov´e. Pro vstupn´ı pole plat´ı, ˇze kaˇzd´ a poloˇzka pole obsahuje jednu cifru dvojkov´e soustavy.
6
Algoritmus
Popiˇste, co je to algoritmus. Vysvˇetlete pojmy v´ ypoˇcetn´ı a pamˇet’ov´a sloˇzitost. Ukaˇzte je na algoritmu nalezen´ı nejvˇetˇs´ıho spoleˇcn´eho dˇelitele dvou ˇc´ısel. Vysvˇetlete, co vyjadˇruje z´ apis sloˇzitosti pomoc´ı velk´eho O. Grafick´e zn´ azornˇen´ı algoritmu – na v´ yvojov´em diagramu algoritmu v´ ypoˇctu koˇren˚ u kvadratick´e rovnice popiˇste z´ akladn´ı symboly v´ yvojov´ ych diagram˚ u. 1
7
Procedur´ aln´ı a neprocedur´ aln´ı programov´ an´ı
Procedur´ aln´ı programov´ an´ı – uved’te pˇr´ıklady programovac´ıch jazyk˚ u pro procedur´aln´ı programov´ an´ı, popiˇste ˇclenˇen´ı zdrojov´eho k´ odu v r˚ uzn´ ych programovac´ıch jazyc´ıch. Neprocedur´ aln´ı programov´ an´ı – uved’te pˇr´ıklady programovac´ıch jazyk˚ u pro neprocedur´aln´ı programov´ an´ı, v ˇcem spoˇc´ıv´ a neprocedur´aln´ı programov´an´ı a na jak´e u ´lohy se hod´ı. Ve zvolen´em programovac´ım jazyce napiˇste funkci, kter´a navrac´ı, zda je jej´ı parametr prvoˇc´ıslo.
8
Programovac´ı jazyky
Jak dˇel´ıme programovac´ı jazyky? Uved’te r˚ uzn´e zp˚ usoby dˇelen´ı programovac´ıch jazyk˚ u a z´astupce tˇechto jednotliv´ ych skupin. Spr´ ava pamˇeti v programovac´ıch jazyc´ıch – popiˇste r˚ uzn´e pˇr´ıstupy programovac´ıch jazyk˚ u pˇri alokaci a dealokaci promˇenn´ ych. Uved’te modern´ı n´ astroje pro v´ yvoj software a spolupr´aci v´ yvoj´aˇrsk´eho t´ ymu. Ve zvolen´em programovac´ım jazyce napiˇste n´asleduj´ıc´ı hru: program vybere n´ahodn´e ˇc´ıslo od 0 do 100, u ´kolem uˇzivatele je ho uhodnout. Program oˇcek´av´a na vstupu ˇc´ısla od uˇzivatele. Poˇc´ıtaˇc uˇzivatele navad´ı slovy v´ıce“ nebo m´enˇe“, dokud uˇzivatel nevloˇz´ı programem vybran´e ˇc´ıslo. Po ” ” uhodnut´ı ˇc´ısla program vyp´ıˇse poˇcet pokus˚ u, kter´e na to uˇzivatel potˇreboval, a nab´ıdne uˇzivateli novou hru.
9
Datov´ e typy
Jednoduch´e datov´e typy – popiˇste, co je to jednoduch´ y datov´ y typ, a uved’te pˇr´ıklady v nˇekter´ ych programovac´ıch jazyc´ıch. Ve v´ ami zvolen´em jazyce uved’te oper´atory nad jednoduch´ ymi datov´ ymi typy a zmiˇ nte se o poˇrad´ı jejich vyhodnocov´ an´ı. Vysvˇetlete v´ yznam sloˇzen´ ych datov´ ych typ˚ u v jazyc´ıch, kter´e je maj´ı. Zapiˇste ve zvolen´em programovac´ım jazyce funkci, kter´a na vstupu dostane libovolnou posloupnost znak˚ u ASCII a urˇc´ı ˇcetnost v´ yskytu jednotliv´ ych p´ısmen anglick´e abecedy, bez ohledu na velikost p´ısmen (case-insensitive).
10
Halda
Popiˇste datovou struturu halda a jej´ı operace. Popiˇste algoritmus Heapsort (tˇr´ıdˇen´ı haldou) a vyj´adˇrete se o jeho ˇcasov´e sloˇzitosti. Naznaˇcte fungov´ an´ı bin´ arn´ı haldy pracuj´ıc´ı s polem a umoˇzn ˇuj´ıc´ı operaci vloˇzen´ı prvku a operaci odebr´ an´ı minim´ aln´ıho prvku. Jednu z tˇechto operac´ı zapiˇste v libovoln´em programovac´ım jazyce.
11
N´ avrhov´ e vzory
Co jsou to n´ avrhov´e vzory? Vysvˇetlete jejich v´ yznam pˇri v´ yvoji software. Vysvˇetlete princip n´ avrhov´eho vzoru Model-View-Controller. Realizujte n´ avrhov´ y vzor Singleton ve zvolen´em programovac´ım jazyce.
2
12
ˇ Sifrov´ an´ı a ovˇ eˇ rov´ an´ı dat
Vysvˇetlete obecnˇe technologii asymetrick´ ych ˇsifer a digit´aln´ıch podpis˚ u. Popiˇste nˇekter´e uplatnˇen´ı kryptografick´ ych hashovac´ıch funkc´ı. Zmiˇ nte se o bˇeˇzn´ ych zp˚ usobech ˇsifrov´an´ı m´ıstn´ıch dat a s´ıt’ov´e komunikace.
13
ˇ ıdic´ı struktury R´
Uved’te pˇr´ıklady cykl˚ u a jejich formu v nˇekter´ ych programovac´ıch jazyc´ıch. Rozved’te, v ˇcem se liˇs´ı pˇri pouˇzit´ı a za jak´ ych okolnost´ı jsou navz´ajem z´amˇenn´e. Uved’te pˇr´ıklady podm´ınˇen´ ych pˇr´ıkaz˚ u pro vˇetven´ı programu a jejich formu v nˇekter´ ych programovac´ıch jazyc´ıch. Zapiˇste ve zvolen´em programovac´ım jazyce funkci, kter´a jako vstup dostane pole cel´ ych ˇc´ısel reprezentuj´ıc´ıch platy zamˇestnanc˚ u podniku. Funkce navr´at´ı poˇcet zamˇestnanc˚ u, kteˇr´ı vydˇel´avaj´ı m´enˇe neˇz podnikov´ y pr˚ umˇer.
14
Rekurze
Popiˇste co je rekurze, jak´e jsou v´ yhody a nev´ yhody pˇri implementaci a pouˇzit´ı na ˇreˇsen´ı u ´loh. Zapiˇste ve zvolen´em programovac´ım jazyce dvˇe funkce, kter´e budou slouˇzit k v´ ypoˇctu faktori´alu zadan´eho ˇc´ısla. Prvn´ı funkce bude faktori´al poˇc´ıtat pomoc´ı rekurze a druh´a bez pouˇzit´ı rekurze. Ve zvolen´em programovac´ım jazyce napiˇste funkci, kter´a vyp´ıˇse prvn´ıch 20 ˇclen˚ u Fibonacciho posloupnosti. Pro jej´ı ˇcleny plat´ı: • F(1) = F(2) = 1, • F(n+2) = F(n) + F(n+1).
15
Backtracking
Popiˇste metodu bactrackingu na u ´loze 8 dam na ˇsachovnici (´ ukolem je rozestavit na ˇsachovnici 8x8 8 dam tak, aby se vz´ ajemnˇe neohroˇzovaly). Obecnˇe naznaˇcte programovou realizaci algoritmu vyuˇz´ıvaj´ıc´ıho backtracking. Jak´ ym zp˚ usobem je moˇzn´e zrychlovat realizaci backtrackingu?
16
Pˇ r´ım´ e metody vnitˇ rn´ıho tˇ r´ıdˇ en´ı
Na pˇr´ıkladech popiˇste principy tˇr´ıdˇen´ı metodou Bubblesort (bublinkov´e tˇr´ıdˇen´ı), tˇr´ıdˇen´ı pˇr´ım´ ym vkl´ ad´ an´ım, tˇr´ıdˇen´ı pˇr´ım´ ym v´ ybˇerem. Napiˇste program ve zvolen´em programovac´ım jazyce, kter´ y napln´ı pole o zadan´e velikosti pˇrirozen´ ymi ˇc´ısly a seˇrad´ı ho pomoc´ı Bubblesortu.
17
Sloˇ zitˇ ejˇ s´ı algoritmy tˇ r´ıdˇ en´ı
Na pˇr´ıkladech popiˇste principy tˇr´ıdˇen´ı algoritmem Quicksort (tˇr´ıdˇen´ı rozdˇelov´an´ım) a Mergesort (tˇr´ıdˇen´ı sl´ev´ an´ım). Porovnejte tyto dva algoritmy mezi sebou. Napiˇste program ve zvolen´em programovac´ım jazyce, kter´ y napln´ı pole o zadan´e velikosti pˇrirozen´ ymi ˇc´ısly menˇs´ımi neˇz tato velikost a seˇrad´ı ho metodou Bucketsort (pˇrihr´adkov´e tˇr´ıdˇen´ı).
3
18
Line´ arn´ı datov´ e struktury
Charakterizujte frontu a z´ asobn´ık a naznaˇcte jejich programovou realizaci s polem pevn´e velikosti. Popiˇste z´ akladn´ı operace pro pr´ aci s line´arn´ım spojov´ ym seznamem. Popiˇste, v ˇcem spoˇc´ıvaj´ı v´ yhody a nev´ yhody sloˇzitˇejˇs´ıch variant spojov´eho seznamu. Zapiˇste ve zvolen´em programovac´ım jazyce funkci, kter´a vytvoˇr´ı line´arn´ı spojov´ y seznam cel´ ych ˇc´ısel. Seznam bude m´ıt 10 prvk˚ u s hodnotami, kter´e funkce pˇreˇcte ze vstupu. Poˇrad´ı ˇc´ısel uloˇzen´ ych v seznamu bude stejn´e, v jak´em byla ˇc´ısla zad´ana. Nakonec vypiˇste obsah seznamu uˇzivateli.
19
Teorie graf˚ u
Popiˇste z´ akladn´ı pojmy z teorie graf˚ u. Vyjmenujte nˇekter´e zp˚ usoby implementace grafu v programu. Minim´ aln´ı kostra grafu – popiˇste na pˇr´ıkladˇe funkci algoritmu a naznaˇcte programovou realizaci.
20
Algoritmy na grafech
Floyd˚ uv-Warshall˚ uv algoritmus – popiˇste, k ˇcemu slouˇz´ı a jakou m´a ˇcasovou sloˇzitost. ˇ Dijkstr˚ uv algoritmus – popiˇste na pˇr´ıkladˇe funkci algoritmu. Reknˇ ete, jak´a je jeho ˇcasov´ a sloˇzitost a jak´e jsou jeho podm´ınky ˇreˇsitelnosti. Topologick´e tˇr´ıdˇen´ı – popiˇste na pˇr´ıkladˇe algoritmus topologick´eho tˇr´ıdˇen´ı prvk˚ u a vyj´adˇrete se o jeho ˇcasov´e sloˇzitosti.
21
Bin´ arn´ı stromy
Popiˇste dynamickou reprezentaci bin´ arn´ıho stromu a z´akladn´ı operace pˇrid´an´ı a odebr´an´ı vrcholu v bin´ arn´ım stromu a v bin´ arn´ım vyhled´avac´ım stromu. Popiˇste zp˚ usob pˇrid´ av´ an´ı prvku do vyv´aˇzen´eho bin´arn´ıho stromu. Popiˇste metody pr˚ uchodu stromem na pˇr´ıkladu vyhodnocov´an´ı v´ yraz˚ u.
22
Objektovˇ e orientovan´ e programov´ an´ı
Na pˇr´ıkladech popiˇste z´ akladn´ı koncepce objektovˇe orientovan´eho programov´an´ı – vysvˇetlete pojmy tˇr´ıda, objekt, dˇediˇcnost, zapouzdˇren´ı, polymorfismus Jste program´ atorem simulace ˇzivota dinosaur˚ u. V libovoln´em programovac´ım jazyce vytvoˇrte tˇr´ıdu Dinosaurus. Kaˇzd´ y dinosaurus m´a vlastnosti vek, vyska a metodu sezer(co). Chov´an´ı t´eto metody je upˇresnˇeno podtˇr´ıdami dinosaura: Velociraptor a Brontosaurus. Brontosaurus m´ a nav´ıc vlastnost vaha a pˇri zavol´an´ı metody sezer se v´aha zv´ yˇs´ı o jedna. Brontosaurus ˇzere pouze ˇretˇezce trava“. ” Velociraptor m´ a nav´ıc vlastnost obsah zaludku a pˇri zavol´an´ı sezer pˇrid´a do sv´eho ˇzaludku svoji obˇet’. Vytvoˇrte 10 Brontosaur˚ u a 10 Velociraptor˚ u. Vˇek a v´ yˇsku zvolte n´ahodnˇe. Vˇsechny vytvoˇren´e dinosaury vloˇzte do jednoho pole. Pole projdˇete a pˇri pr˚ uchodu polem volejte na kaˇzd´em dinosaurovi metodu sezer s vhodnou potravou. Velociraptory krmte ostatn´ımi dinosaury z tohoto pole. Vhodn´ ym zp˚ usobem zajistˇete, ˇze nevol´ate metodu sezer na seˇzran´ ych dinosaurech.
4
23
Datab´ azov´ e syst´ emy
Vysvˇetlete z´ akladn´ı pojmy a principy datab´azov´ ych syst´em˚ u (datab´aze, datab´azov´ y software a hardware, data, z´ aznam, relaˇcn´ı datab´aze, relace, prim´arn´ı kl´ıˇc). Navrhnˇete strukturu relaˇcn´ı datab´aze pro turnaje ve hˇre piˇskvorky. Mus´ı b´ yt moˇzn´e evidovat stav hrac´ı desky kaˇzd´e hry s histori´ı tah˚ u a v´ ysledky her v turnaj´ıch. Hern´ı pl´an nem´a pevnˇe danou velikost. Nejd˚ uleˇzitˇejˇs´ı je rychle zpracov´avat dotazy t´ ykaj´ıc´ı se aktu´aln´ıho stavu hry, uvaˇzte vhodn´e indexov´ an´ı a pˇr´ınosnou m´ıru redundance u ´daj˚ u.
24
Dotazy v datab´ azov´ ych syst´ emech
Vysvˇetlete pojem dotaz v datab´ azov´ ych syst´emech. Popiˇste typy dotaz˚ u v jazyce SQL (Standard Query Language). Pˇredpokl´ adejte n´ asleduj´ıc´ı tabulky se sloupci: • Knihy: ISBN, autor, titul; ˇ aˇri: jm´eno, pˇr´ıjmen´ı, adresa; • Cten´ • V´ yp˚ ujˇcky: kniha, ˇcten´ aˇr, datum p˚ ujˇcky. Strukturu tabulek upˇresnˇete a podle potˇreby doplˇ nte. Zapiˇste pomoc´ı dotazovac´ıho jazyka SQL dotazy zodpov´ıdaj´ıc´ı n´asleduj´ıc´ı ot´azky: • Kteˇr´ı lid´e maj´ı p˚ ujˇcenu Babiˇcku od Boˇzeny Nˇemcov´e? • Kteˇr´ı ˇcten´ aˇri z Prahy si p˚ ujˇcili knihu od 15. 4. 2010?
25
Z´ akladn´ı techniky vyhled´ av´ an´ı
Na pˇr´ıkladech popiˇste z´ akladn´ı techniky vyhled´av´an´ı v jednorozmˇern´em poli. ˇ Reknˇ ete, k ˇcemu se pˇri vyhled´ av´ an´ı pouˇz´ıv´a hashovac´ı tabulka. Naprogramujte ve zvolen´em jazyce vyhled´av´an´ı v utˇr´ıdˇen´em poli p˚ ulen´ım interval˚ u.
5
