Kontrolní test znalostí pro jazyk C++

Kontrolní test znalostí pro jazyk C++

(Řešení)

Vážení čtenáři,

toto je kontrolní test, na kterém si můžete ověřit své znalosti algoritmizace a programování v jazyce C++. Test je složen z otevřených otázek. Při otevřených otázkách odpovídáte volným stylem. Při každé otázce je v hranatých závorkách uveden maximální počet bodů, které za její správné zodpovězení můžete získat.

Otázka č. 1 [1 bod]: Jak byste definovali algoritmus?

Odpověď: Algoritmus je exaktní předpis definující výpočtový proces, jenž řeší vymezenou úlohu. Algoritmus je tvořen neprázdnou a konečnou množinou kroků, které vedou od vstupů k výstupům.

Otázka č. 2 [5 bodů]: Charakterizujte základní vlastnosti algoritmu.

Odpověď: K základním vlastnostem algoritmu patří:

Všeobecnost: Algoritmus řeší jakoukoliv úlohu z jisté všeobecné kategorie úloh.

Jednoznačnost: Po provedení libovolného kroku algoritmu musí být zřejmé, jaký bude krok následující.

Konečnost: Algoritmus je tvořen konečnou posloupností kroků.

Rezultativnost: Po realizaci konečného počtu kroků nám algoritmus poskytne výsledek své činnosti.

Efektivnost: Obecně říkáme, že algoritmus je efektivní, pokud dovede vyřešit úlohu v polynomiálním čase (čas provádění algoritmu je ohraničen matematickou funkcí, v níž se vyskytuje polynom n-tého stupně). U algoritmů rozlišujeme časovou a prostorovou (paměťovou) efektivnost. Časová efektivnost algoritmu vyjadřuje, za jak dlouho je algoritmus schopen vyřešit předestřenou úlohu (jak vidíme, efektivností algoritmu se implicitně rozumí jeho časová efektivnost). Prostorová efektivnost algoritmu říká, jak produktivně manipuluje algoritmus s operační pamětí počítače. Efektivnost algoritmů je velice úzce spojena s analýzou výpočetní složitosti algoritmů.

Otázka č. 3 [4 body]: Uvažujme dva algoritmy, α a β, jejichž časová složitost je následující:

α: O(n² + 3)

β: O(100n * log n)

Který z algoritmů je efektivnější? Svoji odpověď zdůvodněte.

Odpověď: Při analýze asymptotické časové složitosti algoritmů nejprve zkoumáme, zda mají algoritmy polynomiální povahu. Pokud ano, pracujeme s efektivními algoritmy, tedy algoritmy, jež realizují svou činnost v polynomiálním čase. Jestliže by algoritmy byly jiné než polynomiální (například exponenciální), nebyly by v praktických podmínkách použitelné pro rozsáhlé množiny vstupních dat. Oba zkoumané algoritmy jsou polynomiálními algoritmy. Dále zjišťujeme stupeň polynomu každého algoritmu. A zde vidíme, že algoritmus α obsahuje polynom druhého stupně (kvadratický člen), zatímco algoritmus β obsahuje polynom prvního stupně (lineární člen). Ačkoliv je lineární člen n algoritmu β násoben konstantou 100, v konečném důsledku dojdeme k poznání, že právě tento algoritmus je efektivnější. Při analýze časové složitosti algoritmů nám jde o počet elementárních operací, které algoritmus provede s množinou vstupních dat o objemu n. Položme tedy n = 1000, přičemž předpokládejme, že výkon jedné operace, která je aplikována na jeden prvek vstupní datové množiny, bude proveden v konstantním čase 1 ms. Dosazením získáváme:

α: 1000² + 3 = 1000003 operací

β: 100 * 1000 * log 1000 = 300000 operací

Pro vyřešení problému si algoritmus β vystačí s 0,3 mil. operacemi, zatímco algoritmus α bude vyžadovat zpracování 1 mil. operací.

