MFF UK / Ústav teoretické fyziky / Tomáš Ledvinka
Přednášky
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
  Úvod
  Programy a algoritmy
  Píšeme program
  Píšeme program II
  Procedury a funkce
  Malujeme funkce
  Chyby. Typy I.
  Typy II. Pole a Záznamy
  Pole II.Řetězce.Soubory.
  Gnuplot.Interpolace...
  Matice. Velké O...
  Fronta,Zásobník. Postscript
    Fronta
    Zásobník
    Postscript I
    Postscript II
    Postscript - cvičení
  Bin. soubory, ...
  Ukazatele,Objekty, ...
Počítačová algebra
Klasická elektrodynamika (2.r)
Vybrané partie OTR

Cvičení
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
Teoretická mechanika (2.r)
Klasická elektrodynamika (2.r)


Věda
. . . . . . . . . . . . . . . . . . . . . . . . . .
Diskové zdroje v OTR
Hyperbolické systémy v OTR


Kontakt
. . . . . . . . . . . . . . . . . . . . . . . . . .
Email
Konzultační hodiny


Ostatní
. . . . . . . . . . . . . . . . . . . . . . . . .
Mallorca
Ze společnosti

Zásobník

Jedničkou mezi lineárními datovými strukturami je zásobník. Od prvopočátku počítačové doby se totiž používá pro řešení otázky kam se má vrátit běh programu po ukončení podprogramu a v posledních desetiletích se také stará o postor a život lokálních proměnných procedur.

Poznámka: (Rozpor idejí a reality): V matematice se zavedla dvě značení pro operace s dvěma operandy:
1. Plus(A,B)
2. A Plus B
Protože ale operaci nemůžeme obecně uskutečnit dokud nemáme k dispozici oba operandy, měl by být preferovaným zápisem tento:
A B Plus

Např. 3+4*2 bychom přece měli psát jako
4 2 * 3 +

Podobně sice v Pascalu píšeme Secti(x,Soucin(y,z)), ale je zřejmé že vše probíhá jak je psáno výše:

Ilustrace (na přednášce): Zásobník volání a vůbec jak v principu probíhá předávání parametrů, volání funkcí a alokace lokálních proměnných (bez konstrukce ebp-leseni /tzv. stack frame/)

Ilustrace na přednášce: Vyhodnocení o něco složitějšího reálného aritmetického výrazu na zásobníkovém stroji (bez FPU registrů) ln(-x+sqrt(x**2++1))

Cvičení: Zásobník a prohledávání do hloubky - Změňte program pro hledání souboru tak aby prováděl hledání do hloubky. Napište dvě verze: jednu s explicitním zásobníkem, druhou jen s použitíme zásobníku volání tj. pomocí rekurse. Ze způsobu prohledávání adresářů je zřejmý název prohledávání do hloubky.

U datové struktury zásobník máme opět k dipozici tři operace: Vložení, Výběr a Test na prázdný zásobník.

[]
Vlož(A)
[A]
Vlož(B)
[AB]
Vlož(C)
[ABC]
Vyber --> C
[AB]
Vlož(D)
[ABD]
Vyber --> D
[AB]
Vlož(E)
[ABE]


Při realizaci v poli nám stačí jediná stavová proměnná a snad to ani nejde napsat jinak než O(1).

Ilustace (na přednášce): prohledávání do hloubky, viz [Příklady z programování]

Pozn. Zásobník v dynamickém poli a jak často alokovat a proč ne pokaždé SetLength.

Cvičení: Změňte minulý program aby porhledával adresářový strom do hloubky.

.