Celková osnova přednášek. Algoritmy I prezentace k přednáškám. Celková osnova přednášek (pokrač.) Celková osnova přednášek (pokrač

Celková osnova přednášek 0. Úvodní přednáška O předmětu Algoritmy I Prezenční forma studia

Algoritmy I – prezentace k přednáškám

Výuka Úkoly a jejich hodnocení

Kombinovaná forma studia

doc. Mgr. Jiří Dvorský, Ph.D.

Výuka Úkoly a jejich hodnocení

Katedra informatiky Fakulta elektrotechniky a informatiky VŠB – TU Ostrava

Software pro výuku Studijní literatura 1. Pojem algoritmus Algoritmický problém Pojem algoritmu Vlastnosti algoritmu Turingův stroj Church-Turingova teze

Prezentace ke dni 12. září 2016

2. Shrnutí Jiří Dvorský (VŠB – TUO)

Algoritmy I

1 / 358

Jiří Dvorský (VŠB – TUO)

Algoritmy I

Celková osnova přednášek (pokrač.)

Celková osnova přednášek (pokrač.)

3. Základy C++ 4. Počítač Hardware – základní struktura počítače Software Osobní počítače 5. Programovací jazyk 6. Jazyk C++ Jazyk C Vznik spustitelného programu 7. Základní stavební bloky C++ Datové typy v C++ Proměné 8. Řídící struktury jazyka C++ 9. Funkce v jazyce C++ 10. Složitost algoritmů 11. Motivace

12. Analýza složitosti algoritmů 13. Pole v jazyce C++ 14. Pole Výpočty lineární algebry


Algoritmy I

2 / 358

Vektorové výpočty Výpočty se čtvercovými maticemi

15. 16. 17. 18. 19. 20. 21. 22. 23. 3 / 358

Rekurze Co si představit pod pojmem rekurze? Faktoriál Fibonacciho posloupnost Využití rekurze pro řešení problémů Backtracking Jezdcova procházka Vyhledávání Vyhledávání Definice problému


Algoritmy I

4 / 358

Celková osnova přednášek (pokrač.) Sekvenční vyhledávání Vyhledávání půlením intervalu

Úvodní přednáška

24. Třídění 25. Třídění RadixSort


26. Základní třídící algoritmy


27. Asociativní třídicí algoritmy Základní třídící algoritmy Třídění výběrem – SelectSort Třídění vkládáním – InsertSort Bublinové třídění – BubbleSort

28. Pokročilé třídící algoritmy QuickSort – Třídění rozdělováním Třídění haldou – HeapSort Jiří Dvorský (VŠB – TUO)

Algoritmy I

5 / 358

O předmětu Algoritmy I



O předmětu Algoritmy I

Upozornění

předmět je úvodním kurzem programování,

Všechny aktuální informace k předmětu naleznete na

vazba na předmět Programování I, předpokládá se znalost středoškolské matematiky a obecná orientace ve výpočetní technice,

http://www.cs.vsb.cz/dvorsky/

algoritmy a datové struktury budou demonstrovány v jazyce C++,

Tato prezentace slouží jen pro účely úvodní přednášky a nebude dále aktualizována.


6 / 358


praktická implementace probíraných algoritmů a datových struktur.

7 / 358



8 / 358

Rozsah předmětu, způsob zakončení

Garant předmětu

Rozsah předmětu výuka probíhá v zimním semestru prvního ročníku bakalářského studia, hodinová dotace: 2 hodiny přednášky a 2 hodiny cvičení týdně v prezenční formě, 7 tutoriálů v kombinované formě studia.

předmět je ohodnocen 5 kredity.

doc. Mgr. Kancelář: Email: Web:

Jiří Dvorský, Ph.D. EA441 [email protected] www.cs.vsb.cz/dvorsky

K čemu je garant předmětu?

Způsob zakončení

Garant předmětu zodpovídá za průběh výuky celého předmětu, průběh cvičení, plnění úkolů na cvičeních a za korektní hodnocení úkolů. Problémy spojené se cvičeními řešte primárně se svým cvičícím. Pokud se nepodaří dosáhnout řešení problému s cvičícím obracejte se na garanta předmětu.

zakončení klasifikovaným zápočtem, klasifikovaný zápočet není zkouška, nejsou tři termíny jako u zkoušky,


Garant předmětu, přednášející, tutor komb. formy


9 / 358

Konzultační hodiny



10 / 358

Studenti se specifickými nároky

Pokud na přednášce nebudete něčemu rozumět, potřebujete poradit nebo vyřešit nějaký problém s přednáškou, cvičeními, testy, Vaší absencí na výuce například z důvodů plánované operace atd. je možné využít konzultační hodiny. V tento čas jsem připraven věnovat se Vám osobně. Termín konzultačních hodin je uveřejněn mým webových stránkách. Žádám Vás ale o dodržení několika pravidel: 1. Konzultaci je nutné si domluvit předem, nejlépe emailem. 2. Pokud potřebujete poradit s učivem, přineste si s sebou materiály, které jste si k tématu prostudovali, vypište si co je Vám jasné a kde jste se „zasekli“ a potřebujete poradit.

Rozhodně neplatí myšlenka: „Já k němu přijdu na konzultaci, on si o mě bude myslet, že jsem úplně blbej a u zápočtu mě vyhodí“.

Centrum Slunečnice FEI http://slunecnice-fei.vsb.cz/, poskytování služeb a podpory zpřístupňující studium i pro studenty se specifickými nároky, lze získat, mimo jiné, zvýšenou časovou dotaci na úkoly.

Výzva Je vysoce žádoucí, aby studenti, kteří dostanou tuto zvýšenou časovou dotaci, neprodleně kontaktovali svého cvičícího a garanta předmětu, abychom předešli případným problémům!

Přijdte se zeptat rovnou ke zdroji informací – internetová fóra jsou zaplevelena různými polopravdami i naprostými nesmysly. Jiří Dvorský (VŠB – TUO)


11 / 358



12 / 358

Algoritmy I – výuka, úkoly a jejich hodnocení

Výuka, úkoly a jejich hodnocení pro různé formy studia

Prezenční forma studia

prezenční a kombinované studium má specifickou formu výuky, obě formy studia mají specifické podmínky pro splnění předmětu, podle formy Vašeho studia se Vás týká pouze jedna ze dvou následujících částí prezentace.



13 / 358

Přednášky



14 / 358

Stručná osnova přednášek 1. Úvodní přednáška, Pojem algoritmus 2. Základy jazyka C++ 3. Řídící struktury jazyka C++

každé pondělí od 12:30 do 14:00, učebna NA1, slouží především k:

4. Funkce v jazyce C++

výkladu učiva, zdůraznění klíčových poznatků či postupů v dané části učiva, předvedení ukázkových příkladů, jejich typických řešení a tak dále,

5. Složitost algoritmů 6. Pole v jazyce C++ 7. Rekurze 8. Využití rekurze pro řešení problémů

na Vaše případné dotazy k přednášce jsem schopen odpovídat v konzultačních hodinách.

9. Vyhledávání 10. Třídění 11. Základní třídící algoritmy 12. Pokročilé třídící algoritmy



15 / 358



16 / 358

Cvičení

Cvičení

Přímá výuka ve cvičeních odpovídá přednáškám. Ve cvičeních pracují studenti pod vedením cvičícího na konkrétní implementaci příkladů v jazyce C++. V každém cvičení se předpokládá implementace jednoho až dvou příkladů.

Upozornění

Další náplní cvičení je testování Vašich znalostí formou různých testů.

Neočekávejte, že pokud nebudete chodit na přednášky, tak Vám cvičící na cvičeních bude dělat jakousi bleskovou náhradní přednášku, abyste se vůbec mohli pustit do příkladů, jejichž řešení se na cvičení předpokládá.

Cvičení nenahrazuje přednášku!

Dále je také možné konzultovat s cvičícím probírané učivo. Rozdělení do cvičení tak, jak je uvedeno v informačním systému Edison, je nutné respektovat.

Bývá dobrým zvykem, že studenti se na cvičení aspoň minimálně připraví. Není nutné látku precizně ovládat, ale je nutné se orientovat v základních pojmech. Jinak cvičení nemají smysl.

Není možné překračovat kapacitu cvičení. Veškeré přesuny je nutné mít zaznamenány v systému Edison. Až na výjimky, nelze psát testy na jiných cvičeních, než která máte zapsaná v Edisonu.



17 / 358

Úkoly – první test



18 / 358

Úkoly – druhý test

První test se bude psát na přednášce 24. října 2016 – řádný termín. Tento test se jako jediný bude psát na přednášce. Opravný termín se bude psát ve cvičeních v týdnu počínaje 31. října 2016. Bude to krátký písemný test na cca 10 až 15 minut maximálně. Test bude zaměřen na syntaxi a sémantiku jazyka C++. Jinak řečeno, otázky typu „co tato konstrukce v C++ znamená“, „je tato konstrukce správná“, „jak se deklaruje proměnná“, „co znamená tento operátor“, „jak se napíše cyklus od jedné do pěti“ atd.



19 / 358

Druhý test se bude psát na cvičeních v týdnu od 7. listopadu 2016 – řádný termín. Opravný termín bude v následujícím týdnu tj. od 14. listopadu 2016. Na začátku vymezené doby, jedno 90-ti minutové cvičení, dostanete zadání, které ve zbývajícím čase naprogramujete, odladíte a předvedete cvičícímu, který Vaše řešení ihned ohodnotí. Podrobnosti na webu předmětu.



20 / 358

Úkoly – třetí test

Úkoly – závěrečná písemná práce

Třetí test se bude psát na cvičeních v týdnu od 5. prosince 2016 – řádný termín. Opravný termín bude v následujícím týdnu tj. od 12. prosince 2016. Na začátku vymezené doby, jedno 90-ti minutové cvičení, dostanete zadání, které ve zbývajícím čase naprogramujete, odladíte a předvedete cvičícímu, který Vaše řešení ihned ohodnotí. Podrobnosti na webu předmětu.



21 / 358

V systému Edison budou vypsány termíny na které se přihlásíte. Podrobnosti na webu předmětu.



22 / 358

Obecné pokyny ke všem úkolům

Je nutné splnit všechny výše uvedené úkoly, a zároveň u všech úkolů aspoň minimální počet bodů. Minimální počet bodů 10 10 10 21 51

Maximální počet bodů 20 20 20 40 100

Všechna bodová hodnocení jsou průběžně zapisována do systému Edison.


Bude zaměřena spíše na teoretické znalosti, dále schopnost vysvětlit ukázku kódu v C++ nebo naopak napsat jednoduchou ukázku kódu v C++ podle slovního či matematického zadání.

Studenti, kteří splní všechny úkoly v řádném termínu, budou mít uzavřený předmět ke konci zápočtového týdne.

Hodnocení úkolů

První test Druhý test Třetí test Písemná práce Celkem

Řádný termín závěrečné písemná práce proběhne na přednášce 12. prosince 2016.


23 / 358

U všech úkolů jste povinni se prokázat svou studentskou kartou nebo jiným oficiálním dokladem totožnosti. Bez prokázání totožnosti Vám nebude výsledek započítán. Každý prohřešek vůči studijnímu řádu u testů a písemné práce bude nekompromisně postihován. Jde především o opisování, plagiátorství, a záměnu studentů. Je zakázáno zadání testů, písemek atd. kopírovat, fotit mobily, fotoaparáty, skenovat či jakkoliv jinak kopírovat, rozmnožovat, přenášet elektronickým způsobem a podobně. Na každý úkol máte jeden řádný pokus a jeden opravný pokus. Podmínky pro umožnění opravného termínu jsou uvedeny dále. Předmět je ukončen klasifikovaným zápočtem. Nevztahuje se tudíž na něj požadavek dvou opravných pokusů, jak to vyžaduje studijní řád u zkoušky. Žádné další pokusy nejsou možné, například dvě opravy jednoho testu. Jiří Dvorský (VŠB – TUO)


24 / 358

Pokyny k prvnímu, druhému a třetímu testu

Pokyny k prvnímu, druhému a třetímu testu Proč nepovolovat opravný termín? Plýtvání časem vyučujícího!

Řádný termín každého úkolu je pro všechny studenty daného cvičení povinný. Pokud se řádného termínu úkolu nezúčastníte, je vaší povinností se cvičícímu předem omluvit. Termín „předem“ znamená nejpozději do začátku daného cvičení. Pokud se neomluvíte, daný úkol bude považován za nesplněný (0 bodů) a opravný termín vám nebude umožněn. Důsledkem je pak neúspěšné ukončení celého předmětu. Pokud se řádného termínu zúčastníte a neuspějete s řešením zadaného úkolu, máte nárok na opravný termín. Obdobná povinnost omluvit se platí i pro opravný termín.



25 / 358

Pokyny k závěrečné písemné práci



„A budou termíny ve zkouškovém? A budou v březnu?“ „A mě to časově nevyhovuje, nemohl bych přijít někdy jindy než na to moje cvičení?“ „Víte já se vrátím v sobotu z hor, mohl bych si napsat ten test třeba v neděli odpoledne?“ V mailu jsem našel i toto: „Z důvodu pracovní vytíženosti Vám oznamuji, že úkoly z předmětu Algoritmy I budu plnit až v letním semestru. Chci se zeptat, kdy budou vypsány termíny?“ Odpověď: „Z důvodu pracovní vytíženosti v letním semestru nebudou žádné termíny. V letním semestru probíhá předmět Algoritmy II.“ „Víte mě šéf nepustí z práce! Nešlo by to nějak?“ Nešlo, v práci jste tady! Jiří Dvorský (VŠB – TUO)


26 / 358

Pokyny k závěrečné písemné práci

Řádný termín závěrečné písemné práce je pro všechny studenty povinný. Pokud se řádného termínu nezúčastníte, je vaší povinností se garantovi předmětu předem omluvit. Termín „předem“ znamená nejpozději do začátku daného termínu. Pokud se neomluvíte, daný úkol bude považován za nesplněný (0 bodů) a opravný termín vám nebude umožněn. Důsledkem je pak neúspěšné ukončení celého předmětu. Opravný termín na závěrečnou písemnou práci je poskytován jen těm studentům, kteří u svého prvního pokusu získali aspoň 10 bodů. Obdobná povinnost omluvit se platí i pro opravný termín. Počet bodů na řádném termínu 0 až 9 10 až 20 více než 21

Neúčast na řádných termínech – test se musí psát i když je přítomna jen třetina studentů, Požadavky typu:

Proč nepovolovat opravný termín Pokud někteří studenti nepovažují za nutné se na písemnou práci aspoň trochu připravit, já zase nepovažuji za nutné s těmito studenty ztrácet čas opravováním jejich písemek, či spíše „výtvorů“!

Opravný termín NE ANO není nutný, úspěch 27 / 358



28 / 358

Ukázky písemných prací

Ukázky písemných prací

Pusto, prázdno

Co si o tom myslet?

Křivka A3 má být grafem funkce Toto není zmýlení se v odpovědi, záměna dvou pojmů. . . Tady prostě nic není!

y = log2 x zatímco křivka A4 má být grafem funkce y = x 2.



29 / 358



30 / 358

Ukázky písemných prací Tak takhle ne!

Konec části pro prezenční formu studia

Odpověď na otázku 4: WTF? Neumín goauldsky! Odpověď na otázku 5: DUNNO



31 / 358



32 / 358

Tutoriály

1. tutoriál – nepovinný 16. září 2016 Na tomto úvodním tutoriálu Vám budou sděleny informace o organizaci studia předmětu a informace o náplni předmětu.

Kombinovaná forma studia

2. tutoriál – nepovinný 30. září 2016 K tomuto datu se předpokládá zvládnutí následujících témat: První program v C++, algoritmus, program, překlad, procesor, proces. Proměnné, konstanty, datové typy. Řídící konstrukce jazyka (sekvence, větvení, cyklus).



33 / 358

Tutoriály



34 / 358

Tutoriály 5. tutoriál – povinný

3. tutoriál – povinný

11. listopadu 2016

14. října 2016

Tento tutoriál je rozdělen do několika skupin, tutoriál proběhne na počítačové učebně, celou náplň tutoriálu bude tvořit druhý test.

V průběhu tutoriálu proběhne první test. K tomuto datu se předpokládá zvládnutí následujících témat: Strukturované programování v C++, funkce a jejich parametry, volání funkcí. Pole. Vyhledávání v poli (sekvenční, půlením intervalu).

V systému Edison budou vypsány termíny na které se přihlásíte.

6. tutoriál – nepovinný 25. listopadu 2016

4. tutoriál – nepovinný

K tomuto datu se předpokládá zvládnutí následujících kapitol: Třídění, vymezení problému, adresní třídění. Základní třídící algoritmy (třídění vkládáním, výběrem, bublinové). Pokročilé třídící algoritmy (QuickSort, HeapSort, MergeSort).

29. října 2016 K tomuto datu se předpokládá zvládnutí následujících témat: Rekurze, vymezení pojmu, příklady, jednoduchý backtracking.

Konzultace k semestrálnímu projektu. Jiří Dvorský (VŠB – TUO)


35 / 358



36 / 358

Tutoriály

Úkoly – první test

První test se bude psát na třetím tutoriálu 14. října 2016.

7. tutoriál – povinný

Opravný termín se bude psát na dalším tutoriálu.

9. prosince 2016

Bude to krátký písemný test na cca 10 až 15 minut maximálně.

Tento tutoriál je rozdělen do několika skupin, tutoriál proběhne na počítačové učebně, celou náplň tutoriálu bude tvořit třetí test. V systému Edison budou vypsány termíny na které se přihlásíte.



37 / 358

Úkoly – druhý test

Test bude zaměřen na syntaxi a sémantiku jazyka C++. Jinak řečeno, otázky typu „co tato konstrukce v C++ znamená“, „je tato konstrukce správná“, „jak se deklaruje proměnná“, „co znamená tento operátor“, „jak se napíše cyklus od jedné do pěti“ a tak dále.



38 / 358

Úkoly – třetí test

Druhý test se bude psát na pátém tutoriálu 11. listopadu 2016.

Třetí test se bude psát na sedmém tutoriálu 9. prosince 2016.

Opravný termín bude ve zkouškovém období.

Opravný termín bude ve zkouškovém období.

Na začátku vymezené doby dostanete zadání, které ve zbývajícím čase naprogramujete, odladíte a předvedete.

Na začátku vymezené doby dostanete zadání, které ve zbývajícím čase naprogramujete, odladíte a předvedete.

Zadání druhého testu budou obsahovat práci s cykly, podmínkami, poli, i dvourozměrnými. Podívejte se jak se používají různé druhy cyklů, různé druhy podmínek, logické operace (logický součet, součin atd.). Prostudujte si jak se pracuje s vnořenými cykly, jak je lze pomocí příkazu break a continue předčasně ukončovat atd. Prostudujte si práci s polem. Podívejte se, jak se takové pole indexuje, jak se prochází v cyklu.

Zadání třetího testu bude o něco komplikovanější než v předchozím testu. Pro úspěšné zvládnutí tohoto testu je nutné abyste uměli napsat funkce s různými způsoby předávání parametrů (hodnotou, odkazem), uměli předávat do funkcí pole. A potom takové funkce správně zavolat. V tomto testu se budou provádět výpočty nad polem, hledat v poli, přepisovat hodnoty, zjišťovat počet prvků pole větší než, menší než daná hodnota, tisknout pole na obrazovku atd.



39 / 358



40 / 358

Úkoly – projekt

Úkoly – projekt (pokrač.)

V předmětech Algoritmy I a Programování I je v kombinované formě studia požadováno po studentech vypracování projektu. Po dohodě mezi garanty předmětů budou studenti této formy studia, mající zapsány oba dva předměty současně, vypracovávat jen jeden projekt. Studenti mající zapsán pouze jeden z těchto předmětů, jde většinou o studenty opakující předmět či celý ročník, vypracují projekt samozřejmě v tom předmětu, který mají zapsán. Cca v polovině října bude na webu tutora zveřejněno: rozdělení studentů podle předmětu do kterého budou zpracovávat projekt, zadání projektů v předmetu Algoritmy I a rozdělení zadání projektů mezi studenty zpracovávající projekt v předmětu Algoritmy. Jiří Dvorský (VŠB – TUO)


Projekt se odevzdává jako řešení (solution) pro vývojové prostředí Visual Studio 2015 ve formě zip archivu. Způsob odevzdání bude upřesněn. Před odevzdáním projektu odstraňte z adresáře s Vaším projektem všechny spustitelné soubory (exe, bat). Striktní deadline pro odevzdání projektu je 11. prosince 2016 23:59. Obhajoba proběhne v zápočtovém týdnu. Termíny budou vypsány v systému Edison. K obhajobě projektu není opravný termín. Zásadním kritériem pro úspěšnou obhajobu je funkční program.

41 / 358

Hodnocení úkolů



42 / 358

Obecné poznámky k úkolům U všech úkolů jste povinni se prokázat svou studentskou kartou nebo jiným oficiálním dokladem totožnosti. Bez prokázání totožnosti Vám nebude výsledek započítán.

Je nutné splnit všechny výše uvedené úkoly, a zároveň u všech úkolů aspoň minimální počet bodů.

První test Druhý test Třetí test Projekt Celkem

Obdobné informace k projektům zveřejní i tutor předmětu Programování I.

Minimální počet bodů 10 10 10 21 51

Každý prohřešek vůči studijnímu řádu u testů a písemné práce bude nekompromisně postihován. Jde především o opisování, plagiátorství, a záměnu studentů.

Maximální počet bodů 20 20 20 40 100

Je zakázáno zadání testů, písemek atd. kopírovat, fotit mobily, fotoaparáty, skenovat či jakkoliv jinak kopírovat, rozmnožovat, přenášet elektronickým způsobem a podobně.

Všechna bodová hodnocení jsou průběžně zapisována do systému Edison.

Předmět je ukončen klasifikovaným zápočtem. Nevztahuje se tudíž na něj požadavek dvou opravných pokusů, jak to vyžaduje studijní řád u zkoušky. Žádné další pokusy nejsou možné, například dvě opravy jednoho testu.



43 / 358



44 / 358

Pokyny k prvnímu, druhému a třetímu testu

Pokyny k prvnímu, druhému a třetímu testu (pokrač.)

Na každý z těchto úkolů máte jeden řádný pokus a jeden opravný pokus. Na všechny tři úkoly budou v Edisonu vypsány řádné termíny, kde se budete hlásit. Na první test bude vypsán jeden řádný termín. Na druhý a třetí test bude v jeden den vypsáno několik řádných termínů (kapacita počítačových učeben je menší, test musí běžet na několik „kol“).

Pokud se neomluvíte, daný úkol bude považován za nesplněný (0 bodů) a opravný termín vám nebude umožněn. Důsledkem je pak neúspěšné ukončení celého předmětu.

Absolvování prvního, druhého a třetího testu v řádném termín tj. na příslušném tutoriálu je povinné.

Obdobná povinnost omluvit se platí i pro opravný termín.

Pokud se řádného termínu zúčastníte a neuspějete s řešením zadaného úkolu, máte nárok na opravný termín. Opravné termíny budou vypsány ve zkouškovém období.

Pokud se řádného termínu testu nezúčastníte, bez ohledu na to zda jste byli přihlášeni nebo ne, je vaší povinností se garantovi předmětu předem omluvit. Termín „předem“ znamená nejpozději do začátku termínu, na kterém máte daný test psát. Postačující je omluva emailem na adresu garanta předmětu. Jiří Dvorský (VŠB – TUO)


45 / 358



46 / 358

Software pro výuku

Primární software: Vývojové prostředí pro C++

Konec části pro kombinovanou formu studia

Dokumentace k C++ Doplňkový software: Dokumentační systém Doxygen, www.doxygen.org Typografický systém LATEX, www.cstug.cz



47 / 358



48 / 358

Vývojová prostředí pro C++


Microsoft Visual Studio 2013 (VS2013):

Microsoft Visual Studio 2015 (VS2015):

pro výukové účely zcela legálně a zadarmo,

pro výukové účely zcela legálně a zadarmo,

image instalačních disků lze stáhnout z Microsoft DreamSpark for Academic Institutions, elms.cs.vsb.cz

image instalačních disků lze stáhnout z Microsoft DreamSpark for Academic Institutions, elms.cs.vsb.cz

instalace včetně dokumentace – Microsoft Developer Network, msdn.microsoft.com,

instalace včetně dokumentace – Microsoft Developer Network, msdn.microsoft.com,

bezplatně ke stažení jazyková sada pro češtinu.

alternativou je tzv. Community Edition, ke stažení přímo od Microsoftu.

alternativou jsou tzv. Express Edition, ke stažení přímo od Microsoftu.



49 / 358




50 / 358

Studijní literatura

Lze pracovat v obou vývojových prostředích. Ovládání obou prostředí je téměř totožné. Rozdíly mezi překladačem jazyka C++ ve VS2013 a VS2015 jsou z pohledu předmětu Algoritmy I a Algoritmy II zanedbatelné. VS2015 je v současné době instalováno na počítačových učebnách katedry. Vývojové prostředí VS2015 spolu s integrovaným překladačem jazyka C++ bude užíváno jednak pro výuku a jednak jako referenční překladač při hodnocení Vašich případných projektů, úkolů a jiných zdrojových kódů, které budete odevzdávat.

Učební materiály lze rozdělit do dvou skupin: literatura o programovacím jazyku C++, literatura o algoritmech a datových strukturách. Níže uvedenou literaturu využijete v předmětech: Algoritmy I a Algoritmy II, Programování I a Programování II.

Pochopitelně stačí mít instalováno jen jedno z obou vývojových prostředí.



51 / 358



52 / 358

Základní literatura o C++

Doplňková literatura o C++

O jazyce C++, který je naším hlavním tématem, existuje v dnešní době řada česky psaných knih. Následující knihy můžete využít pro své studium: 1. Liberty J., Jones B. L.: Naučte se C++ za 21 dní, 2. aktualizované vydání, ComputerPress, 2007, ISBN 978-80-251-1583-1. Zdařilá učebnice jazyka C++. Kniha je sice poněkud tlustá, nicméně je rozdělena do 21 lekcí rozumného rozsahu. Pokrývá veškerou látku, kterou bychom měli za oba semestry probrat. 2. Eckel B.: Myslíme v jazyku C++, Grada Publishing, 2000, ISBN 80-247-9009-2. Kniha od klasika ve výuce jazyka C++. Opět pokrývá veškerou látku, kterou bychom měli za oba semestry probrat.. Kniha je dostupná v angličtině i online na serveru http://www.mindviewinc.com/Index.php 3. Stroustrup, B.: C++ Programovací jazyk. Česky: BEN-technická literatura, Praha 1997. Vynikající kniha přímo od autora jazyka C++. Kniha dosti rozsáhlá, ale na druhou stranu obsahující naprosto vše co lze o C++ napsat.

Dále je možné čerpat zajímavé informace z následujících knih:



53 / 358

Ostatní literatura o C++

2. Alexandrescu A.: Moderní programování v C++ Šablony, generické komponenty a návrhové vzory, ComputerPress 2004, ISBN 80-251-0370-6. Pro ty z Vás, kteří se hodlají dozvědět něco o trendech ve využití jazyka C++, nabízí tato kniha rozšiřující informace. Pozor, nejedná se přímo o učebnici jazyka C++. 3. Koenig A., Moo B.E.: Rozumíme C++, ComputerPress, 2003, ISBN 80-7226-656-X. Alternativní učebnice jazyka C++ s odlišnou metodou výkladu než předchozí doporučené. Výuka je vedena přes využití knihoven jazyka C++, okamžitý nástup objektového programování atd. Jiří Dvorský (VŠB – TUO)


54 / 358

Základní literatura o algoritmech

1. Šaloun, P.: Programovací jazyk C++ pro zelenáče, Neocortex Praha, 2005, ISBN 80-86330-18-4. 2. Richta, K., Šaloun, P.: Programovací jazyk C, skriptum ČVUT, Praha 1998 3. Šaloun, P.: Programovací jazyk C. Skriptum FEI VŠB-TU Ostrava 1994 4. Kernighan, B., Ritchie, D.: Programovací jazyk C, Alfa Bratislava, 1988 5. Herout, P., Rudolf, V., Šmrha, P.: ABC programátora v jazyce C, nakladatelství KOPP, České Budějovice, 1992 6. Vondrák, I., Šaloun, P.: Objektově orientované programování, skriptum VŠB Ostrava, 1994 7. Horstmann, C. S.: Vyšší škola objektového návrhu v C++. Science, Veletiny 1997 8. Večerka, A.: Jazyk C++: popis jazyka s příklady, skriptum UP Olomouc, Olomouc 1996, ISBN 80-7067-658-2 Jiří Dvorský (VŠB – TUO)

1. Virius M.: Pasti a propasti jazyka C++, 2. aktualizované a rozšířené vydání, ComputerPress, 2005, ISBN 80-251-0509-1. V této knize naleznete podrobné vysvětlení, pro začátečníka mnohdy překvapivého chování překladače jazyka C++.


55 / 358

1. Skripta Algoritmy 2. Wirth, N.: Algoritmy a štruktúry údajov, Alfa, Bratislava, 1989 3. Sedgewick R.: Algoritmy v C, části 1-4, SoftPress, Praha, 2003. Existuje i v anglické verzi, náročná, ale vynikající kniha. 4. Wróblewski P.: Algoritmy. Datové struktury a programovací techniky, Computer Press, Praha 2003, druhé vydání 2015



56 / 358

Doplňková literatura o algoritmech

Ostatní učební materiály

1. Topfer, P.: Algoritmy a programovací techniky, Prometheus, Praha 1995.

Prezentace z přednášek

2. Virius, M.: Základy algoritmizace, ČVUT Praha, 1997, skripta.

Prezentace z přednášek nejsou studijním materiálem.

3. Honzík, J. a kolektiv: Programovací techniky, VUT Brno, 1987, skripta.

Slouží přednášejícímu jako osnova jeho výkladu a studentům jako přehled probrané látky.

4. Harel, D.: Algorithmics, The Spirits of Computing, Addison-Wesley Publishing Company, 1993.

Pročtení těchto několika prezentací není možné považovat za dostatečnou přípravu – k tomu slouží studijní literatura a hlavně vlastní, samostatné programování.

5. Cormen, Leiserson, Rievest: Introduction to Algorithms, MIT Press, 2001.

Další materiály budou případně doplněny na webových stránkách předmětu.

6. Sedgewick, R.: Algorithms in C++, Addison-Wesley Publishing Company, 1992. 7. Wood, D.: Data Structures, Algorithms and Performance, Addison-Wesley Publishing Company, 1993. Jiří Dvorský (VŠB – TUO)


57 / 358



58 / 358

Pojem algoritmus Děkuji za pozornost

doc. Mgr. Jiří Dvorský, Ph.D. Katedra informatiky Fakulta elektrotechniky a informatiky VŠB – TU Ostrava



59 / 358


Pojem algoritmus

60 / 358

Algoritmický problém

Algoritmus Algoritmus

Algoritmus – pravidla definující postup jak vstupní data transformovat na výstupní

Název algoritmus pochází ze začátku devátého století z Arábie. V letech 800 až 825 napsal arabský matematik Muhammad ibn Músá al Chwárizmí dvě knihy, z nichž jedna se v latinském překladu jmenovala Algoritmi dicit, česky „Tak praví al Chwárizmí“. Byla to kniha postupů pro počítání s čísly. Těmto postupům my dnes říkáme „písemné sčítání“, „písemné násobení“ atd.

Algoritmus můžeme chápat také jako konečnou posloupnost instrukcí, které po konečném počtu kroků vydá požadovaný výstup

Poznámky

Algoritmický problém – vstup, výstup, vstupní a výstupní podmínka

Sestavit správný algoritmus řešení problému nemusí být vždy snadnou činností.

K našim účelům bude stačit tato intuitivní definice algoritmu

Logická chyba v algoritmu může vést k nesprávným výsledkům. Pro řešení jedné a té samé úlohy může existovat více různých algoritmů, tyto algoritmy se můžou lišit v množství spotřebovaného času a paměťového prostoru. Jiří Dvorský (VŠB – TUO)

Pojem algoritmus

61 / 358


Pojem algoritmus

62 / 358

Algoritmus

Nekonstruktivní řešení problému aneb Na tohle není algoritmus!

Algoritmu můžeme rozumět jako předpisu pro řešení nějakého problému. Jako příklad vezměme třídění množiny celých čísel. Pokud rozebereme řešení takové úlohy do důsledku, musí obsahovat tři věci:

Příklad Naším úkolem je najít dvě iracionální čísla x a y taková aby platilo, že x y je číslo racionální.

1. hodnoty vstupních dat (množina celých čísel), 2. předpis pro řešení,

Řešení

3. požadovaný výsledek, tj. výstupní data (setříděná čísla).

Zvolíme x =

√

2. Je-li x y číslo racionální jsme hotovi, není-li x y √ √2 √ číslo racionální, zvolíme například x = 2 a y = 2. Potom dostaneme

Konstruktivní řešení problémů

2ay=

√

Všimněte si, že řešení problému je pomocí algoritmu konstruováno ze vstupních dat!

Pojem algoritmus

y

x =

(︁√ )︁√2

2

2

=

(︁√ )︁√2√2

2

=

(︁√ )︁2

2

=2

√ √ Je zřejmé, že√řešením je buď dvojice čísel x = 2 a y = 2 nebo dvojice √ √ 2 čísel x = 2 a y = 2, přičemž nejsme z uvedeného řešení schopni říci která dvojice je vlastně řešením našeho problému.

Stejný postup používá například geometrie.


√

63 / 358


Pojem algoritmus

64 / 358

Nekonstruktivní řešení problému aneb Na tohle není algoritmus!

Algoritmus

V čem spočívá problém? 1. není jasné zda je

√

√

2

2

Algoritmus je předpis, který se skládá z kroků a který zabezpečí, že na základě vstupních dat jsou poskytnuta požadovaná data výstupní. Navíc každý algoritmus musí mít následující vlastnosti:

číslo iracionální nebo ne,

2. není jasné jak volit kandidáty na řešení – iracionální čísla jsou nespočetná.

konečnost, hromadnost,

Spočetnost množiny čísel O množině řekneme, že je spočetná pokud ji lze zobrazit na množinu přirozených čísel.

jednoznačnost, opakovatelnost,

Přirozená čísla lze „probírat, vyjmenovat, jedno po druhém“.

rezultativnost,

Stejně to lze provést s čísly celými a racionálními (zlomky).

elementárnost.

Nelze to provést s čísly iracionálními, reálnými a komplexními. Po 1 následuje nutně 2, po 2, 5 následuje co? 2, 51 nebo 2, 501 nebo √ 2, 5001? Jaké číslo následuje po 2? Jiří Dvorský (VŠB – TUO)

Pojem algoritmus

65 / 358


Pojem algoritmus

66 / 358

Algoritmus – vlastnosti


Konečnost

Hromadnost

Požadovaný výsledek musí být poskytnut v „rozumném“ čase (pokud by výpočet trval na nejrychlejším počítači např. jeden milion let, těžko bychom mohli hovořit o algoritmu řešení, nemluvě o výpočtu, který by neskončil vůbec). Za rozumný lze považovat čas, kdy nám výsledek výpočtu k něčemu bude.

Vstupní data nejsou v popisu algoritmu reprezentována konkrétními hodnotami, ale spíše množinami, ze kterých lze data vybrat (např. při třídění přirozených čísel bude vstup konečnou podmnožinou množiny všech přirozených čísel). Při popisu algoritmu v programovacím jazyce se to projeví tím, že vstupy do algoritmu jsou označeny symbolickými jmény.


Pojem algoritmus

67 / 358


Pojem algoritmus

68 / 358



Opakovatelnost

Jednoznačnost Každý předpis je složen z kroků, které na sebe navazují. Každý krok můžeme charakterizovat jako přechod z jednoho stavu algoritmu do jiného, přičemž každý stav je určen zpracovávanými daty. Tím, jak data v jednotlivých stavech algoritmu vypadají, musí být jednoznačně určeno, který krok následuje (např: V řešení trojúhelníka může nastat situace, kdy vychází na základě vstupních dat jedno nebo dvě řešení. Situace je tedy nejednoznačná, řešení musí být jednoznačné, tzn. v předpisu se s touto možností musí počítat a musí v něm být návod, jak ji řešit.).


Pojem algoritmus

69 / 358

Algoritmus – formálnější přístup

Rezultativnost Algoritmus vede ke správnému výsledku.

Elementárnost Algoritmus se skládá z konečného počtu jednoduchých (elementárních) kroků.


Pojem algoritmus

70 / 358


Turingův stroj

Church-Turingova teze

teoretický model počítače popsaný matematikem Alanem Turingem,

Ke každému algoritmu existuje ekvivalentní Turingův stroj. Kvůli neformální definici pojmu algoritmus nemůže být tato teze nikdy dokázána.

procesorová jednotka, tvořená konečným automatem,

Lze ji ale vyvrátit, podaří-li se sestrojit algoritmus, který bude umět řešit problémy, které Turingův stroj řešit neumí.

program ve tvaru pravidel přechodové funkce,

Jelikož každý počítačový program lze přeložit do jazyka Turingova stroje a obvykle i naopak, lze tezi ekvivalentně formulovat pro kterýkoli běžně používaný programovací jazyk.

cs.wikipedia.org/wiki/Turingův_stroj

a pravostranně nekonečné pásky pro zápis mezivýsledků.


Při použití stejných vstupních údajů musí algoritmus dospět vždy k témuž výsledku.

Pojem algoritmus

71 / 358


Pojem algoritmus

72 / 358


Shrnutí

Přesněji, programovací jazyk potřebuje jednu z následujících konstrukcí, aby byl s Turingovým strojem ekvivalentní:

Algoritmický problém Algoritmus konečnost, hromadnost, jednoznačnost, opakovatelnost, rezultativnost, elementárnost.

while-cyklus nebo neomezenou (alespoň teoreticky) rekurzi nebo podmíněný skok. Běžné programovací jazyky mívají všechny tři tyto konstrukce. Mezi jazyky, které nejsou ekvivalentní s Turingovým strojem patří například jazyk SQL (myšleno bez vložených procedur).

Turingův stroj Church-Turingova teze


Pojem algoritmus

73 / 358


Pojem algoritmus

74 / 358

Základy C++ Děkuji za pozornost



Pojem algoritmus

75 / 358


Základy C++

76 / 358

Co je to počítač?

Z čeho se skládá počítač Hardware (HW) technická část počítače, různá zařízení z nichž je počítač sestaven, např. klávesnice, monitor, pevný disk, paměť, procesor, sběrnice . . .

Počítač Software (SW)

Počítač můžeme definovat jako zařízení schopné provádět výpočty a rozhodnutí založená na logice.

programové vybavení počítače, „oživuje“ hardware, mnoho úrovní software: ovladače zařízení, jádro operačního systému, moduly operačního systému (správa uživatelů, správa disků atd.), grafické uživatelské rozhraní, uživatelské aplikace.


Základy C++

77 / 358

Základní struktura počítače


Základy C++

78 / 358


Konceptuální schéma počítače

Vstup

vstup, výstup,

zařízení pomocí kterého se dostávají informace do počítače,

paměť,

klávesnice, myš, scanner, počítačová síť . . .

řadič a

Výstup

aritmeticko logická jednotka (ALU).

předává informace z počítače jeho periferiím – výsledky výpočtů a řídící informace.

Poznámky O takto koncipovaném počítačí říkáme, že má von Neumannovskou architekturu. Řadič a ALU tvoří dohromady to, čemu se běžně říká procesor. Jiří Dvorský (VŠB – TUO)

Základy C++

79 / 358


Základy C++

80 / 358


Základní struktura počítače Paměť Paměť můžeme rozdělit na paměť primární a sekundární.

Aritmeticko logická jednotka, ALU centrální výkonná část počítače,

Primární paměť

Sekundární paměť

provádí veškeré výpočty, logické operace atd.

vnitřní paměť počítače,

vnější paměti počítače,

Random Access Memory (RAM),

relativně pomalé, velká kapacita,

velice rychlá, relativně malá kapacita, obsahuje zpracovávané programy, jejich data,

obsahuje všechny programy počítače,

Charles Babbage nazýval ALU slovem „mlýnice“

Řadič řídící část počítače, řídí a koordinuje ostatní části počítače.

data pro tyto programy.

data ze vstupu, data čekající na výstup. Jiří Dvorský (VŠB – TUO)

Základy C++

81 / 358

Program versus proces


Základy C++

82 / 358

Operační systém (OS)

první počítače OS postrádaly, procesy si zajišťovaly vše samy, snaha usnadnit a sjednotit práci s počítačem, periferiemi,

Program

poskytnout podporu pro běžně prováděné činnosti – čtení dat ze vstupu, tisk na tiskárně atd.,

posloupnost instrukcí které řídí počítač při zpracování dat, statický.

zvýšit výkon počítače, jednoúlohový vs. víceúlohový OS,

Proces program, který je v daném okamžiku již vykonáván počítačem,

jednouživatelský vs. víceuživatelský OS,

dynamický

dnešní OS: UNIX/Linux, Windows, Mac OS X Mountain Lion atd., Pozor! Grafické uživatelské rozhraní (GUI), které vidíte na obrazovce je jen „špičkou“ ledovce. OS je rozsáhlá infrasturktura skrytá za tímto rozhranním.


Základy C++

83 / 358


Základy C++

84 / 358

Osobní počítače

Programovací jazyk

v průběhu 70. let 20. století používá Apple pro své počítače označení osobní,

prostředek pro zápis algoritmů ve formě použitelné na počítači,

v roce 1981 uvedlo IBM osobní počítač, PC s procesorem Intel 8088,

jde formální jazyk – formálně tj. matematicky popsaná syntaxe a sémantika jazyka,

IBM zvolilo cestu otevřeného standardu, podíleli se různí výrobci HW a SW.

jinak řečeno jde o jazyk, který má svou gramatiku, slova, věty, věty mají svůj význam . . .

typicky procesory Intel či AMD, operační systém zprvu DOS, následně Windows a Linux.

program – zápis algoritmu ve zvoleném programovacím jazyce,


Základy C++

85 / 358

programovací jazyky lze členit dle mnoha hledisek.


Základy C++

86 / 358

Programovací jazyky – způsob překladu a spuštění

Programovací jazyky

Kompilované programovací jazyky Nižší programovací jazyky

program je nejprve kompletně přeložen překladačem do strojového kódu počítače,

jazyk plně přizpůsobený počítači,

teprve po bezchybném překladu je možné přeložený tvar programu spustit, výhody:

jazyk symbolických adres, strojový kód, částečně VHDL.

Vyšší programovací jazyky jazyk lépe pochopitelnější pro člověka, vyšší míra abstrakce, syntaxe podobná primitivní angličtině, užití např. běžných značek pro matematické operace, jednomu příkazu ve vyšším jazyce odpovídá obecně mnoho instrukcí ve strojovém jazyce, většina současně používaných jazyků.

výsledný spustitelný tvar programu může být přesně optimalizován na konkrétní HW a OS, větší rychlost běhu takového programu, lepší využití prostředků HW.

nevýhody: závislost na konkrétním HW a OS, pro každý HW a OS nutno zvlášť přeložit, menší pružnost při odstraňování chyb v programech, nelze snadno měnit kód programu za jeho běhu.

typické překládané jazyky – C, C++, Pascal (Delphi), Fortran. Jiří Dvorský (VŠB – TUO)

Základy C++

87 / 358


Základy C++

88 / 358



Interpretované programovací jazyky speciální prostředí pro běh programu,

Kompilované programovací jazyky – poznámka překladač se někdy označuje jako kompilátor (compiler) a překlad jako kompilování (to compile),

toto prostředí čte zdrojový kód programu a jakmile načte celý příkaz, okamžitě jej vykoná a pokračuje na další příkaz, výhody: nezávislost programů na HW a OS, závislý je pouze interpret, dynamičtější manipulace s programem, např. za běhu programu lze opravovat zdrojový kód, protože tento kód je interpretem opakovaně načítán.

překladač je program, který překládá program z jednoho jazyka do jiného jazyka, typicky například z C++ do strojového kódu procesoru, překladače nemusí překládat jen „programy“, například tato prezentace je napsána v jazyku LATEX a překladem textu v tomto počítačovém jazyce získáme PDF dokument, který právě čtete.

nevýhody: obtížná optimalizace pro daný HW a OS, horší využití prostředků HW a OS (na počítači musí běžet i interpret).

typický interpretovaný jazyk je BASIC ve své klasické podobě, například na starých 8-bitových počítačích pozor – jazyk Visual Basic .NET nebo Java jsou uspořádány jinak! Jiří Dvorský (VŠB – TUO)

Základy C++

89 / 358



Základy C++

90 / 358

Nižší programovací jazyky

Interpretované programovací jazyky členění na kompilované a interpretované není absolutní, tyto přístupy lze kombinovat, jazyk Java a jeho Java Virtual Machine (JVM): JVM představuje virtuální procesor se svým specifickým strojovým jazykem, zdrojový kód v jazyku Java je kompilován do strojového kódu JVM (výsledkem jsou class a jar soubory), při spuštění JVM začne jednotlivé instrukce uložené např. v jar souboru interpretovat.

obdobně se chová i Visual Basic .NET či Python, Just in Time (JIT) kompilace: zdrojový kód programu je teprve při spuštění kompilován do strojového kódu počítače a okamžitě spuštěn, přeložený tvar programu se nikde neukládá, program je vždy kompilován znovu. Jiří Dvorský (VŠB – TUO)

Základy C++

91 / 358

Strojový kód jediný jazyk, kterému počítač (procesor) rozumí, sekvence 0 a 1, strojově závislý, pro člověka „nestravitelný“.

Příklad 0010 1101 1001 0001 0010

1101 1000 1000 0010 0000


Základy C++

92 / 358

Nižší programovací jazyky

Vyšší programovací jazyky

Jazyk symbolických adres nesprávně česky nazýván „assembler“, assembler – překladač do strojového kódu,

Procedurální (imperativní)

assembly language,

Strukturované, např. C, BASIC,

anglické zkratky názvů instrukcí,

Objektově orientované, např. Smalltalk, Java.

pro člověka „stravitelnější“,

Neprocedurální (deklarativní) Příklad

Funkcionální, např. Lisp, Haskell,

MOV reg0, Vyska MOV reg1, Sirka MUL reg0, reg1 MOV reg0, Plocha

Logické, např. Prolog.


Základy C++

93 / 358

Příklady vyšších programovacích jazyků


Základy C++

Co je C++?

FORTRAN (FORmula TRANslation) – první vyšší jazyk z roku 1957, vývoj trval tři roky, dodnes používán pro numerické výpočty, COBOL (COmmon Business-Oriented Language) – 1959, jazyk pro „hromadné zpracování dat“, Pascal – 1970, strukturované programování, výuka programování.

C++ je: vyšší programovací jazyk, určen pro všeobecné použití, určen pro profesionální programátory, zachovává zpětnou kompatibilitu s jazykem C.

Basic (Beginner’s All-purpose Symbolic Instruction Code) – 1963, nyní převážně MS Visual Basic

C++ je jazyk typicky překládaný do strojového kódu.

Příklad

C++ dnes

Plocha = Vyska * Sirka

V dnešní době plní jazyk C++ úlohu moderního assembleru.


Základy C++

94 / 358

95 / 358


Základy C++

96 / 358

Historie jazyka C

Jazyk C++

1979 – Bjarne Stroustrup (Bell Laboratories) vyvíjí jazyk „C with classes“

autor – Dennis Ritchie, Bell Laboratories, v letech 1968 až 1973, vychází z jazyků BCPL a B,

1983 – název změněn na C++

silná vazba na OS UNIX, jádro OS UNIX práno v C, Brian Kernighan a Dennis Ritchie vydávají v roce 1978 knihu The C Programming Language, jazyk označováno jako „K & R C“ 1989 – ANSI standard

1998 – norma ISO/IEC 14882:1998 2011 – norma ISO/IEC 14882:2011, 12. srpna 2011,

1990 – ANSI a ISO norma ANSI/ISO 9899: 1990

rozšíření jazyka C o OOP, plus další úpravy,

2000 – C99, ISO 9899:1999


1985 – vychází kniha The C++ Programming Language, zatím se nejedná o standard,

jazyk není čistě objektový.

Základy C++

97 / 358

Vznik spustitelného programu – základní pojmy


Základy C++

98 / 358

První program Hello World

zdrojový kód – napsán programátorem, textový soubor obsahující konstrukce C++ o kterých programátor doufá, že budou vykonávat to co požaduje. hlavičkový soubor – deklarace funkcí, tříd, konstant atd. Buď napsán programátorem nebo dodán s překladačem. projekt – soubor popisující, ze kterých zdrojových kódů a knihoven vznikne výsledný program. kód s relativními adresami – anglicky object file, zdrojové kódy jsou přeloženy do instrukcí procesoru, ale nejsou dořešeny všechny vazby. spustitelný kód – soubor s binárním zápisem instrukcí, přímo vykonavatelný procesorem.

#include using namespace std; // This is single line comment. void main() { cout << "Hello World" << endl; }

Čeština ve zdrojovém kódu Nedoporučuji psát do C++ cokoliv česky s diakritikou, ani komentáře.


Základy C++

99 / 358


Základy C++

100 / 358

Vznik spustitelného programu

Vznik spustitelného programu

Vznik spustitelného programu ze zdrojového kódu prochází těmito fázemi: Ke vzniku spustitelného programu se využívají následující programy:

1. Edit – editace zdrojového kódu,

1. Edit – textový editor,

2. Preprocess – rozvinutí maker, vložení hlavičkových souborů, 3. Compile – vlastní překlad, výsledkem je modul s relativními adresami nebo alternativně program v assembleru,

2. Preprocess – preprocesor, 3. Compile – překladač, kompilátor,

4. Link – sestavení výsledného programu, vstupem jsou moduly s relativními adresami, plus knihovny; výsledkem spustitelný program,

4. Link – linker (sestavovač, spojovač?),

5. Load – OS zavede spustitelný kód do primární paměti,

6. Execute – operační systém.

5. Load – operační systém,

6. Execute – vlastní vykonávání programu.


Základy C++

101 / 358

Ladění


Základy C++

102 / 358

Základní stavební bloky C++

Proces odstraňování chyb v programu se nazývá ladění. K ladění slouží program zvaný

Debugger

Data – údaje, které bude program zpracovávat,

umožňuje sledovat vykonávání programu,

Kód – instrukce programu prostřednictvím jsou zapisovány algoritmy,

vypisovat hodnoty proměnných,

Komentáře – pomocné informace pro programátora umístěné ve zdrojovém kódu.

zobrazuje zásobník volání funkcí, umožňuje nastavovat tzv. breakpointy, tj. místa, kde se má přerušit vykonávání programu krokování programu po jednom příkazu.


Základy C++

103 / 358


Základy C++

104 / 358

Datové typy v C++

Datové typy v C++

Datový typy v C++ dělíme na: základní Datový typ definuje dvě vlastnosti:

celočíselné s plovoucí řádovou čárkou logické

rozsah povolených dat, čili jaké hodnoty jsou povolené a jaké ne, povolené operace, čili co s těmi hodnotami lze provádět.

adresní ukazatelé reference

Berte je vážně Datové typy jsou jedním z prostředků pro psaní kvalitních programů.

strukturované pole struktura třída


Základy C++

105 / 358

Celočíselné datové typy v C++

desítková – základ soustavy je číslo 10, číslice 0 až 9, např. 158 osmičková – základ soustavy je číslo 8, číslice 0 až 7, např. 0236

Rozsahy celočíselných datových typů ve VS 2010


Rozsah hodnot –128 . . . 127 –32 768 . . . 32 767 –2 147 483 648 . . . 2 147 483 647 –2 147 483 648 . . . 2 147 483 647 –9223372036854775808 . . . 9223372036854775807 Základy C++

106 / 358

Číselné soustavy v C++:

Všechny typy jsou automaticky se znaménkem, neznaménková verze se uvádí klíčovým slovem unsigned, např. unsigned int.

Bajty 1 2 4 4 8

Základy C++

Celočíselné datové typy v C++

char – jeden byte short – větší nebo roven char int – větší nebo roven short long – větší nebo roven int long long – větší nebo roven long

Typ char short int long long long


107 / 358

šesnáctková – základ soustavy je číslo 16, číslice 0 až 9, písmena A až F, kde A je deset, B jedenáct atd., např. 0x9E Nejběžnější se pochopitelně desítková soustava. Binární soustava se nepoužívá ve zdrojovém kódu přímo nepoužívá (dlouhý zápis čísel). Osmičková soustava je spíše historický přežitek. Šestnáctková soustava se používá pro manipulaci s bity – vždy 4 bity na jednu šestnáctkovou číslici. Šestnáctková soustava se také často nazývá jako hexadecimální soustava.


Základy C++

108 / 358

Číselné soustavy – příklad

Datové typy s plovoucí řádovou čárkou v C++

Číslo 158 můžeme vyjádřit v jednotlivých číselných soustavách takto: binárně 100111102 = 1×27 +0×26 +0×25 +1×24 +1×23 +1×22 +1×21 +0×20 osmičkově 2368 = 2 × 82 + 3 × 81 + 6 × 80

Datový typ float double long double

Počet bajtů Rozsah hodnot Platné číslice ±38 4 ±3, 4 × 10 7 8 ±1, 7 × 10±308 15 ve Visual Studio 2013 shodné s double

Reálná čísla vs. čísla s plovoucí řádovou čárkou

desítkově

Čísla s plovoucí řádovou čárkou nejsou totožná s reálnými čísly z matematiky – problém s periodickými čísly, iracionálními čísly!

15810 = 1 × 102 + 5 × 101 + 8 × 100 hexadecimálně 9E16 = 9 × 161 + 14 × 160


Základy C++

109 / 358

Logický datový typ v C++


Základy C++

110 / 358

Logický datový typ v C++

jazyk C++ zavádí pro logické hodnoty datový typ bool, konstanty true pravda a false nepravda,

Platné vztahy

platí že true ̸= false,

true ̸= false ¬true = false ¬false = true

neexistuje žádná souvislost mezi bool a int!

Logické hodnoty v ANSI C Jazyk ANSI C používá pro uložení logických hodnot typ int včetně svérázné definice hodnot true a false. V jazyce C++ důrazně doporučuji nepoužívat tento zastaralý přístup a doporučuji používat typ bool.


Základy C++

111 / 358


Základy C++

112 / 358

Identifikátor

Proměné

obecný název pro pojmenování čehokoliv v programu co lze pojmenovat, konečná neprázdná posloupnost písmen, číslic, znaků podtržítko, která nesmí začínat číslicí, rozlišují se malá a velká písmena. délka identifikátoru není teoreticky omezena

Data v programu jsou reprezentována pomocí proměnných.

Proměnná identifikátor,

Příklad

datový typ,

a A a1 ab _a _a1 a_b VeryLongIdentifier

hodnota.

Jak správně volit identifikátory? Buď česky nebo anglicky, ne mixovat! NextMove nebo DalsiTah ne NextTah. Raději anglicky. Identifikátor musí popisovat co obsahuje! NumberOfStudents nebo PocetStudentu ne A28.


Základy C++

113 / 358


Základy C++

115 / 358

114 / 358

Děkuji za pozornost

Nikdy není hotovo, dopsat další slajdy. . .


Základy C++


Základy C++

116 / 358

Řídící struktury jazyka C++ Děkuji za pozornost



Řídící struktury jazyka C++

117 / 358


Řídící struktury jazyka C++

118 / 358

Funkce v jazyce C++ Děkuji za pozornost



Funkce v jazyce C++

119 / 358


Funkce v jazyce C++

120 / 358

Motivace – kvalita řešení problémů 1. Máme navrhnout algoritmus potažmo software pro řešení problému. 2. Navrhneme algoritmus a implementujeme jej.

Složitost algoritmů

3. Máme zájem řešit problémy efektivně. 4. Naskýtá se otázka, jak kvalitní řešení problému jsme vlastně navrhli. Nejlepší? Nejhorší? Průměrné? Jak tedy měřit kvalitu řešení?


5. Kvalitu řešení budeme měřit pomocí tzv. složitosti. Složitost budeme chápat jako míru náročnosti našeho řešení na zdroje počítače.


6. Složitost problému budeme definovat jako složitost nejlepšího algoritmu řešícího daný problém.

Příklad Problém – Vyvrtání díry do betonového panelu Řešení – kávová lžička, ruční vrtačka, příklepová vrtačka, vrtací kladivo s SDS upínáním vrtáku Jiří Dvorský (VŠB – TUO)


121 / 358

Motivace



Motivace

1. Algoritmus je dosud chápán jako „mlýnek na maso“ – vložíme vstupní data, zatočíme klikou a dostaneme požadovaný výstup.

1. V programech budeme používat i různé datové struktury – zásobníky, fronty, seznamy, množiny, tabulky atd.

2. Je jasné, že různé mlýnky na maso se můžou kvalitativně lišit.

2. Někdy si prostě nevystačíme s „proměnnou typu int“.

3. Máme zájem o vývoj kvalitních algoritmů a datových struktur.

3. Datové struktury můžeme zjednodušeně chápat jako „skladiště“ informací.

4. Musíme tedy najít nástroj, který umožní měřit kvalitu algoritmů. Nástroj pro měření kvality algoritmů se nazývá složitost algoritmů. Pro měření složitosti algoritmů se okamžitě nabízí dvě měřítka: čas – doba běhu programu.


4. Kvalitu datových struktur budeme měřit kvalitou operací pracujících s danou datovou strukturou, např. složitost nalezení prvku v tabulce, vložení prvku do tabulky, smazání prvku v tabulce atd. 5. Tímto získáme jednotný nástroj na měření kvality algoritmů a datových struktur.

prostor – paměť potřebná pro výpočet a


122 / 358

123 / 358



124 / 358

Prostorová složitost algoritmu

Časová složitost algoritmu Doba běhu programu závisí typicky na mnoha faktorech. Jak tedy provést měření? Máme-li program řešící danou úlohu, můžeme na něm testovat jak dlouho program poběží pro různé velikosti vstupu a různé vstupy stejné velikosti. Můžeme sestrojit graf, jedna osa velikost vstupu, druhá osa doba běhu programu. Pozor nemusí to být funkce, pro jednu hodnotu na ose x může existovat více hodnot na ose y ! Pro tutéž velikost vstupu může existovat více výsledků – nelze brát do úvahy jen prostou velikost vstupu. Například třídění posloupnosti čísel. Někdy stačí jen zkontrolovat, že posloupnost je již setříděná, jindy je potřeba ji celou „přeskládat“. Aby měl takový test smysl, musí být počet testů statisticky významný. Nelze dělat závěry z jednoho testu.

rozsah použité pracovní paměti (RAM či diskový prostor), lze ji jednoduše měřit v bajtech a násobcích, měření je poměrně přímočaré – lze provést jakousi inventuru programu, využívá stejné matematické postupy jako složitost časová.



125 / 358

Časová složitost algoritmu



126 / 358


Obecně se dá říci: že doba běhu se bude zvyšovat s rostoucím velikostí vstupu a doba běhu bude záviset na HW a SW platformě, na které byly testy prováděny.

Metoda měření časové složitosti algoritmů: Musí brát do úvahy všechny možné vstupy.

Úskalí experimentální analýzy časové složitosti programu Experimenty lze většinou provádět na omezeném vzorku dat (třídění 100 prvků, počet možných vstupů je 100!). Vybrat statisticky významný vzorek tak, aby poskytoval hodnověrné výsledky může být velice obtížné.

Lze srovnávat složitost dvou algoritmů nezávisle na HW a SW platformě analýzu algoritmu lze provést studiem formálního popisu algoritmu bez nutnosti provést detailní implementaci a provádět experimentální výpočty pomocí takto implementovaného programu

Je velice problematické srovnávat měření na počítači A s operačním systémem B s počítačem C, který pracuje s operačním systémem D. A je také nutné algoritmus reálně implementovat a experimenty provést. Kdo to zaplatí?! Jiří Dvorský (VŠB – TUO)


127 / 358



128 / 358


Analýza složitosti algoritmů

Po formální stránce směřujeme k tomu, že každému algoritmu přiřadíme funkci f (n), která udává dobu běhu daného algoritmu vzhledem k velikosti vstupních dat n. Doba běhu algoritmu – předpokládáme, že máme k dispozici hypotetický počítač, který přímo vykonává formálně popsané algoritmy. Výsledkem našeho zkoumání je tvrzení typu Algoritmus A pracuje s časovou složitostí úměrnou n2 . Toto tvrzení znamená, že pokud bychom algoritmus implementovali a provedli měření doby běhu, tak pro žádný vstup nepřekročí doba běhu tohoto programu čas cn2 , kde c je konstanta závisející na HW a SW platformě.



129 / 358

Měření času

Potřebné nástroje: měřítko (metrika) pro měření doby běhu algoritmu, model počítače, který bude vykonávat analyzované algoritmy, jazyk pro popis algoritmů, teoretický aparát pro zápis charakteristické doby běhu algoritmu.



130 / 358

Primitivní operace nezávislé na programovacím jazyku předpokládáme vykonání v konstantním čase na různých HW a SW platformách budou časy vykonaní primitivních operací podobné

jak změřit čas nezávisle na HW a SW platformě jak změřit čas teoreticky, bez implementace programu rychlost počítačů se postupně zvyšuje – zvyšuje se i rychlost (kvalita) algoritmů?

získáváme odhad doby běhu programu na základě počtu primitivních operací

dobu běhu algoritmu tedy nemůžeme měřit v obvyklých časových jednotkách

přiřazení hodnoty do proměnné

dobu běhu algoritmu budeme měřit počtem provedených instrukcí

provedení aritmetické operace

volání funkce porovnání dvou čísel indexování pole získání reference na objekt vrácení výsledku funkce



131 / 358



132 / 358

RAM stroj – Random Access Machine

Jazyk pro popis algoritmů Nalezení maxima z posloupnosti čísel, zápis v C++

zjednodušený model počítače model počítače obsahuje jednoduchý procesor s jedním registrem (akumulátor) potenciálně neomezená paměť rozsahu 0 . . . n základní aritmetické operace přímé a nepřímé (pomocí obsahu akumulátoru) adresování paměti RAM stroj je ekvivalentní Turingovu stroji http://en.wikipedia.org/wiki/RAM_machine



133 / 358

Počítání primitivních operací

int Maximum(int[] a, int n) { int max = a[0]; for(int i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } } return max; }



