====== Programování ======
===== Algoritmy =====
==== Algoritmizace ====
=== Algoritmus ===
  *obecný návod, který přesně, krok za krokem, popisuje akci, kterou musíme provést, abychom vyřešili daný problém 
    *je to konečná, přesně definovaná posloupnost příkazů, jejíž provedení nám umožní po konečném počtu kroků získat pro přípustné vstupní údaje odpovídající výstupní údaje
  *konečná, přesně definovaná posloupnost příkazů, po jejichž provedení získáme k přípustným vstupním datům odpovídající data výstupní
  *logika a řízení
    *základní postup výpočtu
    *je to prvotní pojem (nemůžeme ho definovat jednoznačně)
  *posloupnost příkazů
    *při tvorbě algoritmů musíme vědět, jaké akce umí procesor provést a jak mu provedení těchto akcí předepsat
    *ne každý přepis je algorimem

=== Proces===
  *postupné provádění příkazů návodu (skládá se z jednotlivých dílčích činností)
    *podle jednoho návodu může probíhat více různých procesů
    *procesor musí návodu rozumět a umět provádět popisované akce

=== Procesor ===
  *realizuje proces
  *musí návodu rozumět a umět provádět popisované akce

=== Příkaz ===
  *popis akce

=== Akce ===
  *činnost, která má konečné trvání a přesně definovaný účinek

==== Vlastnosti algoritmu ====
  ***Determinovanost** (jednoznačnost) -- jednotlivé kroky algoritmu a pořadí, v jakém jsou prováděny jsou jednoznačně určeny (=> při stejných počátečních hodnotách dostaneme vždy stejný výsledek)
  ***Hromadnost** -- algoritmus lze použít pro řešení obecné úlohy (zapsat v jakékoli symbolice)
  ***Rezultativnost** (Konečnost) -- postup řešení vede po konečném počtu kroků vždy k výsledku

==== Proměnná ====
=== Operační paměť ===
  *je rozdělena na byty

=== Bity ===
  *slučují se po 8 do bytů

=== Byty ===
  *nejmenší jednotka, na kterou můžeme ukládat

=== Proměnná ===
  *objekt, který má pevně stanovené označení (identifikátor) a nese určitou hodnotu
    *hodnota se může v průběhu procesu měnit

=== Identifikátor ===
  *skládá se z písmen a číslic a jiných povolených znaků (začíná vždy písmenem)
    *označení (jméno) proměnné

=== Výraz ===
  *přepis pro získání hodnoty (konstanta, aritmetický výraz, …)

==== Příkazy ====
=== Přiřazovací příkaz ===
přiřazovací znaménko:
<code pascal>:=</code>
přiřazovací příkaz:
<code pascal>proměnná := výraz</code>

=== Příkaz vstupu ===
read/readln (seznam proměnných)

=== Příkaz výstupu ===
write/writeln (seznam proměnných/'text na vystup')

==== Způsoby zápisu algoritmu ====
  *Slovně -- v přirozeném jazyce popřípadě s matematickými vzorci
  *Graficky -- vývojový diagram
  *Programovacím jazykem (vyšším, nižším-strojovým kódem, pseudokódem)

==== Vývojové diagramy ====
//jazyk vývojových diagramů je normalizován a přehled značek lze nalézt na internetu//

==== Strukturované programování ====
Zásady pro snadnou modifikovatelnost a přehlednost metod:

  ***Metoda shora dolů** -- složitější problém rozdělíme na jednodušší, které pak samostatně řešíme:
    -Úlohu postupně rozkládáme na jednodušší, takto postupujeme tak dlouho, dokud je to třeba
    -Nejprve určíme podobu vstupních a výstupních dat, pak sestavíme hrubý vývojový diagram (hlavní program)
    -Podle něj budeme úlohu dále rozkládat
    -Při rozkladu se používají pouze doporučené struktury (Posloupnost, Větvení, Cyklus)
    -Prvky struktur mohou být opět tvořeny strukturami
  ***Posloupnost** – posloupnost příkazů uzavřená mezi Begin a End (do složených závorek atp.)
  ***Větvení** – If (if podmínka then příkaz else příkaz;) Case (case řídící proměnná of : příkaz_1; 2:příkaz_2; ...)  
  ***Cyklus**
    *S podmínkou na začátku – While: While podmínka do Příkaz; (Dokud platí podmínka, prováděj příkaz)
    *S podmínkou na konci – Repeat: Repeat Příkaz until podmínka; (Prováděj příkaz, dokud neplatí podmínka)
    *S určeným počtem opakování – For: For řídící proměnná := počáteční hodnota to/downto koncová hodnota do Příkaz/Posloupnost příkazů (Prováděj dokud pokud je ř. prom. v intervalu <poč. hodnota; konc. hodnota>)

