Size: 17760
Comment:
|
Size: 20310
Comment: stav
|
Deletions are marked like this. | Additions are marked like this. |
Line 1: | Line 1: |
= Skúška = * Nutnou podmienkou k absolvovaniu skúšky je získanie zápočtu čo je podmienené úspešným odovzdaním všetkých povinných zadaní * Na termín sa treba prihlásiť, možno sa z neho odhlásiť. Deje sa tak zaslaním e-mailu (čo sa tohoto týka, platia klasické inštrukcie uvedené nižšie) ktorého textová časť je nespochybniteľnou deklaráciou tohoto aktu. * Skúška pozostáva z písomnej a ústnej časti. * Termíny konania písomnej časti sú: * 14.6 * 21.6 * 28.6 Písomka sa píše v miestnosti B008 o 9:00 ráno * Ako pomôcku si na skúšku možno priniesť akúkoľvek písomnosť. Elektronické pomôcky sú zakázané. |
= Všeobecné = [[http://en.wikipedia.org/wiki/Necessary_and_sufficient_condition|Nutnou podmienkou]] k absolvovaniu skúšky je získanie zápočtu. Získanie zápočtu je podmienené úspešným odovzdaním 4 spomedzi 8 zadaní. Päťnásobok úspešne odovzdaných zadaní sa v podobe bodov prenáša ku skúške. Samotná skúška pozostáva z písomnej a ústnej časti, obe sú po 30 bodov. Ako pomôcku si na skúšku možno priniesť akúkoľvek písomnosť, elektronické pomôcky sú zakázané. = Štúdijné materiály = || Slajdy k prednáškam || Iné zdroje || || [[http://www.math.sk/sarkoci/MPM1SZP/01_seminar_z_programovania.pdf|Pamať, jej adresovanie a smerníky]] || [[http://mercurial.selenic.com/quickstart/|Mercurial: Quick Start]] || || [[http://www.math.sk/sarkoci/MPM1SZP/02_seminar_z_programovania.pdf|Dynamická allokácia pamäti]] || [[http://hgbook.red-bean.com/read/|Mercurial: The Definitive Guide]] || || [[http://www.math.sk/sarkoci/MPM1SZP/03_seminar_z_programovania.pdf|Reprezentácia matíc]] || [[http://mercurial.selenic.com/wiki/CzechMercurial|Mercurial: Navod v Ceskom jazyku]] || || [[http://www.math.sk/sarkoci/MPM1SZP/04_seminar_z_programovania.pdf|Výpočtová zložitosť I., Rekurzia]] || || || [[http://www.math.sk/sarkoci/MPM1SZP/05_seminar_z_programovania.pdf|Quicksort]] || || || [[http://www.math.sk/sarkoci/MPM1SZP/06_seminar_z_programovania.pdf|Nizkoúrovňové I/O]] || || |
Line 15: | Line 17: |
Všeobecné zásady: * Vypracované zadania zasielajte na peter.kantor.sarkoci@gmail.com, prikladajte ich k e-mailu skomprimované ako prílohu a subject nastavte na "seminar z programovania". Čo nedostanem e-mailom, to pre mňa neexistuje. * Pred odovzdaním riešenia skontrolujte, či sa nedopúšťate niektorej spomedzi [[#chyby|často sa vyskytujúcich chýb]]. * Zdrojový kód odsádzajte. * Program rozbíjajte na zmysluplné funkčné bloky ktoré sú realizované funkciami - čím viac, tým lepšie. * Ošetrujte chybové stavy. Funkcie programujte tak, aby cez návratové hodnoty (alebo nejako inak) oznamovali chybové stavy ktore pri ich vykonávaní nastali. * Programujte tak, aby kompilátor nevyhlasoval ani jedno varovanie pri pedantnom móde kompilácie. === 1 === Naprogramujte funkciu ktorá zadané dynamicky allokované <<latex($n$)>>-prvkové pole premenných typu `int`: * Inicializuje na hodnotu 0. * Inicializuje na aritmetickú postupnosť <<latex($\{a+i.b\}_{i\in \mathbf{Z}_{n}}$)>> so zadanými parametrami <<latex($a,b\in\mathbf{Z}$)>>. * Inicializuje na postupnosť náhodne generovaných celých čísel. * Analyzuje a zisťuje pozíciu a dĺžku najdlhšej klesajúcej podpostupnosti bezprostredne po sebe nasledujúcich prvkov. * Sčituje a vracia hodnotu súčtu všetkých prvkov v poli. * Analyzuje a vracia aritmetický priemer prvkov v poli. * Analyzuje a vracia rozptyl prvkov v poli. Design funkcií (čiže voľba návratových typov a argumentov) je na vás. === 2 === Napíšte program ktorý od uživateľa z klávesnice načíta prirodzené číslo <<latex($n$)>> a následne, metódou Erastotenovho sita, zistí všetky prvočísla nie väčšie než <<latex($n$)>>. Pamäť v ktorej Erastotenov algoritmus vykonáva Erastotenovské značkovanie allokujte dynamicky. === 3 === Budeme pracovať s racionálnymi číslami reprezentovanými v tvare zlomku. Za účelom reprezentácie takéhoto zlomku si zavedieme zavedieme datový typ `zlomok` a to bude štruktúra o dvoch členských premenných: čitateľ bude reprezentovať premenná typu `int`, menovateľ bude reprezentovať premenná typu `unsigned int`. Implementujte nasledujúce funkcie: * funkciu ktorá porovná dva takto reprezentované zlomky a cez návratový typ referuje, ktorý z nich je väčší. * funkciu ktorá vypočíta súčet dvoch zlomkov * funkciu ktorá vypočíta rozdiel dvoch zlomkov * funkciu ktorá vypočíta súčin dvoch zlomkov * funkciu ktorá vypočíta podiel dvoch zlomkov Funkcie implementujte tak, aby výsledok výpočtu reprezentovali a odovzdali opäť ako zlomok. === 4 === K riešeniu úlohy 1. doprogramujte funkciu ktorá zadané pole premenných typu int preusporiada vzostupne. To znamená, že výsledné pole obsahuje presne tie isté prvky ako zadané pole, ale hodnoty v ňom uložené su neklesajúcou funkciou indexu. <!> Aspoň približné riešenie zaslať do 21.Marca a to aj v prípade, že ste ešte úspešne neodovzdali zadanie 1. === 5 === Navrhnite datový typ reprezentujúci maticu (v matematickom zmysle slova) čísel typu double. Taký datový typ by mal niesť informáciu o počte riadkov, počte stĺpcov a, samozrejme, o hodnotách jednotlivých prvkov matice. Je jasné, že tu hovoríme o nejakej štruktúre. Okrem týchto vecí môže taký datový typ zastrešovať aj rôzne servisné a obslužné informácie - to už závisí od vašeho programátorského vkusu a rôznych implementačných nutností na ktoré cestou narazíte. Pre tento datový typ potom naprogramujte funkciu ktorá: * vytvorí a pripraví všetky potrebné štruktúry pre neinicializovanú maticu typu <<latex($m\times n$)>> * uvolní pamäť po štruktúrach reprezentujúcich zadanú maticu * zadanú maticu skopíruje do inej, tiež zadanej matice * zadanú maticu inicializuje na nulovú maticu * zadanú maticu inicializuje na jednotkovú maticu * zadanú maticu inicializuje na maticu náhodných hodnôt * vypočíta euklidovskú normu zadanej matice * maticu transponuje * vypočíta súčin dvoch zadaných matíc a uloží ho do tretej zadanej matice * Na zadanú maticu aplikuje také elementárne riadkové operácie ktoré ju prevedú na dolnú trojuholníkovú maticu a súbežne ich aplikuje na inú, tiež zadanú maticu * nad zadanou maticou vykoná Gramm-Schmidtovu ortogonalizáciu === 6 === Čo je to šedotónový obrázok formátu PGM typu P5 sa dozviete na internete - napríklad tu [[http://morse.cs.byu.edu/450/resources/pnm.html|tu]] alebo aj [[http://codeding.com/?article=3|tu]] ale nie len. Ako konkrétne príklady obrázkov v tomto formáte sú vám k dispozícii [[attachment:baboon.pgm|baboon]], [[attachment:barbara.pgm|barbara]] a [[attachment:lena.pgm|lena]]. Vašou úlohou je navrhnúť jednoduchý datový typ na reprezentáciu šedotónového obrázku o 256 úrovniach šedi (čiže presne toho, čo reprezentuje formát PGM). Ďalej, pre tento datový typ naprogramujte funkciu ktorá: * vytvorí a pripraví všetky potrebné štruktúry pre obrázok zadaných rozmerov a všetky stupne šedi nastaví na čiernu * vytvorí a pripraví všetky potrebné štruktúry pre obrázok reprezentovaný vo formáte PGM typu P5 v súbore zadaného mena a hodnoty šedi takto vytvoreného obrázku inicializuje hodnotami prečítanými zo súboru * zadanú obdĺžnikovitú časť jedného obrázku okopíruje na zadanú pozíciu v druhom obrázku * nad obrázkom vykoná primitívnu binarizáciu, čiže - čo je svetlejšie než polovičná šedá zostane úplne biele a čo je tvamvšie než polovičná šedá zostane úplne čierne * na obrázok aplikuje [[http://en.wikipedia.org/wiki/Sobel_operator|Sobelov hranový detektor]] * na obrázok aplikuje nejaký algoritmus [[http://homepages.inf.ed.ac.uk/rbf/HIPR2/adpthrsh.htm|lokálnej adaptívnej binarizácie]] - voľba konkrétneho algoritmu je otázkou vašeho vkusu * obrázok uloží na disk do súboru zadaného mena vo formáte PGM typu P5 === 7 === Naprogramujte jednoduchú aplikáciu `obrazkovac` na spracovanie obrázkov vo formáte PGM typu P5. Aplikácii sa všetky pokyny pre jej činnosť budú odovzdávať ako parametre príkazového riadku. Aplikácia zo zadaného súboru (hovorme mu `vstupny_obrazok`, ale môže sa samozrejme volať aj inakšie) prečíta šedotónový obrázok a následne naň aplikuje rôzne algoritmy spracovania obrazu v takom poradí v akom sú uvedené v príkazovom riadku. Syntax príkazového riadku: `obrazkovac [parametre] vstupny_obrazok` počíta s nasledujúcimi parametrami: * `-b` aktuálny obrázok zbinarizuj primitívnou binarizačnou metódou, * `-lab` na aktuálny obrázok aplikuj algoritmus lokálnej adaptívnej binarizácie, * `-s` na aktuálny obrázok aplikuj Sobelov hranový dekektor, * `-o vystupny_obrazok` aktuálny obrázok uloží do súboru s menom `vystupny_obrazok` vo formáte PGM typu P5. Čiže napríklad `obrazkovac -s -s -o dvojhrany.pgm -lab -s -lab -o definitivne.pgm baboon.pgm` vezme obrázok opice, aplikuje naň Sobelov detektor a potom ešte raz Sobelov detektor, medzivýsledok uloží do súboru `dvojhrany.pgm`, ďalej na obraz aplikuje lokálnu adaptívnu binarizáciu, opäť Sobelov detektor a ešte raz lokálnu adaptívnu binarizáciu a aktuálny obraz uloží do `definitivne.pgm`. Všetky funkcie na prácu s reťazcami si naprogramujte sami, hlavičkový súbor `string.h` je pre toto zadanie tabu. === 8 (*) === K riešeniu úloh 1. a 4. doprogramujte merge-sort. |
Akceptujem len také vypracovania zadaní, ktoré v plnej miere vyhovujú zneniu zadania a v ktorých sa nevyskytuje ani jedna chyba zo zoznamu [[#chyby|častých chýb]]. Pri každom zadaní je uvedený termín do kedy je možné jeho vypracovanie úspešne odovzdať. Po tomto termíne vypracovania neakceptujem. Neodovzdávajte vypracovania okopírované od svojich kolegov. Zvyčajne na to veľmi ľahko prídem. Za <<latex($n$)>>-tý pokus o odovzdanie práce druhej osoby získate formálne <<latex($-n$)>> odovzdaných zadaní. Pretože nie je v mojich silách robiť detektíva a zisťovať kto čo od koho odpísal, záporné body získajú všetky strany plagiátorského kontraktu. === Termíny pre odovzdanie zadaní === * Prvé zadanie - 18. Apríl, 2011 * Druhé zadanie - 18. Apríl, 2011 === Hinty === * Zadanie '''1'''. Úloha naprogramovať funkciu ktorá generuje náhodnú permutáciu predpísaného cyklického typu má, okrem mnohých komplikovaných, aj jedno naozaj elegantné riešenie. Ako návod na jeho nájdenie si sami pre seba zodpovedzte nasledujúcu otázku: ak sú <<latex($f$)>> a <<latex($g$)>> permutácie množiny <<latex($X$)>>, v akom vzťahu je cyklický typ permutácie <<latex($g\circ f\circ g^{-1}$)>> k cyklickému typu permutácie <<latex($f$)>>? |
Line 104: | Line 30: |
|| ID || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || ## Cifra Štefan || 41458 || || || || || || || || || ## Kandová Andrea || 67640 || <!> || (./) || (./) || (./) || <!> || (./) || {i} || || ## Húska Martin || 67644 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || || ## Zboranova Maria || 67654 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || || ## Kleinová Viera || 67660 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || || ## Kurajová Jana || 67667 || (./) || (./) || <!> || (./) || || || || || ## Brázdilová Veronika || 67674 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || || ## Tješšová Mária || 67678 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || || ## Barboríková Lucia || 67682 || || || || || || || || || ## Juhász Dávid || 67687 || (./) || {i} || {i} || (./) || (./) || (./) || <!> || || ## Rentka František || 67692 || (./) || (./) || (./) || (./) || (./) || <!> || || || ## Trubač Martin || 67698 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || || ## Medľa Matej || 67705 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || <!> || ## Kmeťo Tibor || 67708 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || <!> || ## Kalina Jakub || 67718 || (./) || (./) || (./) || (./) || {i} || || || (./) || ## Bohumel Tomáš || 67720 || (./) || (./) || (./) || (./) || <!> || || || || ## Miklašová Monika || 67725 || (./) || (./) || (./) || (./) || <!> || (./) || {i} || || ## Kottáš Peter || 67728 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || || ## Tücsök Nikolett || 67733 || <!> || (./) || <!> || (./) || <!> || || || || ## Petkaničová Jana || 67737 || (./) || (./) || (./) || (./) || <!> || || || || ## Kollár Michal || 67743 || <!> || (./) || (./) || (./) || || || || <!> || ## Lacko Vladimír || 67746 || || || (./) || (./) || || || || || ## Frolkovič Richard || 69782 || (./) || (./) || (./) || (./) || (./) || (./) || (./) || (./) || |
|| ID || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || <<latex($\sum$)>> || ## Barborikova Lucia: || 67682 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Cifra Stefan: || 41458 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Daniel Patrik: || 7430 || {*} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 1 || ## Dobňak Peter: || 7439 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Jasa~n Peter: || 7449 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Juhásová Ľubica: || 7425 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Kósa Balázs: || 7433 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Krull Samuel || 7503 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Lukáč Matej || 7455 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Mesiar Martin || 7446 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Meszáros Michal || 7465 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Očenáš Martin || 64702 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Petrovič Pavol || 64426 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Škabla Peter || 7408 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Šťastná Hilda || 40071 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Tucsok Nikolett: || 67733 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Vranková Andrea: || 7431 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Zubaj Lukáš || 7415 || {o} || {o} || {o} || {o} || {o} || {o} || {o} || {o} || 0 || ## Priklad || || || || || || || || || || || || napr. || {*} || {*} || {X} || {o} || {*} || {X} || {*} || {*} || 2 || || vysv. || +1 || +1 || -1 || +0 || +1 || -2 || +1 || +1 || = || ##=== Zadanie 1 === ## ##Naprogramujte funkciu ktorá zadané dynamicky allokované <<latex($n$)>>-prvkové pole premenných typu `int`: ## * Inicializuje na hodnotu 0. ## * Inicializuje na aritmetickú postupnosť <<latex($\{a+i.b\}_{i\in \mathbf{Z}_{n}}$)>> so zadanými parametrami <<latex($a,b\in\mathbf{Z}$)>>. ## * Inicializuje na postupnosť náhodne generovaných celých čísel. ## * Analyzuje a zisťuje pozíciu a dĺžku najdlhšej klesajúcej podpostupnosti bezprostredne po sebe nasledujúcich prvkov. ## * Sčituje a vracia hodnotu súčtu všetkých prvkov v poli. ## * Analyzuje a vracia aritmetický priemer prvkov v poli. ## * Analyzuje a vracia rozptyl prvkov v poli. ## ##Design funkcií (čiže voľba návratových typov a argumentov) je na vás. ## ##=== 2 === ## ##Napíšte program ktorý od uživateľa z klávesnice načíta prirodzené číslo <<latex($n$)>> a následne, metódou Erastotenovho sita, ##zistí všetky prvočísla nie väčšie než <<latex($n$)>>. Pamäť v ktorej Erastotenov algoritmus vykonáva Erastotenovské značkovanie ##allokujte dynamicky. ## ##=== 3 === ## ##Budeme pracovať s racionálnymi číslami reprezentovanými v tvare zlomku. Za účelom reprezentácie takéhoto zlomku si zavedieme ##zavedieme datový typ `zlomok` a to bude štruktúra o dvoch členských premenných: čitateľ bude reprezentovať premenná typu `int`, ##menovateľ bude reprezentovať premenná typu `unsigned int`. Implementujte nasledujúce funkcie: ## * funkciu ktorá porovná dva takto reprezentované zlomky a cez návratový typ referuje, ktorý z nich je väčší. ## * funkciu ktorá vypočíta súčet dvoch zlomkov ## * funkciu ktorá vypočíta rozdiel dvoch zlomkov ## * funkciu ktorá vypočíta súčin dvoch zlomkov ## * funkciu ktorá vypočíta podiel dvoch zlomkov ##Funkcie implementujte tak, aby výsledok výpočtu reprezentovali a odovzdali opäť ako zlomok. ## ##=== 4 === ## ##K riešeniu úlohy 1. doprogramujte funkciu ktorá zadané pole premenných typu int preusporiada vzostupne. To znamená, že výsledné ##pole obsahuje presne tie isté prvky ako zadané pole, ale hodnoty v ňom uložené su neklesajúcou funkciou indexu. <!> Aspoň ##približné riešenie zaslať do 21.Marca a to aj v prípade, že ste ešte úspešne neodovzdali zadanie 1. ## ##=== 5 === ## ##Navrhnite datový typ reprezentujúci maticu (v matematickom zmysle slova) čísel typu double. Taký datový typ by mal niesť ##informáciu o počte riadkov, počte stĺpcov a, samozrejme, o hodnotách jednotlivých prvkov matice. Je jasné, že tu hovoríme o ##nejakej štruktúre. Okrem týchto vecí môže taký datový typ zastrešovať aj rôzne servisné a obslužné informácie - to už závisí od ##vašeho programátorského vkusu a rôznych implementačných nutností na ktoré cestou narazíte. ## ##Pre tento datový typ potom naprogramujte funkciu ktorá: ## * vytvorí a pripraví všetky potrebné štruktúry pre neinicializovanú maticu typu <<latex($m\times n$)>> ## * uvolní pamäť po štruktúrach reprezentujúcich zadanú maticu ## * zadanú maticu skopíruje do inej, tiež zadanej matice ## * zadanú maticu inicializuje na nulovú maticu ## * zadanú maticu inicializuje na jednotkovú maticu ## * zadanú maticu inicializuje na maticu náhodných hodnôt ## * vypočíta euklidovskú normu zadanej matice ## * maticu transponuje ## * vypočíta súčin dvoch zadaných matíc a uloží ho do tretej zadanej matice ## * Na zadanú maticu aplikuje také elementárne riadkové operácie ktoré ju prevedú na dolnú trojuholníkovú maticu a súbežne ich ##aplikuje na inú, tiež zadanú maticu ## * nad zadanou maticou vykoná Gramm-Schmidtovu ortogonalizáciu ## ##=== 6 === ## ##Čo je to šedotónový obrázok formátu PGM typu P5 sa dozviete na internete - napríklad tu [[http://morse.cs.byu.edu/450/resources/pnm.html|tu]] alebo aj [[http://codeding.com/?article=3|tu]] ale nie len. Ako konkrétne príklady obrázkov v tomto formáte sú vám k ##dispozícii [[attachment:baboon.pgm|baboon]], [[attachment:barbara.pgm|barbara]] a [[attachment:lena.pgm|lena]]. Vašou úlohou je ##navrhnúť jednoduchý datový typ na reprezentáciu šedotónového obrázku o 256 úrovniach šedi (čiže presne toho, čo reprezentuje ##formát PGM). Ďalej, pre tento datový typ naprogramujte funkciu ktorá: ## * vytvorí a pripraví všetky potrebné štruktúry pre obrázok zadaných rozmerov a všetky stupne šedi nastaví na čiernu ## * vytvorí a pripraví všetky potrebné štruktúry pre obrázok reprezentovaný vo formáte PGM typu P5 v súbore zadaného mena a ##hodnoty šedi takto vytvoreného obrázku inicializuje hodnotami prečítanými zo súboru ## * zadanú obdĺžnikovitú časť jedného obrázku okopíruje na zadanú pozíciu v druhom obrázku ## * nad obrázkom vykoná primitívnu binarizáciu, čiže - čo je svetlejšie než polovičná šedá zostane úplne biele a čo je tvamvšie než polovičná šedá zostane úplne čierne ## * na obrázok aplikuje [[http://en.wikipedia.org/wiki/Sobel_operator|Sobelov hranový detektor]] ## * na obrázok aplikuje nejaký algoritmus [[http://homepages.inf.ed.ac.uk/rbf/HIPR2/adpthrsh.htm|lokálnej adaptívnej binarizácie]] - voľba konkrétneho algoritmu je otázkou vašeho vkusu ## * obrázok uloží na disk do súboru zadaného mena vo formáte PGM typu P5 ## ##=== 7 === ## ##Naprogramujte jednoduchú aplikáciu `obrazkovac` na spracovanie obrázkov vo formáte PGM typu P5. Aplikácii sa všetky pokyny pre jej činnosť budú odovzdávať ako parametre príkazového riadku. Aplikácia zo zadaného súboru (hovorme mu `vstupny_obrazok`, ale môže sa samozrejme volať aj inakšie) prečíta šedotónový obrázok a následne naň aplikuje rôzne algoritmy spracovania obrazu v takom poradí v akom sú uvedené v príkazovom riadku. Syntax príkazového riadku: ## `obrazkovac [parametre] vstupny_obrazok` ##počíta s nasledujúcimi parametrami: ## * `-b` aktuálny obrázok zbinarizuj primitívnou binarizačnou metódou, ## * `-lab` na aktuálny obrázok aplikuj algoritmus lokálnej adaptívnej binarizácie, ## * `-s` na aktuálny obrázok aplikuj Sobelov hranový dekektor, ## * `-o vystupny_obrazok` aktuálny obrázok uloží do súboru s menom `vystupny_obrazok` vo formáte PGM typu P5. ##Čiže napríklad ## `obrazkovac -s -s -o dvojhrany.pgm -lab -s -lab -o definitivne.pgm baboon.pgm` ##vezme obrázok opice, aplikuje naň Sobelov detektor a potom ešte raz Sobelov detektor, medzivýsledok uloží do súboru ##`dvojhrany.pgm`, ďalej na obraz aplikuje lokálnu adaptívnu binarizáciu, opäť Sobelov detektor a ešte raz lokálnu adaptívnu ##binarizáciu a aktuálny obraz uloží do `definitivne.pgm`. ## ##Všetky funkcie na prácu s reťazcami si naprogramujte sami, hlavičkový súbor `string.h` je pre toto zadanie tabu. ## ##=== 8 (*) === ## ##K riešeniu úloh 1. a 4. doprogramujte merge-sort. |
Line 153: | Line 152: |
=== Časté chyby === | == Časté chyby == |
Line 156: | Line 155: |
a. Funkcia alebo procedúra má vykonávať ''jednu'', čo možno ''najjednoduchšiu'' činnosť a túto činnosť má vykonávať dobre. | a. Každá jedna funkcia alebo procedúra má vykonávať ''jednu'', čo možno ''najjednoduchšiu'' činnosť a túto činnosť má vykonávať dobre. Áno, existujú výnimky z tohoto pravidla, ale na tomto seminári sa s nimi nestretneme. |
Line 159: | Line 158: |
a. Funkcie vymýšlajte tak, aby referovali všetky možné typy chybových stavov ktoré pri ich vykonávaní môžu nastať. Príznaky týchto chybových stavov referujú primárne cez návratovú hodnotu a ak len ak sa to nedá nejak inak. | |
Line 162: | Line 162: |
a. Ak deklarujete napríklad `int pole[n]` kde `n` je nejaká predtým inicializovaná premenná, devcpp, žial, nebude frflať. Lenže niečo podobné je z hladiska čistého ANSI C striktne zakázané. Keďže hodnota `n` nie je v čase kompilácie známa, to čo takouto deklaráciou hovoríte, je vlastne dynamická allokácia pamate. Ale tá sa správne rieši cez funkciu `malloc` a jej príbuzné. Jediný dôvod prečo takýto riadok ide skompilovať je to, že devcpp nie je dôsledný kompilátor a, aj bez toho aby o to bol požiadaný, do jazyka mieša črty neoficiálnych rozšírení a C++. Ja ale takéto tolerovať nebudem; skúste to skompilovať pod linuxom pomocou `gcc` a hneď pochopíte prečo. | a. Ak deklarujete napríklad `int pole[n]` kde `n` je nejaká predtým inicializovaná premenná, devcpp, žial, nebude frflať. Lenže niečo podobné je z hladiska čistého ANSI C striktne zakázané. Keďže hodnota `n` nie je v čase kompilácie známa, to čo takouto deklaráciou hovoríte, je vlastne dynamická allokácia pamate. Ale tá sa správne rieši cez funkciu `malloc` a jej príbuzné. |
Line 172: | Line 172: |
a. Všetky deklarácie lokálnych premenných sa vybavia na začiatku tela funkcie. Dalej nasleduje už iba kód, žiadne prípadné ďalšie deklarácie. |
Všeobecné
Nutnou podmienkou k absolvovaniu skúšky je získanie zápočtu. Získanie zápočtu je podmienené úspešným odovzdaním 4 spomedzi 8 zadaní. Päťnásobok úspešne odovzdaných zadaní sa v podobe bodov prenáša ku skúške. Samotná skúška pozostáva z písomnej a ústnej časti, obe sú po 30 bodov. Ako pomôcku si na skúšku možno priniesť akúkoľvek písomnosť, elektronické pomôcky sú zakázané.
Štúdijné materiály
Slajdy k prednáškam |
Iné zdroje |
|
|
|
|
|
Zadania
Akceptujem len také vypracovania zadaní, ktoré v plnej miere vyhovujú zneniu zadania a v ktorých sa nevyskytuje ani jedna chyba zo zoznamu častých chýb. Pri každom zadaní je uvedený termín do kedy je možné jeho vypracovanie úspešne odovzdať. Po tomto termíne vypracovania neakceptujem. Neodovzdávajte vypracovania okopírované od svojich kolegov. Zvyčajne na to veľmi ľahko prídem. Za -tý pokus o odovzdanie práce druhej osoby získate formálne
odovzdaných zadaní. Pretože nie je v mojich silách robiť detektíva a zisťovať kto čo od koho odpísal, záporné body získajú všetky strany plagiátorského kontraktu.
Termíny pre odovzdanie zadaní
- Prvé zadanie - 18. Apríl, 2011
- Druhé zadanie - 18. Apríl, 2011
Hinty
Zadanie 1. Úloha naprogramovať funkciu ktorá generuje náhodnú permutáciu predpísaného cyklického typu má, okrem mnohých komplikovaných, aj jedno naozaj elegantné riešenie. Ako návod na jeho nájdenie si sami pre seba zodpovedzte nasledujúcu otázku: ak sú
a
permutácie množiny
, v akom vzťahu je cyklický typ permutácie
k cyklickému typu permutácie
?
Priebežný stav
ID |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
67682 |
|
|
|
|
|
|
|
|
0 |
41458 |
|
|
|
|
|
|
|
|
0 |
7430 |
|
|
|
|
|
|
|
|
1 |
7439 |
|
|
|
|
|
|
|
|
0 |
7449 |
|
|
|
|
|
|
|
|
0 |
7425 |
|
|
|
|
|
|
|
|
0 |
7433 |
|
|
|
|
|
|
|
|
0 |
7503 |
|
|
|
|
|
|
|
|
0 |
7455 |
|
|
|
|
|
|
|
|
0 |
7446 |
|
|
|
|
|
|
|
|
0 |
7465 |
|
|
|
|
|
|
|
|
0 |
64702 |
|
|
|
|
|
|
|
|
0 |
64426 |
|
|
|
|
|
|
|
|
0 |
7408 |
|
|
|
|
|
|
|
|
0 |
40071 |
|
|
|
|
|
|
|
|
0 |
67733 |
|
|
|
|
|
|
|
|
0 |
7431 |
|
|
|
|
|
|
|
|
0 |
7415 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
napr. |
|
|
|
|
|
|
|
|
2 |
vysv. |
+1 |
+1 |
-1 |
+0 |
+1 |
-2 |
+1 |
+1 |
= |
Časté chyby
- Chyby týkajúce sa designu funkcií
Každá jedna funkcia alebo procedúra má vykonávať jednu, čo možno najjednoduchšiu činnosť a túto činnosť má vykonávať dobre. Áno, existujú výnimky z tohoto pravidla, ale na tomto seminári sa s nimi nestretneme.
Rozmeniac na drobné predchádzajúci bod: ak žiadam implementáciu funkcie ktorá vykonáva činnosť Č tak tým myslím, bez toho aby som to explicitne zdôraznoval, že funkcia žiadnu inú činnosť nevykonáva. Napríklad ak chcem, aby funkcia inicializovala pole premenných typu int na zadanú hodnotu
tak, bez toho aby som to explicitne písal, očakávam, že funkcia nebude ani nič čítať z klávesnice, ani nič písať na obrazovku a vôbec, nebude robiť nič čo bezprostredne nesúvisí s inicializáciou pola.
Veľké datové typy a komplikované datové štruktúry sa funkciám nikdy neodovzdávajú ako argumenty. Namieto toho sa ako argumenty odovdávajú iba smerníky na ne. Prečo? Na prednáške som vám vysvetloval, že každé odovzdanie argumentu funkcii pri jej volaní obnáša kopírovanie hodnôt argumentov. Jazyk C toto kopírovanie zakrýva ale to neznamená, že k nemu nedochádza. Ak sú argumentami funkcie nejaké veľké štruktúry, znamená to veľa kopírovania a to je neefektívne (spomeňte si na príklad s renováciou budovy bloku C o ktorom som rozprával na prednáške). Naproti tomu smerník je iba jedno relatívne malé číslo a to sa kopíruje ľahko.
- Funkcie vymýšlajte tak, aby referovali všetky možné typy chybových stavov ktoré pri ich vykonávaní môžu nastať. Príznaky týchto chybových stavov referujú primárne cez návratovú hodnotu a ak len ak sa to nedá nejak inak.
Zásada o pred-objektovej disciplíne: Všetky "konštruktory" (čiže funkcie, ktoré sa starajú o allokáciu pamäte pre komplikované datové štruktúry) allokujú celé datové štruktúry a volajúcemu procesu cez navratovu hodnotu odovzdávajú iba ich adresy. Všetky "deštruktory" (čiže funkcie, ktoré sa starajú o uvoľnovanie pamäte po komplikovaných datových štruktúrach) uvoľňujú pamäť po celých datových štruktúrach a ako argument preberajú iba smerník na štruktúru ktorú treba zničiť.
- Všetky "konštruktory" (čiže funkcie, ktoré sa starajú o allokáciu pamäte pre komplikované datové štruktúry) treba implementovať tak, aby v prípade keď sa proces allokacie pamäte nepodarí z nejakého dôvodu úspešne zavŕšiť, uvolnili tie časti pamäte ktoré sa im ešte pred nastaním problému allokovať podarilo. Motivácia pre túto zásadu je úplne jasná: kedykoľvek proces allokácie niekde uviazne, treba volajúcemu procesu namiesto allokovanej štruktúry vrátiť chybový stav - ak sa však konštruktor ešte predtým nepostará o upratanie tých častí pamäte ktoré sa mu allokovať podarilo, budú ich adresy nenávratne zabudnuté a nikomu sa ich už nepodarí po celú dobu behu programu uvoľniť.
- Črty jazyka ktoré nepatria do ANSI C
Ak deklarujete napríklad int pole[n] kde n je nejaká predtým inicializovaná premenná, devcpp, žial, nebude frflať. Lenže niečo podobné je z hladiska čistého ANSI C striktne zakázané. Keďže hodnota n nie je v čase kompilácie známa, to čo takouto deklaráciou hovoríte, je vlastne dynamická allokácia pamate. Ale tá sa správne rieši cez funkciu malloc a jej príbuzné.
- Programátorský štýl
Blok kódu začína vždy na novom riadku. Aj v prípade, že sám nemá viac než jeden riadok. Prečo? Už z letmého pohladu na zdroják je jasné aké panujú medzi časťami kódu logické vzťahy.
- Blok kódu je oproti okolitému kódu odsadený o jeden tabulátor doprava. Prečo? Už z letmého pohladu na zdroják je jasné, kde blok kódu začína a kde končí.
- Mená symbolických konštánt sa píšu vždy veľkými písmenami. Prečo? Táto jednoduchá konvencia ktorá programátora prakticky nič nestojí umožnuje už letmým pohladom odlíšiť symbolické konštanty od premenných, čo je viac než užitočné.
- Návratové chybové stavy funkcií sa realizujú ako symbolické konštanty. Prečo? Pri letmom pohlade na kondicionál
if(sucet(argumenty1, argumentyn) == 1)
by sa mohlo zdať, že testujeme, či sa výsledok nejakého výpočtu (ktorý realizuje funkcia sucet) náhodou nerovná jednej. Ak ale čítame
if(sucet(argumenty1, argumentyn) == PROBLEM_PRETECENIE_ROZSAHU_INT)
- Všetky deklarácie lokálnych premenných sa vybavia na začiatku tela funkcie. Dalej nasleduje už iba kód, žiadne prípadné ďalšie deklarácie.
- Medzi deklarácie premenných na začiatku tela funkcie a jeho zvyšok sa vkladá prázdny riadok. Prečo? Programátor čítajúci zdrojový kód preskakuje deklarácie premenných a vracia sa k nim až neskôr, keď sa chce dozvedieť akého typu tá ktorá premenná je. Prázdny riadok na konci deklarácií výrazne ulahčuje takýto spôsob čítania zdrojáku.
- Medzi definíciami funkcií ako aj medzi inštrukciami preprocesora na začiatku zdrojového kódu a kódom samotným sa nachádzajú voľné riadky. Prečo? Opticky to oddeluje veci ktoré spolu súvisia od vecí ktore spolu nesúvisia čo, opäť, zvyšuje čitateľnosť kódu.
- Pri funkciach sa explicitne uvadza datovy typ a navratovy typ aj vtedy, ak tieto nemaju argumenty alebo ziadnu hodnotu nevracaju. Prečo? Dáva nám to dopredu vedieť, čo možno od tej ktorej funkcie očakávať, čo opäť sprehľadňuje zdroják.
Ukážkový Zdroják
1 #include <stdlib.h>
2 #include <stdio.h>
3
4 void print_num(int a)
5 {
6 printf("%d",a);
7 }
8
9 int main(void)
10 {
11 int i, j, k;
12 char *string;
13 double ratio;
14
15 /* nadomnou je volny riadok oddelujuci deklaracie (zasada 3.e) */
16 if(i == j)
17 printf("Premenne i a j maju, zhodou okolnosti, rovnaku hodnotu.\n");
18 else {
19 printf("Premenne i a j maju, zhodou okolnosti, roznu hodnotu.\n");
20 print_num(i);
21 print_num(j);
22 }
23
24 if(&i == (int*)string) {
25 printf("tento kod sa NIKDY nevykona.");
26 i = j+k;
27 j = i-k;
28 }
29
30 for(i=0;;i++)
31 if(i != k) {
32 printf(".");
33 k -= i;
34 } else {
35 printf("zaverecna");
36 break;
37 }
38
39 if(i < 0)
40 i = -i;
41
42 do{
43 i--;
44 printf(".");
45 }while(i!=1)
46
47 /* aj jednoriadkovy blok je blok */
48 if(i>0)
49 if(j<0)
50 j=i;
51 else
52 if(j>0)
53 i=j;
54
55 /* dovidenia */
56 return(0);
57 }