1. týždeň

Week 1

Algoritmus, Karel the Robot, základná štruktúra programu, preklad a spustenie programu, Don't Repeat Yourself (DRY), funkcia, typ void, definícia/deklarácia, sekvencia, vetvenie (if, if/else), iterácia a cyklus (while, do-while)

Video (30.09.2019, Paralelka D)

Prezentácia

Zdrojový kód

Poznámky k prednáške

Úvod

  • Predmet sa volá Zaklady algoritmizácie a programovania. Programovať budeme v jazyku C.
  • Naša stránka: http://kurzy.kpi.fei.tuke.sk/zap
    • tu nájdete Zadania (Problem Sets), Cvičenia (Labs), Prednášky (Lectures), príklady použité na prednáškach aj všetko potrebné pre úspešné absolvovanie tohto kurzu.
    • vybrané časti našej stránky budú v ruskom jazyku
  • Ak hľadáte literatúru pre tento predmet, môžete použiť:
  • Inšpirovať sa môžete aj inými kurzami, napr.
  • Pravidlá hodnotenia nájdete tu
  • Pri absolvovaní predmetu budeme dbať na to, aby ste postupovali podľa etického kódexu a to hlavne pri práci na Vašich zadaniach. Včas Vás naň budeme opätovne upozorňovať.
  • Všetci študenti majú možnosť získať certifikát ECDL zdarma (viac info nájdete v pravidlách predmetu), avšak študenti KB a INF ho musia absolvovať povinne. Termín: 20.01.2020
  • Pre všetkých študentov je k dispozícii konzultácia každý piatok v čase 9:55-11:35 v miestnosti Duna (L9-B529). Vždy bude prítomný konzultant hovoriaci slovensky aj rusky/ukrajinsky.
  • Каждый студент имеет право прийти на консультации, которые проходят каждую пятницу с 9:55 до 11:35 в помещении Duna (L9-B529). Студенты-консультанты свободно разговаривают на словацком, русском и украинском языках.

Algoritmus

  • Popis postupného riešenia problému (kódom alebo vývojovým diagramom)
  • Postupne počas semestra si tento termín upresníme

Karel the Robot

  • Predstavuje jednoduchý úvod do programovania, pracovať s ním budete od cvičenia č. 2
  • Svet - dvojrozmerný
  • Steny - objekty vo svete, komplikujú nám vykonávanie úloh
  • Značky - objekty vo svete, môžeme ich zbierať alebo ukladať
  • Karel - objekt vo svete, pomocou neho riešime rôzne úlohy
  • Stavový riadok - obsahuje informácie o aktuálnej pozícii Karla, jeho smerovaní, počte značiek v jeho batohu a počte značiek na aktuálnej pozícii (keďže vidíme Karla, ale značky pod ním nie)
  CORNER  FACING  BEEP-BAG  BEEP-CORNER
  (3, 2)   EAST       0         1
 ST.+-----------------------------------+
  9 | .   .   .   .   .   .   .   .   . |
    |                                   |
  8 | .   .   .   .   .   .   .   .   . |
    |                                   |
  7 | .   .   .   .   .   .   .   .   . |
    |                                   |
  6 | .   .   .   .   .   .   .   .   . |
    |                       +---+       |
  5 | .   .   .   .   .   . | . | .   . |
    |                   +---+   |       |
  4 | .   .   .   .   2 | .   . | .   . |
    |               +---+       |       |
  3 | .   .   .   . | .   .   . | .   . |
    |           +---+           |       |
  2 | .   .   > | .   .   .   . | .   . |
    |       +---+               |       |
  1 | .   . | .   .   .   .   . | .   . |
    +-----------------------------------+
      1   2   3   4   5   6   7   8   9   AVE.
  • Primitívy (základné príkazy):

    • turn_on("world.kw")
    • step()
    • turn_left()
    • pick_beeper()
    • put_beeper()
    • turn_off()
  • Základná štruktúra programu:

#include <karel.h>

int main() {
    turn_on("world.kw");

    turn_left();
    pick_beeper();

    turn_off();
}

Preklad a spustenie programu

  • Práve sme napísali zdrojový kód v jazyku C. Aby sme však "ochutnali" výsledok, musíme zo zdrojového kódu vytvoriť spustiteľný kód procesom prekladu (kompilácie)
  • Prekladač je nástroj, ktorý zo zdrojového kódu vytvorí objektový kód. Objektovému kódu rozumie samotný procesor a je možné ho už vykonať (spustiť)
  • Pre preklad budeme používať prekladač GNU C Compiler (gcc)
  • Program môžete prekladať aj použitím nástroja make. Predvolené správanie však funguje bez použitia extra prepínačov. Ak chcete dosiahnuť správne správanie, potrebujete nastaviť minimálne premenné prostredia alebo použiť predpripravený Makefile:
make karel
  • Program následne spustíte napísaním príkazu ./karel z príkazového riadku. Ak budete používať vývojové prostredie, budete mať možnosť spustiť výslednú aplikáciu priamo z neho
  • Bug - chyba v programe
    • In 1946, when Hopper was released from active duty, she joined the Harvard Faculty at the Computation Laboratory where she continued her work on the Mark II and Mark III. Operators traced an error in the Mark II to a moth trapped in a relay, coining the term bug. This bug was carefully removed and taped to the log book. Stemming from the first bug, today we call errors or glitch's [sic] in a program a bug.
    • zdroj: wikipedia: software bug

DRY

  • V programovaní existuje jeden princíp s názvom DRY - Don't Repeat Yourself. A aj keď je jeho význam možné aplikovať v rozličných oblastiach vývoja softvéru, dnes sa sústredíme na jeden z nich - na izoláciu opakujúcich sa častí kódu do funkcií.
  • Funkcie nám teda pomôžu v znovupoužiteľnosti našej časti programu v programe.
  • Funkcie už pritom dávno používame - akýkoľvek zápis v tvare name() ako napr. pick_beeper(), step() je volaním funkcie. Ďalej si ale ukážeme to, ako vytvárať vlastné funkcie.

Čo je to funkcia?

  • Čo je to teda funkcia?
    • Sequence of program instructions that perform a specific task, packaged as a unit
    • zdroj: wikipedia
  • Aby sme neostali nič dlžní ani pascalistom:
    • Jazyk Pascal rozpoznáva dva termíny: funkcie a procedúry. Funkcia je v ponímaní Pascal-u analógiou ku matematickej funkcii - po zavolaní a vykonaní svojej činnosti, vráti hodnotu (výsledok), napr.: cos(x), abs(x), ale aj scanf(). Procedúra naopak po svojom vykonaní žiadnu hodnotu nevráti, napr.: zmaž obrazovku alebo turn_right().

void

  • Jazyk C pozná iba termín funkcia, ale docieliť, aby funkcia nevrátila žiadnu hodnotu, je veľmi jednoduché: Ak nechceme, aby funkcia mala nejakú návratovú hodnotu, zapíšeme to v riadku jej deklarácie slovom void.
  • Vytvorme jednoduchú "procedúru" s názvom turn_right():
void turn_right() {
    turn_left();
    turn_left();
    turn_left();
}

Definícia a deklarácia funkcie

  • Na mieste, kde chceme funkciu volať, už musí byť funkcia známa. Ak teda prekladač dôjde na miesto, kde sa má volať funkcia, o ktorej nič nevie, dôjde ku chybe aj napriek tomu, že sa definícia tejto funkcie nachádza v programe neskôr:
#include <karel.h>

// function definition
void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(400);
    turn_left();
}

