WICHTERLOVO GYMNÁZIUM, OSTRAVA-PORUBA. Programování MATURITNÍ OTÁZKY

WICHTERLOVO GYMNÁZIUM, OSTRAVA-PORUBA

Programování MATURITNÍ OTÁZKY

Ostrava 2008

Tomáš Vejpustek

1

Algoritmus a jeho vlastnosti • algoritmus a jeho vlastnosti, formy zápisu algoritmu • ověřování správnosti algoritmu, krokovací tabulka • program jako forma zápisu algoritmu • základní algoritmické konstrukce – sekvence, podmínka, cyklus

Co programovací jazyky, přijdou tam taky? Algoritmus je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Může se objevovat v jakémkoli vědním odvětví (např. matematika). Heuristika je postup, který nedává přesné řešení problému, ale v krátkém čase. Přesnému řešení se jen blíží, ale obecně přesnost řešení nelze dokázat. Často se používá, z důvodu, že algoritmus neexistuje nebo je příliš složitý a tudíž časově náročný. Slovo algoritmus – zlatinštěná, špatně použitá a zkomolená podoba jména významného arabského matematika Al-Chórezmího (nebo Chwazírmího – angl. Al-Kchwarizmi) – „otce algebryÿ, podle jeho díla, které představuje indickou číselnou soustavu a počítání v ní – od toho pak latinsky „provádění aritmetiky pomocí arabských číslicÿ. Později býval používán jako označení různých matematických postupů.

1.1

Algoritmy a stroje

Algoritmus přináší dvě výhody: 1. Zobecnění problému – tedy abstrakce – neřeší jeden problém, ale obecněji typ problému, viz níže – Hromadnost. 2. Zjednodušení problému – přesný postup může vykonat i stroj. Stroje používají algoritmy z obou výše uvedených důvodů. Každý problém se dá zjednodušit na dílčí kroky, které může provést i stroj a zároveň umožňují řešit více problémů podle jednoho vzoru. Je možné zmínit něco o Turingově stroji (nekonečná páska papíru, hlava – pozor, to s tím úředníkem je zjednodušení).

1.2

Vlastnosti algoritmu

Resultativnost Algoritmus má alespoň jeden výstup – odpověď na problém, který řeší. Vede od zpracování hodnot k výstupu. Zároveň je ukončený – musí skončit v konečném počtu kroků (není jasné, jestli to není nová vlastnost). Determinovanost V každém kroku je známý následující – nestane se to, že najednou není jasné, co dělat. 1

Hromadnost Abstrakce – řeší typ problému, ne jen jeden konkrétní problém (např. součin dvou celých čísel, ne kolik je 5 · 7) Každá operace by měla být elementární.

1.3

Návrh

Proměnná je způsob reprezentace objektu, jehož hodnota se může měnit. vstupní proměnné tj. to, co algoritmus bude přijímat, bez kterých jej nelze realizovat. vstupní podmínky určují přípustné hodnoty pro vstup. výstupní proměnné tedy výsledek, řešení problému. výstupní podmínky požadovaný vztah mezi vstupními a výstupnímy proměnnými.

1.4

Zápis

1. Slovní 2. Grafický – např. vývojové diagramy 3. Matematický – vztahem mezi veličinami, soustavou rovnoc. . . 4. Počítačový program – program je zaznamenaný postup počítačových operací, který popisuje praktickou realizaci algoritmu. Někde mezi slovním a programovým zápisem je kvasilogický zápis – používá prvky vyšších programovacích jazyků.

1.5

Ověřování správnosti

Algoritmus je správný, když pro všechny vstupní proměnné splňující vstupní podmínky generuje výstupní proměnné splňující výstupní podmínky. Jedinným pravým ověřením jsou matematické důkazové metody, ostatní prostředky slouží jako heuristika. Využívá se sledování programu krok po kroku (tzv. krokování) například za pomoci testovací tabulky, která sleduje hodnoty všech vnitřních proměnných krok po krok. Běžnou praxí u komerčních programů jsou zkoužky v provozu (tzv. beta verze programů).

2

1.6

Základní konstrukce

Sekvence (tady si nejsem tak jistý) po sobě jdoucí příkazy (jako vstup, výstup, přiřazení apod.) Přiřazení, vstup, výstup. Podmínka Větvení algoritmu na základě pravdivosti výrazu (týkající se např. hodnot proměnných apod.) Cyklus Sekvence je opakována vícekrát. 1. S danným počtem opakování 2. S podmínkou na začátku/konci – pokračuje ve vykonávání sekvence na základě pravdivosti výrazu.

3

2

Strukturované programování. Programovací jazyk Pascal. • pravidla pro strukturované programování • struktura programu v jazyce Pascal • prostředky pro dodržení zásad strukturovaného programování v jazyce Pascal • lokální a globální proměnné • ladění programu, direktivy překladu

Co více k ladění? Strukturované programování označuje programovací techniku, kdy se implementovaný algoritmus rozděluje na dílčí úlohy. K implementaci v programu se používá vybraných řídících struktur. Ruší příkaz skoku (např. GOTO). Strukturované programování pracuje nejčastěji s tak zvaným top-down designem, kdy se nejprve navrhne jak má program v zásadě pracovat a problém se pak rozděluje do menších částí. Tento postup by správně měl končit až u elementálních částí. Pascal patří mezi imperativní (tj. příkazové – pomocí příkazů popisuje algoritmus) – procedurální programovací jazyky. Byl vyvinut především jako programovací jazyk na výuku strukturovaného programování (Niklaus Wirth, Curych). Základem je blok, konstrukce obsahující deklarace a příkazy. Tvoří rozsah platnosti deklarovaných objektů. Bloky se můžou vnořovat, s čímž se nejčastěji setkáváme u procedur a funkcí – základních stavebních jednotek strukturovaného programování (také podprogramy). Hlavička Definuje název bloku a jeho vztah k programu.

Co k ní?

Deklarační část Definuje významy identifikátorů použitých v bloku. Příkazová část Vlastní výpočetní část. Sekvence příkazů oddělená středníkem. Uzavřena mezi klíčová slova begin a end.

2.1

Povolené názvy

Názvy idintefikátorů, tj. název programu, typu, proměnné či konstanty, procedury a funkce. Každý název je unikátní – žádné dva různé objekty nemůžou mít stejný název. Pascal není case sensitive. • Délka menší než 63 znaků. • Bez speciálních znaků a mezery (ale číslice a podtržítko ano)

4

• Nesmí začínat číslicí • Nesmí se shodovat se žádným klíčovým slovem programu. Doporučuje se také nepoužívat českou diakritiku.

2.2

Struktura programu

program [název programu]; uses [knihovna1], [knihovna2], . . . ; const [konstanta1] = hodnota; ... type [typ] = definice typu; ... var [globální proměnná] : typ; ... podprogramy – procedury a funkce begin algoritmická konstrukce end. Identifikátory, klíčová slova a čísla od sebe musí být odděleny prázdným znakem (mezera, konec řádku, apod.). Pro lepší přehlednost zdrojového kódu je dobré vnořené bloky odsazovat (např. tabulátorem).

2.3

Platnost proměnných

Tedy místo v programovém kódu, z kterého lze k objektu přistupovat – doba přidělení paměti. Globální platí v celém programu – ve všech podprogramech. Jsou definovány v deklarační části hlavního programu. Také obecné proměnná bloku ve vyšší úrovni. Lokální platí pouze v daném bloku a blocích v něm vnořených. Definována v deklarační části daného bloku. Dynamické Platnost definována programátorem. Viz níže Je zde výjimka pro stejné názvy identifikátorů. Pokud je název globální a lokální proměnné stejný, lokální proměnná tu globální překrývá.

5

2.4

Direktivy překladu

Programovací jazyk slouží k zápisu programu a je speciálním programem – překladačem (kompilátorem) – převeden do strojového kódu počítače – – čímž je vytvořen spustitelný program. Direktivy překladu informují překladač, jak má ke zdrojovému kódu přistupovat, například co se týče vyhodnocování chyb. Nejčastější jsou přepínače {$±název}. Názvem bývá jeden znak.

6

3

Deklarace datových typů a konstant datových typů • rozdělení datových typů a jejich popis • operace nad ordinálními datovými typy • množina přípustných hodnot a množina operací • operace a funkce pro jednoduché standardní typy • datová šířka jednotlivých datových typů • konstanty s definovaným typem

Co výčtový datový typ? Název proměnných – viz Povolené názvy identifikátorů 2.1. 1. Jednoduché (a) Desetinné – číslo s pohyblivou desetinnou čárkou (b) Ordinální – celočíselné (c) boolean – pravda/nepravda 2. Strukturované – složeno z více typů (ať už jednoduchých nebo strukturovaných) (a) Pole (b) Záznam (c) Množina (d) Soubor 3. Ukazatel – obsahuje adresu v paměti

3.1

Inicializace proměnných

Než se proměnné použijí poprvé pro numerické či jiné operace, je dobré je inicializovat, tedy přiřadit jim nějakou hodnotu. Jejich hodnota po definici totiž nemusí být nulová.

7

3.2

Celočíselné typy

Jejich hodnota může být interpretována jako celé číslo. Integer Nejběžnější typ (−32768 → 32767, velikost 2 B – ±215 , znaménkový bit a nula) Nejdůležitější operace pro něj definované: • relační operace (<, >, =) • + sčítání • - odčítání nebo unární změna znaménka • * násobení • div celočíselné dělení • mod zbytek po celočíselném dělení Tyto platí i pro další celočíselné typy s výjimkou char Longint Podobný typu integer, větší rozsah (−2147483648 → 2147483647, velikost 4 B – ±231 , znaménkový bit a nula) Byte Nezáporný (0 → 255, 1 B) Vhodné použití např. jako řídící proměnná cyklu Word Větší nezáporný (0 → 65535, 2 B) Char zvláštní typ – znak ASCII (American Standard Code for Information Interchange) kódu (velikost 1 B) Přestože se dá brát jako celé číslo, mnoho operací s celými čísly pro něj Pascal neumožňuje. Existují pro něj speciální funkce: • chr() – převede číslo na znak odpovídající jemu kódu. • ord() – převede znak na odpovídající číslo • succ() – vrací násladující znak (’d’→’e’) • pred() – vrací předchozí znak (’d’→’c’)

3.3

Desetinné typy

Lépe typy s pohyblivou desetinnou čárkou. Pozor! V Pascalu se místo ní používá desetinná tečka. V paměti je tvoří dvě celá čísla (a bit pro znaménko): 1. Mantisa – tj. významové číslice (v paměti bez desetinné čárky) 2. Exponent Z toho vyplývá druhý možný zápis – exponenciální: 5.45E−3 = 0, 00545 Kromě celočíselných operací je definováno i dělení a jiné matematické funkce. Převody mezi číselnými typy:

8

• Z celočíselných na desetinná je implicitní (automatický). • Z desetinných na celočíelných nelze – existují speciální zaokrouhlovací funkce. Real Základní typ (velikost 6 B, zhruba −1039 → 1038 ) Single 4 B – 1, 5E−45 → 3, 4E38 Double 8 B – 5E−324 → 1, 7E308

