Differences between revisions 245 and 248 (spanning 3 versions)
⇤ ← Revision 245 as of 2011-06-26 10:18:54 →
Size: 20646
Editor: sarkoci
Comment: lukac zapocet
← Revision 248 as of 2011-06-26 14:19:17 → ⇥
Size: 20646
Editor: sarkoci
Comment:
Deletions are marked like this. Additions are marked like this.
Line 38: Line 38:
|| 7439  || {o} || {o} || {*} || {o} || {o} || || 2 || 10 || || 7439 || {o} || {*} || {*} || {*} || {o} || || 3 || 27 ||
Line 52: Line 52:
|| 7465 || {o} || {o} || {o} || {o} || {o} || || || 0 || || 7465 || {o} || {o} || {o} || {o} || {*} || || || 8 ||

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

Pamať, jej adresovanie a smerníky

Mercurial: Quick Start

Dynamická allokácia pamäti

Mercurial: The Definitive Guide

Reprezentácia matíc

Mercurial: Navod v Ceskom jazyku

Výpočtová zložitosť I., Rekurzia

Quicksort

Nizkoúrovňové I/O

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 $n$-tý pokus o odovzdanie práce druhej osoby získate formálne $-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ú $f$ a $g$ permutácie množiny $X$, v akom vzťahu je cyklický typ permutácie $g\circ f\circ g^{-1}$ k cyklickému typu permutácie $f$?

Priebežný stav

ID

1

3

4

5

6

protokol k zadaniu 3

ine bonusy

$\sum$

67682

{o}

{o}

{o}

{o}

{o}

0

41458

{o}

{o}

{o}

{o}

{o}

0

7430

{*}

{*}

{*}

{*}

{o}

3

35

7439

{o}

{*}

{*}

{*}

{o}

3

27

7449

{o}

{o}

{o}

{o}

{o}

0

7425

{o}

{o}

{o}

{o}

{o}

0

7433

{*}

{*}

{*}

{*}

{*}

4

3

47

7503

{o}

{o}

{o}

{o}

{o}

0

7455

{o}

{*}

{*}

{*}

{*}

4

3

39

7446

{o}

{o}

{o}

{o}

{o}

0

7465

{o}

{o}

{o}

{o}

{*}

8

64702

{o}

{o}

{o}

{o}

{o}

0

64426

{o}

{o}

{o}

{o}

{o}

0

7408

{*}

{o}

{*}

{o}

{o}

1

17

40071

{*}

{o}

{o}

{o}

{o}

8

67733

{*}

{o}

{o}

{o}

{o}

8

7431

{o}

{o}

{o}

{o}

{o}

0

7415

{o}

{o}

{o}

{o}

{o}

0

napr.

{*}

{X}

{o}

{*}

{*}

{X}

3

+3

vysv.

+8

-8

+0

+8

+8

-16

+3

=

Časté chyby

  1. Chyby týkajúce sa designu funkcií

    1. 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.

    2. 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 $h$ 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.

    3. 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.

    4. 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.

    5. 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ť.

    6. 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ť.
  2. Črty jazyka ktoré nepatria do ANSI C

    1. 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é.

  3. Programátorský štýl

    1. 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.

    2. 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čí.
    3. 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é.
    4. 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)

      je nám okamžite jasné, že je to test na chybový stav. To, samozrejme, nesmierne sprehľadňuje zdrojový kód.
    5. 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.
    6. 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.
    7. 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.
    8. 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 }

KMaDGWiki: KurzSeminarZProgramovania (last edited 2019-01-28 14:51:18 by sarkoci)