134 / 358

Počítání primitivních operací

1. inicializace proměnné max hodnotou A[0], 2. dvě operace na začátku cyklu je proměnná i inicializována na 1, Celkový počet primitivních operací je v nejlepším případě

3. jedna operace – před každým provedením cyklu je provedeno porovnání i < n, jedna operace n-krát,

2 + 1 + n + 4(n − 1) + 1 = 5n

4. tělo cyklu je provedeno n − 1 krát, 5. pokaždé je provedeno porovnání max < A[i], což jsou dvě operace (indexování a porovnání) 6. pokud podmínka platí je provedeno přiřazení, což jsou dvě operace (indexování a přiřazení) 7. na konci těla cyklu se provede inkrementace proměnné i, což jsou dvě operace (přičtení a přiřazení)

v nejhorším případě je to 2 + 1 + n + 6(n − 1) + 1 = 7n − 2 Nejlepší případ nastane pokud A[0] je maximem. Nejhorší případ nastane pokud jsou prvky v poli A setříděny vzestupně.

8. celkově se v těle cyklu vykoná 4(n − 1) až 6(n − 1) operací 9. vrácení výsledku odpovídá jedné operaci Jiří Dvorský (VŠB – TUO)


135 / 358



136 / 358

Nejlepší, nejhorší, průměrný případ

