http://geo.mff.cuni.cz/~lh/NOFY056
Poznámky k přednášce
PROGRAMOVÁNÍ PRO FYZIKY (NOFY056)
Podoby programování
Podle účelu: numerické modelování (vědeckotechnické výpočty), vizualizace, databáze, web, rozhraní, ...
Podle způsobu: imperativní programování, objektově orientované programování, funkcionální programování, ...
Nástroje: programovací jazyky
– strojový kód, assembler
– klasické programovací jazyky (C, Fortran, Pascal; C++, Java, LISP, ...)
Fortran: od 1957; normy 66, 77, 90, 95, 2003, 2008
C:
od 1968; normy C89, C99; východisko objektově orientovaného jazyka C++ (od 1983)
Pascal: od 1971; norma ISO 7185; Object Pascal
typické užití: pro vědeckotechnické výpočty C/C++ a Fortran, Pascal pro výuku
– skriptovací jazyky (příkazový interpret Windows, unixové shelly, Perl, Python, ...)
– interaktivní systémy (Mathematica, Matlab, Octave, ...)
Viz cs.wikipedia.org/wiki/Programování, cs.wikipedia.org/wiki/Imperativní_programování
Literatura
Poznámky k této přednášce
Ledvinka T., utf.troja.mff.cuni.cz/~ledvinka
Hanyk L., geo.mff.cuni.cz/~lh/NOFY056
Pascal
Satrapa P., Pascal pro zelenáče, Neocortex Praha, 2005
Free Pascal: Reference guide, www.freepascal.org/docs-html/ref/ref.html
Polách E., Programování v jazyku Turbo Pascal, PFJU České Budějovice, 1993, home.pf.jcu.cz/~edpo
C, Fortran
Herout P., Učebnice jazyka C, Kopp České Budějovice, 2010
Virius M., Od C k C++, Kopp České Budějovice, 2000
Kernighan B. W., Ritchie D. M., Programovací jazyk C, Computer Press Brno, 2008
Metcalf M., Reid J., Cohen M., Modern Fortran Explained, Oxford Science, 2011
Numerické metody, programovací techniky
Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P., Numerical Recipes: The Art of Scientific Computing,
Second Edition, Cambridge University Press, 1992, otevřený přístup: www.nrbook.com
C book: www.nrbook.com/a/bookcpdf.php, Fortran book: www.nrbook.com/a/bookfpdf.php
Third Edition, Cambridge University Press, 2007, www.nr.com
Töpfer P., Algoritmy a programovací techniky, Prometheus Praha, 1995, dotisk 2010
Překladače
Pascal
Delphi (Windows), www.slunecnice.cz/sw/delphi, artax.karlin.mff.cuni.cz/~konim5am/vyuka/nprg030/delphi.html
Free Pascal a jeho vývojová prostředí, www.freepascal.org, www.lazarus.freepascal.org, ims.mii.lt/fps
GNU Pascal, www.gnu-pascal.de
C, Fortran (volně dostupné překladače)
GNU C/C++, gcc.gnu.org
GNU Fortran, gcc.gnu.org/fortran, a příbuzný g95, g95.org
Vývojové prostředí NetBeans pro GNU překladače, netbeans.org
Microsoft Visual C++ Express 2010 (Windows), www.microsoft.com/express
C, Fortran (komerční překladače)
Intel Composer XE, software.intel.com/en-us/articles/intel-composer-xe
Portland Group C/C++/Fortran, www.pgroup.com
http://geo.mff.cuni.cz/~lh/NOFY056
Strukturované programování
a) preference návrhu shora dolů (dekompozice)
fáze řešení úlohy: návrh, realizace, ladění
snižování úrovní abstrakce, dekompozice, iterace
b) modularita a stavebnicovost programu
samostatné programové jednotky (separátní překlad, knihovny)
vnořované bloky (lokalita dat i operací)
moduly (hlavička s rozhraním, oddělené tělo s implementací)
vlastnosti: samostatnost, univerzálnost, definované (co nejmenší) rozhraní, jeden i/o bod, reentrantnost
c) užívání vhodných řídicích konstrukcí (sekvence, větvení, cykly) a datových struktur (proměnné, pole, záznamy)
řízení běhu programu: sekvence, větvení do 2 cest, větvení do více cest, cyklus s řídicí proměnnou,
cyklus s podmínkou, skoky v cyklu, volání procedury
datové struktury:
standardní typy = celá čísla, racionální („reálná“) čísla, logické hodnoty, znaky
složené typy = pole, záznam aj. (množina, soubor, procedura, objekt)
d) formální úprava programu
mnemotechnické identifikátory
grafická úprava výpisu
komentáře
Algoritmus
~ recept, metoda, technika, procedura, rutina
etymologie:
Peršan Muhammad al-Khwārizmī (autor knihy Kitāb al-jabr wa’l-muqābala)
vlastnosti:
konečnost (rozumná konečnost)
proveditelnost, jednoznačnost (programovací jazyky, programy)
vstup (0+) a výstup (1+)
ale i jiné:
časová a paměťová složitost, adaptibilita, jednoduchost, elegance
Analýza složitosti algoritmu
obvykle závislost potřebného času a paměti na velikosti vstupních dat
čas:
jednotkou nikoliv sekundy, ale počty elementárních operací
paměť: jednotkou (mega)byty nebo počty proměnných
odhad složitosti v nejhorším vs. v průměrném případě
asymptotická složitost: O(log N), O(N), O(N log N), O(N2), O(N3), O(2N), O(N!) aj.
– polynomiální, logaritmická, exponenciální
– někdy podstatná i multiplikativní konstanta
příklady časové složitosti algoritmů:
O(log N)
hledání půlením v setříděném seznamu
O(N)
řešení soustavy lineárních rovnic s třídiagonální maticí
O(N log N)
rychlá Fourierova transformace, třídění metodou Quicksort
bublinkové třídění
O(N2)
násobení matic, přímé řešení soustavy lineárních rovnic s plnou maticí
O(N3)
O(N!)
výpočet determinantu násobením řádku se subdeterminanty
Ukázka: Euklidův algoritmus pro největšího společného dělitele dvou kladných celých čísel
Symbolický zápis
Input:
m, n positive integer
E0 (příprava): if m<n then swap(m,n)
E1 (dělení):
r := zbytek po dělení m/n
E2 (test nuly): if r=0 then goto Output
E3 (redukce): m := n; n := r; goto E1
Output:
write(n)
Odhad průměrné složitosti Euklidova algoritmu:
– pro dané n spočíst počet kroků E1 pro všechna m = 1, 2, ..., n a položit Tn rovno jejich průměru
– prý Tn ~ 12 ln 2 / pi2 x ln n pro velká n
– výjimka: závislost nikoliv na velikosti, ale na konkrétních hodnotách vstupních dat
Download

Poznámky k přednášce PROGRAMOVÁNÍ PRO FYZIKY (NOFY056)