PA2

Question 1

Programovací styly

Answer 1

• Naivní – veškerý kód ve funkci main
• Procedurální – rozložení problému na podproblémy, které jsou realizovány funkcemi a procedurami
• Objektově orientovaný – při rozkladu na podproblémy specifikujeme nové datové typy

Question 2

Objektově orientovaného programování v C++

Answer 2

• Realizace datový abstrakcí (typů) použitím tříd a objektů
• Objekt se může nacházet v různých stavech daných hodnotami atributů
objektu
• Chování objektu je dáno metodami, které jsou pro něj definovány
• Datové položky a metody objektu jsou dány typem objektu (třídou)

Question 3

Zapouzdření (Encapsulation)

Answer 3

• Ukrytí implementačních detailů rozhraním třídy (metodami třídy)
• Řízení přístupu pomocí klíčových slov
o public,
o protected
o private
• Privátní metody a atributy jsou zapouzdřeny, přístupné jen v metodách dané třídy
• Chráněné metody a atributy jsou částečně zapouzdřeny, jsou přístupné v metodách dané třídy a jejích potomků

Question 4

Dědičnost (Inheritance)

Answer 4

• Existence vztahu rodič – potomek mezi třídami (datovými typy)
• Může deklarovat nové atributy a metody
• Metodu je možné předefinovat, atribut nikoli
• Potomek má přístup ke všem veřejným a neprivátním atributům a metodám
• Potomek může být přiřazen předkovi, nikoli však předek potomkovi

Question 5

Atributy a metody

Answer 5

Atribúty
- zachytávajú vlastnosti objektu pomocou dátových typov

Metody

• chovanie objektu
• procedura/funkce spojená s triedou
• špeciálne - konštruktor, deštruktor

Question 6

Statické atributy a metody

Answer 6

Statické atribúty
- nie sú súčasťou objektu, ale triedy

Statické metódy

• nejde aplikovať na objekty, ale len na triedu (triedne metódy)
• statické metódy nemôžu používať nestatické položky

Question 7

Virtuální metody

Answer 7

• Dynamicky viazaná metóda
• Kľúčové slovo virtual
• Je volaná podľa typu objektu - zavolá sa vždy správná metoda, aj keď ju voláme na premennú typu predka
• virtual table method

Question 8

Polymorfismus (Mnohotvarovost)

Answer 8

• Operace s prvkem v závislosti na jeho presnom type
• v kolekcií môžu byť prvky typu abstraktného predka, ale každá položka je konkrétneho typu a podľa toho sa volá pri volaní metódy - polymorfne

Příklad:
• Použití například pro kolekci prvků (např.: třída Element), které chceme vypsat.
• Procházíme kolekci a každou položku pošleme do streamu, protože víme, že má přetížený operátor pro uložení
do streamu.
• V každém potomkovi třídy Element může být tento výpis různý.
• Polymorfismus se postará o to, aby se každý prvek vypsal podle svého typu a nikoli obecným způsobem
definovaným ve třídě Element.

Question 9

Abstraktní třída

Answer 9

• Je třída, která definuje nebo dědí alespoň 1 čistě virtuální funkci.
o Virtuální funkce se značí funkce() = 0; (+ na začátku může být nepovinné klíčové slovo „virtual“)
• Definuje abstraktní typ z kterého nemůže být vytvořena instance.
• Slouží jako základní třída v třídním uspořádání.
• Například čítač může být číselný, znakový a pro datum, ale předek může být stejný pro všechny a deklarovat jim
rozhraní (například jako šablona).
• Operace definovány až pro potomky.

Question 10

Výjimky

Answer 10

• Ošetřování chyb při běhu programu.
• Zachycovány ovladači výjimek (exception handlers) – try catch bloky.
• Vyvolání výjimky příkazem throw.
• Výjimka se šíří vzhůru k nejbližšímu ovladači, který ji ošetří, v průběhu je čištěn zásobník a volány destruktory lokálních objektů (implementačně závislé).

Question 11

Šablona - Funkce

Answer 11

• Parametrizozvaná deklarace funkce, z kt. prekladač môže dosadením za parametre vytvoriť instanciu šablóny
• Parametrom šablóny môže byť typ parametru alebo návratového typu funkcie
• Typ je možné určit explicitně umístěním do špičatých závorek

Question 12

Šablona - Triedy

Answer 12

• Parametrizovaná deklarace třídy, ze které překladač může dosazením za parametry vytvořit instanci šablony, tj. deklaraci konkrétní třídy.
• Principy podobné jako pro šablony funkcí.
• Metody třídy jsou definovány šablonami funkcí.

Question 13

Přetěžování operátorů

Answer 13

• Použití běžných operátorů jazyka pro vlastní datové typy (třídy)
o Např třída Zlomek může implementovat operátor + a umožnit tak sčítání dvou zlomků.
• Operátory pro práci s proudy (streamy), operátor přiřazení, sčítací znaménko, přístup k položce pole, volání metody, atd.
• Možné přetížit běžnou funkcí nebo metodou – nepřirozená syntax
• Pro použití běžným zápisem (c = a + b) použijeme friend metody, případně lze :

Question 14

Mělká a hluboká kopie

Answer 14