Notace „Velké O“

Z hlediska časové složitosti lze uvažovat tři případy: analýza komplexnějších algoritmů než je vyhledání maxima může být velice složitá musíme se spokojit s odhadem odhad by se od skutečné složitosti neměl lišit více než o nějakou multiplikativní konstantu snaha detekovat hlavní faktory, části kódu, které ovlivňují složitost algoritmu je nutný matematický aparát, který nám umožní skládat složitosti jednotlivých částí kódu a zahrnovat je pod nějaký jednotící celek

nejlepší – není zajímavý, nic o podstatě algoritmu nevypovídá průměrný – zajímavý, ale jde velice těžko analyzovat, je nutné brát do úvahy pravděpodobnosti výskytu jednotlivých možných vstupů nejhorší – není potřeba prát do úvahy pravděpodobnost jak v předchozím případu, analyzuje se jednodušeji, v případě malé složitosti nejhoršího případu, je to pro nás dobrá zpráva Budeme uvažovat vždy složitost v nejhorším případě, až na některé výjimky.



137 / 358



138 / 358

21

KAPITOLA 2. ALGORITMUS, JEHO VLASTNOSTI Notace „Velké O“

Notace „Velké O“

c2 g(n)

cg(n)

Definice

f (n)

„Velké O“ Mějme funkce f (n) a g(n), kde f (n), g(n) : N → R. Říkáme, že funkce f (n) je O(g(n)), jestliže existuje reálná konstanta c, c > 0 a přirozené číslo n0 > 1 takové, že f (n) ≤ cg(n) pro všechna n ≥ n0 . Můžeme také říci, že f(n) je řádu g(n).