FIXME

*Jeden začátek, jeden konec

*Rozlišování vstupních, výstupních a pomocných proměnných

*Každá struktura má jeden vstup a výstup

Při řešení úlohy ji musíme specifikovat:

*Musíme znát vstupní údaje a vědět, co chceme získat (délka strany čtverce a, jeho objem a povrch)
*Vstupní hodnoty (známé před začátkem řešení) musí být procesoru dodány v průběhu realizace procesu, nemohou být libovolné, musí splňovat vstupní podmínku (a >0, a je celé číslo)
*Výstupní hodnoty zadáváme pomocí výstupní podmínky, kterou musí splňovat (Objem = a^3, Povrch = 6a^2)

Verifikace a testování

Verifikace Algoritmu = ověření správností algoritmu (např pomoc testovacích/trasovacích tabulek)

Trasovací tabulka – do záhlaví tabulky zapíšeme hodnoty proměnné a pod ně zapisujeme hodnoty proměnných, které se po provedení příslušného kroku změnily (jako krokování na papíře). Neslouží k důkazu správnosti algoritmu!

Programovací jazyk

Při sestavování programů pro řešení konkrétní úlohy řešíme dva základní okruhy:
1)Sestavit algoritmus (nalézt postup vedoucí k řešení úlohy)
2)určit, jakými objekty v programu budou reprezentována data

=>Programovací jazyk musí poskytnout:
1)Prostředky pro formulaci příkazů k provedení akcí
2)Prostředky pro popis dat

Abeceda jazyka (Pascal)
a) písmena latinské abecedy (a-z)
b) číslice desítkové soustavy (0-9)
c) speciální symboly (operátory, čárky, tečky, ...)

Z nich tvoříme na lexikální (slovotvorné) úrovni lexikální jednotky=elementy (podobně jako v mateřštině slova).
Lexikální jednotky mohou být:

1)Klíčová slova – domluvená slova používaná v programu, chápou se jako nedělitelný symbol (jediný znak)
2)Identifikátory – veškerá označení (jména objektů, proměnných, konstant, programů, datových typů, procedur, fcí, ...)   

	*Jako identifikátor nelze použít klíčové slovo!
	*Jedním identifikátorem nelze označit dva různé objekty v jednom bloku!
	*Standardní identifikátor – význam je definován jazykem, je předepsaný
3)Čísla – zapisujeme v desítkové (i šestnáctkové) soustavě.
známe celá čísla ve tvaru se znaménkem/bez znaménka
nebo reálná čísla, která zapisujeme buď v desetinném nebo semilogaritmickém tvaru
4)Řetěz – posloupnost znaků uzavřená mezi apostrofy ('například když vypisujeme uživateli')

5)+Oddělovače lexikálních jednotek: mezera, přechod na nový řádek, komentář (libovolná posloupnost znaků uzavřená do složených závorek/mezi jednoduchou závorku a hvězdičku/za dvěma lomítky do konce řádku atp)

Výraz
=Předpis pro výpočet hodnoty
-Může být na různých přesně definovaných místech
-může obsahovat
a) operandy (proměnné, konstanty, funkce, …)
b) operátory (+, -, *, div, mod, …)
c) závorky (jen kulaté) 
-může být
a) aritmetický výraz => hodnotou je číslo
b) logický výraz => hodnotou je logická hodnota (true/false)

Syntaxe (Syntaktická pravidla; Syntax error)
-pravidla pro vytvoření přípustných zápisů v daném jazyce