int main() {
    turn_on("stairs1.kw");

    set_step_delay(400);

    pick_beeper();
    turn_left();
    step();
    // function call
    turn_right();
    step();

    turn_off();
}
  • Spôsob, ktorým je možné sa tomuto problému vyhnúť, okrem samotnej definície funkcie pred jej prvým použitím, je deklarácia funkcie pred jej prvým použitím. Tým prekladaču povieme, že táto funkcia bude zadefinovaná neskôr.
  • To isté musí platiť aj o volaní funkcie z inej funkcie. Funkcia, ktorá volá inú funkciu, musí poznať v dobe jej volania aspoň jej deklaráciu.
  • Častý spôsob, ktorý sa používa, je uviesť pred funkciou main() zoznam všetkých deklarácií funkcií, ktoré budú zadefinované v programe neskôr (za funkciou main()). Na poradí deklarovaných funkcií pritom nezáleží:
#include <karel.h>

// function declaration
void turn_right();

int main() {
    turn_on("stairs1.kw");

    set_step_delay(400);

    pick_beeper();
    turn_left();
    step();
    // function call
    turn_right();
    step();

    turn_off();
}

// function definition
void turn_right() {
    set_step_delay(0);
    turn_left();
    turn_left();
    set_step_delay(400);
    turn_left();
}

Sekvencia, vetvenie, cyklus

  • Ak píšeme algoritmus krok za krokom, hovoríme o sekvencii.
  • Avšak nie vždy je výhodné zapísať celý algorimus krok po kroku. Ak sa v programe potrebujeme rozhodnúť, t.j. rozdeliť ho na viac častí, hovoríme o vetvení. Programy vetvíme na základe rôznych podmienok.
  • Robot Karel sa v programoch môže rozhodovať podľa senzorov:

    • front_is_clear()
    • beepers_present()
    • beepers_in_bag()
    • facing_north()
  • V jazyku C môžeme program vetviť pomocou podmienky if:

if (front_is_clear()) {
    step();
    turn_left();
}
  • Ak je podmienka splnená, vykonajú sa obidva príkazy (step() aj turn_left()). Ak podmienka nie je splnená, obidva príkazy sa preskočia a program pokračuje ďalej.
  • Avšak netreba zabúdať na ohraničenie tela cyklu. V tomto prípade ak je podmienka splnená, vykonajú sa síce obidva príkazy, no ak podmienka nie je splnená, preskočí sa iba prvý príkaz (funkcia) a turn_left() sa vykoná, pretože už nie je súčasťou tela podmienky if:
if (front_is_clear())
    step();
    turn_left();
  • Ak potrebujeme program rozdeliť do dvoch vetiev, k if pridáme vetvu else:
if (front_is_clear()) {
    step();
}
else {
    turn_left();
    turn_left();
    turn_left();
}
  • Opať si dajme pozor na ohraničenie príkazov

Iterácia

  • Opakovanie určitého procesu
  • Vyskytuje sa v cykloch, my si ukážeme cyklus while a do-while
  • Cyklus while nám umožňuje opakovať určitý proces, kým je podmienka splnená. Typické príklady pre robota Karla:
// run to the end of the street
while (front_is_clear()) {
    step();
}

// collect all the beepers at the corner
while (beepers_present()) {
    pick_beeper();
}
  • Pri prvom nesplnení podmienky sa vykonávanie iterácií cyklu ukončí. Cyklus while má podmienku uvedenú na jeho začiatku, a teda je možné, že telo cyklu sa nevykoná ani raz.
  • Cyklus do-while nám tiež umožňuje opakovať určitý proces, kým je podmienka splnená. Avšak podmienku má uvedenú na konci, čo znamená, že telo cyklu sa vykoná minimálne raz. Príklad:
do{
    step();
    if (beepers_in_bag()) {
        put_beeper();
    }
} while (front_is_clear());

Doplňujúce zdroje

  1. Herout: Učebnica jazyka C
  2. Kernighan, Ritchie: Programovací jazyk C
  3. Pattis: Karel The Robot: A Gentle Introduction to the Art of Programming, 2nd Edition

Video