c1 g(n)

Tato definice nám umožňuje porovnávat funkce. Můžeme říci že jedna funkce „je menší než“ funkce jiná až na konstantní faktor (konstanta c z definice). Funkce lze takto porovnávat asymptoticky, čili kdy n roste k nekonečnu (požadavek pro n ≥ n0 ).

n0

n f (n) = Θ(g(n)) (a)



f (n)

139 / 358

n0

n f (n) = O(g(n))

n0

(b) Jiří Dvorský (VŠB – TUO)


f (n) (c)

140 / 358

Notace „Velké O“ – příklad

Notace „Velké O“ – příklad

Příklad Výraz 7n − 2 je O(n).

Řešení Podle definice „Velké O“ notace potřebujeme konstantu c > 0 a přirozené číslo n0 > 1 takové, že 7n − 2 ≤ cn pro všechna n ≥ n0 . Je zřejmé, že lze vzít c = 7 a n0 = 1.

Časová složitost algoritmu vyhledání maxima v poli n čísel je O(n). Řešení: Víme že v nejhorším případě je pro vyhledání maxima potřeba 7n − 2 primitivních operací a víme také že výraz 7n − 2 je O(n). Tudíž algoritmus vyhledání maxima v poli n čísel má složitost O(n).

Poznámka Řešení je dokonce nekonečně mnoho, protože definici velkého O vyhovuje vzít za konstantu c libovolné reálné číslo větší nebo rovno 7 a za n0 lze zvolit libovolné přirozené číslo větší nebo rovné 1.