Sémantika (Sémantická pravidla)
-pravidla, určující jaký význam má syntakticky správně vytvořený zápis

Priorita operátorů

1)NOT
2)*, /, div, mod, AND
3)+, -, OR
4)=, <, >, <>, <=, => (relační operátory)

Struktura programu

Program = Hlavička + Blok (Tělo)

Hlavička = Program a identifikátor programu

Blok (Tělo) = část deklarací a definicí + příkazová část programu
                   = každý program, procedura, funkce
                   - každý příkaz je ukončen středníkem, za posledním Endem programu je tečka

Část definicí a deklarací – definují se zde proměnné, typy, konstanty, podprogramy, ...

Příkazová část programu – posloupnost příkazů uzavřená mezi Begin a End

Programovací jazyk Pascal

Příkazy v Pascalu

Příkaz – předpis pro prováděnou akci

z hlediska funkce:
a) Příkazy k provedení základů
b) Příkazy určující pořadí provádění dalších příkazů
Pořadí provádění příkazů určujeme
1)pomocí příkazu skoku (GoTo – většinou se jeho používání snažíme vyhnout pro přehlednost)
2)Strukturovanými příkazy (např cyklů)

z hlediska strukturovanosti:
a) jednoduché – takové příkazy, které neobsahují jiné příkazy
b) strukturované – obsahují další příkaz(y)

Jednoduché příkazy

Přiřazovací příkaz
proměnná := výraz
-nejprve se vypočítá výraz na pravé straně a poté se hodnota přiřadí do proměnné vlevo
-proměnná i výraz musí být stejného typu 

Příkaz vstupu (čtení)
read (seznam proměnných) 
-hodnota na vstupu se přiřadí proměnné uvedené jako parametr (musí být stejného typu)
readln (seznam parametrů)
-přečte ze vstupu všechno, co na něm aktuálně je, co patří do proměnné do ní uloží a zbytek zahodí

Příkaz výstupu (výpis)
write (seznam proměnných) nebo ('text')
-parametrem je buď proměnná nebo řetěz (posloupnost znaků uzavřená mezi apostrofy)
-vypíše na výstup svůj parametr
writeln (seznam proměnných) nebo ('text')
-po výpise „odřádkuje“ a příští výpis se píše na nový řádek

Prázdný příkaz
;
-nevykoná žádnou akci, ale může znehodnotit příkaz za ním následující
před end nemusíme psát středník (prázdný příkaz se provede a end to nijak neohrozí)
před until nebo else středník nesmíme napsat, protože to jsou jen části příkazů (If a repeat) a středník příkaz ukončuje, tedy by se zbytek příkazu neprovedl a program by přeskočil na začátek následujícího příkazu

Strukturované příkazy

1)Příkaz složený
2)Příkazy podmíněné
3)Příkazy cyklů

Příkaz složený
Begin Příkaz_1; Příkaz_2; … Příkaz_n end;
=Posloupnost příkazů uzavřená mezi Begin a end
-program jej chápe jako jeden příkaz a můžeme jej tedy použít ve všech příkazech

Příkazy podmíněné
1)If 
a) neúplný: If Podmínka then Příkaz
b) úplný: If Podmínka then Příkaz
                                    else Příkaz_2;
-Podmínku tvoří logický výraz (může být vyjádřena zápisem relace s použitím relačních operátorů)

2)Case
Case řídící proměnná of 1: Příkaz_1
                                                      2: Příkaz_2 …
                                                      n: Příkaz_n
               end;
-Při vícenásobném větvení
-řídící proměnná je většinou typu integer (může však být jakéhokoli jiného, ten se však musí shodovat se znaky, které určují, který příkaz se bude provádět)

Příkazy cyklů
-umožňují opakované provádění (posloupnosti) příkazů

