Cvičení probíhají v kancelářích CESNETu v budově Gotexu, 3. poschodí.

Nejjednodušší cesta je:

1. vstup přes hlavní vchod
2. skrz dvůr
3. vyjít po schodech na vrchní patro
4. vejít přes dveře vlevo

Protože kanceláře CESNETu nejsou veřejně dostupné, budu vás muset pustit dovnitř. Proto prosím přijďte zavčas. 18:00 půjdu otevřít dveře. Jinak se prosím domluvte s někým kdo vás tam pustí.

Cvičení probíhá v místnosti bez počítačů. Je proto nutné mít notebook  s Linuxem (GCC 4.7). Práce dvojice na jednom notebooku je v pořádku.

Pro toto cvičení nejsou k dispozici žádné materiály.

Na cvičení jsme si prošli obsah semináře a organizační záležitosti.

Implementujte následující program:

Program dostane na vstupu (může být jak soubor tak standardní vstup) seznam čísel.

Např:

10 231254 42 32 1 32 10 23

Program spočítá frekvence (počet výskytů) jednotlivých čísel a vypíše tuto informaci v přehledné tabulce.

Např:

2x 10
2x 32
1x 42
1x 1
1x 23
1x 231254

Pokud program dostane na příkazovém řádku parametr "<tt>--cifry</tt>" bude místo frekvence čísel počítat frekvenci cifer. Výstup opět vypíše v přehledné tabulce.

Např:

4x 3
6x 2
1x 5
2x 4
4x 1
2x 0

Vzorové řešení jsem vám ukázal na cvičení. Na následujícím odkazu si můžete prohlédnout trochu čistější verzi s prvky C++11 https://gist.github.com/3768301

Na tomto cvičení si procvičíme několik jednodušších vlastností C++11.

• klíčové slovo auto
• klíčové slovo nullptr
• automatické ukazatele
• range for cyklus
• funkce begin() a end()

Díky technickým problémům (sype se mi synchronizace videa a zvuku) bohužel zatím nejsou k dispozici videa. Budu se opravdu snažit je dodat ještě před cvičením.

Klíčové slovo auto:

• https://en.wikipedia.org/wiki/C%2B%2B11#Type_inference

Klíčové slovo nullptr:

• http://www.codeguru.com/cpp/cpp/article.php/c19093/C-2011-nullptr.htm

Automatické ukazatele:

• https://en.wikipedia.org/wiki/Smart_pointer#unique_ptr

Range for cyklus, begin() a end():

• http://en.cppreference.com/w/cpp/language/range-for
• http://www.cprogramming.com/c++11/c++11-ranged-for-loop.html

Navrhněte a implementujte datovou strukturu Strom.

• pro uložení a manipulaci s prvky použijte možnosti C++11
  • chytré ukazatele
  • STL
• implementujte na této struktuře metody begin() a end() aby ji bylo možné použít s range for-cyklem
• strom naimplementujte jako univerzální datovou strukturu (šablona)
• připravte pro strom několik operací
  • vstup a výstup v závorkovém formátu
  • suma
  • maximální hloubka listu
  • minimální hloubka listu
  • maximální hodnota
  • maximální hodnota na listech
  • průměrná hodnota
  • průměrná hodnota na listech
  • průměrná hodnota na maximální hloubce

Na tomto cvičení si probereme vlastnosti, které jsou poněkud více teoreticky náročné. Soustřeďte se prosím proto na přípravu.

• uniformní inicializace
• inicializační seznamy
• lambdy
• úvod do async

Uniformní inicializace a inicializační seznamy:

• https://en.wikipedia.org/wiki/C%2B%2B11#Initializer_lists

Lambdy:

• https://en.wikipedia.org/wiki/Anonymous_function#C.2B.2B
• http://en.cppreference.com/w/cpp/language/lambda

Async

• http://en.cppreference.com/w/cpp/thread/async

Tento týden si procvičíme asynchronní operace.

Async

• http://en.cppreference.com/w/cpp/thread/async

Thread

• http://en.cppreference.com/w/cpp/thread/thread
• http://en.cppreference.com/w/cpp/thread/sleep_for
• http://en.cppreference.com/w/cpp/thread/sleep_until
• http://en.cppreference.com/w/cpp/thread/yield

Future, Promise

• http://en.cppreference.com/w/cpp/thread/future
• http://en.cppreference.com/w/cpp/thread/promise
• http://stackoverflow.com/a/12620264/211659

Packaged task

• http://en.cppreference.com/w/cpp/thread/packaged_task

Atomické proměnné

• http://en.cppreference.com/w/cpp/atomic/atomic

Mutexy

• http://en.cppreference.com/w/cpp/thread/mutex
• http://en.cppreference.com/w/cpp/thread/timed_mutex
• http://en.cppreference.com/w/cpp/thread/recursive_mutex

Volba šéfa na obousměrném kruhu - diskuze o algoritmu.