141 / 358

Význam asymptotického přístupu


složitost n n log n n2 n3 2n

1s 1000 140 31 10 9



142 / 358

Význam asymptotického přístupu

Předpokládejme dále, že elementární operace vykonávané programy trvají 1ms a spočítejme, jak rozsáhlá data mohou jednotlivé programy zpracovat za sekundu, za minutu a za hodinu. algortimus t1 (n) t2 (n) t3 (n) t4 (n) t5 (n)


1min 6 · 104 4895 244 39 15

1hod 3, 6 · 106 2, 0 · 105 1897 153 21

143 / 358

10-násobné zrychlení (nebo zvětšení doby) lineární složitost – 10-násobným zvětšením rozsahu zpracovávaných dat kvadratická složitost – 3-násobným zvětšením rozsahu zpracovávaných dat exponenciální složitost – zvětšení rozsahu dat zhruba o 3, 3. Dosažení rozsahu dat například n = 50 u algoritmu t5 zrychlováním (nebo prodlužováním) výpočtu už vůbec nepřichází v úvahu.



144 / 358

Typické třídy asymptotických složitostí

1 log n log2 n √ n n n log n n2 n3 nk 2n

konstantní logaritmická

Děkuji za pozornost lineární lineárně logaritmická kvadratická kubická obecně polynomiální exponenciální

Třídy jsou uspořádány vzestupně.



145 / 358



146 / 358

Pole v jazyce C++

148 / 358

Obecné deklarace

Pole v jazyce C++ doc. Mgr. Jiří Dvorský, Ph.D.

#include <math.h> #include


using namespace std; const int N = 5;


Pole v jazyce C++

147 / 358


Zobrazení vektoru na standardní výstup

Nulování vektoru

void Print(double v[], const int n) { for(int i = 0; i < n; i++) { cout << v[i] << "\t"; } cout << endl; }

void Clear(double v[], const int n) { for(int i = 0; i < n; i++) { v[i] = 0; } }


Pole v jazyce C++

149 / 358

Součet vektorů


150 / 358

Délka vektoru

⎯ ⎸n−1 ⎸ ∑︁ |u| = ⎷ ui2

wi = ui + vi

i=0

void Add(double u[], double v[], double w[], const int n) { for(int i = 0; i < n; i++) { w[i] = u[i] + v[i]; } }


Pole v jazyce C++

Pole v jazyce C++

151 / 358

double Length(double u[], const int n) { double sum = 0; for(int i = 0; i < n; i++) { sum += u[i] * u[i]; } return sqrt(sum); }


Pole v jazyce C++

152 / 358

Skalární součin dvou vektorů

u·v =

Odchylka dvou vektorů

n−1 ∑︁

ui vi cos 𝜑 =

i=0

double DotProduct(double u[], double v[], const int n) { double sum = 0; for(int i = 0; i < n; i++) { sum += u[i] * v[i]; } }


Pole v jazyce C++

u·v |u||v |

double VectorsAngle(double u[], double v[], const int n) { return DotProduct(u, v, n) / (Length(u, n) * Length (v, n)); }

153 / 358


Pole v jazyce C++

Zobrazení matice na standardní výstup

Nulová matice

void Print(double A[][N], const int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << A[i][j] << "\t"; } cout << endl; } cout << endl; }

void Clear(double A[][N], const int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { A[i][j] = 0; } } }


Pole v jazyce C++

155 / 358


Pole v jazyce C++

154 / 358

156 / 358

Jednotková matice

Součet dvou matic C =A+B ci,j = ai,j + bi,j

void Unity(double A[][N], const int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { A[i][j] = i == j ? 1 : 0; } } }


Pole v jazyce C++

void Add(double A[][N], double B[][N], double C[][N], const int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { C[i][j] = A[i][j] + B[i][j]; } } } 157 / 358

Násobení dvou matic


Pole v jazyce C++

158 / 358

Násobení dvou matic (pokrač.) C = AB ci,j =

n−1 ∑︁

ai,k bk,j

sum += A[i][k] * B[k][j];

k=0

void Multiply(double A[][N], double B[][N], double C[][N], const int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { double sum = 0; for(int k = 0; k < n; k++) { Jiří Dvorský (VŠB – TUO)

Pole v jazyce C++

159 / 358

} C[i][j] = sum; } } }


Pole v jazyce C++

160 / 358

Rekurze doc. Mgr. Jiří Dvorský, Ph.D.




Pole v jazyce C++

161 / 358


Rekurze

162 / 358

Rekurze

Co si představit pod pojmem rekurze? 1. „seber všechny hračky!“, 2. soběpodobnost, fraktály,

Ukázka rekurze graficky

3. z hlediska algoritmů, je to algoritmus, který v určitém okamžiku výpočtu volá sám sebe, 4. rozklad na menší podproblémy, princip rozděl a panuj, (divide et impera), 5. dělení končí u atomického problému – řešení je známo například z definice, 6. rekurze je jistým způsobem ekvivalentní iteraci (cyklu).


Rekurze

163 / 358


Rekurze

164 / 358




Rekurze

165 / 358




Rekurze

166 / 358

Rekurze

168 / 358


Rekurze

167 / 358





Rekurze

169 / 358



Rekurze

170 / 358

Funkce vykreslující ukázkový fraktál void Draw(const int Level, const double CenterX, const double CenterY, const double A) { if (Level > MaxLevel) return; double A2 = A / 2; Draw(Level + 1, CenterX - A2, CenterY - A2, A2); Draw(Level + 1, CenterX + A2, CenterY - A2, A2); Draw(Level + 1, CenterX + A2, CenterY + A2, A2); Draw(Level + 1, CenterX - A2, CenterY + A2, A2); DrawSquare(CenterX - A2, CenterY - A2, A); } Ukázka volání Draw(0, 0, 0, 50);


Rekurze

171 / 358


Rekurze

172 / 358

Některé pojmy

