Prednáška 23

Oznamy

Koniec semestra:

• Dnešná prednáška: informácia o skúškach, detaily skúšky z programovania, opakovanie, vaše otázky
• Doplnkové cvičenia tento piatok: ako obvykle, bonusová rozcvička nebude
• Pondelok prednáška: nepreberané črty C resp. C++. Nebudeme skúšať, ale môžu sa zísť (môžete použiť aj na skúške). Dohadovanie termínu opravnej písomky.
• Budúcu stredu prednáška nebude
• Cvičenia budúci utorok: už dnes po prednáške sa na testovači objavia tréningové príklady na skúšku. Za niektoré budete môcť získať bonusový bod, ak ich vyriešite do 6.1. (ako tréning sa dajú riešiť aj neskôr). V utorok na cvičeniach pribudne ešte jeden tréningový príklad za 4 body. Ak prídete na cvičenia a odovzdáte na konci aspoň rozumne rozrobenú verziu programu, získate jeden bonusový bod, aj keď ho nestihnete dokončiť.
  • Ak ste na programovaní používali webové prostredia, nainštalujte si a vyskúšajte nejaký softvér, ktorý pobeží priamo na vašom počítači.
  • Dobrým nápadom je naučiť sa používať aj program Valgrind alebo alternatívy, ktorý vám na skúške môže pomôcť nájsť chýbajúce odalokovanie alebo chybu, pre ktorú váš program padá.
• Namiesto piatkových cvičení budúci týždeň bude predtermín skúšky.

• Ak ste namiesto úloh robili rýchlostné programovanie, nezabudnite do 18.12. odovzdať zoznam príkladov vyriešených v C alebo C++ podľa pokynov na testovači.

Iné

• Do konca skúškového môžete vypĺňať študentskú anketu: https://anketa.uniba.sk/fmph/ (ešte nebola spustená) Tešíme sa na konštruktívne návrhy, ktoré nám pomôžu zlepšiť predmet do budúcnosti.
• Ak by ste cez skúškové obdobie mali záujem o konzultácie pred opravným testom alebo pred skúškou, dajte nám vedieť.

Sylaby predmetu

Základy

Konštrukcie jazyka C

• premenné typov int, double, char, bool, konverzie medzi nimi
• podmienky (if, else, switch), cykly (for, while)
• funkcie (a parametre funkcií - odovzdávanie hodnotou, referenciou, smerníkom)

void f1(int x){}                                 //hodnotou
void f2(int &x){}                                //referenciou
void f3(int* x){}                                //smerníkom
void f(int a[], int n){}                         //polia bez & (ostanú zmeny)
void kresli(Turtle &t){}                         //korytnačky, SVGdraw a pod. s &

Polia, reťazce (char[])

int A[4]={3, 6, 8, 10}; 
int B[4];               
B[0]=3; B[1]=6; B[2]=8; B[3]=10;

char C[100] = "pes";
char D[100] = {'p', 'e', 's', 0};

• funkcie strlen, strcpy, strcmp, strcat

Súbory, spracovanie vstupu

• cin, cout alebo printf, scanf
• fopen, fclose, feof
• fprintf, fscanf
• getc, putc, ungetc, fgets, fputs
• spracovanie súboru po znakoch, po riadkoch, po číslach alebo slovách

Smerníky, dynamicky alokovaná pamäť, dvojrozmerné polia

int i;    // „klasická“ celočíselná premenná
int *p;   // ukazovateľ na celočíselnú premennú

p = &i;         // spravne
p = &(i + 3);   // zle i+3 nie je premenna
p = &15;        // zle konstanta nema adresu
i = *p;         // spravne ak p bol inicializovany

int * cislo = new int;  // alokovanie jednej premennej
*cislo = 50;
..
delete cislo;

int a[4];
int *b = a;  // a,b su teraz takmer rovnocenne premenne 

int *A = new int[n]; // alokovanie 1D pola danej dlzky
..
delete[] A;

int **a;       // alokovanie 2D matice
a = new int *[n];
for (int i = 0; i < n; i++) a[i] = new int[m];
..
for (int i = 0; i < n; i++) delete[] a[i];
delete[] a;