1)While: While Podmínka do Příkaz; (Dokud platí podmínka, prováděj příkaz)
-S podmínkou na začátku
2)Repeat: Repeat Příkaz until Podmínka; (Prováděj příkaz, dokud neplatí podmínka)
-S podmínkou na konci
3)For: For řídící proměnná := počáteční hodnota to/downto koncová hodnota do Příkaz/Posloupnost příkazů (Prováděj dokud pokud je řídící proměnná v intervalu <počáteční hodnota; koncová hodnota>)
-S určeným počtem opakování 
-to pro stoupající cyklus, downto pro klesající cyklus
-Poč. a konc. hodnota musí být stejného typu jako řídící proměnná (ordinárního)
-Vypočítají se výrazy (jedinkrát) a řídící proměnné se přiřadí počáteční hodnota (první vstup ze shora, následně už jen z boku-pro diagram)
-Je zakázáno měnit hodnotu řídící proměnné uvnitř cyklu
-po skončení cyklu je hodnota řídící proměnné nedefinovaná

Datové typy

Datový typ 
-určuje, jakých (z jakého oboru) hodnot bude proměnná nabývat. 
Každá proměnná může nabývat pouze určitých hodnot (V Pascalu musí být předem definována=určeno jakých typů může nabývat)
je určen:
1)množinou přípustných hodnot (celá čísla, reálná čísla, true/false, znaky, ...)
2)množinou přípustných operací (závislé od datového typu-to pro co je obor uzavřený)
3)identifikátorem (jméno)

je definován:
1)jazykem - předdefinován
2)programátorem v programu

může být:
1)ordinální – můžeme určit, jaký prvek bude následovat či předcházet
2)neordinální – nelze určit, jaký prvek je předchůdcem či následníkem daného prvku

Typ (v Pascalu) může být:
1)jednoduchý
a) standardní (integer, real, boolean, char)
b) programátorem definovaný (výčtový typ, typ interval)
2)strukturovaný (pole, záznam, množina, soubor)
3)ukazatel

Ordinální typy
-množina hodnot je uspořádaná: pro každé dvě hodnoty lze určit, která je větší (menší)
-každé hodnotě je přiřazeno ordinální číslo
-můžeme určit následující a předcházející hodnotu
-jsou pro ně definovány standardní fce:	
1)ord – přiřazuje každé hodnotě její ordinální číslo [ord (8) – ord (0) = 8; ord (0) = 48; ord (true) = 1]
2)succ – určuje následníka (následující hodnotu v dané množině) [succ (false) = true; succ (3) = 4 ]
3)pred – určuje předchůdce [pred (false) není definován; pred (true) = false]
-ordinální číslo – pořadové číslo hodnoty v množině přípustných hodnot
-ordinálními typy jsou všechny, krom real

Jednoduché typy:

4 základní předdefinované (standardní) typy:	

1)Integer (celá čísla; +, -, …)
2)Real (desetinná čísla; +, -, *, …; není ordinální!) 
3)boolean (logické hodnoty; AND, OR, …)
4)char (znakové hodnoty)

*Integer
množina příp. hodnot: množina celých čísel zobrazitelná v počítači
-Konstanta MAXINT: hodnota největšího zobrazitelného čísla
-Oblast přetečení: oblast mimo rozsah zobrazitelných hodnot
množina příp. operací: aritmetické (+, -, *, div, mod; výsledek nemusí být integer) relační (<, <=, ==, <>, =>, >)

*Real
množina příp. hodnot: množina reálných čísel zobrazitelná v počítači (oblast mimo tento rozsah je oblast přetečení)
množina příp. operací: aritmetické (+, -, *, div, mod; výsledek je typu real) relační (<, <=, ==, <>, =>, >)
-možnosti zápisu desetinného čísla
1)desetinný tvar (číslo s desetinnou tečkou)
2)semilogaritmický tvar
-tvar: mantisa E exponent (5E+4 „pětkrát deset na čtvrtou“)
-mantisa-celé číslo (nebo číslo reálné v desetinném tvaru) vyjadřující násobek desítky na x-tou
-exponent-celé číslo, vyjadřující stupeň mocniny (nakolikátou)
Převod hodnot 
1)integer -> real - provádí se automaticky (za tečku se přidají nuly)
2)real -> integer – musíme zaokrouhlit nebo odseknout desetinnou část, neprovádí se automaticky

*Boolean
množina příp. hodnot: true/false {true (1) > false (0)}
množina příp. operací: relační (<, <=, ==, <>, =>, >), logické (NOT, AND, OR) 