Faktoriál Princip rekurze si ukážeme na výpočtu faktoriálu čísla n. Funkce faktoriál je definována jako {︃

n! =

přímá rekurze – funkce volá sama sebe. nepřímá rekurze – funkce A volá funkci B a ta opět volá funkce A. ukončovací podmínka – jistá část řešení problému je atomická, řešení je známo např. z definice problému.

1 pro n = 0 n * (n − 1)! pro n ≥ 1

Pokud funkci faktoriál místo n! označíme jako f (n) můžeme faktoriál zapsat jako {︃ 1 pro n = 0 f (n) = n * f (n − 1) pro n ≥ 1 Což vede ke známému vyjádření n! = n * (n − 1)! = n * (n − 1)(n − 2)! = · · · = n * (n − 1) * (n − 2) * · · · * 1 * 0!


Rekurze

173 / 358

Výpočet hodnot funkce faktoriál Vstupní hodnota 0 1 2 3 4 5 6 7 8 9 10


Výpočet hodnoty podle definice 1*1 2*1 3*2 4*6 5 * 24 6 * 120 7 * 720 8 * 5 040 9 * 40 320 10 * 362 880

Rekurze


Rekurze

174 / 358

Faktoriál – ukázka kódu Hodnota faktoriálu 1 1 2 6 24 120 720 5 040 40 320 362 880 3 628 800

int factorial(const int n) { if(n == 0) return 1; return n * factorial(n - 1); }

175 / 358


Rekurze

176 / 358

Faktoriál – výpočet

Faktoriál – schéma rekurze Požadavek na výpočet 4!

Co se děje při rekurzívním výpočtu? Jak je zajištěno, aby se uchovaly všechny hodnoty proměnných v okamžiku rekurentního volání dílčí úlohy a při jejím ukončení, tj.návratu z poslední rekurentní funkce či procedury byly předány správné hodnoty?

První volání n = 4 Druhé volání n = 3 Třetí volání n = 2 Čtvrté volání n = 1 Páté volání n = 0 Návrat přímo

jednotlivé úlohy seřadíme do řady, aktuální úloha je na konci v okamžiku dokončení výpočtu, je výsledek předán volající metodě, ruší se lokální proměnné

s hodnotou 1 Násobeno 1 Návrat s hodnotou 1

je to zásobník, LIFO

Násobeno 2 Návrat s hodnotou 2

každým rekurzivním voláním metody vzniká nová množina všech parametrů a lokálních proměnných

Násobeno 3 Návrat s hodnotou 6

mají sice stejné identifikátory jako při prvním volání, ale jejich hodnoty jsou jiné

Násobeno 4 Návrat s hodnotou 24 Ukončení s hodnotou 24


Rekurze

177 / 358

Fibonacciho posloupnost


Obrázek 3.2: Princip vnořování rekurze Rekurze

178 / 358

Fibonacciho posloupnost Řešení:

aneb Kolik potomků – párů králíků bude mít po roce jeden původní králičí pár?

1. Po prvním měsíci bude na poli stále jeden pár králíků. Na poli je 1 pár.

1. Na pole vypustíme pár králíků.

2. Na konci druhého měsíce vznikne jeden nový pár králíků. Na poli jsou 2 páry.

2. Králíci dospívají po jednom měsíci, březost trvá jeden měsíc. To znamená, že po dvou měsících samice vyprodukuje nový pár králíků.

3. Na konci třetího měsíce původní pár vyprodukuje nový pár, druhý pár dospívá. Na poli jsou 3 páry.

3. Králíci neumírají a nejsou nemocní.

4. Na konci čtvrtého měsíce, původní pár vyprodukoval další pár, pár narozený před dvěma měsíci má svoje první potomstvo. Na poli je 5 párů.

4. Každý pár králíků vždy vyprodukuje jeden nový pár samec/samice. Úloha byla poprvé publikována roku 1202 Leonardem Pisano (Leonardo Fibonacci) v knize Liber Abacci


Rekurze

179 / 358

Na konci n-tého měsíce je počet párů králíků roven počtu nových párů králíků (což je počet párů v měsíci n-2) plus počet párů žijících v minulém měsíci.


Rekurze

180 / 358

Fibonacciho posloupnost

Fibonacciho posloupnost – ukázka kódu

Matematické vyjádření:

int F(const int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n - 1) + F(n - 2); }

F (n) =

⎧ ⎪ ⎨ 0

pro n = 0 1 pro n = 1 ⎪ ⎩ F (n − 1) + F (n − 2) pro n > 1

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . . F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, . . .


Rekurze

181 / 358

Fibonacciho posloupnost – ukázka výpočtu


Rekurze

182 / 358


4

3 3

2

2

2

1

0

1


n=3

Rekurze

1

1

0

0 1

n=2

2

1

0

n=4

183 / 358


Rekurze

184 / 358


Vyhledání maxima hodnot v poli iterativně

int maximumIter(int[] a, const int N) { int max = a[0]; for(int i = 0; i < N; i++) { if (a[i] > max) max = a[i]; } return max; }

5 3

4 3 2 1

2 1

1

1

2 0

1

0

0

n=5


Rekurze

185 / 358

Vyhledání maxima hodnot v poli rekurzivně

Rekurze

Rekurze

186 / 358

Rekurze – shrnutí

int maxRecursive(int[] a, const int left, const int right) { if (left == right) return a[left]; int m = (left + right) / 2; int lm = maxRecursive(a, left, m); int rm = maxRecursive(a, m+1, right); return lm > rm ? lm : rm; }



187 / 358

užitečná technika jak psát programy, založena na rozdělení problému na menší podproblémy, z vyřešených dílčích částí skládá celek, spíše deklarujeme co chceme řešit, než jak to máme řešit, používána pro vyhledávání řešení.


Rekurze

188 / 358

Využití rekurze pro řešení problémů Děkuji za pozornost



Rekurze

189 / 358

Backtracking


Využití rekurze pro řešení problémů

190 / 358

Jezdcova procházka

šachový a matematický problém popsaný pomocí šachové figury jezdce a šachovnice,

zpětné vyhledávání, metoda pokusů a oprav, metoda zpětného sledování, metoda prohledávání do hloubky, způsob řešení algoritmických problémů

jezdec se pohybuje v souladu s šachovými pravidly po prázdné šachovnici,

založený na prohledávání stavového stromu problému

úkolem je, aby každé pole navštívil právě jednou,

možné použít pro řešení velkého množství problémů

úloha již z 9. století,

obecně exponenciální časová složitost

pro šachovnici 8 × 8 existuje 26 534 728 821 064 řešení, kdy kůň ohrožuje své výchozí postavení,

jen pro data malé velikosti, popřípadě pro něj existuje dobrá heuristika.

řešení uzavřená vs otevřená.



191 / 358



192 / 358

Možné tahy šachovým koněm



Výsledné řešení

193 / 358

Animace výsledného řešení



194 / 358

Zdrojové kódy řešení, soubor KnightsTour.h #pragma once #include #include using namespace std;

Animace jsou v poznámkách k prezentaci vynechány.

/** * Demonstracni ukazka backtrackingu. * Cilem ukazky je implementace sachove ulohy zname pod nazvem Jezdcova prochazka, anglicky Kniht’s tour. * Informace o uloze lze najit napriklad na http://cs. wikipedia.org/wiki/Jezdcova_proch%C3%A1zka * * @author Jiri Dvorsky <[email protected]> Jiří Dvorský (VŠB – TUO)


195 / 358



196 / 358

Zdrojové kódy řešení, soubor KnightsTour.h (pokrač.)


* * Prostor jmen pro projekt KnightsTour. */ namespace KnightsTour { /** * Velikost sachovnice */ const int BoardSize = 8;

/** * Zmeny hodnoty radku pro jednotlive mozne tahy konem */ const int RowMoveDelta[NumberOfKnightMoves] = {-2, -1, +1, +2, +2, +1, -1, -2};

/** * Pocet vsech potencialne moznych tahu konem z policka sachovnice */ const int NumberOfKnightMoves = 8;



197 / 358




198 / 358

* Funkce vyplni vsechna policka sachovnice nulami, coz znamena, ze na dane pole kun dosud neskocil. * * @param Board Inicializovana sachovnice */ void InitBoard(int Board[BoardSize][BoardSize]);

/** * radek dane pozice */ int Row; /** * Sloupec dane pozice */ int Column;

/** * Vystup sachovnice na standardni vystup (obrazovku). * * @param Board Vypisovana sachovnice */ void PrintBoard(const int Board[BoardSize][BoardSize]);

};

/** * Inicializace sachovnice. * Využití rekurze pro řešení problémů

/** * Struktura pro ulozeni pozice kone na sachovnici */ struct Position


{


/** * Zmeny hodnoty sloupce pro jednotlive mozne tahy konem */ const int ColumnMoveDelta[NumberOfKnightMoves] = {+1, +2, +2, +1, -1, -2, -2, -1};

199 / 358



200 / 358



/** * Posun konem po sachovnici. * * Funkce provede jeden z NumberOfKnightMoves moznych tahu. * Funkce nezkouma, jestli provedeny tah je platny ( napriklad, zda se kun neocitnul mimo sachovnici). * * @param CurrentPos Soucasna poloha kone na sachovnici * @param MoveIndex cislo tahu, ktery z NumberOfKnightMoves moznych tahu chceme provest. * @return Funkce vraci novou polohu kone na sachovnici. */ Position Move(const Position& CurrentPos, const int MoveIndex);



201 / 358





202 / 358


/** * Rekurzivni hledani reseni ulohy, implementace pomoci backtrackingu. * * Funkce postupne provadi jednotlive mozne tahy konem ze soucasne polohy kone na sachovnici (celkem az NumberOfKnightMoves tahu). * Pokud ja takto provedeny tah platny, tah se zaznamena do sachovnice a rekurzivne se pokracuje dal. * Pokud funkce vycerpa vsechny mozne tahy ze soucasne pozice, vraci funkce false jako signal, ze reseni * z teto polohy kone na sachovnici neni mozne v dalsich tazich najit. Prohledavani se tedy vraci o jeden tah zpet (vraceni zpet - backtracking). * Jiří Dvorský (VŠB – TUO)

/** * Test, zda je tah platny. * * Tah je platny pokud se kun neocitnul mimo sachovnici a pokud neskocil na policko, kde jiz jednou byl. * * @param Pos Soucasna poloha kone na sachovnici * @param Board sachovnice * @return Funkce vraci true pokud je tah platny, jinak vraci false. */ bool IsValidMove(const Position& Pos, const int Board[ BoardSize][BoardSize]);

203 / 358

* Funkce hleda prvni mozne reseni, nikoliv vsechna mozna reseni. * * @param Board sachovnice, v sachovnici jsou zaznamenany vsechny tahy pocinaje prvnim (cislo 1) a konce tahem s cislem MoveNumber-1. * @param CurrentPos Soucasna poloha kone na sachovnici, poloha v tahu s cislem MoveNumber-1. * @param MoveNumber cislo tahu, ktery prave resime * @return Funkce vraci true pokud bylo v naslednych tazich po tahu s cislem MoveNumber nalezeno reseni, jinak vraci false. */ bool SolveKnightsTour(int Board[BoardSize][BoardSize], const Position& CurrentPos, const int MoveNumber); } Jiří Dvorský (VŠB – TUO)


204 / 358


Zdrojové kódy řešení, soubor KnightsTour.cpp #include "KnightsTour.h" namespace KnightsTour { void InitBoard(int Board[BoardSize][BoardSize]) { for(int i = 0; i < BoardSize; i++) { for(int j = 0; j < BoardSize; j++) { Board[i][j] = 0; } } }



205 / 358

Zdrojové kódy řešení, soubor KnightsTour.cpp (pokrač.) void PrintBoard(const int Board[BoardSize][BoardSize]) { for(int i = 0; i < BoardSize; i++) { for(int j = 0; j < BoardSize; j++) { cout << setw(4) << Board[i][j]; } cout << endl; } cout << endl; } Position Move(const Position& Pos, const int MoveIndex) { Position NewPos; Jiří Dvorský (VŠB – TUO)


207 / 358



206 / 358

Zdrojové kódy řešení, soubor KnightsTour.cpp (pokrač.) NewPos.Row = Pos.Row + RowMoveDelta[MoveIndex]; NewPos.Column = Pos.Column + ColumnMoveDelta[MoveIndex ]; return NewPos; } bool IsValidMove(const Position& Pos, const int Board[ BoardSize][BoardSize]) { bool Result = true; Result &= 0 <= Pos.Row; Result &= Pos.Row < BoardSize; Result &= 0 <= Pos.Column; Result &= Pos.Column < BoardSize; if (Result) { Jiří Dvorský (VŠB – TUO)


208 / 358

Zdrojové kódy řešení, soubor KnightsTour.cpp (pokrač.)

Zdrojové kódy řešení, soubor KnightsTour.cpp (pokrač.)

Result &= Board[Pos.Row][Pos.Column] == 0; } return Result;

{ Board[p.Row][p.Column] = MoveNumber; if (SolveKnightsTour(Board, p, MoveNumber+1)) { return true; } Board[p.Row][p.Column] = 0;

} bool SolveKnightsTour(int Board[BoardSize][BoardSize], const Position& CurrentPos, const int MoveNumber) { if (MoveNumber == BoardSize*BoardSize + 1) { return true; } for(int i = 0; i < NumberOfKnightMoves; i++) { Position p = Move(CurrentPos, i); if (IsValidMove(p, Board)) Jiří Dvorský (VŠB – TUO)


} } return false; } }

209 / 358

Zdrojové kódy řešení, soubor main.cpp



210 / 358

Zdrojové kódy řešení, soubor main.cpp (pokrač.)

#include "KnightsTour.h" using namespace KnightsTour;

{

void main() { int Board[BoardSize][BoardSize]; InitBoard(Board); Position InitPos; // vychozi pozice je zvolena nahodne InitPos.Row = 0; InitPos.Column = 0; Board[InitPos.Row][InitPos.Column] = 1; bool HasSolution = SolveKnightsTour(Board, InitPos, 2); if (HasSolution) Jiří Dvorský (VŠB – TUO)


211 / 358

PrintBoard(Board); } else { cout << "Reseni nenalezeno!" << endl; } }



212 / 358

Vyhledávání Děkuji za pozornost




213 / 358

Vyhledávání – definice problému


Vyhledávání

214 / 358

Vyhledávání – jednorozměrné vyhledávání

Základní pojmy adresní vyhledávací algoritmy – využívají jednoznačného vztahu mezi hodnotou klíče prvku a umístěním prvku ve struktuře reprezentující vyhledávací prostor S (přímý přístup k prvkům pole pomocí indexů, hašovací tabulky)

vyhledávací prostor S, klíč, hodnota.

Příklad seznam loginů studentů a jejich hodnocení v předmětu Algoritmy I, autorský katalog v knihovně,

asociativní vyhledávací algoritmy – porovnávání prvků (relativní hodnota vzhledem k ostatním prvkům) při hledání prvku x ∈ S se využívají relace (porovnávání) mezi prvky struktury reprezentující S (vyhledávání v poli).

množina všech českých samohlásek.


Vyhledávání

215 / 358


Vyhledávání

216 / 358

Vyhledávání – vícerozměrné vyhledávání

Vyhledávání – typické úlohy

nevyhledáváme jen podle jednoho klíče, ale podle více klíčů, příslušnost prvku – je obsažen nebo ne? Matematicky x ∈ S nebo x ̸∈ S

nutnost přizpůsobit datové struktury a algoritmy, samotné vyhledávací algoritmy se dají rozdělit do tří kategorií:

hledání extrému – minimum nebo maximum

dotazy na úplnou shodu – dotazy požadující shodu na všech klíčích. dotazy na částečnou shodu – dotazy požadující shodu jen na některých složkách klíče. dotazy na intervalovou shodu – dotazy požadující, aby klíč záznamu byl v určeném intervalu.

dotaz na shodu – úplnou nebo částečnou Při konkrétní implementaci zadané úlohy existuje vzájemná souvislost mezi všemi operacemi a všechny operace závisejí na zvolené reprezentaci vyhledávacího prostoru.

Do této kategorie vlastně spadají všechny databázové systémy.


Vyhledávání

217 / 358


Vyhledávání

218 / 358

Složitost vyhledávání

Vyhledávání v poli

nejjednodušší paměťová struktura, přímý přístup k prvkům,

Prostorová složitost

typicky jednorozměrné vyhledávání (klíč, hodnota),

Konstantní – jen prohledávané pole a konstantní rozsah pomocných proměnných

Řešené úlohy příslušnost prvku

Časová složitost

výsledek jako logická hodnota výsledek index hledaného prvku v poli

Jaké operace zkoumat? Porovnání hledaného prvku s prvkem v poli.

dotaz na úplnou shodu Budeme předpokládat jeden výskyt každého prvku v poli


Vyhledávání

219 / 358


Vyhledávání

220 / 358

Sekvenční vyhledávání

Iterativní implementace

bez požadavků na prohledávané pole, prohledávané pole tedy nemusí být setříděné, algoritmus prohledává celé pole – postupně testuje jednotlivé prvky pole, složitost O(n), kde n je počet prvků v prohledávaném poli.

bool LinearSearch1(const int a[], const int n, const int x) { for(int i = 0; i < n; i++) { if (a[i] == x) { return true; } } return false; } Výsledkem je logická hodnota.


Vyhledávání

221 / 358


Vyhledávání


Rekurzivní implementace

int LinearSearch2(const int a[], const int n, const int x) { for(int i = 0; i < n; i++) { if (a[i] == x) { return i; } } return -1; }