Mělká kopie
• Přiřazení mezi objekty stejného typu → reference ukazuje na stejná data.
• Nevadí, pokud o ní víme.
• Problém s destruktorem – můžeme už uvolnit paměť nebo na data vede ještě nějaká reference?
• Možno řešit počítáním referencí.

Hluboká kopie
• Dealokace paměti, na kterou ukazuje první reference.
• Následně dynamické kopírování dat z jednoho objektu do druhého.
• Ideální přetížit operátor přiřazení.

Kopírovací konstruktor
• Implicitní vytvořen kompilátorem, vytváří mělkou kopii.
• Pro hlubokou kopii musíme sami implementovat (třeba pomocí přetíženého operátoru přiřazení)

Question 15

Abstraktní datový typ (ADT)

Answer 15

• Množina operací nezávislá na konkrétní implementaci
• Hlavním cílem je zjednodušit a zpřehlednit program, který provádí operace s daným datovým typem.
• Při programování je ADT reprezentováno rozhraním, které skrývá vlastní implementaci. Klientského
programátora, který ADT používá, zajímá jak objekt používat (jeho rozhraní), ale ne už vlastní implementace.

signatura operace:
_ + _ : int, int → int celočíselné plus (infixový zápis)
_ – : int → int postdekrementace

Question 16

Datová struktura

Answer 16

Konkrétní implementace ADT v daném programovacím jazyce. Zahrnuje reprezentaci dat a algoritmy, které
implementují danou množinu operací.
Možné implementační datové struktury:
a) pole (statické/dynamické a uspořádané/neuspořádané),
b) rozptylovací (hash) tabulka,
c) lineární spojové struktury (jednosměrný/obousměrný spojový seznam),
d) nelineární spojové struktury (stromy, grafy).

Question 17

Zásobník (Stack)

Answer 17

● Kontejner, kde data vložená naposledy jsou nejdříve
odebrána (last in, first out – LIFO).
● Interface: Push, Pop, Top, isEmpty
● Implementace
○ Spojová struktura
■ Jednosměrný spojový seznam
○ Pole
■ Statické pole (velikost dána konstantou)
■ Dynamicky alokované pole (velikost daná parametrem konstruktoru)
■ Dynamicky alokované pole s možností rozšiřování
● Složitost: O(1) tedy konstantní, kromě implementace pomocí rozšiřitelného pole

Question 18

Fronta (Queue)

Answer 18

● Kontejner, kde data vkládáme na konec a odebíráme ze začátku (first in, first out – FIFO).
● Interface: Enqueue (Push), Dequeue (Pop), Front, isEmpty
● Implementace stejná jako u zásobníku (pole/spojový seznam)
○ Při spojovém seznamu potřebujeme odkaz i na konec (ne jen na začátek)
○ Cyklické pole pro posuny – pozor na přetečení do nového kolečka
● Složitost: O(1), kromě jednoduchého pole – tam dequeue celé pole posouvá -> O(n)

Question 19

Pole (Array)

Answer 19

● Kontejner, kde jsou prvky v n-dimenzích.
● Umožnuje náhodný přístup k prvkům s konstantní časovou složitostí.
● Popis pole
○ Datový typ prvků
○ Počet dimenzí
○ Horní a dolní meze jednotlivých dimenzí
● Příklad: array[l1..h1, l2..h2, · · · , ln..hn] of T
○ T je typ prvku pole
○ n je počet dimenzí
○ li a hi jsou meze indexu v dimenzi i

Question 20

Seznam (List)

Answer 20

● Kontejner, kde data vkládáme, odebíráme a čteme
přímo z dané pozice
● Interface: Insert, Delete, Next, Prev, Read, toEnd, toStart,…
● Implementace:
○ Nejefektivnější je obousměrný spojový seznam s ukazatelem na začátek i konec
● Složitost: O(1), pokud chceme hledat – O(n) – nutno projet celý seznam.

Question 21

Tabulka (Map, Table)

Answer 21

● Kontejner s dvojicí Key-Val
● Prvek je tedy identifikován klíčem typu Key skrz který se dostaneme na hodnotu Val
● Interface: Insert, Delete, isSet, Read
● Implementace:
○ Pole, kde klíče jsou indexy v poli
■ přímý přístup
■ Jsou-li klíči celá čísla od 0..max, použijeme pro uložení hodnot pole, jehož indexy
jsou přímo klíče. Prvek tabulky s klíčem k tedy bude mít hodnotu uloženou v
prvku pole tab[k].
○ Pole (seřazené/neseřazené)
○ Jednosměrný spojový seznam (seřazený/neseřazený )
○ Binární vyhledávací strom
○ Rozptylovací tabulka (hash table)

Question 22

Množina (Set)

Answer 22

● Kontejner, který obsahuje prvky typu T bez duplikátů
● Interface
○ minimálně: Insert, Delete, isSet (příslušnost prvku k množině)
○ Další: sjednocení, porovnání, průnik, výpis prvků
● Implementace:
○ Pole (seřazené/neseřazené)
○ Jednosměrný spojový seznam (seřazený/neseřazený)
○ Binární vyhledávací strom
○ Rozptylovací tabulka (hash table)
○ Indikátorový (charakteristický) vektor - funkce, která má hodnotu 0 pro prvky, které do
množiny nepatří a 1 pro ty, které do ní patří