*Char
množina příp. hodnot: množina všech přípustných znaků (uspořádaná množina hodnot určená implementací – ASCII)
některé znaky jsou nezobrazitelné
množina příp. operací: relační operace
standardní fce: ord, chr, před, succ; 

Typy zavedené programátorem:

Nový typ se v programu zavádí popisem: 
1)bez pojmenování v deklaraci proměnné
2)v části definicí typů s pojmenováním	
{Program ...
type ident = ...
Var … }
1) typ výčtový – vypíšeme prvky {type ident = (červená a modrá)}
2) typ interval – uvedeme interval {type ident = 1..10}

*Výčtový typ
-definuje se výčtem hodnot
definice: type (klíčové slovo) SEMAFOR (identifikátor) = (Zelená, žlutá, červená) (výčet, popis); 
-hodnoty výčtového typu nelze číst ani zobrazit

*Typ interval
-proměnná nabývá hodnot z intervalu hodnot jiného (hostitelského) typu
-popis typu:  
type ident = konstanta1..konstanta2 
-konstanta1 se nazývá horní mez, konstanta2 dolní mez (nemusí být jen kladné)
-hostitelský typ - typ, ze kterého je interval vybírán, určen typem konstant
-pro typ interval jsou definovány stejné operace a fce jako pro hostitelský typ

Strukturované typy:

*Pole (Array, matrix, ...)
-datová struktura skládající se z pevného počtu složek stejného typu (homogenní) uspořádaných v jednom či více rozměrech
-složky pole označujeme identifikátorem pole a indexy
popis typu: type array [typ indexu] of typ složky
-typ indexu musí být ordinální
-typ složky je libovolný 
-typ indexů i složky může být zadán popisem typu ([1..7]) nebo identifikátorem typu (měsíc = 1..12; of měsíc)
-v případě užití definice [1...N] musí být N konstantou, není to proměnná 
-složky = indexované proměnné 
-typ indexu musí být ordinální
-nelze je přečíst nebo vypsat zároveň (For)

*Řetěz (String)
-posloupnost znaků (max 255)
-v nultém bytu je uložen znak s ordinálním číslem odpovídajícímu aktuální délce řetězu (při zřetězení se automaticky mění)
popis typu: type jméno = string [možné omezení počtu znaků] 
Ve standardním Packalu je popis typu řetěz: Packed array [1..n] of char
-lze přečíst zároveň
-k jednotlivým znakům lze přistupovat také pomocí indexů (jako u pole; Pozor na nultý byte!)
-do čísla, jež vyjadřuje omezení počtu znaků se nepočítá nultý byte
-přípustné operace
1)zřetězení
2)relační (porovnávají se ordinální čísla)

*Záznam
-heterogenní strukturovaný datový typ (může se skládat ze složek různého typu) o pevném počtu složek
složky typu záznam se nazývají položky a označují se identifikátory
popis typu: 
Student = record
jméno: String[20];
věk:integer;
propadl:boolean;
end;
Var S :Student;
read (S.jméno) (tečková notace: S=identifikátor proměnné, jméno=identifikátor položky)
-abychom nemuseli opisovat identifikátor proměnné, použijeme WITH
popis: WITH S do Begin
                              read (jméno);
                              read (věk);
                              end;          
-pozor na práci s boolean

*Case
-pro strukturované větvení
-skládá se z výrazů ordinálního typu a seznamu příkazů, z nichž každému předchází jedna nebo více konstant
popis typu: 
Case výraz ord. typu of 
konstanta1:P1
konstanta2:P2
...
konstantaN:PN
else PX
end;
-nejprve se vyhodnotí výraz ordinálního typu a pak se provede příkaz, před kterým je uvedena konstanta odpovídající hodnoty
Pokud se hodnota ordinálního výrazu neshoduje s žádnou z konstant tak se:
1)neprovede nic
2)provede příkaz za else
 
Standardní funkce