3.4

Typové konstanty

Při definici konstanty můžeme definovat kromě její hodnoty i její typ. Nejedná se pak o „pravou konstantuÿ, protože ji za běhu programu můžeme měnit. const K : byte = 4;

9

4

Datový typ řetězec • popis a deklarace typu řetězec, deklarace konstanty • kompatibilita typů char a string • řetězec jako pole znaků • základní procedury a funkce pro práci s řetězci • konverze mezi datovým typem string a číselnými datovými typy

Řetězec je homogenní typ příbuzný poli – jedná se o řetězec znaků. Pascal má zabudouvanou podporu pro řetězce – datový typ string. Ten může mít až 255 znaků. Může mít definovanou i jinou, menší, velikost. Ta za běhu programu nelze měnit. var jmeno : string[50]; V paměti zabírá (velikost+1) B – nultý znak označuje jeho délku. Nezaplněné znaky řetězce jsou nedefinované znaky.

4.1

Řetězcové konstanty

Hodnota řetězcové konstanty je umístěna mezi dvě jednoduché uvozovky (’). const pozdrav[4] = ’ahoj’;

4.2

Operace s řetězci

Řetězce je možno navzájem přiřazovat – i nestejně velké. Pokud se řetězec do proměnné nevejde celý, je ořezán na danou velikost. Je možné přistupovat k jednotlivým znakům řetězce – ten se v tomto případě chová jako pole typu char. Číslování je od jedničky: var radek : string; begin radek[1] := ’A’; radek[2] := ’C’; succ(radek[2]) = ’D’; • Relační operace – podle pořadí znaků v ASCII. • Spojování řetězců – operátorem +. • Length() – vrací aktuální délku řetězce.

10

• Pos() – vrací polohu podřetězce v řetězci. • Copy(S, index, count) – vrací část řetězce – count znaků od čísla znaku index. • Concat(S1, S2, S3, . . . ) – spojuje řetězce. • Insert(Source, S, index) – vloží řetězec source do řetězce S od znaku index. • Delete(S, index, count) – vymaže count znaků od znaku index. • Str(cislo,retezec)– převede číslo na řetězec. • Val(retezec,cislo,chyba) – pokusí se převést řetězec na číslo. Pokud je převod úspěšný, chyba je 0, jinak vrací pozici prvního nepřípustného znaku.

11

5

Datový typ pole • deklarace typu pole a proměnné typu pole • deklarace konstant • načítání a výpis prvků pole

Dvě věci mám jisté jen pro turbopascal – přiřazování polí a omezení velikosti indexovacího typu Pole je strukturovaná proměnná složená z více proměnných stejného typu. Jeho prvky jsou uspořádané a přístupné přes indexování – podle pořadí v poli. Má pevně danou velikost – tedy počet prvků.

5.1

Pole v Pascalu

Deklarace: array [ typ indexu ] of datový typ typ indexu Udává nejen počet prvků, ale i způsob, kterým se k nim bude přistupovat. Pole může být indexováno pouze ordinálními (celočíselnými) typy, které bývají navíc omezeny velikostí (2 B) Pascal umožňuje: • Stanovení počtu prvků – array[5] of Indexují se od jedničky, nikoli od nuly! • Stanovení intervalu – array[1..40] of Pozor! Používají se dvě tečky místo tří. Pozn.: char je také ordinální typ, a proto array[a..z] of je možné datový typ Udává datový typ jednotlivých prvků. Může být i další pole. Práce s jednotlivým členem: var pole : array[1..4] of integer; pole[1] := 5; Pozor! Pokud chceme pole předávat proceduře nebo funkci, musíme si jej nadefinovat jako typ: type pole_t = array[1..4] of integer; procedure nacti(var pole : pole_t) ...

5.2

Pole jako konstanta