Otázka č. 4 [4 body]: Navrhněte, pomocí vývojového diagramu znázorněte, a posléze implementujte algoritmus pro výpočet celkového množství tranzistorů, které budou zapotřebí na výrobu 1000 n-jádrových procesorů v jednom výrobním cyklu. Počet tranzistorů na jednom procesoru nechť je dán funkcí , kde je počet exekučních jader procesoru.

Odpověď: Vývojový diagram může mít následující podobu:

Implementace znázorněného algoritmu v jazyce C++ je takováto:

#include <iostream>

using namespace std;

int main()

Ukázková data: Na výrobu 1000 4jadrových procesorů budeme potřebovat celkem 400 miliard tranzistorů.

Otázka č. 5 [4 body]: Charakterizujte tyto termíny:

a)     Datový typ: Datový typ je abstrakcí, která nám v programování umožňuje pracovat s různorodými daty. Datový typ určuje množinu dat, která budeme moci ukládat do proměnných dotyčného datového typu. Kromě toho datový typ determinuje rovněž množinu operací, které budeme moci s daty uskutečňovat. Každý datový typ má rozsah, jenž je vyjádřen počtem bitů, které jsou nutné k uchování kterékoliv z přípustných hodnot daného datového typu. 

b)    Alokační kapacita proměnné: Proměnná je symbolické pojmenování datového objektu, který je alokován v operační paměti počítače. (Přesněji: Jestliže předpokládáme užití proměnné primitivního datového typu jazyka C++, tak můžeme proměnnou definovat jako datový objekt, jenž je umístěn v zásobníku primárního vlákna počítačového programu.) Paměťový prostor, který je datovému objektu přidělen, se označuje jako alokační kapacita proměnné. Tento prostor je měřen v bajtech (B). Proměnné mohou mít rozličnou alokační kapacitu, v závislosti na svých datových typech. Alokační kapacitu proměnné zjistíme operátorem sizeof ve výrazu sizeof(I_P), kde I_P je identifikátor proměnné (dodejme, že závorky obklopující I_P nejsou ve výrazu povinné).

c)     Funkce: V programování definujeme funkci jako konečnou a neprázdnou množinu programových příkazu, které jsou provedeny vždy, když je funkce zavolána. Toto chápání funkce je tedy zcela odlišné od ryze matematického aspektu funkce, v němž je funkce zobrazením prvků jedné množiny do jiné množiny. V dobách strukturovaného programování byly funkce základními stavebními bloky počítačových programů. V objektově orientovaném programování jsou funkce mechanizmem, pomocí kterého se implementují tzv. metody, jež formují behaviorální složku virtuálních objektů.

d)    Přiřazovací příkaz: Základní příkaz, jenž realizuje přiřazení hodnoty do cílového datového objektu. Jeho generický zápis je následující:

I_P = V;

kde:

I_P je identifikátor proměnné.

V je výraz.

Hodnota, která je předmětem přiřazení, může na syntaktické úrovni vystupovat jako diskrétní konstanta, anebo může být vypočtena na základě korektně zapsaného výrazu. Cílovým datovým objektem, do něhož bude hodnota umístěna, je nejčastěji samostatná proměnná primitivního datového typu. Nemusí tomu tak ale být vždy: cílovým datovým objektem může být například také prvek pole, anebo datový člen instance struktury. Jazyk C++ umožňuje i vícenásobné přiřazení, kdy je jedna hodnota přiřazena do více datových objektů současně. Všeobecná syntaktická podoba vícenásobného přiřazení je takováto:

I_P1 = I_P2 = I_P3 = V;

kde:

I_P1, I_P2 a I_P3 jsou identifikátory proměnných.

V je výraz.

Poznamenejme, že operátor přiřazení (=) je asociativní ve směru zprava doleva ( ). To tedy znamená, že výše zapsaný příkaz s vícenásobným přiřazením, bude vyhodnocen následovně:

(I_P1 = (I_P2 = (I_P3 = V)));

Otázka č. 6 [5 bodů]: Vysvětlete, jak budou realizovány typové konverze v následujícím fragmentu zdrojového kódu:

int main()

Odpověď: Ze zadání úlohy vyplývá, že kritickým místem fragmentu zdrojového kódu, je definiční inicializace proměnné c. Věnujme se proto analýze výrazu, jenž je situován na pravé straně od přiřazovacího operátoru. Výraz a + b / 3 je aritmetickým výrazem, poněvadž v něm jasně identifikujeme užití dvou aritmetických operátorů. Podle priority zúčastněných operátorů víme povědět, že výraz bude vyhodnocen takto: a + (b / 3). Nejprve se bude překladač soustředit na vyhodnocení podvýrazu b / 3. Než může být výraz vyhodnocen, je nutno určit, zda je zachována kompatibilita datových typů obou operandů. Prvním operandem je proměnná b, jejímž typem je float. Druhým operandem je diskrétní celočíselná konstanta 3, které překladač implicitně přisoudí typ int. Omezíme-li se pouze na datové typy, pak máme před sebou výraz float / int. Jak vidíme, existuje zde nesoulad datových typů, který bude zapotřebí odstranit implicitní typovou konverzí. Překladač proto implicitně převede typ konstanty 3 z int na float. Tím se z konstanty 3 stává konstanta 3.0f. V tuto chvíli má překladač před sebou upravený výraz b / 3.0f, resp. float / float, ve vyjádření datových typů. Jsou-li oba operandy operátoru / reálné, bude uskutečněno reálné dělení. Výsledkem bude podíl, jenž bude opět reálný. Pro zjednodušení označme hodnotu podílu identifikátorem p.

Když překladač vyhodnotil podvýraz, vrací se zpět k původnímu výrazu, jenž má v tomto momentě podobu a + p. Dále postupujeme analogicky jako při vyhodnocování podvýrazu. Po provedení analýzy datových typů operandů zjišťujeme, že 1. operand (proměnná a) je celočíselná, zatímco 2. operand (hodnota podílu symbolicky označena jako p) je reálná. Poněvadž znovu detekujeme nesoulad datových typů, překladač zpracuje implicitní typovou konverzi, cílem které bude převést hodnotu 1. operandu z typu int na typ float. Po sjednocení datových typů má překladač před sebou výraz float + float, který jednoduše vyhodnotí.

Tím ještě nekončíme, neboť reálná hodnota (typu float) aritmetického výrazu má být přiřazena do cílové proměnné typu double. Před přiřazením se tedy uskuteční poslední typová konverze, která transformuje hodnotu typu float na hodnotu typu double. Ta pak bude uložena do proměnné. Vzhledem k tomu, že typ double se vyznačuje dvojnásobnou přesností oproti typu float, tato implicitní typová konverze je bezpečná (nikdy nemůže dojít ke ztrátě datové informace).

Otázka č. 7 [4 body]: Napište program, který vypočte druhou mocninu uživatelem zadaného přirozeného čísla. 

Odpověď:

#include <iostream>

using namespace std;

int main()

Otázka č. 8 [2 body]: Je možné v jednom definičním příkazu vytvořit a inicializovat více proměnných? Pokud ano, ukažte jak. Jestliže ne, vysvětlete proč.

Odpověď: Ano, je to možné, ovšem za předpokladu, že všechny definované a inicializované proměnné disponují identickým datovým typem. Například:

int a = 10, b = 20;

Otázka č. 9 [5 bodů]: Pro potřeby medicínského softwaru vytvořte program, který bude schopen identifikovat ejekční frakci pacientova srdce. Ejekční frakce je ukazatelem, jenž vyjadřuje schopnost levé komory srdce přečerpávat krev. Ejekční frakce je procentuální hodnotou, kterou vypočteme podle následujícího matematického vzorce:

kde:

je objem krve (v ml) v levé komoře před kontrakcí srdce.

je objem krve (v ml) v levé komoře po kontrakci srdce.

U zdravého jedince se hodnota ejekční frakce pohybuje v intervalu <55 %, 75 %>.

Odpověď:

#include <iostream>

using namespace std;

int main()

Ukázková data: Pokud budeme předpokládat, že objem srdeční komory před kontrakcí srdcového svalu je 120 ml a objem srdeční komory po kontrakci srdcového svalu je 50 ml, pak pacientova ejekční frakce je přibližně 58 %, což je spodní hranice intervalu normálních hodnot.

Otázka č. 10 [2 body]: Co je to priorita a asociativita operátorů?

Odpověď: Priorita definuje pořadí realizace programových operací předepsaných operátory. Podle své priority se operátory řadí do mnoha prioritních tříd, přičemž platí, že operátory patřící do jedné prioritní třídy mají stejnou prioritu. Kupříkladu v podmínkovém výrazu rozhodovacího příkazu if(x + y < z) budou nejprve sečteny hodnoty uložené v proměnných x a y. A až poté se ke slovu dostane relační operátor, jenž bude testovat, zda je hodnota součtu menší než aktuální hodnota proměnné z. Jednoduše řečeno, podmínkový výraz bude vyhodnocen, jako kdyby byl zapsán takto: (x + y) < z. Je to proto, že binární aritmetický operátor + má vyšší prioritu než binární relační operátor <. (Pochopitelně, jestli chceme, smíme aritmetický podvýraz podmínkového výrazu vložit do závorek, ovšem není to nutné, protože na základě prioritních pravidel dovede překladač výraz správně vyhodnotit.)

Asociativita je definována jako pořadí realizace programových operací, které jsou předepsány operátory se stejnou prioritou. Operátory mohou být asociativní zleva doprava ( ), nebo zprava doleva ( ). Překladač upotřebuje asociativní pravidla tehdy, pokud vyhodnocuje výraz, v němž se vyskytují operátory se stejnou prioritou (čili operátory pocházející z jedné prioritní třídy).

Otázka č. 11 [3 body]: Je v jazyku C++ garantováno pořadí vyhodnocování operandů?

Odpověď: Ano i ne. Existuje čtveřice operátorů, které mají pořadí vyhodnocování svých operandů vždy jasně determinované. Jedná se o tyto operátory: && (operátor logické konjunkce), || (operátor logické disjunkce), ?: (ternární operátor) a , (operátor čárka neboli operátor postupného vyhodnocování). Logické operátory && a || uskutečňují zkrácené vyhodnocování logických výrazů, takže vždy začínají svou práci vyhodnocením levého (1. operandu). Na základě hodnoty 1. operandu pak tyto logické operátory přijímají rozhodnutí, zda bude nutné vyhodnotit také pravý (2. operand), či nikoliv. Ternární operátor ?: realizuje kompaktní dvojcestné rozhodování. Jelikož rozhodování se odvíjí od hodnoty 1. operandu, jeho vyhodnocením bude operátor ?: začínat. Operátor postupného vyhodnocení (,) vždy nejdříve vyhodnotí 1. operand, a poté pokračuje vyhodnocením 2. operandu.

U ostatních operátorů není zaručeno, v jakém pořadí budou vyhodnocovány operandy, na něž jsou tyto operátory aplikovány. Kupříkladu ve výrazu o * p není pevně deklarováno, zda bude nejprve vyhodnocen operand o, nebo operand p. Přesné pořadí vyhodnocování operandů je závislé na použitém překladači.

Vyhodnocení

Na základě dosažených bodů získáváte klasifikační známku podle následující hodnotící tabulky. Intervalové rozpětí a příslušné známky odpovídají klasifikační stupnici používané na vysokých školách. Abyste absolvovali zkoušku, musíte být hodnoceni nejméně známkou E.

Ján Hanák