Příklady z přednášek PRM030 PRG031 paralelka Y

Tato stránka obsahuje některé programy z paralelky Y přednášek PRM030 Programování I a PRG031 Programování II konané ve školním roce 2004/5 pro studenty informatiky 1.ročníku MFF UK.

Budu se snažit, aby na ní studenti nalezli zdrojové texty rozsáhlejších a důležitých programů probíraných na přednášce. Většinou bude uveden pouze zdrojový text, nikoli rozsáhlejší komentované zadání úlohy nebo diskusi různých řešení.
Primárním cílem není vytvářet učebnici, ale "pouze" odbřemenit studenty od nutnosti na přednášce opisovat dlouhé texty. Předpokládá se tedy, že si student přesné zadání úlohy a podrobnější diskusi o programu zapíše na přednášce.

1. Demonstrační příklad na zaokrouhlovací chyby.
2. Výpočet hodnoty čísla zapsaného v poziční soustavě o obecném základě.
3. Kvadratický algoritmus pro nalezení délky nejdelší rostoucí vybrané posloupnosti (dokáže nalézt i tuto posloupnost)
4. Algoritmus pro nalezení délky nejdelší rostoucí vybrané posloupnosti mající složitost N*log(N)
5. Jednotka utab obsahujici typ tab reprezentujici tabulku.
6. Jednotka obsahující knihovnu několika podprogramů pro hledaní v tabulce.
   Jednotka užívá typ tabulky importovaý z jednotky utab.
7. Program hledá M navzájem se neohrožujících se dam na šachovnici M x M.
8. Nerekursivní a rekursivní verze programu hledajícího všechny rozklady zadaného čísla na sčítance
9. Program realizující jednoduchý sekvenční algoritmus hledající reflexivní, symetrický a transitivní uzávěr relace nad čísly z intervalu 0..M
   Současně jde o příklad na zacházení s množinami.
10. Realističtější verze předchozího programu. Do vytvářené relace bere jen ty prvku, které se explicitně objevili na vstupu, vstup a výstup do textového souboru.
11. Třídící algoritmy vnitřního třídění
• Programová jednotka demonstrující algoritmy
  • Přímého zatříďování
  • Binárního zatříďování
  • Přímého výběru
  • Shake_sort
  • Heap_sort
  • Merge_sort
• Testovací program
• Testovací data
• Programová jednotka demonstrující nerekursivní implementaci quicksortu a příslušný testovací program
12. Program vyhledávání v uspořádaném seznamu s přístupem na fiktivní začátek (hlavu) a fiktivní konec (ocas).
13. Hledání kořene metodou půlení intervalu - příklad použití funkcionálních parametrů
14. Programová jednotka realizující streamy čísel
15. Implementace algoritmu přirozeného slučování na streamech
16. Pomocný program, který vytváří z textového souboru obsahujícího integery stream se stejným obsahem.
17. Zvětšování počtu běhu procezením přes dva heapy v operační paměti.
18. Motivační příklad pro zavedení objektového programování
    • Neobjektová fronta implementovaná v začátku pole
    • Stejná fronta implementovaná objektově, podtřída realizující "cyklickou frontu"
19. Unita obsahující objektovou implementaci dvojsměrných lineárních seznamů s hlavou
20. Programy demonstrující virtuální metody
21. Trasování algoritmu batohu