Je možné definovat pole i jako konsantu (která vlastně konstanta není – viz datové typy. Hodnoty prvků se pak zadávají v pořadí od prvního do posledního oddělené čárkami. const pole : array[1..4] of integer = (25, 30, 18, 22); 12

5.3

Operace s poli

S poli není možno provádět většinu matematických operací jako je sčítání odčítání apod. Nemohou být ani porovnávána. Přiřadit pole poli je možné pouze, pokud jsou stejného typu, tedy mají stejné indexování a stejný typ prvku. Všechny operace prováděné s jednotlivými prvky (matematické, načítání, výpis) se provádějí většinou pomocí cyklů s daným počtem opakování. Viz cykly. const N = 10; var cislo : array[1..N] of integer; begin for i := 1 to N do begin cislo[i] = i*i+i+1; end; end.

13

6

Datový typ záznam • deklarace typu záznam a proměnné typu záznam • deklarace konstant • přístupy ke složkám záznamu • způsoby uchování záznamů v operační paměti a na externím médiu

Záznam je heterogenní posloupnost skládající se z určitého počtu po sobě jdoucích položek různých typů. Položky jsou v paměti umístěné za sebou a jejich počet není omezen (pouze velikost záznamu musí být menší než 65535 B). type název = record položka : typ; ... end; K jednotlivým položkám záznamu se přistupuje tečkovou notací – s pomocí tečky a jejich názvu. záznam.položka Záznamy stejného typu lze sobě navzájem přiřazovat (pokud přiřazovaný záznam není prázdný).

6.1

Konstanty

Hodnota se konstantám přiřazuje přes jednotlivé položky: type souradnice = record X, Y : integer; end; const pocatek : souradnice = (X: 0, Y: 0);

6.2

Operace nad záznamem

Pokud provádíme více operací s prvky záznamu, můžeme s výhodou využít blokové konstrukce: with záznam do Ve vnořeném bloku nemusíme prvky záznamu adresovat skrze tečkovou notaci ale přímo jejich názvy.

14

6.3

Variantní záznam

Pascal umožňuje, aby měly dva záznamy jednoho typu různé položky (jakýsi předek dědičnosti objektů), a to v závislosti na jiném jeho prvku – přepínači : type souradnice = record case polarni : boolean of true : (X,Y : real); false : (delka, uhel : real); end; Přepínač může být pouze jeden a je vždy ordinální. Variantní část je vždy na konci. Variantní část zabírá v paměti tolik místa, kolik zabírá její paměťově nejnáročnější varianta. Kontrola přístupu ke správné variantě je na autorovi programu. Při definici konstanty je třeba nejprve uvést hodnotu přepínače a až pak hodnoty prvků ve variantní části.

6.4

Záznamy a relace

Vzhledem k možnosti prvků různého typu je možno záznam s výhodou využít pro relační databázi, kde položky jsou jednotlivé atributy.

15

7

Dynamické proměnné • popis dynamické proměnné z hlediska práce s pamětí • srovnání se statickou proměnnou • metody práce s dynamickou proměnnou • tvorba seznamů a stromů

Terminologií (lineární versus kruhové) si nejsem jist. Binární strom – „synovéÿ. Navíc, co ty regulérní výrazy? Na rozdíl od statické proměnné, o jejíž vytvoření se stará překladač sám a která je platná v jednom bloku, vytváření a ničení dynamické proměnné je řízeno autorem programu.

7.1

Ukazatele

Vytváření dynamických proměnných se děje skrze ukazatele. Ukazatel je specifický datový typ, který obsahuje adresu paměti, říkáme tedy, že ukazuje na místo v paměti. Má jednotnou velikost, 4 B. Ukazatel sám o sobě je proměnná statická a jeho správu řeší překladač. Ukazuje ale na úsek paměti. Rozlišujeme ukazatele: • typové – ukazují na konkrétní typ • univerzální (netypové) – typ pointer – kompatibilní se všemi ukazateli Ukazatele si můžeme pouze přiřazovat – a to pouze ukazatele stejného typu. Existuje významná ukazatelová konstanta – nil, která značí, že ukazatel na nic neukazuje. Pomocí operátoru @ nebo funkce addr() můžeme získat adresu statického objektu. var uk_cislo : ^integer; cislo : integer; begin uk_cislo := @cislo; ...

7.2

Alokace a uvolnit

Tedy proces vytvoření dynamické proměnné. Je úzce vázána na ukazatel, který pak na nově vytvořenou proměnnou ukazuje. Paměť se bere z místa označeného heap (halda). Jeho velikost záleží na překladači (kde lze nastavit). new(ukazatel); – přidělí paměť typu daného typem ukazatele 16

Alokací se přidělí ukazateli místo v paměti a program jej rezervuje, takže nemůže být znova přiděleno. K dynamické proměnné se přistupuje pomocí ^. var uk_int : ^integer; begin new(uk_int); uk_int^ := 6; ... Chceme-li uvolnit paměť a tím zrušit proměnnou: dispose(ukazatel); Uvolněný ukazatel má hodnotu nil. Pokusíme-li se uvolnit nenaalokovanou paměť, program skončí chybou. Poznámka: Lze použít i procedury GetMem(var P : Pointer; Velikost : word) a FreeMem(var P : Pointer; Velikost : word) – zvláště pracujeme-li s univerzálním ukazatelem.

7.3

Chyby při práci s dynamickými proměnnými

Přidělování paměti je plně v rukou autora programu. Platí ale, že to, co bylo naalokováno musí být také uvolněno. Při práci s ukazateli se v zásadě můžeme dopustit dvou chyb: 1. Ztracení ukazatele na paměť. Zůstane naalokovaná paměť, na kterou nevede žádný ukazatel, nelze tedy uvolnit. Často vede až k přetečení haldy (heap overflow ). Může se přihodit především ve dvou případech: • Alokace nové paměti na ukazatel, kterou má už paměť přidělenou má: new(uk_int); new(uk_int); – a paměť je ztracená • Přiřazení adresy ukazateli, který má přidělenou paměť: new(uk_int); uk_int := uk_int2; – a paměť je ztracená Obojí v případě, že neexistuje ještě jeden ukazatel ukazující na danou paměť. 2. Ukazatel na nealokovanou paměť. Můžeme pomocí něj měnit obsah paměti, která pak může přidělena jiné proměnné. Špatně se odhaluje. Obecně se děje, pokud dva ukazatelé ukazují na stejné místo v paměti a pak pomocí jednoho z nich paměť uvolníme: new(uk_int); uk_int2 := uk_int; 17

dispose(uk_int2); uk_int := 3; – a už máme v paměti zmatek Není také dobré předpokládat, že nově vytvořené ukazatele budou mít hodnotu nil. Viz inicializace proměnných (datové typy).

7.4

Dynamické struktury

Využívají dynamických proměnných, čímž získávají výraznou výhodu – nemají pevně danou velikost. Jejich velikost je ale omezená velikostí haldy. Implementačně je základem dynamické struktury uzel – nejčastěji typu record, který obsahuje datovou část a jeden nebo více ukazatelů na další uzly. Každá struktura má základní uzel, na něhož máme ukazatel. Na ostatní uzly je možné se z něj dostat. Pokud ztratíme adresu základního uzlu, je celá struktura ztracena a zabírá už jen paměť. 7.4.1

Spojové seznamy

Vytváří uspořádanou strukturu podobnou poli. Na rozdíl od polí je ale přístup k jednotlivým prvkům operačně a tím časově náročný, protože je potřeba projít všechny předchozí prvky. Proto se u setřízených seznamů zavádí indexování – ukazatele na některé uzly seznamu (např. pro seznam jmen ukazatele na první jména pro písmena v abecedě). Z hlediska implementace rozlišujeme seznamy na: jednosměrné – každý uzel nese ukazatel na následující uzel obousměrné – každý uzel nese ukazatel na předchozí a následující uzel lineární – jasně daný začátek a konec (nejčastěji prázdnými ukazateli) kruhové – poslední uzel ukazuje na první (a v případě obousměrného i první na poslední) Nejčastěji používané jsou jednosměrný lineární seznam pro jeho nenáročnost na paměť a obousměrný kruhový seznam pro jeho jednodušší a časově méně náročnou správu. Logicky pak rozlišujeme dva typy: Zásobník – LIFO (Last-In-First-Out) – pracuje se pouze s vrcholem, první vložený prvek je odebrán jako poslední. Potřebně operace: • vytvoření prázdného zásobníku • vložení prvku na vrchol zásobníku • odebrání prvku z vrcholu zásobníku • testování prázdnosti zásobníku

18

Fronta – FIFO (First-In-First-Out) – pracuje se začátkem i koncem, první vložený prvek je také první odebrán. Potřebné operace: • vytvoření prázdné fronty • vložení prvku na konec fronty • odebrání prvku ze začátku fronty • test prázdnosti fronty 7.4.2

Binární strom

Každý uzel má ukazatele na syny. Z kořene (tj. uzel, který není synem žádného uzlu) se dá dojít do všech listů (bez synů). Lze implementovat i pomocí pole (pro indexy jsou důležité mocniny dvou). Nejčastěji bývá používán jako binární vyhledávací strom, halda (neplést s haldou – uložištěm) nebo pro analýzu regulérních výrazů.

19

8

Příkazy (procedury) vstupu ze standardního zařízení • syntaxe příkazů read a readln • uživatelsky přívětivý vstup dat • vstup posloupnosti dat se zarážkou • vstup dat z externího souboru, standardní input soubor.

Pascal má standartně zabudovaný bufferovaný vstup. Z klávesnice se do bufferu – vyrovnávací paměti – načte určitý počet znaků a až pak se předají programu. Buffer je 128B, má tedy kapacitu 128 znaků. Naplní se při ukončení řádku, tedy když uživatel stiskne klávesu enter. Konec řádku je značen řídícími znaky chr(13) – CR (carriage return) a chr(10) – LF (line feed). CR vrací kurzor na začátek řádku, LF jej posunuje na další řádek. Do bufferu se načítá pouze CR. Další možný řídící znak je chr(26) – EOF, kterým se standartně označuje konec souboru. Vyvolat jej můžeme například kombinací kláve ctrl+Z. Buffer tedy končí znakem CR nebo EOF, proto může uživatel najednou zadat jen 127 znaků. Výše uvedená reprezentace konce řádku řádku platí jen v některých operačních systémech (DOS, Windows a další), pro přenositelnost je proto lepší pro kontrolu konce řádku použít funkci eoln.

8.1

Příkazy vstupu

Dva základní příkazy jsou read a readln. Jako parametr se uvádí proměnná, do které načítají. Těch může být i více za sebou. Načítá pouze jednoduché typy (kromě boolean) a řetězec. Podle typu proměnné program načte (ukončující znak bufferu se nikdy nezačítá): • char – jeden znak • string – znaky do řetězce dokud se nezaplní a nebo neskončí buffer • číselné typy – posloupnost znaků tvořící zápis čísla v desítkové soustavě (i se znaménkem). Může před ním být libovolný počet prázdných znaků a končí prázdným znakem nebo s bufferem. U desetinných typů je možný i exponenciální zápis. Oproti read načte readln data do danných proměnných a zbytek bufferu zahodí. Příkazu readln bez parametru se využívá jako konstrukce „pro pokračování stiskněte enterÿ.

20

8.2

Kontrola vstupu

Zatímco načítání typů char a string je relativně bezproblémové, závažný problém nastává při načítání čísel. Uživatel může zadat i jiné znaky než prázdné a číselné, což způsobí, že program skončí chybou. 1. Jednodušší možností je načtení řádku do řetězce a následné převedení na číslo pomocí val(), kdy při chybě vrácené val() uživatele požádáme o opětovné zadání čísla – viz také zadávání se zarážkou. 2. Složitější, avšak přívětivější cesta je načítání po znacích – funkcemi jednotky crt, kdy uživateli nedovolíme nečíselné znaky. Problémy zde přináší zvláště desetinná tečka (!) a exponenciální zápis desetinných čísel. Po zadání opět pracujeme s val().

8.3

Uživatelská přívětivost

Pokud se má uživateli s programem dobře pracovat, měli bychom dodržet pár zásad: • Uživatel musí vědět, co má zadat, pokud možno co nejpřesněji. Zadejte své telefonní číslo (9 číslic bez mezer): _ (to už je trochu extrém, ale znáte uživatele) • Uživatel by neměl zadávat více hodnot najednou – pouze jedna hodnota na řádek. Pro zadávání čísel je užitečná kontrola platných číslic – viz výše.

8.4

Zadávání se zarážkou

Využívá se ho tehdy, má-li vstup splňovat určité podmínky. Například má-li se jednat o číslo, popřípadě číslo z nějakého intervalu. Využívá cyklu s podmínkou na konci a nutí uživatele stále zadávat, dokud vstup nesplňuje výstupní podmínku.

8.5

Standartní vstupní soubor

Standartní vstupní soubor je textový. Je tvořen znaky rozdělenými do řádků. Ty jsou odděleny znaky CR a LF (opět závisí na OS). Soubor končí znakem EOF. Načítá se také pomocí read() a readln(), kde se před seznam proměnných umístí identifikátor souboru. Doporučuje se testovat pomocí funkce eof(identifikátor souboru), zda jsme již nedosáhli konce souboru.

21

9

Příkazy (procedury) výstupu na standardní zařízení • syntaxe příkazů write a writeln • formátovaný výstup • výstup do diskového souboru

Obrazovka je rozdělena souřadnicovou sítí na řádky a sloupce. Pozice znaku pak určuje jeho souřadnice. Operační systém si vždy pamatuje pozici, na kterou bude vložen další znak. Tato pozice je na obrazovce označena kurzorem. Standartní výstup je podřízen univerzálnímu zpracování textových souborů, a proto umožňuje jen základní výpisové operace. Pokročilejší práci s obrazovkou umožňuje jednotka crt. Základní příkazy pro výstup jsou write a writeln. Obě mají jako parametry vypisované proměnné. Procedura writeln ještě navíc nakonec vytiskne znaky pro konec řádku. Dochází ke konverzi všech proměnných na řetězec.

9.1

Formát výstupu

Jedná se hlavně o oddělení jednotlivých proměnných. Klasikou jednoho řádku je oddělení řetězcovou konstantou, především mezerou (’ ’), jde ale také vytvořit tabulku, napíšeme-li proměnné ve formátu: proměnná : délka Pokud je délka výstupní interpretace proměnné menší, doplní se zleva mezerami, pokud je větší, zachová se celá proměnná. Zvláštnosti některých typů: • boolean – vypisován jako TRUE nebo FALSE • desetinná čísla – znaménko, jedna významová číslice, desetinná tečka, zbytek významových číslic, E, exponent. Může být vypsáno jako klasické desetinné číslo: proměnná : délka : počet desetinných míst

9.2

Standartní výstupní soubor

Standartní výstupní soubor je textový. Pracuje se s ním stejně jako se standartním výstupem na obrazovku (výstup na obrazovku se řídí výstupem do textového souboru), jen u procedur write a writeln patří před seznam proměnných identifikátor souboru.

22

10

Sekvence a podmínka

• syntaxe a sémantika přiřazovacího příkazu • způsob vyhodnocení přiřazovacího příkazu překladačem • syntaxe a sémantika úplného a neúplného podmíněného příkazu, • vývojový diagram podmíněného příkazu • příkaz case • vnořené podmíněné příkazy

Má tam cenu dávat ty zbytečné konstrukce Co vnořené podmínky? 10.1

Přiřazovací příkaz

proměnná := výraz Realizuje přiřazení hodnoty proměnné. Nejdříve je vyhodnocena pravá strana a pak je přiřazena proměnné na levé straně. Typ výsledku výrazu musí být kompatibilní s proměnnou (tj. musí se na ni dát převést). Všechny proměnné ve výrazu by měly mít definovanou hodnotu!

10.2

Typ boolean

Specifikuje logické hodnoty pravda (TRUE) a nepravda (FALSE) – má velikost 1 B (menší už prostě nemůže být). Platí TRUE > FALSE. Základní operace jsou: • AND – logický součin • OR – logický součet • NOT – negace (unární) Získáváme jej také porovnáváním proměnných. Celkově ale mluvíme o výrazu, který je typu boolean, tedy jeho výsledkem je pravda nebo nepravda.

10.3

Podmínka

Podmíněný příkaz je základním větví konstrukcí. Umožňuje na základě hodnoty výrazu typu boolean provést jeden nebo druhý příkaz nebo blok. Po jeho provedení program pokračuje dále. if výraz then

23

1. Neúplná podmínka – je-li výraz pravdivý, provede se příkaz (nebo blok), je-li nepravdivý, neprovede se nic. if výraz then begin ... end; 2. Úplná podmínka – má dvě větve. Využívá klíčového slova else if výraz then begin ... end else begin ... end; Poznámka: Na konci posledního příkazu, nebo end před else se nepíše středník! Poznámka: mezi začínajícími programátory se vyskytují dvě zbytečné konstrukce, které se dají zjednodušit: 1. if vyraz = true then → if výraz then 2. if výraz then proměnná := true else proměnná := false; ↓ proměnná := výraz;

10.4

Selektor

Příkaz case větví program na základě hodnoty ordinálního (celočíselného) výrazu. case výraz of hodnota : příkaz; ... hodnotaN : příkazN else příkaz end; Část else se provede, pokud výraz nenabyde žádné z uvedených hodnot a není povinná. Na konci posledního příkazu nebo end (místo příkazu vždy může být blok) před else se opět nepíše středník.

24

11

Cyklus

• cykly s podmínkou na začátku a na konci a rozdíly mezi nimi • podmínka opuštění cyklu, tělo cyklu, parametr cyklu • načítání dat se zarážkou • záměna cyklů while a repeat • cykly se známým počtem opakování • požadavky na řídící proměnnou cyklu

Podmíněné cykly vykonávají opakovaně příkaz (nebo blok) v závislosti na hodnotě výrazu typu boolean, tedy v případě, že předem neznáme počet opakování. V zájmu resultativnosti algoritmu a konečnosti programu je dobré věnovat pozornost podmínce cyklu.

11.1

Podmínka na začátku

Cyklus se opouští nesplněním podmínky. Nejprve se vyhodnotí podmínka, pak provede tělo cyklu. Počet průchodů tělem může být tedy nulový. while výraz do begin ... end;

11.2

Podmínka na konci

Cyklus se opouští splněním podmínky. Nejprve proběhne tělo, pak se vyhodnotí podmínka. Tělo je tedy vždy alespoň jednou provedeno. repeat ... until výraz;

11.3

Záměna podmíněných cyklů

Oba cykly s podmínkou jsou zaměnitelné. Při rozhodování mezi nimi vždy vybíráme ten, kterým lze vyjádřit algoritmus snadněji. Při záměně je třeba vždy znegovat podmínku – jeden z cyklů se ukončuje při splnění, druhý při nesplnění. • while → repeat: Cyklus repeat vložíme do podmínky původního cyklu. • repeat → while: Před cyklus while zkopírujeme tělo cyklu.

25

11.4

Zadávání dat se zarážkou

Používá se, pokud chceme od uživatele data splňující určitou podmínku (např. číslo). Využívá se cyklus načítající data, dokud nesplňují podmínku.

11.5

Cyklus s dvěmi podmínkami

Pokud má cyklus dvě podmínky, z nichž jedna stačí, aby se ukončil, kontrolujeme po proběhnutí cyklu, která z podmínek jej ukončila: while výraz1 and výraz2 do příkaz; if výraz1 then ... Tento cyklus se využívá především při procházení struktur (např. polí nebo seznamů), kdy se zároveň kontroluje hodnota položky a jestli nebyl překročen rozsah struktury.

11.6

Cyklus s daným počtem opakování

Pro cyklus s předem daným počtem opakování. for proměnná := dolní to horní do begin ... end; Řídící proměnné se přiřadí hodnota výrazu dolní. Pokud je řídící proměnná menší nebo rovna výrazu horní, proběhne tělo cyklu. Po každém proběhnutí těla cyklu je řídící proměnné přiřazen její následovník (tj. zvýší se o 1). Řídící proměnná musí být ordinální. S řídící proměnnou lze pracovat v těle cyklu – pak je ale třeba dávat pozor, aby byl cyklus vždy konečný. Pokud horní < dolní, neprovede se tělo cyklu ani jednou. Je možné aby se řídící proměnná snižovala. Cyklus má pak syntaxi: for proměnná := horní downto dolní do Dolní a horní mez se vyhodnotí pouze na počátku (v průběhu cyklu se nemění), oproti podmíněným cyklům, kdy se výraz vyhodnocuje průběžně.

26

12

Procedury

• bloková struktura procedury • procedury s parametry a bez parametrů, formální parametry procedury • uživatelem definované procedury a procedury implementované v jazyce Pascal • lokální a globální objekty (proměnné, procedury, funkce) • parametry volané hodnotou a odkazem • volání procedur

Procedura je druh podprogramu, který nevrací svým voláním žádnou hodnotu. Využívá se především na dělení programu do menších částí – tedy základ strukturovaného programování – a k jako výkonný podprogram. Často obsahuje pracuje se vstupem nebo výstupem. Je to prvek blokové struktury (viz Strukturované programování), je v něm tedy možné definovat vlastní (lokální) proměnné, konstanty, typy a dokonce další podprogramy. Hlavička const definice konstant type definice typů var definice proměnných Definice podprogramů begin Příkazy end; Všechny definované konstanty, typy, proměnné a podprogramy jsou lokální – tj. jsou přístupné pouze z daného bloku a do něj vnořených bloků. Zároveň překrývají globální objekty stejného názvu.

12.1

Hlavička

1. Bez parametrů: procedure identifikátor; 2. S parametry: procedure identifikátor(seznam parametrů); Procedura volá svým identifikátorem se seznamem svých parametrů. printhello; print(Hello’);’ Formální parametry mohou být různého typu a mohou být předávány různým způsobem. Uvedením parametru v hlavičce procedury prakticky vytváříme

27

lokální proměnnou daného názvu. Pozor! Pokud předáváme parametry strukturovaného typu, musí být nadefinován v typové části nadřazeného bloku. Např. pole : array[1..5] of integer nejde v hlavičce vůbec použít. Skutečný parametr je proměnná stejného typu jako formální parametr, kterou mu přiřazujeme. parametr : typ Při předávání hodnotou si program v paměti vytvoří novou lokální proměnnou a do ní zkopíruje obsah skutečného parametru. Od té doby nemá proměnná se skutečným parametrem žádný vztah a její změna jej nijak neovlivňuje. Předávání hodnotou má především tu výhodu, že nemůže dojít ke změně skutečného parametru, proto se používá standartně, pokud skutečný parametr nechceme měnit. Přesto se nedoporučuje používat jej pro velké strukturované typy (např. pole), protože celá proměnná se kopíruje, což by bylo náročné na paměť. var parametr : typ Při předání odkazem vznikne proměnná obsahující odkaz na skutečný parametr. Všechny změny na proměnné se tedy provádějí na skutečném parametru. Předávání odkazem se používá pouze tehdy, je-li účelem podprogramu měnit skutečný parametr. Toho využívá také, pokud má parametr tvořit jistou formu výstupu. Také se používá pro právi s velkými datovými strukturami, ačkoli to není bezpečné a je třeba si dávat pozor. Parametry stejného typu se oddělují čárkou, různé typy středníkem. 12.1.1

Netypový parametr

Odkazem může být předán i parametr bez udání typu. Ten se pak chová jako hodnota, na kterou ukazuje univerzální ukazatel (typ pointer – viz DDS). Před použitím je většinou třeba jej přetypovat. Jeho použití není ale příliš časté. var identifikátor

12.2

Zásady tvorby podprogramů

Při tvorbě podprogramů obecně je dobré se řídit několika pravidly: • Dílčí úkoly programu by měl být prováděny podprogramy. • Pokud se v programu opakuje kód, je dobré uvažovat o použití podprogramu. • Všechny globální proměnné, které podprogram potřebuje se mu mají předat – podprogram je pak obecnější a víceúčelovější. Poslední uvedená zásada je častou chybou – dochází tím k předčasné optimalizaci, která se projeví například v případě znovupoužití kódu nebo rozšiřování programu.

28

12.3

Rekurze

Pascal umožňuje, aby poprogram volal sám sebe. Využívá se toho například při procházení stromu nebo rekurzivních matematických řádách (faktoriál apod.). Vždy je třeba určit výstupní podmínku, při které se rekurze ukončí, aby nedošlo k zacyklení. Rekurze je z hlediska efektivity algoritmu nevýhodná, protože při volání podprogramu se provádí pomocné akce (vytvoření lokálních proměnných a další), proto se doporučuje ji používat jen pokud příliš nezáleží na efektivitě algoritmu a rekurzivní zápis je výrazně jednodušší, nebo nerekurzivní algoritmus vůbec není znám. Alternativou k rekurzi jsou cykly.

29

13

Funkce

• bloková struktura funkce • formální parametry funkce • uživatelem definované funkce a funkce implementované v jazyce Pascal • lokální a globální objekty (proměnné, procedury, funkce) • přiřazení hodnoty funkcí • rozdíl mezi procedurou a funkcí • volání funkcí

Funkce je druh podprogramu, který svým voláním předává hodotu. Jeho využití je především matematické, v rámci funkce by neměl být prováděn vstup ani výstup1 . Je to prvek blokové struktury (viz Strukturované programování), je v něm tedy možné definovat vlastní (lokální) proměnné, konstanty, typy a dokonce další podprogramy. Hlavička const definice konstant type definice typů var definice proměnných Definice podprogramů begin Příkazy end; Všechny definované konstanty, typy, proměnné a podprogramy jsou lokální – tj. jsou přístupné pouze z daného bloku a do něj vnořených bloků. Zároveň překrývají globální objekty stejného názvu.

13.1

Hlavička

Lze volat i bez parametrů, čož se ale většinou nedělá, vzhledem k jejímu použití (viz Zásady tvorby podprogramů). Výstupní typ nesmí být strukturovaný. function identifikátor(seznam parametrů) : typ funkce; Funkce se volá svým identifikátorem a seznamem parametrů. Protože má výstupní hodnotu, musí být součástí výrazu – ze syntaktického hlediska je výrazem, ne příkazem. V těle funkce musí být identifikátoru funkce přiřazena hodnota – výstupní hodnota funkce. 1 Alespoň

co se Pascalu, výukového programovacího jazyka, týče. Jinak je běžnou praxí například používat funkce, které vrací úspěšnost operace apod.

30

Formální parametry mohou být různého typu a mohou být předávány různým způsobem. Uvedením parametru v hlavičce procedury prakticky vytváříme lokální proměnnou daného názvu. Pozor! Pokud předáváme parametry strukturovaného typu, musí být nadefinován v typové části nadřazeného bloku. Např. pole : array[1..5] of integer nejde v hlavičce vůbec použít. Skutečný parametr je proměnná stejného typu jako formální parametr, kterou mu přiřazujeme. parametr : typ Při předávání hodnotou si program v paměti vytvoří novou lokální proměnnou a do ní zkopíruje obsah skutečného parametru. Od té doby nemá proměnná se skutečným parametrem žádný vztah a její změna jej nijak neovlivňuje. Předávání hodnotou má především tu výhodu, že nemůže dojít ke změně skutečného parametru, proto se používá standartně, pokud skutečný parametr nechceme měnit. Přesto se nedoporučuje používat jej pro velké strukturované typy (např. pole), protože celá proměnná se kopíruje, což by bylo náročné na paměť. var parametr : typ Při předání odkazem vznikne proměnná obsahující odkaz na skutečný parametr. Všechny změny na proměnné se tedy provádějí na skutečném parametru. Předávání odkazem se používá pouze tehdy, je-li účelem podprogramu měnit skutečný parametr. Toho využívá také, pokud má parametr tvořit jistou formu výstupu. Také se používá pro právi s velkými datovými strukturami, ačkoli to není bezpečné a je třeba si dávat pozor. Parametry stejného typu se oddělují čárkou, různé typy středníkem. 13.1.1

Netypový parametr

Odkazem může být předán i parametr bez udání typu. Ten se pak chová jako hodnota, na kterou ukazuje univerzální ukazatel (typ pointer – viz DDS). Před použitím je většinou třeba jej přetypovat. Jeho použití není ale příliš časté. var identifikátor

13.2

Zásady tvorby podprogramů

Při tvorbě podprogramů obecně je dobré se řídit několika pravidly: • Dílčí úkoly programu by měl být prováděny podprogramy. • Pokud se v programu opakuje kód, je dobré uvažovat o použití podprogramu. • Všechny globální proměnné, které podprogram potřebuje se mu mají předat – podprogram je pak obecnější a víceúčelovější. Poslední uvedená zásada je častou chybou – dochází tím k předčasné optimalizaci, která se projeví například v případě znovupoužití kódu nebo rozšiřování programu. 31

13.3

Rekurze

Pascal umožňuje, aby poprogram volal sám sebe. Využívá se toho například při procházení stromu nebo rekurzivních matematických řádách (faktoriál apod.). Vždy je třeba určit výstupní podmínku, při které se rekurze ukončí, aby nedošlo k zacyklení. Rekurze je z hlediska efektivity algoritmu nevýhodná, protože při volání podprogramu se provádí pomocné akce (vytvoření lokálních proměnných a další), proto se doporučuje ji používat jen pokud příliš nezáleží na efektivitě algoritmu a rekurzivní zápis je výrazně jednodušší, nebo nerekurzivní algoritmus vůbec není znám. Alternativou k rekurzi jsou cykly.

32

14

Datový typ soubor

• soubor fyzický a soubor jako proměnná • textový soubor, typový soubor, soubor bez udání typu • čtení ze souboru a zápis do souboru • procedury a funkce pro práci se soubory • zásady pro práci se souborem

Zajímavé jsou předdefinované proměnné Output a Input – standartní výstup a vstup, typ text. Je také možno zmínit vazbu na relační databázi. Soubor je uspořádaná pojmenovaná kolekce dat, která je uložená v trvalém uložišti. Trvalém v tom smyslu, že zůstává přístupný jiným programům poté, co program, který jej vytvoři, skončil. Fyzicky se jedná o sekvenci bytů. Ty můžou reprezentovat data různého typu. V programu je soubor spojen s jednou proměnnou souborového typu. Rozlišujeme tři typy souborů: 1. Typový soubor – má udaný typ (i strukturovaný – jen součástí struktury nesmí být soubor) Bere se jako sekvence proměnných danného typu. identifikátor : file of typ 2. Textový soubor – standartní vstupní a výstupní soubor Bere se jako sekvence znaků. identifikátor : text 3. Netypový soubor – bez udání typu. Používá se, když není třeba brát ohled na vnitřní formát. Bere se obecně – jako sekvence bytů. identifikátor : file

14.1

Spracování souboru

Datovému typu soubor nepřísluší žádné operace, ani přiřazování, veškerá manipulace se provádí pomocí standartních procedur. 1. Spojení proměnné se souborem. Děje se pomocí procedury assign: assign(proměnná soborového typu, název souboru); 2. Otevření souboru. Děje se pomocí procedur reset, rewrite a append (pouze textové). Jejich použití závisí na typu souboru. 3. Zpracování souboru. Děje se především pomocí procedur read a write a pomocných funkcí. Opět závisí na typu. Základní kontrolní funkce je eof, která vrací true, jestliže program dosáhl konce souboru. 33

4. Zavření souboru. Je nutné, aby s jistotou došlo k zápisu na disk (a nedošlo ke ztrátě dat). close(identifikátor souboru);

14.2

Textový soubor

• rewrite – vytvoří nový prázdný soubor, popřípadě vymaže existující. Přístup pro psaní. • reset – otevře existující soubor na začátku. Pouze pro čtení. • append – otevře existující soubor pro zápis na konec souboru. Vstup je prováděn pomocí procedur readln a read (která ale neumí načíst konec řádku). Více k standartnímu souboru – viz Standartní vstup.

14.3

Typový soubor

Procedura rewrite otevře nový soubor nebo vymaže existující. Co udělá se souborem procedura reset záleží na konstantě FileMode : byte. 0 pouze pro čtení 1 pouze pro zápis 2 pro čtení i pro zápis – standartní hodnota Zpracování typových souborů je sekvenčně-indexové. Funkce write(identifikátor souboru, proměnné typu souboru) a read(viz předchzí) čtou a zapisují komponenty sekvenčně od aktuální pozice v souboru, tu však lze nastavit explicitně. K tomu slouží podprogramy: • FileSize – vrací velikost souboru v komponentách • FilePos – vrací aktuální pozici (první komponenta má pozici 0). • Seek – nastavuje aktuální pozici na dannou hodnotu. • Truncate – Odstraní aktuální komponentu a všechny následující.

14.4

Ošetření vstupu

Zpracování souboru je kritická situace, kdy může dojít k chybám, nad kterými nemá program (a někdy ani uživatel) kontrolu, jako například neexistující soubor otevíraný ke čtení (časté), už otevřený soubor nebo vadné médium. Tyto chyby program standartně ukončí, Pascal ovšem umožňuje ošetření těchto vstupně-výstupních chyb. Uživatelské ošetření IO (input/output) operací se nastavuje pomocí direktivy {$I}. • {$I-} – kontroluje uživatel (program se neukončí běhovou chybou) • {$I+} – kontroluje program Po každé chybné IO operaci můžeme vyvolat číslo chyby pomocí funkce IOResult. Nulová hodnota značí úspěšnou operaci. 34

15

Matice a operace s nimi

• datové struktury pro uložení matic • základní matematické operace s maticemi

Matice je v Pascalu reprezentována dvojrozměrným polem, které je ve skutečnosti polem polí: matice : array[1..N] of array[1..N] of integer zkráceně matice : array[1..N,1..N] of integer Podobně jako u pole (viz datový typ pole), můžeme dvě matice stejného typu navzájem přiřazovat a k jednotlivým prvkům matice přistupujeme pomocí indexů: matice[3,3] := 5; To, že je matice prakticky pole polí nám umožňuje operovat také s jednotlivými řádky. Například pokud je chceme prohodit nebo vynulovat. Při práci s jednotlivými prvky matic využíváme nejčastěji vnořené cykly (jeden pro řádky, druhý pro sloupce).

15.1

Operace s maticemi

Z matematického hlediska je pro matici významná hlavní diagonála – prvky s indexem [i,i]. 1. Nulování (a stejně inicializace) – vynuluje se první řádek a přiřadí ostatním. 2. Načítání – vnořené cykly s danným počtem opakování. Konvenčně vnější cyklus prochází řádky. 3. Výpis – opět dva vnořené cykly 4. Transponování – přehození řádků a sloupců 5. Násobení konstantou 6. Lineární kombinace matic (součet, rozdíl a další) 7. Násobení Cmn = Ams · Bsn s P cij = aik bkj k=1

Bude potřeba tří cyklů – dvou, které projdou všechny prvky matice C a jednoho pro proměnnou k.

35

16

Třídící a vyhledávací algoritmy

• třídící algoritmy (insert sort, select sort, buble sort) • efektivita třídicích algoritmů • vyhledávání v nesetříděném souboru dat (lineární vyhledávání se zarážkou a bez zarážky) • vyhledávání v setříděném souboru dat (binární vyhledávání) • srovnání vyhledávacích metod Třídící algoritmus je algoritmus, který seřadí prvky seznamu podle určitého klíče. Nejčastěji se řadí podle numerické velikosti čísel nebo abecedně. Z formálního hlediska musí výstup splňovat: 1. Výstup je v nesestupujícím pořadí (tj. hodnota klíče prvku je menší nebo rovna klíči dalšího prvku) 2. Výstup je permutace vstupu. Nejčastěji se setřizují pole nebo seznamy (viz DDS).

16.1

Asymptotická složitost

Je to způsob klasifikace algoritmů – jak se bude měnit chování algoritmu když se změní velikost
vstupních dat (počet prvků). Jednoduše řečeno, pokud je náročnost O N 2 , zvýšíme-li počet prvků dvakrát, prodlouží se trvání procesu čtyřikrát. Nejčastější náročnosti třídících algoritmů jsou:
• O N 2 – kvadratická: Většina jednoduchých algoritmů. • O (N log N ) – lineárnělogaritmická: Většina sofistikovanějších (a složitějších) algoritmů.

Operace s vyšší složitostí než je polynomiální O N X nemají z praktického hlediska (při větším objemu vstupních dat) využití.

16.2

Klasifikace

Kromě asymptotické složitosti se třídící algoritmy ještě dají klasifikovat: Stabilita Pokud jsou v seznamu dva prvky se stejnou hodnotou, stabilní algoritmus zaručí, že po setřízení jsou ve stejném pořadí vůči sobě. Nestabilní algoritmus to nezaručuje. Přirozenost Přirozený algoritmus rychleji zpracuje už seřazený seznam. Nepřirozený spracovává všechny seznamy stejně rychle. 36

Dodatečná paměť Většinou závisí na počtu prvků – uvádí se stejně jako asymptotická složitost. O(1) znamená, že dochází k setřízení na původním místě. Princip Existuje několik základních druhů algoritmů, přičemž některé algoritmy kombinují více z nich. V pokročilejších algoritmech se často používá řazení slučováním, také metoda „rozděl a panujÿ, kdy se soubor dělí na menší části (většinou rekurzivně), které se potom slučují určitým způsobem. Obecně platí, že každý algoritmus je svými parametry vhodný pro jinou situaci a neexistuje žádný „univerzálníÿ, který by byl nejvhodnější pro všechny.

16.3

Bubble sort


Metoda přirozená a stabilní, sice nejjednodušší, ale nejpomalejší (O N 2 ). Nejrychlejší je pouze v případě, pokud je seznam už setřízen (pak má složitost O (N )). Nevyžaduje pomocnou paměť (z praktického hlediska jen jednu pomocnou proměnnou). Prochází seznam a porovnává sousední prvky. Pokud nejsou ve správném pořadí, prohodí je. V tom pokračuje, dokud není seznam setřízen (většinou je potřeba větší množství průchodů seznamem). Pro praktické účely není příliš vhodný, protože je pomalý a oproti algoritmům se stejnou náročností vyžaduje velké množství zápisů do paměti.

16.4

Shell sort

Svým způsobem vylepšený bubble sort, který vychází z vysledovaných vlastností posloupností, kdy se každý prvek v průměru přesune o jednu třetinu její délky. Není stabilní a její přirozenost není jednoznačná.
Složitost zatím nejlepší varianty byla experimentálně odvozena na O N log2 N . Implemetnačně se velmi podobá bubble sortu, jen se pracuje s určitým krokem v závislosti na velikosti posloupnosti. Porovnávají se vždy prvky vzdálené od sebe o krok, který se při každém průchodu posloupnosti zmenšuje, až na jedna. Zatím nejúspěšnější posloupnost kroků je: 1, 4, 10, 23, 57, 132, 301, 701

16.5

Selection sort

Přirozený a stabilní algoritmus s kvadratickou složitostí. Pro jednoduchou implementaci, relativně malý počet zápisů do paměti a třízení na místě se často používá pro malé objemy dat. Je výhodný pro pole, pro seznamy je lepší insertion sort. Vyhledá v poli nejmenší prvek a prohodí jej s prvním prvkem. Dále pokračuje v nesetřízené části pole, která se tím neustále zmenšuje.

37

16.6

Insertion sort

Přirozený a stabilní algoritmus s kvadratickou složitostí (pro už setřízené pole má lineární složitost). Nevhodný pro pole (velký počet zápisů do paměti), alternativa selection sortu pro seznamy, kde třídí na místě. Vyhledá v seznamu nejmenší prvek a vloží jej na začátek. Dále pokračuje v nesetřízené části a nejmenší prvky na konec setřízené části. Implemetace pro pole vyžaduje buď posouvání prvků (což je náročné na operace a zápis do paměti) a nebo vkládání do nového pole (což vyžaduje další paměť).

16.7

Quick sort

Známý a relativně jednoduchý algoritmus s průměrnou složitostí O (N log N ), která může vzrůst až na kvadratickou. Prakticky je na pseudonáhodné posloupnosti jeden z nejrychlejších algoritmů (i rychlejší než Heapsort a Mergesort, které jsou formálně rychlejší). Lze dobře paralelizovat. Ze seznamu se vybere pivot, podle kterého se rozdělí na dvě části. Na ty se tento postup rekurzivně opakuje. Pivot je prvek, který by měl seznam rozdělit na stejně velké části. Optimálně je to medián.

16.8

Merge sort

Formálně rychlejší než quick sort – v nejhorším případě má složitost O (N log N ) a celkově provádí méně porovnání. Na druhou stranu vyžaduje více dodatečné paměti. Je nejčastěji nejlepší volbou pro seznamy (DDS), navíc se dá dobře paralelizovat. Seznam se rozdělí na dvě přibližně stejné části. Ty se dále rekurzivně rozdělují až na jednotlivé prvky. Ty se pak postupně po částech spojují (na začátek výsledné větší části se vždy přidá menší z prvních prvků vstupních částí).

16.9

Heap sort

Jeho výhoda je maximální složitost O (N log) a třízení na místě. Není ale žádný zřejmý způsob jak jej paralelizovat a je nestabilní. Využívá speciální strukturu, binární haldu (heap) – jistý druh binárního stromu, která je nejprve vytvořena a pak jsou z ní odebírány kořenové prvky.

16.10

Lineární vyhledávání

Prochází postupně seznam, dokud nenarazí na hledaný prvek. Využívá se u nesetřízených seznamů a má složitost O (N ). Většinou využívá cyklu se dvěmi podmínkami (překročení seznamu a rovnost prvků). Lineární vyhledávání se zarážkou spočívá v nahrazení dvou podmínek jednou. Prvek s požadovanou vložíme za konec seznamu (nárazník) a kontrolujeme pouze rovnost prvků. Na konci pak zkontrolujeme index nalezeného prvku. 38

16.11

Binární vyhledávání

Využívá se u setřízených seznamů a má náročnost O (log N ). Je tedy mnohem rychlejší. Seznam se rozdělí na dvě přibližně velké části a pomocí porovnání s krajními prvky se zjistí, ve které hledaný prvek je. Proces se rekurzivně opakuje až k nalezení prvku.

39

17

Databáze

• základní pojmy databází • zásady pro návrh a tvorbu databáze, pravidla pro tvorbu bezpečných databází • základní databázové operace • realizace databáze ve vyšších programovacích jazycích • model databáze realizovaný pomocí datového typu záznam a externího souboru • model databáze realizovaný pomocí dynamických datových struktur

Tato otázka je propojena s následující Co ta realizace ve vyšších programovacích jazycích? Databáze je určitá uspořádaná množina informací společně s prostředky umožňující manipulaci s uloženými daty a přístup k nim – SŘBD, systém řízení báze dat. Iformace jsou data, která zobrazují konkrétní výsek reálného světa – jsou nám nějak užitečná. Entity jsou vzájmně rozlišitelné konkrétní nebo abstraktní objekty zobrazovaného výseku světa. Entitní množina je soubor vzájemně příbuzných entit. Atribut je vlastnost entity. Má povolenou množinu hodnot – datový typ. Může být jednoduchý nebo složený – v závislosti na datovém typu.

17.1

Návrh a tvorba databází

Základem je část skutečného světa, kterou má zobrazovat. Je třeba nadefinovat si entity, jejich atributy a vzájemné vztahy. Nezávislost dat Požadavek, aby změna dat nevyžadovala změnu aplikačního programu a naopak. Přístup k informacím Poskytnout uživateli efektivní prostředky přístupu k informacím nezávisle na jeho kvalifikovanosti. Sdílení dat K datům má přístup více uživatelů – jejich pohled se ale může lišit (uživatelská práva). Redundance dat Tedy vícenásobné uchovávání stejných dat v jedné databázi. Jedná se o negativní jev: 40

• Ohrožuje konzistenci – stačí opomenout jeden výskyt dat při aktualizaci. • Zvětšuje velikost databáze a tím i čas potřebný k operacím. Integrita dat Soulad se zobrazovanou realitou (která se v čase mění). Vztahy mezi daty Schopnost vyjádřovat vztahy mezi datovými strukturami bez použití algoritmů. Způsob, kterým se vyjadřují, závisí na databázovém modelu. Přístup uživatele k datům je zpravidla víceúrovňový. Například: 1. Data 2. SŘBD 3. Uživatelské rozhraní

17.2

Základní operace

• vyhledání záznamu dle libovolné hodnoty atributu • vložení záznamu • zrušení záznamu • modifikace záznamu • operace s částmi databáze (např. tabulkami)

17.3

Datový typ záznam

Je vhodný pro implementaci jednoduché databáze, protože se může chovat jako entita s atributy. Jedna z možností je externí soubor se záznamy, ke kterému je ale pomalý přístup. Navíc je problém s mazáním záznamů (je možné buď všechny ostatní posunout a nebo nechávat prázdná místa) a s třízením. Daleko lepší možností jsou dynamické datové struktury – například spojové seznamy, které kromě toho, že řeší problémy externího souboru umožňují lepší vyjádření vztahů pomocí ukazatelů. Pro trvalé uložení databáze ale musí být opět použit externí soubor.

41

18

Relační datový model

• popis relačního datového modelu • primární a sekundární klíč • základní databázové operace • normální formy relací, dekompozice relace • programovací prostředky pro realizaci relačního datového modelu

Tato otázka je úzce propojena s předchozí Databáze obecně – viz předchozí otázka. Relační datový model sdružuje data do tzv. relací (tabulek), které obsahují n-tice (řádky) – vlastní data relace (záznamy). Název relační tedy prakticky znamená tabulkový, nemá nic společného se vztahy mezi jednotlivými tabulkami. Schéma relace popisuje relaci – udává její název a definuje její struktru – jednotlivé řádky mají pevně danné položky – atributy. Každý atribut má definovaný název a rozsah (tedy vlastně datový typ).

18.1

Klíče

Klíč je všeobecně podmnožina všech atributů. Kandidátní klíč Jednoznačně definuje prvky. Každá relace má alespoň jeden – všechny atributy. Primární klíč Nejjednodušší kandidátní klíč – získá se postupným odebíráním atributů až další nelze odebrat (tj. není redundantní). Sekundární klíč Také vyhledávací. Jedná se pouze o neprázdnou množinu atributů. Cizí klíč Primární klíč jiné relace – slouží především k definici vztahů mezi relacemi.

18.2

Základní operace

• vyhledání záznamu dle libovolné hodnoty atributu • vložení záznamu • zrušení záznamu • modifikace záznamu • operace s částmi databáze (např. tabulkami)

42

18.3

Normální formy2

Jedná se o způsob zápisu, kterým je relace jednoznačně prezentována. Obecně je to tabulka. První normální forma Prvky relace nejsou další relace. Prakticky jsou to tedy všechna data v jedné tabulce. Její hlavní negativum je redundance dat – změnou jednoho záznamu můžeme porušit konzistenci dat (viz databáze obecně). Proto se provádí dekompozice – na základě funkční závislosti atributů. Atributy jsou závislé, jestliže platí, že pokud se libovolné dva prvky relace shodují v jednom atributu, shodují se i v druhém. Dekompozici provádíme tak, že z funkčně závislých atributů vytvoříme další relaci, kterou svážeme s původní cizím klíčem. Druhá normální forma Vzniká dekompozicí první normální formy. Platí pro ni, že všechny neklíčové atributy jsou funkčně závislé na klíči. Může se v ní vyskytnout negativní jev – tranzitivní závislost. Ta nastává, když ze tří atributů druhý je funkčně závislý na prvním, třetí na druhém, ale třetí není závislý na prvním. Řeší se dalším rozdělením relace, kdy se druhý atribut stává cizím klíčem. Třetí normální forma Vzniká opět dekompozicí druhé normální formy. Kromě toho, co platí pro druhou formu pro ni platí, že všechny její neklíčové atributy jsou na sobě navzájem nezávislé. Boyce-Coddova normální forma Je odvozena od třetí, ale platí na ni, že atribut může být závislý pouze na klíči. To neplatí například když je v tabulce více klíčů. Jsou ještě vyšší normální formy (čtvrtá, pátá a nově i nepodporovaná šestá), které jsou vždy založeny na předchozí a snižují redundanci dat. Čtvrtá například řeší mnohoznačnou závislost, všechny atributy musí být na klíči závislé stejným způsobem. Postupná úprava relace, aby odpovádala vyšším normálním formám se nazývá normalizace relace.

18.4

Jazykové prostředky

Rozlišujeme dva způsoby přístupu: 1. Jazyky založené na relační algebře. Procedurální jazyky. Mají matematický základ a spolu s požadavkem předávají i způsob jeho plnění. Výsledkem je opět relace. 2. Jazyky založené na relačním kalkulu. Jedná se o uživatelský pohled – udává se pouze dotaz na data. Jsou ale odkázány na procedurální jazyk relační algebry. 2 Důležitá

je první, druhá a možná třetí. Pak už to začíná být zatraceně komplikované.

43

19

Internetové programování a databáze

• technologie MySQL, realizace základních databázových operací • podpora databází ve skriptovacím jazyce PHP • manipulace s daty pomocí prohlížeče

Tohle je opravdu základ – snad si každý vzpomene na více Komunikace s většinou internetových databází je založena na jazyce SQL (structured query language). Jeden ze systémů používající jeho dialekt je MySQL, pod kterým kromě mnoha drobných projektů běží například i Wikipedie a YouTube. Jeho výhodou je kromě jednoduchosti i to, že je k dispozici pod GNU/GPL licencí. Databáze MySQL pracuje podle relačního modelu.

19.1

Datové typy

−128 → 127 1B −2147483648 → 2147483647 4B a další celočíselné typy float(m,d) maximální délka, desetinné část 4 B a další desetinné typy char(x) X znaků (až 255) XB varchar(X) X znaků (až 255) X + 1B text až k ukládání souborů 65537 B U každého typu je dáno, zda je null nebo not null. Druhý zaručuje, že atribut nebude moci být prázdný. null značí prázdnou hodnotu. Všechny kromě text můžou mít definovanou defaultní hodnotu, kterou mají, pokud ji jinak nespecifikujeme (atributy s vlastností null jsou defaultně prázdné). Zadává se pomocí klíčového slova default. Všechny celočíselné typy můžou být unsigned – tedy nezáporné. Navíc je pro ně přípustná speciální hodnota auto increment, která každému novému záznamu přiřadí číslo o jedna vyšší. Využívá se především pro primární klíče. Základní rozdíl mezi char a varchar je ten, že char má konstantní velikost, ale práce s ním je rychlejší, zatímco velikost varchar se mění podle obsahu. text má proměnnou velikost. tinyint int

19.2

Základní syntaxe

MySQL umožňuje pracovat s více databázemi, v každé z nich může být více navzájem provázaných tabulek. MySQL v některých místech syntaxi SQL rozšiřuje, mluví se proto o dialektu SQL. Vytvoření tabulky create table název(atribut typ, . . . ). Na konci seznamu se uvádějí klíče: • primární primary key(atribut) 44

• unikátní (dva se sobě nesmějí rovnat) unique key(atribut) • sekundární key(atribut) Přidání záznamu insert into tabulka (atributy) values(hodnoty) Seznam atributů není nutný, pak je ale třeba vypsat hodnoty pro všechny atributy (i pro defaultní a auto increment). Výpis záznamů select atributy from tabulka [where atribut = hodnota] [order by atribut [desc]] [limit [odkud,] kolik] Místo seznamu atributů je možno uvést * pro dotázání na všechny, ale není to doporučováno kvůli časové náročnosti. • where – vybere pouze ty záznamy jejichž atribut má dannou hodnotu • order by – seřadí výsledek podle daného atributu (desc – sestupně) • limit – omezí počet položek výsledku, popřípadě bere určitý počet až od danné položky Je možno spojovat více tabulek – syntaxe left join. Dotazovaným atributům je třeba přidat identifikátor tabulky – tabulka.atribut. left join tabulka on primární klíč = cizí klíč Zrušení záznamu delete from tabulka [where atribut = hodnota] [limit kolik] Pozor, bez specifikace podmínky nebo limitu vymaže celou tabulku. Modifikace záznamu update tabulka set atribut = hodnota [where atribut = hodnota] [limit kolik] Opět, bez specifikace podmínky nebo limitu přemění celou tabulku.

19.3

PHP a MySQL

PHP má zabudovanou podporu spolupráce s databázovým systémem MySQL. Připojení k databázi mysql_connect(server, uživatel, heslo) Výběr databáze mysql_select_db(název) Zadání dotazu mysql_query(dotaz) Funkce vrací výsledek. Pokud dojde k chybě, můžeme ji vypsat pomocí funkce mysql_error(). Často se používá struktura mysql_query(dotaz) or die(mysql_error());, která v případě chyby ukončí běh programu a vytiskne chybu na obrazovku. Protože výsledek každého dotazu je relace, pro další zpracování se většinou používá funkce mysql_fetch_array(výsledek dotazu), která při každém svém použití vrací pole s jedním záznamem. Na kontrolu počtu záznamů ve výsledku slouží funkce mysql_num_rows(výsledek dotazu).

45

"; while ($zaznam = mysql_fetch_array($vysledek)) { echo $zaznam["name"]."
"; } } ?>

19.4

PHPMyAdmin

Kromě námi vytvořeného prostředí pro správu databáze existuje jednoduché a především pohodlné prostředí PHPMyAdmin, které umožňuje správu databází pomocí webového prohlížeče.

46

20

Jazyk C

• vlastnosti jazyka C, srovnání C a Pascal • základní stavba programu v jazyce C++ • základní algoritmické konstrukce v jazyce C

Velmi obsáhlé. Je třeba si vybrat. Jazyk C je imperativní (příkazový) procedurální programovací jazyk s blokovou strukturou. Byl vytvořen Dennisem Ritchiem (v Bell Labs) pro použití na operačním systému Unix a jako jazyk pro implementaci systému (většina Unixu, původně psaného v assembleru, byla přepsána do céčka v roce 1973, jádro Linuxu je psáno v céčku). Jazyk C umožňuje nízkoúrovňový přístup k paměti, na druhé straně podporuje přenositelnost na různé platformy. Jazyk C++ je původně rozšíření jazyka C (až na určité výjimky jsou všechny programy v céčku platné i v C++), který kromě procedurálního programování umožňuje i objektově orientované a generické programování. Zachovává si nízkoúrovňový přístup k paměti. Vyvinul jej Bjarne Soustrup (také v Bell Labs).

20.1

Překlad

Vlastní překlad probíhá ve třech fázích. 1. Preprocessing – zpracovávají se direktivy, které ovlivňují průběh překladu. Nejčastěji používané: • #include soubor – k vlastnímu zdrojovému kódu se připojí danný soubor. Pokud jej uvedeme v uvozovkách, je to relativní cesta k souboru, pokud v úhlových závorkách (<>), je hledán v adresářích, které má překladač nastavené pro knihovny. • #define jméno [hodnota] – definuje konstantu. Výskyt konstanty v programu je jí při preprocessingu nahrazen. Je zvykem psát ji velkými písmeny (C je case sensitive). • Bloková direktiva – podmíněný překlad. Umožňuje zahrnout nebo vypustit část zdrojového kódu do překladu. #ifdef/#ifndef jméno zdrojový kód #endif 2. Překlad – předzpracovaný soubor se překládá jako celek. 3. Spojování – spojení přeložených modulů s moduly knihoven.

47

20.2

Základní syntaxe

Veškerý běh programu se odehrává ve výrazech, které jsou obsaženy ve funkcích. Operační systém při spuštění programu volá funkci int main(int argc, char* argv[]). Ta má dva volitelné parametry – počet parametrů příkazové řádky a jednotlivé parametry. V každém projektu můsí být jedna funkce main. Všechny příkazy končí středníkem. Bloky se uzavírají do složených závorek ({}). Pozor, oproti Pascalu zásadní rozdíl v operátorech přiřazení a porovnání: := → = = → == Navíc zavádí operátor nerovnosti !=. Změnou prošly i logické operátory: and → && or → || not → ! 20.2.1

Základní datové typy

Proměnné můžeme deklarovat kdekoliv v bloku a jsou platné pouze pro danný blok a bloky vnořené. Globální proměnné se deklarují mimo všechny bloky. C obsah velikost Pascal integer int celé číslo 16 b nebo 32 b real float desetinné číslo 32 b char char znak 8b record struct záznam podle položek string neexistuje řetězec Číselné typy můžou být signed (defaultně) – se znaménkem a unsigned – bez znaménka. Řetězec se řeší jako pole znaků (platí pro něj složitější pravidla) – viz níže. 20.2.2

Podmínky a podmíněné cykly

Céčko nemá definovaný logický typ (boolean) a používá místo něj nejčastěji typ int (0 – nepravda, 1 – pravda). • podmínka if (výraz) příkaz (nebo blok) else příkaz (nebo blok) • přepínač – pokud se vynechá break;, pokračuje se ve vykonávání příkazů následující hodnoty. switch (ordinální výraz) { case hodnota: příkazy break; ... 48

default: příkazy break; } • cyklus s podmínkou na začátku while (výraz) příkaz (nebo blok) • cyklus s podmínkou na konci – pozor probíhá, dokud výraz platí! do příkaz (nebo blok) while (výraz); 20.2.3

Cyklus s danným počtem opakování

V céčku je mnohem obecnější než v Pascalu. for (inicializace; podmínka; krok) příkaz (nebo blok) Nejprve se provede inicializace (např. int i = 0), pak je vyhodnocena podmínka (např. i < 10). Není-li splněna, cyklus se ukončí, v opačném případě proběhne tělo, provede se krok (např. i = i + 1 – zkráceně i++) a pokračuje se opět podmínkou.

20.3

Ukazatele a pole

Řeší dynamický přístup k paměti (viz ukazatele v Pascalu) a jsou jednou z nejsilnějších technik (a Achillovou patou) céčka. Značí se pomocí deferenčního operátoru *: int * pint; K hodnotám se také přistupuje pomocí deferenčního operátoru: *pint = 3; Adresu proměnné získáme referenčním operátorem &: int a = 5; pint = &a; Opět platí, že přidělování paměti řídí programátor, proto je si třeba dávat pozor. Pole jsou v céčku řešena pomocí ukazatelů. V paměti je pole tvořeno položkami uspořádanými za sebou, identifikuje nám je ukazatel na jeho první položku. Jdou definovat staticky (není třeba alokovat paměť), pomocí indexování nebo dynamicky, pomocí ukazatelů. Pozor, indexování je vždy od nuly. Alokování paměti se řeší pomocí operátoru malloc() a její uvolnění pomocí free(). int pole[5];n int * pole; 49

pole = (*int)malloc(5*sizeof(int)); free(pole); K prvkům pole lze přistupovat buď indexováním nebo pomocí ukazatelové aritmetiky – oba následující zápisy jsou ekvivalentní: pole[5] = 3; *(pole+5) = 3; 20.3.1

Řetězec

Řetězec je speciální formou pole – char*. Jeho poslední platný znak je prázdný (může mít i více prvků) – \0. Proto je třeba pro konkrétní řetězec alokovat pole o jeden prvek větší než je počet jeho znaků.

20.4

Podprogramy

V céčku neexistují procedury – jejich funkci přebírají funkce typu void. Každá funkce kromě typu void má v těle return, kterým funkce vrací dannou hodnotu. Hlavička funkce: typ název(parametry) Překlad vyžaduje pouze deklaraci funkce, tj. její hlavičku, která se umisťuje před main nebo do hlavičkového souboru. Definice funkce, bez které neproběhne spojování, se zpravidla umisťuje až za main. Základní předávání je hodnotou, pascalovské předávání odkazem se realizuje pomocí ukazatelů, kdy se funkci předává adresa proměnné. Pozor, při volání funkce je třeba použít referenční operátor! C++ umožňuje i předávání odkazem.

20.5

Vstup a výstup

Standartní formátovaný vstup se v céčku provádí pomocí funkcí printf() a scanf() (je třeba použít hlavičkový soubor stdio.h). • printf(char * formát, proměnné) • scanf(char * formát, proměnné) Obě funkce vyžadují stanovení formátu, který je dán řetězcem s kontrolními znaky určujícími typ proměnné. Nejpoužívanější: %c znak %d celé číslo %f desetinné číslo %s řetězec C++ ve svých knihovnách iostream a fstream používá přijemnější technologii streamů.

50

21

Událostmi řízené programování

• vývojové prostředí • Delphi, Lazarus • událostmi řízené programování • knihovny komponent

Nevím, nevím, do tohohle se mi nechce. událost akce, která je iniciována čímkoli mimo program, tedy uživatelem (přes vstupní zařízení) nebo operačním systémem. Program může událost buď ignorovat a nebo ošetřena tak zvaným handlerem 3 , což je subrutina programu. událostmi řízené programování programovací paradigma, v němž je průběh programu řízen událostmi, tedy vstupními zařízeními (a tím uživatelkými akcemi jako stisknutí klávesy nebo kliknutí myší) a zprávami od ostatních programů. Zjednodušeně můžeme říci, že program čeká na to, co uživatel udělá a pak na tento podnět zareaguje. Jakmile jej vyřeší, čeká na další podnět. Při vytváření událostmi řízeného programu se postupuje následovně: 1. Vytvoření handlerů, tedy subrutin (metod) programu, ošetřujících dannou událost. 2. Svázání handlerů s dannými událostmi. 3. Vytvoření hlavní smyčky, která kontroluje, zda nedošlo k události a spouští podle toho metody.

21.1

GUI

Graphical user interface, čili grafické uživatelské rozhraní, má podobu grafických interaktivních prvků. Máme tedy celou řadu objektů (widgets), z nichž každý má určitou funkci a možnost ovlivnění uživatelem. Základní formou grafického rozhraní je WIMP (window, icon, menu, ponting device). Je běžně používané ve všech operačních systémech. Většinou se snaží poskytnout jistou obměnu skutečného pracovního stolu (desktop environment). Má následující prvky: kursor také ukazatel. Je to grafické označení místa ukazovacího zařízení (myš apod.) na obrazovce, které umožňuje vybírat objekty a pohybovat jimi. Běžně bývá zobrazen jako šipka. Základní prvek ovládání. 3 česky

asi správce událostí

51

okno Podmnožina obrazovky, která je nezávislá na všech ostatních částech obrazovky. Má svůj obsah, většinou informace a prvky. Umožňuje tedy mít na obrazovce více různých nezávislých procesů (programů). Existuje vždy program, který okna spravuje (tzv. windows manager ). menu Dovoluje uživateli vykonávat příkazy výběrem z jejich seznamu. Výhodné především proto, že nevyžaduje znalost přesné formulace příkazu a obsahuje automatickou kontrolu vstupu (uživatel nemůže zadat neplatný příkaz). ikona Malý obrázek reprezentující soubor, program nebo příkaz. Jsou rychlou cestou vykonávání příkazů, navíc umožňují graficky vystihnout obsah věci, kterou představují (například typ souboru). Grafické rozhraní obsahuje ohromné množství prvků, z nichž nejběžnější jsou4 : tlačítko (button) Posktytuje uživateli jednoduchou cestu spuštění události. Většinou je obdélníkové s centrovaným popisným textem. radio button Umožňuje uživateli vybrat si jednu z více možností – vyskytují se ve skupinách. Klasický je kroužek před popisem možnosti, který změní při výběru barvu. check box Umožňuje uživateli vybrat u možnosti ano/ne. Klasickým vzhledem je čtverec před popisem možnosti, který při výběru změní barvu. combo box Výběr možností pomocí rozbalovacího seznamu nebo přímým zadáním textu. lišta s menu Místo, na kterém jsou umístěna všechna relevatní menu, čímž usnadňuje orientaci. Většinou bývá umístěno na horním okraji okna. text box Slouží k zadávání textu. nálepka (label) Zobrazuje text. dialogové okno Speciální typ okna, který se používá k zobrazení informace, popřípadě k získání odezvy od uživatele. Je v něm pouze text zprávy, ikona charakterizující typ zprávy a jedno nebo více tlačítek. 21.1.1

Knihovna komponent

Protože pro programátora by bylo příliš složité a časově náročné vyvinout vlastní grafické prostředí, používají se většinou knihovny komponent, které obsahují systém na správu prvků grafického prostředí, jejich definice a způsob chování. Většinou fungují na základě objektového paradigmatu, kdy programátor pracuje s objekty prostřednictvím jejich metod (viz OOP). Asi nejznámnější knihovny komponent jsou GTK, .NET nebo platforma zabudovaná ve Windowsech. 4 Popište,

co vás napadne, že je důležité, jestli to vůbec má cenu popisovat.

52

21.2

IDE

Integrated development environment, tedy integrované vývojové prostředí, je software usnadňující práci programátorů. Většinou se váže na jeden programovací jazyk. Filosofií vývojových prostředí je co nejvíce zjednodušit a zefektivnit tvorbu programů. Vývojové prostředí se většinou skládá z textového editoru, překladače (nebo interpretu) a debugger (zařízení na hledání chyb). Novější prostředí, které se zabývají objektově orientovaným programováním, také můžou obsahovat zařízení na správu objektů. Důležité jsou ovšem nástroje, které zjednodušují vytváření uživatelského prostředí. Ty se pak nejčastěji vážou na jednu knihovnu komponent. Co se týče tvorby uživatelské prostředí, zjednodušují nejčastěji vývojová prostředí práci programátora těmito způsoby: • Poskytnutím knihovny komponent a rozhraní pro práce s ní • Poskytnutím hlavní smyčky • Grafickým prostředím pro tvorbu a správu jednotlivých prvků GUI • Jednoduchým svázáním akcí s jejich handlery Celkově se dá říci, že bez IDE je tvorba grafických aplikací velmi obtížná. Nejznámější vývojová prostředí jsou například Microsoft Visual Studio nebo freeware Anjuta, pro Pascal specifickké Borland Delphi.

53

22

Object Pascal

• datové typy jazyka Object Pascal • přetypování proměnných • rozšířené možnosti řízení běhu cyklů • přetěžování procedur a funkcí

Nemohl jsem neuvést tady nějaké základy OOP – ať je o čem kecat. Všeobecně je Object Pascal programovací jazyk založený na Pascalu, který podporuje objektově orientované programování.

22.1

OOP

Jedná se o programovací paradigma (vedle například procedurálního programování), které k vytváření programů používá objekty a jejich vzájemné působení. Pracuje se zde nejčastěji s tak zvaným bottom-up designem, kdy se nejprve navrhují struktury a jejich vzájemné vztahy a pak se spojí do složitějších struktur. Používá se především při návrhu složitých a komplexních systémů, protože vyjadřuje fungování a strukturu skutečného světa. Je založeno na následujících konceptech: třída Abstraktní charakteristika věci. Definuje charakteristiky (atributy) a chování (tj. co může dělat – také metody) věci, ne však jejich konkrétní hodnoty. objekt Konkrétní instance třídy. Jeho atributy mají konkrétní hodnotu. zapouzdření K obsahu objektu se lze dostat pouze přes jeho rozhraní – způsob komunikace s vnějším světem. Má zabránit Důvodem je, aby komunikace s objektem nebyla závislá na jeho vnitřní struktuře, která se může měnit. Navíc poskytuje zabezpečení, prvků, ke kterým by neměl být zvenčí objektu přístup. dědičnost Existují „podtřídyÿ, které jsou více specializovanou verzí tříd. Mají všechny atributy a metody třídy, ale ještě nějaké navíc. polymorfismus Ačkoli dvě různé podtřídy jedné třídy zdědí stejnou metodu, u každé z nich může probíhat jinak. skládání Objekt může využívat služeb jiných objektů.

22.2

Datové typy

Object Pascal zavádí některé nové datové typy a definici jiných mírně mění.

54

22.2.1

Ordinální datové typy

Tedy ty, u kterých je dána posloupnost mezi hodnotami. Patří mezi ně například všechny celočíselné typy a typ char. Definujeme u nich operace: • ord – zjistí ordinální hodnotu prvku • pred – vrací hodnotu předcházejícího prvku • succ – vrací hodnotu následujícího prvku • high – nejvyšš hodnota, kterou může typ nabývat • low – nejnižší hodnota, kterou může typ nabývat Velikost typu integer, a tím i jeho rozsah, se zvětšuje na 32 bitů (4 B). Dále je zaveden typ cardinal – 32 bitů bez znaménka. U výčtového typu (nabývá pouze vymezených hodnot) se vždy pracuje s číselnou reprezentací (začíná nulou). Zajímavý je typ comp, který je sice celočíselný, ale svým rozsahem ztrácí ordinalitu (8 B). 22.2.2

Řetězce

Datový typ char ukládád znaky klasicky v kódování ASCII. Řetězcových typů je více, všeobecně se však deklarují typem string, a překladač se sám rozhodne, který použije. 22.2.3

Přetypování

Kromě implicitního přetypování (např. z celého čísla na desetinné) je umožněno i explicitní, avšak pouze u typů se stejnou velikostí. var k : byte; c : char; begin c := ’A’; k := byte(c); S tím pak souvisí datový typ variant, který může uchovávat jakoukoli hodnotu. Jeho velikost je ale 16 B, což výrazně zvyšuje dobu zpracování. 22.2.4

Otevřené pole

Částečně odstraňuje nevýhodu pevně dané délky pole, funguje ale pouze v poprogramech. Umožňuje předat podprogramu typové pole bez udání velikosti, přičemž podprogram si pomocí funkcí high a low zjistí velikost sám.

55

procedure init_pole(var pole : array of byte); var k : integer; begin for k := low(pole) to high(pole) do pole[k] := 0; end;

22.3

Řízení cyklů

Object Pascal přináší rozšířené možnosti řízení cyklů, které jsou ale trochu „neprogramátorskéÿ. Doporučují se používat jen v nejnutnějších případech. • break; okamžitě ukončí cyklus a pokračuje prvním příkazem za tělem cyklu • continue; ukončí aktuální průchod tělem cyklu a začne procházet znova. Je třeba zajistit změnu čítače!

22.4

Přetěžování

Kromě toho, že funkce nyní zavádí novou proměnnou Result, do které je možno přiřadit návratovou hodnotu funkce místo přiřazení identifikátoru funkce, je umožněno přetížení procedur a funkcí – definice procedury nebo funkce se stejným názvem, ale jiným typem a počtem atributů. Provádí se operátorem overload: hlavička : overload;

56

23

Základy internetového programování

• jazyk HTML, základní příkazy • způsob zobrazení a komunikace prohlížeče a serveru • technologie CSS, možnosti zápisu • limitující faktory HTML a další vývoj (XML, PHP, MySQL)

Velmi, velmi obsáhlé. . . Je třeba vybrat, co říci. Co formuláře – kam zařadit ty? Pravděpodobně 25 HTML (HyperText Markup Language) je značkovací jazyk převládající na internetových stránkách. Jeho zdrojový kód tedy obsahuje kromě vlastního textu informace o jeho struktuře. Protože je zdrojový kód obyčejný ASCII soubor, lze editovat i jednoduchými textovými editory, nevyžaduje tedy na svou editaci žádné speciální vybavení. Vzhled výsledného dokumentu je dán interpretací textu jiným programem (například internetovým prohlížečem). Jedná se o deskriptivní značkovací jazyk, jeho konstrukce určují, co dané části textu představují (nadpis apod.).

23.1

Syntaxe HTML

Základem HTML jsou tagy, které uchovávají informace o textu. Uzavírají se do úhlových závorek (<>). Tagy můžou být párové (druhý začíná lomítkem), pak zpravidla určují vlastnosti textu mezi nimi, a nebo nepárové, které zpravidla značí samostatný objekt.

23.2

Struktura dokumentu HTML

Celý dokument je uzavřen v párovém tagu bez atributů. Není povinný (prohlížeče si jej domyslí), ale je součástí standardu. 23.2.1

Hlavička

Uzavřena v bez atributů. Nezobrazuje se a obsahuje další tagy určující vlastnosti dokumentu jako celku. • <meta> – nepárový tag obsahující různé informace o dokumentu. Důležité jsou především dva typy: <meta http-equiv="content-type" content="text/html; charset=kódování"> Určuje kódování dokumentu – důležité pro zobrazení českých znaků. Kódování použijete podle toho, v jakém editoru pracujete: UTF-8 nejčastější zápis sady Unicode – pro všechny jazyky stejná (používá 16 b na znak). 57

ISO 8859-2 standard pro Unix a Linux (čeština a podobné). Windows-1250 preferované ve Windowsu (čeština a podobné). <meta http-equiv="content-language" content="cs"> Určuje jazyk dokumentu, v tomto konkrétním případě češtinu •