abs (A)
výsledek (hodnota fce): absolutní hodnota argumentu
typ argumentu A: integer (real)
typ výsledku: integer (real)
sqr
výsledek (hodnota fce): druhá mocnina argumentu
typ argumentu A: integer (real)
typ výsledku: integer (real)
sqrt
výsledek (hodnota fce): odmocnina z argumentu (pouze pro Argument >=0, jinak chyba) 
typ argumentu A: real/integer
typ výsledku: real
sin
výsledek (hodnota fce): sin Agumentu (pro Argument zadaný v radiánech)
typ argumentu A: real/integer
typ výsledku: real
cos
výsledek (hodnota fce):  cos Argumentu (pro Argument zadaný v radiánech)
typ argumentu A: real/integer
typ výsledku: real
trunc
výsledek (hodnota fce): celá část Argumentu
typ argumentu A: real
typ výsledku: integer
round
výsledek (hodnota fce): zaokrouhlena hodnota argumentu {Pro A>=0 trunc (A+0.5) Pro A<0 trunc (A-0.5)}
typ argumentu A: real
typ výsledku: integer
Typy objektů
1)Proměnná 
2)konstanta
a) nepojmenovaná konstanta (nemá identifikátor; přímý zápis)
b) pojmenovaná konstanta 
-označená identifikátorem
-v průběhu programu se nemůže měnit 
-definice: const identifikátor = konstanta (Pí = 3,14)
3)výraz
-je dán pravidly pro vyhodnocování výrazu

Rozsah platnosti proměnné
globální proměnná 
platí všude, v běhu celého programu (mohou sloužit k předávání hodnot mezi bloky)
deklaruje se v hlavním programu
lokální proměnná 
vzniká v okamžiku zavolání podprogramu a zaniká v okamžiku jeho ukončení (uvolňuje místo)
deklarují se uvnitř proceduryKaždá proměnná je platná i v blocích vnořených
Každá proměnná je platná i v blocích vnořených
Podprogramy

=jednotlivé dílčí podúlohy, získané rozkladem řešení původní úlohy, definované v programu
-Umožňují použít vícenásobně jedenkrát zapsaný kód
-Jejich používáním se zápis stává přehledným a logicky strukturovaným
-Používání pp usnadňuje kontrolu programu
-Umožňuje snadné modifikace kódu (na jedno místě)
-Dělíme je na:
1)Procedury
2)Funkce

Procedury

Deklarace
-uvádí se pod Var
procedure jméno (seznam formálních parametrů); 
lokální deklarace a definice;
begin
příkazová část
end; 

Volání procedury
-jednoduchý příkaz
jméno(seznam skutečných parametrů);

Procedury s parametry
-parametry jsou proměnnými, které vznikají při zahájení a zanikají při skončení procedury
formální parametry – uvádí se v deklaraci procedury (s definicí svého typu), při volání jsou nahrazeny skutečnými 
skutečné parametry – podle předem daných pravidel (záleží na pořadí) nahradí formální parametry

parametry volané hodnotou 
-vstupní 
-jejich změna v těle podprogramu nemá vliv na skutečný parametr (při volání proc se vytvoří lokální proměnná, do které se uloží hodnota skutečného parametru)
-skutečným parametrem mohou být proměnná, konstanta či výraz kompatibilní vzhledem k přiřazení s typem formálního parametru 
parametry volané odkazem (VAR)
-výstupní
-výpočet procedury probíhá se skutečným parametrem
-skutečným parametrem musí být proměnná

 Funkce

Definice
function jméno (seznam formálních parametrů) identifikátor typu; 
lokální deklarace a definice;
begin
příkazová část (alespoň jednou obsahující jméno:=hodnota;);
end; 

Volání fce
-výraz
jméno(seznam skutečných parametrů);

-Slouží k popisu dílčích algoritmů pro výpočet jediné hodnoty (výsledku)
-Funkcí nemůže být strukturovaný dat. typ
Rekurze

=podprogram, který je definován pomocí sám sebe (ve svém těle volá sám sebe)

1)přímá – podprogram A volá přímo podprogram  A
2)nepřímá podprogram A volá podprogram B ( a podprogram B volá...podprogram N)  podprogram N volá podprogram A

-nahrazuje cyklus
-před rekurzivním voláním musí být podmínka, která ukončuje cyklus
-příklad Faktorial, Hanoiské věže,