bool LinearSearchRecursive1(const int a[], const int n, const int x, const int i) { if (i == n) { return false; } if (a[i] == x) { return true; } return LinearSearchRecursive1(a, n, x, i+1); }

Výsledkem je index nalezeného prvku, jinak -1.

222 / 358

Výsledkem je logická hodnota. Jiří Dvorský (VŠB – TUO)

Vyhledávání

223 / 358


Vyhledávání

224 / 358


Vyhledávání půlením intervalu

int LinearSearchRecursive2(const int a[], const int n, const int x, const int i) { if (i == n) { return -1; } if (a[i] == x) { return i; } return LinearSearchRecursive2(a, n, x, i+1); }

Lze zlepšit časovou složitost sekvenčního vyhledávání? Pokud o prohledávaném poli nevíme vůbec nic asi těžko? Co kdybychom pole setřídili? Budeme předpokládat, že pole je setříděno vzestupně. Potom bychom nemuseli prohledávat pole celé. Po nalezení většího prvku než je hledaný už nemá cenu dále hledat. Nešlo by počet prvků, které je nutné otestovat nějak radikálněji zmenšovat?

Výsledkem je index nalezeného prvku, jinak -1. Jiří Dvorský (VŠB – TUO)

Vyhledávání

225 / 358

Půlení intervalu, úspěšné hledání prvku 19

7

Vyhledávání

Vyhledávání

226 / 358


Určíme střed celého pole a srovnáme 19 s 34 11 16 19 23 31 34 40 43 52 56 61 65



227 / 358

7


7

Určíme střed úseku pole a srovnáme 19 s 16 11 16 19 23 31 34 40 43 52 56 61 65


Vyhledávání

228 / 358


7



7


7


7


7


7


7

Určíme střed úseku pole a srovnáme 19 s 19 11 16 19 23 31 34 40 43 52 56 61 65 Prvek 19 byl úspěšně nalezen!


Vyhledávání

229 / 358



Vyhledávání

230 / 358


Zkráceně můžeme postup hledání prvku 19 zachytit takto:

7

11 16 19 23

31 34 40 43

52 56 61 65

7

11 16 19 23

31 34 40 43

52 56 61 65

7

11 16 19 23 31

34 40 43 52

56 61 65

7

11 16 19 23

31 34 40 43

52 56 61 65

7

11 16 19 23 31

34 40 43 52

56 61 65

7

11 16 19 23

31 34 40 43

52 56 61 65

7

11 16 19 23 31

34 40 43 52

56 61 65

Poznámka Celé pole můžeme považovat také za „úsek pole“, který je shodou okolností roven celému poli. Tím se nám zjednoduší další výklad a v důsledku i výsledný algoritmus. Jiří Dvorský (VŠB – TUO)

Vyhledávání

231 / 358


Vyhledávání

232 / 358


Půlení intervalu – úsek pole Jak reprezentovat úsek pole?

7

11 16 19 23

31 34 40 43

52 56 61 65

7

11 16 19 23

31 34 40 43

52 56 61 65

L R M

– – –

index levého okraje prohledávaného úseku pole, Left index pravého okraje prohledávaného úseku pole, Right index středu prohledávaného úseku pole, Mid

Indexy L a R 7

11 16 19 23

31 34 40 43

52 56 61 65

7

11 16 19 23

31 34 40 43

52 56 61 65

Indexy L a R jsou inkluzivní – první a poslední prvek úseku leží na těchto indexech. Srovnej s délkou pole a indexem posledního prvku pole v jazyku C++.

Poznámka Index levého resp. pravého okraje úseku pole budeme také nazývat levou resp. pravou mezí úseku pole. Jiří Dvorský (VŠB – TUO)

Vyhledávání

233 / 358

Půlení intervalu – výpočet středu úseku

Vyhledávání

234 / 358

Půlení intervalu, úspěšné hledání prvku 19 Úseky pole

Výpočet středu úseku M =L+


R −L 2L + R − L L+R = = 2 2 2

Konvence při výpočtu středu úseku Je jasná, že součet L + R nemusí být sudé číslo. Co s tím?! Dělení vždy probíhá celočíselně! Například L = 0 a R = 5. Střed je M = 2, nikoliv M = 2.5.

Indexy

7 11 16 19 23 31 34 40 43 52 56 61 65

L 0

R 12

M 6

7 11 16 19 23 31 34 40 43 52 56 61 65

0

5

2

7 11 16 19 23 31 34 40 43 52 56 61 65

3

5

4

7 11 16 19 23 31 34 40 43 52 56 61 65

3

3

3

Levá část děleného úseku tak bude o jeden prvek kratší. Pokud bychom dělili s plovoucí řádovou čárkou a zaokrouhlovali nahoru, jak je obvyklé, dosáhli bychom jedině toho, že levá část by byla o jeden prvek delší než pravá.


Vyhledávání

235 / 358

Posun doleva L R

Posun doprava

Nová hodnota beze změny M −1


L R Vyhledávání

Nová hodnota M +1 beze změny 236 / 358

Půlení intervalu, neúspěšné hledání prvku 55

7


7


7


7


Půlení intervalu, neúspěšné hledání prvku 55 Jak rozpoznat konec u neúspěšného hledání? Konec rozpoznáme snadno – úsek obsahuje jen jeden prvek a není to ten, který hledáme. Ale! Při úspěšném hledání prvku 19 jsme taky skončili u jednoprvkového úseku. Jsou tedy jednoprvkové úseky nějakou zvláštností? Proč by měly? Takže bychom měli vyhledávání ukončit až úsek zkrátíme na jeden prvek? A když se u více prvkového úseku „trefíme“ tak, že hledaný prvek bude přímo ve středu. To bychom mohli skončit rovnou, ne? Takže redukce na jeden prvek není asi nutná.

Prvek 55 nebyl nalezen!


Vyhledávání

A opačná otázka? Jak poznám, že mám ve vyhledávání naopak stále pokračovat? 237 / 358


Vyhledávání

Půlení intervalu, neúspěšné hledání prvku 55

Půlení intervalu, invariant algoritmu Při výpočtu středu úseku

Úseky pole R −L M =L+ 2

předpokládáme, že R ≥ L! Otázka zní, platí tento předpoklad po celou dobu vykonávání algoritmu? A pokud toto neplatí, kdy je předpoklad porušen?

Invariant algoritmu Invariant je podmínka v algoritmu, která musí být splněna po celou dobu vykonávání algoritmu.

Indexy

7 11 16 19 23 31 34 40 43 52 56 61 65

L 0

R 12

M 6

7 11 16 19 23 31 34 40 43 52 56 61 65

7

12

9

7 11 16 19 23 31 34 40 43 52 56 61 65

10

12

11

7 11 16 19 23 31 34 40 43 52 56 61 65

10

10

10

Prvek 55 je menší než 56, „pokračujeme“ levou částí

10

9

Invariant algoritmu vyhledávání půlením intervalu

Porušení invariantu algoritmu

V našem případě musí vždy platit, že R ≥ L.

Levá mez je větší než pravá. Došlo k překřížení mezí.


Vyhledávání

238 / 358

239 / 358


Vyhledávání

240 / 358



bool BinarySearchRecursive1(const int a[], const int l, const int r, const int x) { if (l > r) return false; int m = (l + r)/2; if (x == a[m]) return true; if (x < a[m]) return BinarySearchRecursive1(a, l, m - 1, x); return BinarySearchRecursive1(a, m + 1, r, x); }

bool BinarySearchRecursive1a(const int a[], const int l, const int r, const int x) { if (l > r) return false; int m = (l + r)/2; if (x == a[m]) return true; return x < a[m] ? BinarySearchRecursive1a(a, l, m - 1, x ) : BinarySearchRecursive1a(a, m + 1, r, x); } Místo příkazu if použit ternární operátor.

Výsledkem je logická hodnota.


Vyhledávání

241 / 358


Vyhledávání

242 / 358



int BinarySearchRecursive2(const int a[], const int l, const int r, const int x) { if (l > r) return -1; int m = (l + r)/2; if (x == a[m]) return m; if (x < a[m]) return BinarySearchRecursive2(a, l, m - 1, x); return BinarySearchRecursive2(a, m + 1, r, x); }

int BinarySearchRecursive3(const int a[], const int l, const int r, const int x) { if (l > r) return ~l; int m = (l + r)/2; if (x == a[m]) return m; if (x < a[m]) return BinarySearchRecursive3(a, l, m - 1, x); return BinarySearchRecursive3(a, m + 1, r, x); }

Výsledkem je index nalezeného prvku, jinak -1.

Výsledkem je index nalezeného prvku, jinak bitový doplněk správné pozice.


Vyhledávání

243 / 358


Vyhledávání

244 / 358



bool BinarySearch1(const int a[], const int n, const int x) { int l = 0; int r = n - 1; while (l <= r) { int m = (l + r)/2; if (x == a[m]) return true; if (x < a[m]) r = m - 1; else l = m + 1; } return false; }

int BinarySearch2(const int a[], const int n, const int x) { int l = 0; int r = n - 1; while (l <= r) { int m = (l + r)/2; if (x == a[m]) return m; if (x < a[m]) r = m - 1; else l = m + 1; } return -1; }

Výsledkem je logická hodnota. Jiří Dvorský (VŠB – TUO)

Výsledkem je index jinak -1. Jiří Dvorský (VŠB – TUO) nalezeného prvku, Vyhledávání

Vyhledávání

245 / 358

246 / 358

Iterativní implementace int BinarySearch3(const int a[], const int n, const int x) { int l = 0; int r = n - 1; while (l <= r) { int m = (l + r)/2; if (x == a[m]) return m; if (x < a[m]) r = m - 1; else l = m + 1; } return ~l; } Výsledkem je index jinak bitový doplněk správné pozice. Jiří Dvorský (VŠB – TUO) nalezeného prvku, Vyhledávání 247 / 358



Vyhledávání

248 / 358

RadixSort – náhodná permutace

Třídění doc. Mgr. Jiří Dvorský, Ph.D. Animace jsou v poznámkách k prezentaci vynechány.



Třídění

249 / 358

RadixSort – identická permutace

Třídění

Třídění

250 / 358

RadixSort – opačná permutace





251 / 358


Třídění

252 / 358

RadixSort – téměř setříděná permutace

RadixSort – permutace pouze několika hodnot



Třídění


253 / 358


Třídění

254 / 358

Základní třídící algoritmy Děkuji za pozornost



Třídění

255 / 358


Základní třídící algoritmy

256 / 358

Asociativní třídicí algoritmy

Složitost asociativních třídicích algoritmů

jsou nejvšeobecnější skupinou třídících algoritmů, nepředpokládají o prvcích tříděné množiny nic víc než že jsou vybrané z uspořádaného univerza, jinak řečeno mezi prvky je definována relace „menší nebo rovno“, jsou založeny na operacích porovnání a přesun (výměna) dvou prvků, tyto dvě operace významně ovlivňují složitost asociativních třídicích algoritmů.



257 / 358

Složitost asociativních třídicích algoritmů

Složitost asociativních třídících algoritmů budeme měřit počtem porovnání a přesunů prvků. Porovnání a přesuny prvků nemusí být triviální operace. Porovnání se týká jen klíče, zatímco přesun se týká celého záznamu. Markantní rozdíl mezi cenou porovnání a cenou přesunu se projeví zvláště tehdy, když je délka záznamu podstatně větší než délka klíče.



258 / 358

Míra nesetříděnosti posloupnosti

Budeme ji definovat jako počet inverzí v permutaci. Efektivnost některých asociativních třídicích algoritmů závisí od toho, v jakém pořadí jsou uspořádané prvky ve vstupní posloupnosti. Je-li vstupní posloupnost již setříděná, neměl by třídící algoritmus, po odhalení tohoto faktu, vykonávat žádnou činnost. Složitost třídícího algoritmu by měla vzrůstat s mírou nesetříděnosti posloupnosti. Třídící algoritmus by měl být přirozený.



Uvažujme permutaci 𝜋 : {1, . . . , n} → {1, . . . , n} Řekneme, že dvojice různých prvků (i, j) představuje inverzi permutace 𝜋, jestliže i ≤ j ∧ 𝜋i > 𝜋j . Inverzi permutace můžeme volně interpretovat tak, že „na menším indexu je větší prvek a naopak na větším indexu je menší prvek“. Ještě jinak řečeno, tyto dva prvky jsou přehozeny, za předpokladu, že chceme posloupnost třídit vzestupně.

259 / 358



260 / 358



Počet inverzí setříděné posloupnosti je 0. Maximální počet inverzí, rovný 12 n(n − 1), obsahuje posloupnost setříděná v opačném pořadí.

Příklad (︃

𝜋=

1 2 3 4 4 1 3 2

)︃

Průměrný počet inverzí v posloupnosti je přibližně 41 n(n − 1), za předpokladu, že každá posloupnosti je stejně pravděpodobná.

Inverze:

Uvažujme všechny permutace n prvků {1, 2, . . . , n}.

1<2∧4>1

Permutace n prvků vytvoříme přidáním čísla n k (n − 1)! permutacím n − 1 prvků {1, 2, . . . , n − 1}. Číslo n můžeme přidat:

1<3∧4>3 1<4∧4>2 3<4∧3>2


na poslední místo – pak se počet inverzí nezvýší, na předposlední místo – pak přibude jedna inverze, a tak dále až na první místo – pak přibude n − 1 inverzí.


261 / 358




262 / 358


Pro průměrný počet inverzí In tedy bude platit: n!In = (n − 1)!In−1 + 0 · (n − 1)! +

Odkud

(n − 1)!In−1 + 1 · (n − 1)! +

1 In = In−1 + (n − 1) 2 .. . 1 1 1 1 = (n − 1) + (n − 2) + (n − 3) + · 1 2 2 2 2 1 = n(n − 1) 4

(n − 1)!In−1 + 2 · (n − 1)! + (n − 1)!In−1 + (n − 1) · (n − 1)! Tedy n!In = n(n − 1)!In−1 + (0 + 1 + 2 + · · · + (n − 1)) · (n − 1)! 1 = n!In−1 + n(n − 1)(n − 1)! 2 1 = n!In−1 + (n − 1)n! 2



263 / 358



264 / 358

Vizualizace permutací

Asociativní třídicí algoritmy

Permutaci

(︃

𝜋=

1 2 ... n 𝜋1 𝜋2 . . . 𝜋n

)︃

můžeme znázornit jako posloupnost n svislých pruhů, kde

Princip

pořadí pruhu odpovídá indexu i a

Na algoritmy asociativního třídění se tedy můžeme dívat jako na algoritmy odstraňující postupně inverze ze vstupní posloupnosti pomocí vzájemných výměn vhodných prvků, do té doby, dokud posloupnost neobsahuje žádné inverze.

výška pruhu odpovídá hodnotě 𝜋i . Šířka všech pruhů je stejná a ve vizualizaci nehraje roli.

Příklad Permutaci (︃

𝜋=

1 2 3 4 4 1 3 2

)︃

odpovídá zobrazení Jiří Dvorský (VŠB – TUO)


265 / 358

Náhodná



266 / 358

Obecná funkce pro výměnu dvou prvků pole

Vizualizace permutací – ukázky Identická


