155IN3G Informatika 3

Základní údaje o předmětu

• Aktuální a kompletní informace jsou na této stránce
• Kód předmětu: 155IN3G
• Garant předmětu:

Ing. Jan Pytel, Ph.D.

• Přednášející:

Ing. Jan Pytel, Ph.D.

• Rozsah: 2+2
• Počet kreditů: 5
• Ukončení: z,zk

Anotace

Úvodní kurz programování v jazyce C++ seznamuje studenty se základními prvky jazyka, strukturou programu a typy dat. Předmět postupuje od elementárních pojmů jako jsou deklarace proměnných, konstanty, inicializace proměnných, výrazy, příkazy, funkce a ukazatele. Výuka probíhá v prostředí operačního systému GNU/Linux.

Důraz je kladen na objektové vlastnosti jazyka a používání vybraných nástrojů standardní C++ knihovny, jako jsou například kontejnery vector a map, a jejich využití při dynamické alokaci paměti, které je nezbytné např. pro programování jednoduchých geodetických úloh a řešení úloh vyrovnávacího počtu.

Třídy, jako nástroj pro definování uživatelských typů, jsou nejprve demonstrovány na jednoduchých příkladech, ve kterých je organizace paměti zajištěna např. standardními kontejnery. Po úvodním výkladu pojmů dědičnost a polymorfismus následuje seznámení s mechanismem výjimek a jejich ošetření. Ke třídám, dědičnosti a polymorfismu se studenti znovu vrací při výkladu dynamické alokace paměti.

Tento úvodní kurz si neklade za cíl vyčerpávajícím způsobem probrat v plné šíři všechny rysy jazyka C++ (např. problematika šablon je pouze naznačena), jeho cílem je ale seznámit studenty dostatečně podrobně s C++, tak aby mohli aktivně programovat a byli připraveni pro následné studium objektového programování.

Doporučená literatura

1. A. Čepek: Úvod do C++ http://geo.fsv.cvut.cz/vyuka/c++bc/skripta/

Přednášky

Přednášející: prof. Ing. Aleš Čepek, CSc.

1. První seznámení s platformou Qt Creator, základní pojmy C++
2. Programování cyklů
3. Funkce, první seznámení
4. Knihovna matvec
5. Gaussova eliminace rozšířené soustavy
6. Zpracování vstupní dávky souřadnic
7. Vstupní/výstupní proudy
8. Ukazatele a dynamická alokace paměti
9. Ukazatel na funkci (2)
10. Výjimky
11. Kontejnery a iterátory
12. Dědičnost a polymorfismus

Přednášky ve formátu PDF a příklady http://geo.fsv.cvut.cz/vyuka/c++bc/ .

Cvičení

Cvičení navazují na látku probíranou na přednáškách.

První seznámení s SDK Qt Creator

Založení projektu:

1. File
2. New File or Project ...
3. Výběr typu projektu (Qt Widget Projekt -> Qt Gui Application
4. jméno projektu a výběr adresáře (umístění projektu)
5. Target Setup (Desktop ... závisí na instalaci, zda je více možností)
6. Class Information (význam si objasníme později)
7. Project Management (správa projektu)

Qt Creator vygeneruje kostru aplikace, základní widgety lze spravovat v grafickém editoru. Překlad a spuštění aplikace: funkce Run CTRL+R

Doplněny widgety typu QLabel, QLineEdit a QPushButton

Qt Creator umožňuje nastavení atributů widgetů a definovat slot pro obsluhu standardních signálů (pravé tlačítko myši -> Go to slot... -> výběr signálu).

Vygenerovaný slot je funkce (metoda dané třídy). V kostře aplikace vygeneruje Qt Creator vždy dvě speciální metody: kostruktor a destruktor, které se automaticky volají při vytvoření a zrušení objektu.

Základní pojmy

1. program hello world, seznámení s prostředím Qt Creator (konzolové aplikace)
2. vybrané základní datové typy (int, double, bool, void)
3. základní aritmetické operace +, -, *, / a %
4. operátor přiřazení a operátory +=, -=, *= ...
5. blok {}, platnost a viditelnost objektů (proměnných)
6. standardní vstup a výstup pro základní číselné typy
7. odvozené typy ukazatel a reference (první zmínka)

Programování cyklů

1. první seznámení s kontejnerem vector
2. relační operátory <, >, <=, >=, !=
3. příkazy for, while, do, continue a break
4. příklady programování jednoduchých cyklů

Funkce, první seznámení

1. napište a otestuje jednoduché funkce jako ${\sqrt {x}},\quad \sin x,\ldots \quad$ (více viz sbírka příkladů C++ Bc.).

Knihovna matvec

1. maticová knihovna matvec
2. součet dvou vektorů, součet dvou matic
3. součin matice a vektoru
4. součin dvou matic

Příklad práce s maticemi a vektory

Gaussova eliminace rozšířené soustavy

Řesení soustavy lineárních rovnic Gaussovou eliminací

1. vstup rozšířená matice soutavy (absolutní členy tvoří N+1 sloupec; na cvičení se omezíme na případ s jedinou pravou stranou)
2. převod na horní trojuhelníkovou soutavou (pomocí elementárních úprav: výměna dvou řádků, přenásobení řádku nenulovývm koeficientem, přičtení k-násobku jiného řádku)
3. řešení horní trojúhelníkové soustavy (zpětná substituce)

Zpracování vstupní dávky souřadnic

Napište program, který načte a zpracuje soubor souřadnic v následujícím formátu (viz zadádí C++ Bc. 19):

• soubor může obsahovat komentáře (#)
• může obsahovat prázdné řádky
• na řádku se uvádí číslo bodu a souřadnice xy, z nebo xyz

# jednoduchy seznam souradnic
# ---------------------------

1001 234.53 345.22          # x y
1002 355.24 456.46 555.12   # x y z
1003 423.12                 # z

# ------ konec dat ------

Vstupní/výstupní proudy

Napište funkci std::istream& komentář(std::istream& inp) podle zadání C++ Bc. 18.

Funkce komentář() vrací referenci na vstupní proud a může být proto použita např. v podmínce while(...) pro čtení vstupních dat.

Poznámka: funkce komentář() je po formální stránce manipulátor bez parametrů (více viz skripta).

Ukazatele a dynamická alokace paměti

• Ukazatel na funkci
  • napište funkci, která metodou půlení hledá řešení soustavy $f(x)=0$, kde $f$ je spojitá funkce, která na zadaném inrevalu $(a,b)$ nabývá hodnot s různými znaménky (viz též metoda tětiv z příkladu 29).
• Napište funkce, které realizují jednoduché funkce s maticemi:
  • alokování paměti pro matici
  • načtení matice ze souboru
  • výpis matice
  • uvolněné alokované paměti

Ukazatel na funkci (2)

Napište funkci pro numerický výpočet určitého integrálu Simpsonovou metodou (příklad 30).

Použijte deklaraci typedef pro typ ukazatel na funkci typu double s jedním argumentem typu double.

typedef double (*Funkce)(double);

double simpson(Funkce f, double a, double b, int m);   // deklarace funkce

Poznámka: deklaraci typedef můžeme použít pro zjednodušení práce s libovolným typem, nevytváří nový typ ale pouze náhradní jméno.

Výjimky

• try blok
• vyvolání výjimky
• zpracování výjimek

Kontejnery a iterátory

• napište program, který po řádcích čte zadaný text a vytváří slovník, ve kterém je pro každé slovo uveden seznam řádků na kterých se dané slovo vyskytuje.

Dědičnost a polymorfismus

Navrhněte jednoduchou soustavu tříd demonstrujících využití polymorfismu. Např. Osoba -> (Student | Učitel) s virtuální metodou info() o dané osobě, demonstrovano na seznamu osob.

Rozpis cvičení

• Zimní semestr 2012/2013
• Zimní semestr 2011/2012
• Zimní semestr 2010/2011
• Zimní semestr 2008/2009
• Zimní semestr 2007/2008
• Zimní semestr 2006/2007
• Letní semestr 2005/2006
• Zimní semestr 2005/2006

Skripta, příklady, tutoriály

Skripta

Úvod do C++, nakladatelství ČVUT

Příklady

Příklady C++ pro bakaláře

Návody, tutoriály

Qt Creator

Maticová C++ knihovna matvec

Tvorba programů v prostředí OS GNU/Linux

GNU Emacs

Code::Blocks

Dev-C++

Zápočet

Během semetru se píší tři testy

1. test na jednoduché funkce
2. test programování úloh s maticemi a vektory
3. test na jednoduché simulace

Uvedené tématické okruhy nikterak neomezují témata úloh u zkoušky. Pro udělení zápočtu jsou nutné alespoň dva úspěšné testy.

Zkouška

• Zkouška v počítačové učebně probíhá v prostředí SDK Qt pod OS Linux, konto "zkouska" (přihlášení obdobně jako na konto "student"). Z tohoto pravidla se nepřipouštějí výjimky, důvodem jsou opakované dřívejší pokusy o podvody u zkoušky.

• Před zahájením zkoušky je vylosováno zadání pro daný termín (zadání pro všechny vypsané termíny, plus rezerva 3, byla připravena předem a jsou uložena v zalepených obálkách). Studenti na zadání vyplní svoje jméno, číslo počítače a datum, po zkončení první části zkoušky zadání odevzdají (slouží pro identifikaci jejich řešení).

• Zkouška má obecně tři části, první a druhá část vždy v počítačové učebně. V první části (60 minut) je zadána jedna úloha a podle výsledku zkouška pokračuje (pokud má student zájem o případné zlepšení známky). Od akademického roku 2009-2010 nejsou zadávány úlohy ze sbírky.

• Do druhé části postupují kandidáti na známky D nebo lepší, není garantováno. Druhá část zkoušky trvá opět 60 minut. Zadání je individuální, obvykle ale společné pro celou skupinu.

• U zkoušky mohou studenti používat skripta, jeden list formátu A4 s poznámkami a jeden list formátu A4 na pracovní poznámky během zkoušky.

• třetí část zkoušky probíhá individuálně a rozřazuje přihlašené studenty do kategorií B a A.

Každý student si může donést jeden list formátu A4 s poznámkami (nesmí ale obsahovat kód ze sbírky příkladů) a může používat jeden čistý list A4 na poznámky. Nutno předložit ke schválení před zahájením zkoušky.

Při zkoušce nesmí studenti používat žádné další pomůcky, jedinou výjimkou jsou text skripta (nesmí pochopitelně obsahovat vepsané či vložené kódy příkladů ze sbírky) a veškeré informace z online dokumentace operačního systému. Skripta musí zůstat u počítače ke kontrole před vyhodnocením daného kola.

Studenti jmenovitě nesmí používat externí media, ani kalkulačky, mobily, organizátory a pod. Veškeré tašky a osobní věci musí být uloženy v prostoru u tabule (B870). Během 45 minut v jednotlivých fázích zkoušky nesmí studenti opouštět učebnu.

Při zkoušce mohou studenti komunikovat pouze s vyučujícími. Komunikace s jinými studenty nebo s kýmkoliv mimo učebnu (jakoukoliv formou) je považována za pokus o podvod.

Pokusy o podvod budou nahlášeny disciplinární komisi fakulty s návrhem na ukončení studia.

Zimní semestr 2011/2012

• první část zkoušky prodloužena ze 45 na 60 minut
• zadání jsou losována před zkouškou.

Zimní semestr 2010/2011

• Napište funkci, která v dané matici zamění i-tý a j-tý řádek anebo m-tý a n-tý sloupec

• Napište funkci, která počítá součin vektoru a symetrické matice, která je uložena v jednorozměrném poli po řádcích (horní trojúhelník). Výpočet ověřte porovnáním s výpočtem A*b s využitím knihovny matvec.

• Napište funkci, která "normalizuje rastrová data." Rastrová data jsou dána maticí s reálnými hodnotami. Přepočítejte je tak, aby minimální hodnota byla převedena na nulu, maximálni na 100 (tj. přepočtěte data na relativní udaje v procentech). Ověřte/demonstrujte výsledky funkce na základě náhodně generovaných dat (rozměry matice a náhodné hodnoty minima a maxima, generované hodnoty prvků matice generujte s rovnoměrným rozdělením).

• C++ Bc. 12 : napište funkci plocha, která počítá plochu polygonu a použijte ji v programu, který čte vstupní data se standardního proudu (např. ze souboru a pod.). Pozn.: byli přihlášeni pouze 3 studenti.

• Napište funkci, která počítá rozklad přirozeného čísla na součet Fibonacciho čísel; tj. posloupnost 1, 2, 3, 5, 8, 13, 21, .... F(n) = F(n-1) + F(n-2). Např. 19 = 13 + 5 + 1.

• napište funkci pro výpočet Pearsonova korelačního koeficientu. Ověřte na simulovaných datech. Pozn.: byli prihlaseni pouze 2 studenti

• Napište funkci, která pro zadaný soubor bodů (x_i, y_i)</cmath> počítá koeficienty lineární regrese ax + b = y. Ověřte na simulovaných vstupních datech.

• Napište funkci, která počítá rozklad přirozeného čísla na souči prvočísel. Funkci ověřte v programu, který pro zadané vstupní hodnoty volá danou funkci a vypisuje rozklad ve formátu čislo = základ^mocnina * ... , např. 240 = 2^4 * 3^1 * 5^1.

• Úloha o koze (zjednodušená verze) Na kruhové oplocené zahradě se pase koza uvazaná na provaze, jehož délka je rovna poloměru parcely a který je uvázán na kůlu na obvodu parcely. Kolik procent plochy parcely koza spase?

• Napište funkci, která pro vektory x a y a matici M vypočíta hodnot bilineární formy x'My. Ve funkci nepoužívejte žádné pomocné objekty (vektory), ale pouze jednoduche proměnné. Výsledek ověřte porovnáním s výpočtem v matvecu.

• Přehled klasifikace V textovém souboru jsou zapisovány tyto údaje: příjmení a jméno studenta, kód předmětu, počet kreditů a klasifikace, např.

     Rambousek Pavel  153DASY 5 A
     Sedláček Pavel   101KOGG 5 C
     Bartošová Eva    152TEG1 6 B
        ....

Vypočítejte vážený studijní průměr pro všechny studenty ze seznamu

     1.91  Bartošková Jana
     1.71  Bartošová Eva
     1.62  Herman Jakub
     1.55  Herman Pavel
        ....

Nejjednodušší cestou je použít standardní kontejner map s uživatelskou strukturou pro společné ukládání souctu kredity*znamka a kredity.

Alternativně napište funkci, která vrací index studenta v seznamu studentů, pokud student v seznamu neni uveden, přidá jej funkce na konec a vrátí index. Prototyp funkce je

    int student(std::string student, std::vector<std::string>& seznam);

kde string student = prijmeni + ' ' + jmeno. Pro trojici index, kredity, znamka lze vážené průmery vypočítat například ze tří pracovních vektorů (do kterých jsou ukládána načítaná data).

• Hammingova čísla jsou čísla, která jsou dělitelná pouze prvočísly 2, 3 a 5, jinak řečeno je lze zapsat ve tvaru 2^i x 3^j x 5^k, kde i,j,k >= 0. Hammingova čísla tvoří posloupnost 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, ...

Napište program, který vypočte n-té Hammingovo číslo, pro n=150.

• Napište funkci pro vyhlazení rastrových dat, uložených v (celočíselné) matici s hodnotami 0 až 127. Funkce pro každý pixel (prvek matice) vypočte novou hodnotu jako vážený aritmetický průměr daného pixelu s váhou p a všech sousedních pixelů s váhou 1, kde váha p je dána počtem sousedů.

Například pro vstupní matici M dimenze 4x5 s prvky

      11 12 13 14 15           15 15 16 17 18
      21 22 23 24 25    ==>    21 22 23 24 25
      31 32 33 34 35	        31 32 33 34 35
      41 42 43 44 45  	        38 39 40 41 41

je vyhlazená hodnot prvku n_11 (tři sousedi) rovna

       n_11 = ( 3 x 11 + 12 + 21 + 22 ) / 6 = 15   (zaokrouhleno 14.667)

podobně

       n_45 = ( 3 x 45 + 34 + 35 + 44 ) / 6 = 41   (zaokrouhleno 41.333)

pro prvek m_22 (osm sousedů)

       n_22 = (8 x 22 + 11+12+13 + 21+23 + 31+32+33) / 16 = 22

Oveřte pro uvedený příklad a pro náhodně generované matice náhodného řádu m x n.

Zimní semestr 2008/2009

Protože mě již unavovalo neustále hlídat některé studenty, aby neopisovali řešené příklady ze sbírky (odmítám připustit, aby vysokoškolská výuka degenerovala na úroveň střední školy; mám na mysli mizerné střední školy), začal jsem pro každou zkoušku dávat individuální zadání, která nebyla použita a která se nebudou v budoucnu opakovat. AČ

Zimní semestr 2007/2008

Na září (16.9.) jsem vypsal termín, na který se mohou přihlásit studenti, kteří nemají zkoušku, ale byl jim explicitně udělen zápočet (všichni ostatní mají v KOSu uvedeno N, tj. zápočet neudělen). Implicitně byly zápočty udělovány studentům, kteří úspěšně složili zkoušku.

Možnost zápisu na zářijový termín je omezena pouze pro studenty, kteří sice neuspěli, ale jejich znalosti byly takříkajíc na hraně a kterým jsem chtěl poskytnout ještě jeden pokus. Především jde o studenty druhého ročníku, kteří snad napoprve zkoušku podcenili. Termín proto byl stanoven tak, aby nekolidoval s letním výcvikovým kurze, který se koná od 31.8 do 7.9.

Pokud se nemůžete na zkoušku přes KOS přihlásit, znamená to, že vám nebyl udělen zápočet a zářijový opravný termín se vás již netýka.

Zimní semestr je uzavřen.

Zimní semestr 2006/2007

• protože má předmět zapsáno 224 studentů, nastavil jsem kapacitu terminů na 21, což je počet počítačů v B870. Obvykle jsem nechával 1-2 mista rezervu pro případ výpadku hardwaru. Letos tedy "jedeme na doraz", doufejme, že technika neselže.

• první termíny zatím nejsou otevřeny (mají kapacitu 0), kapacita bude nastavena na plný počet dodatečně.

• jak bude postupovat zkouškové období, budu postupně odebírat atribut "opravný" termín, tak aby se případně mohli hlásit i studenti, kteří ještě na zkoušce nebyli. Záměr je umožnit studentům, kteří neuspěli přihlásit se na některý z opravných termínu (je jich řádově třetina, jak určují fakultní předpisy)

Externí odkazy

• http://www.cplusplus.com/
• Bjarne Stroustrup's FAQ
• Marshall Cline; C++ FAQ
• Qt