• 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

• 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

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

• popis akce

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

• 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

• je rozdělena na byty

• slučují se po 8 do bytů

• nejmenší jednotka, na kterou můžeme ukládat

• 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

• 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é

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

přiřazovací znaménko:

:=

přiřazovací příkaz:

proměnná := výraz

read/readln (seznam proměnných)

write/writeln (seznam proměnných/'text na vystup')

• 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)

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

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:
  1. Úlohu postupně rozkládáme na jednodušší, takto postupujeme tak dlouho, dokud je to třeba
  2. Nejprve určíme podobu vstupních a výstupních dat, pak sestavíme hrubý vývojový diagram (hlavní program)
  3. Podle něj budeme úlohu dále rozkládat
  4. Při rozkladu se používají pouze doporučené struktury (Posloupnost, Větvení, Cyklus)
  5. 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>)

*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,