Opačně setříděná

void Exchange(int& a, int& b) { int aux = a; a = b; b = aux; }

Téměř setříděná


267 / 358



268 / 358

Třídění výběrem – SelectSort

Třídění výběrem – SelectSort

void SelectSort1(int a[], const int N) { for(int i = 0; i < N; i++) { int min = i; for(int j = i+1; j < N; j++) { if (a[j] < a[min]) { min = j; } } int aux = a[min]; a[min] = a[i]; a[i] = aux; } } Jiří Dvorský (VŠB – TUO) Základní třídící algoritmy

void SelectSort1a(int a[], const int N) { for(int i = 0; i < N; i++) { int min = i; for(int j = i+1; j < N; j++) { if (a[j] < a[min]) { min = j; } } Exchange(a[min], a[i]); } } Nahrazení výměny prvků funkcí Exchange. 269 / 358

Třídění výběrem – náhodná permutace



270 / 358

Třídění výběrem – identická permutace





271 / 358



272 / 358

Třídění výběrem – opačná permutace

Třídění výběrem – téměř setříděná permutace





273 / 358

Třídění výběrem – permutace pouze několika hodnot



274 / 358

Třídění vkládáním – InsertSort void InsertSort(int a[], const int N) { for(int i = 1; i < N; i++) { int v = a[i]; int j = i; while (j > 0) { if (a[j-1] > v) { a[j] = a[j-1]; j -= 1; } else {




275 / 358



276 / 358

Třídění vkládáním – InsertSort (pokrač.)

Třídění vkládáním – náhodná permutace

break; } } a[j] = v;


} }



277 / 358

Třídění vkládáním – identická permutace



278 / 358

Třídění vkládáním – opačná permutace





279 / 358



280 / 358

Třídění vkládáním – téměř setříděná permutace

Třídění vkládáním – permutace pouze několika hodnot





281 / 358

Bublinové třídění – BubbleSort



282 / 358

Bublinové třídění – BubbleSort void BubbleSort0(int a[], const int N) { for(int i = 0; i < N; i++) { for(int j = 0; j < N - 1; j++) { if (a[j] > a[j+1]) { Exchange(a[j], a[j+1]); } } } }

Vezmu dvojici sousedních prvků ai a ai+1 . Pokud tvoří inverzi, vyměním je. Pokračuji další dvojicí prvků ai a ai+1 , ale pro i + 1 atd. Výměnou dvojice prvků odstraním jednu inverzi. Proč bublinové třídění – největší prvek „se rozjede“, „probublá“ směrem ke konci pole.

Tak takhle ne! Jiří Dvorský (VŠB – TUO)


283 / 358

Tato implementace bublinového třídění je nejhorší možná! Takto by se bublinové třídění nemělo nikdyZákladní implementovat. Jiří Dvorský (VŠB – TUO) třídící algoritmy 284 / 358



void BubbleSort1(int a[], const int N) { for(int i = N-1; i > 0; i--) { for(int j = 0; j < i; j++) { if (a[j] > a[j+1]) { Exchange(a[j], a[j+1]); } } } }

Jiná možnost ukončení algoritmu – nedošlo k výměně prvků. Zavedeme si logickou proměnnou AnyExchange, kam si budeme ukládat informaci o případné výměně. Pokud algoritmus obdrží již setříděnou posloupnost – po jednom průchodu pozná, že je posloupnost již setříděná.

Po každém průchodu se dostane jeden prvek určitě na své místo – probublá nahoru. Není nutné jej proto dále zpracovávat. Jiří Tříděnou Dvorský (VŠB –posloupnost TUO) Základní třídící algoritmy prvek zkrátit. 285 / 358 je možné o tento




286 / 358


void BubbleSort2(int a[], const int N) { bool AnyExchange; do { AnyExchange = false; for(int i = 0; i < N - 1; i++) { if (a[i] > a[i+1]) { Exchange(a[i], a[i+1]); AnyExchange = true; } } } while (AnyExchange); } Jiří Dvorský (VŠB – TUO)


Kombinovaná možnost ukončení algoritmu: nedošlo k výměně prvků a zkracování posloupnosti o jeden prvek zprava.

Zavedeme si logickou proměnnou AnyExchange, kam si budeme ukládat informaci o případné výměně. Proměnná Right bude označovat pravý okraj tříděné posloupnosti.

287 / 358



288 / 358

Bublinové třídění

Bublinové třídění (pokrač.)

void BubbleSort3(int a[], const int N) { bool AnyExchange; int Right = N - 1; do { AnyExchange = false; for(int i = 0; i < Right; i++) { if (a[i] > a[i+1]) { Exchange(a[i], a[i+1]); AnyExchange = true; } } Jiří Dvorský (VŠB – TUO)


Right -= 1; } while (AnyExchange); }

289 / 358


nedošlo k výměně prvků a zkracování posloupnosti na index poslední výměny.

Zavedeme si logickou proměnnou AnyExchange, kam si budeme ukládat informaci o případné výměně. Proměnná LastExchangeIndex bude označovat pravý okraj tříděné posloupnosti, index poslední výměny prvků.



290 / 358

Bublinové třídění

Kombinovaná možnost ukončení algoritmu:



291 / 358

void BubbleSort4(int a[], const int N) { int Right = N - 1; int LastExchangeIndex; do { LastExchangeIndex = 0; for(int i = 0; i < Right; i++) { if (a[i] > a[i+1]) { Exchange(a[i], a[i+1]); LastExchangeIndex = i+1; } } Jiří Dvorský (VŠB – TUO)


292 / 358

Bublinové třídění (pokrač.)

Bublinové třídění – náhodná permutace

Right = LastExchangeIndex; } while (LastExchangeIndex > 0);


}



293 / 358

Bublinové třídění – identická permutace



294 / 358

Bublinové třídění – opačná permutace





295 / 358



296 / 358

Bublinové třídění – téměř setříděná permutace

Bublinové třídění – permutace pouze několika hodnot





297 / 358

Třídění přetřásáním


298 / 358

Třídění přetřásáním (pokrač.)

void ShakerSort(int a[], const int N) { int ExchangeIndex; int Left = 0; int Right = N - 1; do { for(int i = Left; i < Right; i++) { if (a[i] > a[i+1]) { Exchange(a[i], a[i+1]); ExchangeIndex = i; } } Jiří Dvorský (VŠB – TUO)



Right = ExchangeIndex; for(int i = Right; i > Left; i--) { if (a[i-1] > a[i]) { Exchange(a[i-1], a[i]); ExchangeIndex = i; } } Left = ExchangeIndex; } while (Left < Right); }

299 / 358



300 / 358

Třídění přetřásáním – náhodná permutace

Třídění přetřásáním – identická permutace





301 / 358

Třídění přetřásáním – opačná permutace



302 / 358

Třídění přetřásáním – téměř setříděná permutace





303 / 358



304 / 358

Třídění přetřásáním – permutace pouze několika hodnot

Děkuji za pozornost Animace jsou v poznámkách k prezentaci vynechány.



305 / 358



306 / 358

QuickSort – Třídění rozdělováním

Pokročilé třídící algoritmy C. A. R. Hoare, 1962. využití metody „rozděl a panuj“ (divide et impera),


rekurzivní algoritmus, výměny na velkou vzdálenost,


v každém kroku rozdělení tříděného úseku pole na dvě disjunktní části, všechny prvky v levé části jsou menší než všechny prvky v pravé částí, rozdělení pomocí prvku pole zvaného pivot, levá a pravá část pole je tříděna pomocí rekurze stejným způsobem.


Pokročilé třídící algoritmy

307 / 358



308 / 358

QuickSort, výběr pivota

QuickSort, výběr pivota ideální případ – pivot rozdělí tříděný úsek pole na dvě přibližně stejné části – medián,

pivotem může být libovolný prvek ze tříděného úseku pole, tříděný úsek pole se prochází:

nejhorší případ – pivot rozdělí tříděný úsek pole na část s jedním prvkem a zbytkem – minimum či maximum, další možnosti:

1. zleva a hledá se prvek větší než pivot, 2. zprava a hledá se prvek menší než pivot, 3. takto nesprávně zařazené prvky se vzájemně prohodí.

prvek ve středu tříděného úseku, medián ze tří prvků tříděného úseku, první prvek, libovolný prvek.

až se indexy kterými pole zleva a zprava „potkají“ je tříděný úsek pole rozdělen na dvě části algoritmus funguje vždy, ale

Složitost algoritmu QuickSort

výběr pivota silně ovlivňuje složitost algoritmu!

průměrná časová složitost O(n log2 n) nejhorší časová složitost O(n2 )!



309 / 358

QucikSort – Třídění rozdělováním



310 / 358

QucikSort – Třídění rozdělováním (pokrač.)

void QuickSort(int a[], const int l, const int r) { int i = l; int j = r; int pivot = a[(l + r)/2]; do { while (a[i] < pivot) i += 1; while (pivot < a[j]) j -= 1; if (i <= j) { Exchange(a[i], a[j]); i += 1; j -= 1; } Jiří Dvorský (VŠB – TUO)


} while (i <= j); if (l < j) QuickSort(a, l, j); if (i < r) QuickSort(a, i, r); }

311 / 358



312 / 358

QuickSort – náhodná permutace, pivot prostřední prvek úseku

QuickSort – náhodná permutace, pivot medián úseku

Animace jsou v poznámkách k prezentaci vynechány. Animace jsou v poznámkách k prezentaci vynechány.



313 / 358

QuickSort – náhodná permutace, pivot minimum úseku






314 / 358

QuickSort – náhodná permutace, pivot levý prvek úseku


315 / 358



316 / 358

QuickSort – náhodná permutace, pivot náhodný z prvek úseku




QuickSort – identická permutace, pivot prostřední prvek úseku


317 / 358

QuickSort – opačná permutace, pivot prostřední prvek úseku



318 / 358

QuickSort – téměř setříděná permutace

Animace jsou v poznámkách k prezentaci vynechány. Animace jsou v poznámkách k prezentaci vynechány.



319 / 358



320 / 358

QuickSort – permutace pouze několika hodnot

Hloubka rekurze v závislosti na volbě pivota – nejlepší případ, medián

Hloubka rekurze

10


8 6 4 2 0



321 / 358

Hloubka rekurze v závislosti na volbě pivota

Doba běhu algoritmu



322 / 358

Hloubka rekurze v závislosti na volbě pivota – extrémy 1000 Hloubka rekurze

Hloubka rekurze

20 15 10 5 0

600 400 200 0


nejlevější prvek Jiří Dvorský (VŠB – TUO)

800

prostřední prvek Pokročilé třídící algoritmy

Doba běhu algoritmu minimum

náhodný prvek 323 / 358



medián 324 / 358

QuickSort – průběh odstraňování inverzí

Průběh odstraňování inverzí v čase

100 Odstraněno inverzí [%]

300

200

[︀

Počet inverzí ×103

]︀

250

150 100

80 60 40 20

50 0

0

Třídění vkládáním Jiří Dvorský (VŠB – TUO)

0 1 2 3 4 5 6 7 8 9 1011121314 15161718

Doba běhu algoritmu Bublinové třídění

Úroveň zanoření rekurze Relativní četnost Kumulativní relativní četnost

QuickSort


325 / 358

Třídění haldou – HeapSort



Halda (Heap)

Halda reprezentující posloupnost S délky n, je úplný binární strom výšky h ≥ 1 s n vrcholy, a následujícími vlastnostmi:

lze říci, že zlepšuje třídění výběrem, efektivně řeší problém výběru i-tého největšího prvku, pro i = 1 je jasné, že potřebujeme n − 1 porovnání,

všechny listy se nachází ve vzdálenosti h nebo h − 1 od kořene,

ale pro další i by bylo vhodné si nějakým způsobem „zapamatovat“ výsledky předchozích porovnání,

všechny listy na úrovni h jsou vlevo od listů na úrovni h − 1,

tomuto účelu nejlépe vyhovuje datová struktura halda (angl. heap).



326 / 358

327 / 358

každému vrcholu tohoto stromu je přiřazen jeden prvek posloupnosti S tak, že všem jeho potomkům jsou přiřazeny menší prvky.



328 / 358

Konstrukce haldy – počáteční stav

Původní halda

44 44

55

12

42

94

18

6

55

67

42 Haldu lze efektivně reprezentovat v poli tak, že leží-li rodič na indexu i, pak jeho levý potomek leží na indexu 2i a pravý potomek na indexu 2i + 1.



329 / 358

Přehozeno 42 a 67

12 94



330 / 358

Přehozeno 18 s 12

44

55

12 94

18

55 6

42


6

67

44

67

18

67

18 94

12

6

42


331 / 358



332 / 358

Přehozeno 55 a 94

Přehozeno 94 a 44

44

94

94 67

18 55

12

44 6

42

67

18 55

12

6

42



333 / 358

Přehozeno 44 a 67



Odebrání 94

94 67 44

334 / 358

42

18 55

12

67

6

44

42

18 55

12

6

Tím je halda hotová! Jiří Dvorský (VŠB – TUO)


335 / 358



336 / 358

Oprava haldy

Odebrání 67

6

67 55 44

18 42


12

55 6


337 / 358

Oprava haldy

44

18 42



12

44


338 / 358

Odebrání 55

55

6

12

18 42 Pokročilé třídící algoritmy

12

44 6

339 / 358


18 42 Pokročilé třídící algoritmy

340 / 358

Oprava haldy

Odebrání 44

44

12

42

42

18

6

6

12



341 / 358

Oprava haldy



342 / 358

Odebrání 42

42 12

6 18

12

6


18


343 / 358


18


344 / 358

Oprava haldy

Odebrání 18

6

18 12


6


12

345 / 358

Oprava haldy


346 / 358

Koncový stav haldy

12

6

6




347 / 358



348 / 358

Halda reprezentovaná v poli

94


67

18

44


55


12

6

42

349 / 358



350 / 358

Třídění haldou – náhodná permutace

void HeapSort(int a[], const int N) { int i; for(i = N/2; i >= 0; i--) { DownHeap(a, i, N); } i = N - 1; do { Exchange(a[0], a[i]); i -= 1; DownHeap(a, 0, i + 1); } while (i > 0); } Jiří Dvorský (VŠB – TUO)

void DownHeap(int a[], int k, int l) { int v = a[k]; while (k < l/2) { int j = 2 * k; if (j < l-1) { if (a[j] < a[j+1]) j += 1; } if (v >= a[j]) break; a[k] = a[j]; k = j; } a[k] = v; Jiří Dvorský (VŠB – TUO) Pokročilé třídící algoritmy }


351 / 358



352 / 358

Třídění haldou – identická permutace

Třídění haldou – opačná permutace





353 / 358

Třídění haldou – téměř setříděná permutace



354 / 358

Třídění haldou – permutace pouze několika hodnot





355 / 358



356 / 358

Průběh odstraňování inverzí v čase – třídění haldou 600 Permutace identická náhodná opačná

400


[︀

Počet inverzí ×103

]︀

500

300 200 100 0




357 / 358



358 / 358

Celková osnova přednášek. Algoritmy I prezentace k přednáškám. Celková osnova přednášek (pokrač.) Celková osnova přednášek (pokrač

Recommend Documents