Abstraktné dátové typy

Abstraktný dátový typ dynamické pole (rastúce pole)

• operácie init, add, get, set, length

Abstraktný dátový typ množina (set)

• operácie init, find, insert, remove
• implementácie pomocou
  • neutriedeného poľa
  • utriedeného poľa
  • spájaných zoznamov
  • binárnych vyhľadávacích stromov
  • hešovacej tabuľky
  • lexikografického stromu (ak kľúč je reťazec)

Abstraktné dátové typy rad a zásobník

• operácie pre rad (frontu, queue): init, isEmpty, enqueue, dequeue, peek
• operácie pre zásobník (stack): init, isEmpty, push, pop
• implementácie: v poli alebo v spájanom zozname
• využitie: ukladanie dát na spracovanie, odstránenie rekurzie
• kontrola zátvoriek a vyhodnocovanie výrazov pomocou zásobníka

Dátové štruktúry

Spájané zoznamy

struct node {
    int data;
    item* next;
};
struct linkedList {
    item* first;
};
void insertFirst(linkedList &z, int d){
    /* do zoznamu z vlozi na zaciatok novy prvok s datami d */
    item* p = new item;   // vytvoríme nový prvok
    p->data = d;          // naplníme dáta
    p->next = z.first;    // prvok bude prvým prvkom zoznamu (ukazuje na doterajší začiatok)
    z.first = p;          // tento prvok je novým začiatkom
}

Strom pre výraz (65 – 3*5)/(2 + 3)

Binárne stromy

struct node {
    /* vrchol stromu  */
    dataType data;
    node * left;  /* lavy syn */
    node * right; /* pravy syn */
};

node * createNode(dataType data, node *left, node *right) {
    node *v = new node;
    v->data = data;
    v->left = left;
    v->right = right;
    return v;
}

• prehľadávanie inorder, preorder, postorder
• použitie na uloženie aritmetických výrazov

Binárne vyhľadávacie stromy

• vrcholy vľavo od koreňa menší kľúč, vpravo od koreňa väčší
• insert, find, remove v čase závisiacom od hĺbky stromu

Lexikografické stromy

• ukladajú množinu reťazcov
• nie sú binárne: vrchol môže mať veľa synov
• insert, find, remove v čase závisiacom od dĺžky kľúča, ale nie od počtu kľúčov, ktoré už sú v strome

struct node {
    /* vrchol lexikografickeho stromu  */
    char data; // pismeno ulozene v tomto vrchole
    bool isWord; // je tento vrchol koncom slova?
    node* next[Abeceda]; // pole smernikov na deti    
};

Hešovanie

• hešovacia tabuľka veľkosti m
• kľúč k premietneme nejakou funkciou na index v poli (0,...,m-1}
• každé políčko hešovacej tabuľky spájaný zoznam prvkov, ktoré sa tam zahešovali
• v ideálnom prípade sa prvky rozhodia pomerne rovnomerne, zoznamy krátke, rýchle hľadanie, vkladenie, mazanie
• v najhoršom prípade všetky prvky v jednom zozname, pomalé hľadanie a mazanie

int hash(int k, int m){ // veľmi jednoduchá hešovacia funkcia, v praxi väčšinou zložitejšie
    return abs(k) % m;
}
struct node {
    int item;
    node* next;
};

struct set {
    node** data;
    int m;
};

Algoritmy

Rekurzia

• Rekurzívne funkcie
• Vykresľovanie fraktálov
• Prehľadávanie s návratom (backtracking)
• Vyfarbovanie
• Prehľadávanie stromov

Triedenia

• nerekurzívne: Bubblesort, Selectionsort, Insertsort
• rekurzívne: Mergesort, Quicksort
• súvisiace algoritmy: binárne vyhľadávanie

Matematické úlohy

• Euklidov algoritmus, Eratostenovo sito
• Práca s aritmetickými výrazmi: vyhodnocovanie postfixovej formy, prevod z infixovej do postfixovej, reprezentácia vo forme stromu