Úvod do programování
Základní literatura
Töpfer, P.: Algoritmy a programovací techniky, Prometheus, Praha
učebnice algoritmů, nikoli jazyka
pokrývá velkou část probíraných algoritmů
Satrapa, P.: Pascal pro zelenáče, Neokortex, Praha
učebnice jazyka Pascal
v podstatě vše, co budeme probírat
přednášky se budou z velké části držet linie daných knih
Algoritmus
podle jména matematika – Abū ʻAbd Allāh Muhammad ibn Mūsā al-Chwārizmī
postup, návod jak vyřešit daný problém
důležité
konečnost
správnost
složitost (efektivita)
Složitost algoritmu
základní dělení:
paměťová
alg. při stejných datech použije více/méně paměti
alg. při stejných datech poběží delší/kratší čas
časová
otázka vzájemného poměru
preferujeme spíše vyšší časovou efektivitu
omezíme se jen na odhady
Časová složitost
nejhorší případ
průměrný případ
asymptotická složitost
porovnávání algoritmů
„pro velká data“
rychlost růstu času v závislosti na velikosti dat
symbol „velké O“
pouze nejrychleji rostoucí člen
v praxi: O(log2 N), O(N), O(N2), … , O(2N)
Příklad
problém: vyhledat hodnotu v setříděné posloupnosti (případně oznámit, že není) možnost volit různé algoritmy
postupné hledání – O(N)
půlení intervalů – O(log2 N)
posloupnost rozdělíme na dvě poloviny podíváme se, ve které hledat opakujeme, dokud nenajdeme nebo nevyloučíme
Složitost problému
jak nejrychleji lze daný problém řešit
Pascal
vznik počátkem 70. let
autor Niklaus Wirth
vyšší programovací jazyk určený pro výuku
překladače a vývoj. prostředí
FreePascal (+ Lazarus) – svobodný
Borland (Turbo) Pascal (+ Delphi, Kylix)
do verze 5.5 uvolněn, poslední verze 7.0
GNU Pascal – svobodný
Nazdar světe!
program Hello; begin write('Hello world!'); end.
Práce programátora
vymyslet správný, vhodný, rychlý algoritmus (nejtěžší) a uživatelské rozhraní přepsat jej do řeči pro počítač – v nějakém programovacím jazyce
přeložit, opravit chyby
otestovat
opravit chyby
otestovat
opravit chyby, ...
Programování
program v pr. jazyce – obyč. textový soubor
převezme kompilátor
kontrola syntaktických chyb
úspěšná kompilace – program v poč. jazyce – binární soubor spouštění, testování sémantické správnosti
Vývojová prostředí
k tvorbě programu s pomůckami
ke kontrole syntaxe
k překladu
k opravě chyb
sledování proměnných
krokování programu
apod.
Struktura programu
hlavička (někdy součást deklarace)
název programu, načítané knihovny
deklarace
typy, proměnné, podprogramy
příkazy (tělo programu)
klíčová slova vs. identifikátory
Nazdar světe!
program Hello; begin write('Hello world!'); end.
Štábní kultura
v podstatě individuální věc
je vhodné zajistit určitou přehlednost
Pascal ignoruje bílé znaky
mnemotechnické identifikátory
dodržovat velikost písmen, i když Pascal není case-sensitive časté kometáře
Přiřazovací příkaz
symbol := uložení do proměnné A := 2;
do proměnné A přiřaď dvojku
nejčastěji používaný příkaz
Vstup a výstup
procedury Read a Write načítání a zápis z/do standardního vstupu/výstupu
tj. pro nás nyní příkazový řádek
relikvie? Nikoli!
načti proměnnou A Read(A);
vypiš proměnnou A Write(A);
a co udělá Write('Hodnota je: ',A); ?
varianta Writeln, Readln
Deklarace proměnných
každá proměnná musí být deklarována
uvádíme na počátku programu
klíčové slovo var
proměnná: typ;
různé typy a rozsahy proměnných
integer
real
char
atd.
Příklad program dvojka; var X: integer; begin X := 2; Write('X je :', X); end.
Jiný příklad program mocnina; var X, X2: integer; begin Read(X); X2 := X * X; Write('Druha mocnina X je :', X2); end.
Operace s čísly
+, -, *, /, mod, div
pozor na neceločíselné dělení celých čísel
Podmíněný příkaz
rozvětvění programu
jedna nebo dvě větve
pokud je splněna podmínka – např. (ne)rovnost if – then – else
před else nesmí být středník
lze vnořovat
více příkazů nutno sevřít do bloku
košile bližší než kabát
While cyklus
cykly – pro opakování „téže“ činnosti provádí, dokud je splněna podmínka while – do příklad: X := 0; while X < 10 do begin writeln(X*X); X := X + 1; end;
Repeat-until cyklus
podobně jako while řízen podmínkou
repeat – until
until = dokud není!
narozdíl od while-cyklu vždy proběhne alespoň jeden krok