Volba šéfa na jednosměrném kruhu - implementace algoritmu.

Routovací tabulky - implementace algoritmu.

Tento týden nebudeme probírat novou látku, ale procvičíme si již probrané koncepty na generování fraktálů.

• Mandelbrotův fraktál má velmi jednoduchý vzorec, nicméně jeho naivní výpočet je velmi náročný na CPU.
• Vaším úkolem bude připravit paralelní variantu algoritmu, která bude schopna využít více jader.

Pomocný kód:

https://gist.github.com/3940039

Vzorové řešení volby šéfa na jednosměrném kruhu https://gist.github.com/3921334

První část vzorového řešení stromu https://gist.github.com/3929158

Oficiální zadání domácích úkolů. Strom má deadline 26.10. 2012 23:59:59. Routing má deadline 29.10. 2012 23:59:59. Odevzdávejte na toth@fi.muni.cz.

Implementujte datovou strukturu reprezentující obecný strom.

Základní popis

Připravte datovou strukturu schopnou reprezentovat strom (můžete vyjít ze vzorového řešení první části). Datová struktura musí být schopná reprezentovat obecný strom (bez omezení množství potomků na uzlech). Strom by měl umožňovat efektivní oprace přidávání, odebírání a přehazování uzlů.

Implementační požadavky

Kde je to možné používejte STL a chytré ukazatele. Výpočetní operace které jde paralelizovat implementujte pomocí asynchronních prvků C++11.

Výpočetní operace

• suma
  • součet hodnot uzlů (podle sémantiky vnitřního datového typu)
• maximální hloubka
  • maximální hloubka stromu (kořen má hloubku 1)
• minimální hloubka listu
  • list je uzel, který nemá žádné potomky
• maximální hodnota
  • podle sémantiky vnitřního datového typu
• maximální hodnota na listech
• průměrná hodnota
• průměrná hodnota na listech
• průměrná hodnota na maximální hloubce

Implementujte zjednodušený algoritmus pro tvorbu kostry sítě. Tento algoritmus se používá pro detekci minimálních cest mezi zapojenými switchi v síti.

Základní popis

Systém začíná ve stavu kdy máme několik switchů, každý ze switchů má předem určené množství portů. Porty můžou být nezapojené, zapojené do jiného switche, nebo zapojené do koncových počítačů.

Pro zjednodušení uvažujeme pouze spojitý systém (existuje cesta z každého switche do každého switche).

Algoritmus

Každý switch začíná ve stavu kdy zná minimální cestu ke strojům zapojeným na jeho portech (cesta délky 0) a u všech ostatních strojů má uvedenou nekonečnou vzdálenost (reprezentující nedosažitelný stroj).

Switch informaci o minimálních cestách (pouze konečných) oznámí všem switchům ke kterým je připojen.

Pokud switch dostane informaci o cestách od svého souseda, spojí si tuto informaci se svojí lokální informací a pokud dojde k aktualizaci některé z cest, pošle tuto informaci svým sousedům.

Např. pokud switch zná cestu na stroj ID10 přes port 3 se vzdáleností 3 a dostane novou informaci na portu 2 o cestě se vzdáleností 1, nastaví se pro stroj ID10 cestu přes port 2 o vzdálenosti 2. Tuto novou cestu vypropaguje svým sousedním switchům.

Ukončení

Tento algoritmus nemá explicitní ukončovací podmínku. Nicméně pokud budeme přepokládat že se zprávy neztrácí, je zřejmé, že systém po nějaké době zkonverguje do stavu kdy každý switch bude znát minimální cestu na každý stroj.

Ve zkonvergovaném stavu v systému nejsou žádné nezpracované zprávy a žádný uzel není ve stavu kdy se chystá notifikovat souseda o nové lepší cestě.

Implementace

Stroje budou v systému reprezentované pouze svými ID, switche budou reprezentovány třídou, která bude zároveň obsahovat hlavní logiku.

Počet portů by měl být konfigurovatelný.

Demonstrační main by měl vytvořit náhodný svět ve kterém bude rozumný počet různě zapojených switchů, na kterých následně budou zapojené koncové stroje.

Algoritmus by měl být schopen pracovat s postupným zapojováním (při zapojení se na nový spoj odešlou minimální cesty, čímž se opět spustí algoritmus).

Tento týden si ukážeme novinky v oblasti tříd.

Uniformní inicializace:

• https://en.wikipedia.org/wiki/C%2B%2B11#Uniform_initialization

Inicializer Lists:

• https://en.wikipedia.org/wiki/C%2B%2B11#Initializer_lists

Delegace konstruktorů a defaultní hodnoty:

• https://en.wikipedia.org/wiki/C%2B%2B11#Object_construction_improvement

default && delete:

• https://en.wikipedia.org/wiki/C%2B%2B11#Explicitly_defaulted_and_deleted_special_member_functions

override && final:

• https://en.wikipedia.org/wiki/C%2B%2B11#Explicit_overrides_and_final