CourseWare Wiki
Switch Term
Winter 2021 / 2022
Winter 2020 / 2021
Winter 2019 / 2020
Winter 2018 / 2019
Older
Search
Log In
b181
courses
b6b36pjc
ukoly
semestralka
Warning
This page is located in archive. Go to the latest version of this
course pages
.
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
2019/01/04 10:02 havlicr [Odevzdání, termín a hodnocení]
2018/10/18 01:31 jerabma7 Autoupdate to version a4008b690c92
2018/10/18 01:20 jerabma7 Autoupdate to version 96233d8551a3
2018/10/17 23:46 horenmar
2018/09/12 12:44 external edit
Go
Next revision
Previous revision
2019/01/04 10:02 havlicr [Odevzdání, termín a hodnocení]
2018/10/18 01:31 jerabma7 Autoupdate to version a4008b690c92
2018/10/18 01:20 jerabma7 Autoupdate to version 96233d8551a3
2018/10/17 23:46 horenmar
2018/09/12 12:44 external edit
Go
Last revision
Both sides next revision
courses:b6b36pjc:ukoly:semestralka [2018/09/12 12:44]
127.0.0.1
external edit
courses:b6b36pjc:ukoly:semestralka [2018/10/18 01:31]
jerabma7
Autoupdate to version a4008b690c92
Line 4:
Line 4:
===== Semestrální práce =====
===== Semestrální práce =====
-
Protože upload systém nepodporuje vlákna (jedno odevzdání má vždy alokováno pouze jedno jádro) a protože bychom od vás rádi viděli větší, samostatně vyrobený program, tento úkol se odevzdává mailem a my ho budeme bodovat manuálně.
+
Protože upload systém nepodporuje vlákna (jedno odevzdání má vždy
+
alokováno pouze jedno jádro) a protože bychom od vás rádi viděli větší,
+
samostatně vyrobený program, tento úkol se odevzdává mailem a my ho
+
budeme bodovat manuálně.
-
[[https://docs.google.com/spreadsheets/d/e/2PACX-
1vQWsczJha_TecXw4ZC9Yr2Z8emm8W
-
2_xjdgBBdCQd0iLjgyclEUflFdg080RO0yBZTv5DNn8l3uMPV
/pubhtml
?gid=0&single=true
|Přehled studentů a vybraných témat]]
+
[[https://docs.google.com/spreadsheets
/u/1
/d/e/2PACX-
1vRprPo1CvaPw07aOMKrTw3VJ5fNT
-
Ns7udonfXkJ8Lcsl6OjGNR05HjYmuKmmUPvxzssnpu7vXxaeRb
/pubhtml|Přehled studentů a vybraných témat]]
==== Zadání ====
==== Zadání ====
Line 23:
Line 26:
* Program musí být přenositelný napříč architekturami a operačními systémy. Je zakázáno používat rozšíření jazyka podporovaná pouze některými kompilátory. Je zakázáno přímo používat rozhraní WINAPI a POSIX. (Zalinkovat knihovnu `pthread` do programu je povoleno, viz níže.)
* Program musí být přenositelný napříč architekturami a operačními systémy. Je zakázáno používat rozšíření jazyka podporovaná pouze některými kompilátory. Je zakázáno přímo používat rozhraní WINAPI a POSIX. (Zalinkovat knihovnu `pthread` do programu je povoleno, viz níže.)
* Program poskytuje neinteraktivní rozhraní, tj. přebírá vstupy z příkazové řádky, vstupní data ze souboru či ze standardního vstupu
* Program poskytuje neinteraktivní rozhraní, tj. přebírá vstupy z příkazové řádky, vstupní data ze souboru či ze standardního vstupu
-
* Program implementuje přepínač ''--help'' -- vypíše použití a skončí
+
* Program implementuje přepínač ''
%%
--
%%
help'' -- vypíše použití a skončí
* Program neakceptuje neznámé přepínače (vypíše chybu)
* Program neakceptuje neznámé přepínače (vypíše chybu)
==== Odevzdání, termín a hodnocení ====
==== Odevzdání, termín a hodnocení ====
-
Semestrální
práci je nutno odevzdat
cvičícímu
e-mailem
.
Tento
e
-mail
musí obsahovat:
+
Semestrální
práce se odevzdává přes GitLab a email
cvičícímu.
Soubory,
+
které odevzdáváte by měly být všechny na
+
[[https://gitlab.fel.cvut.cz/|fakultním GitLabu]], email pak slouží
+
k notifikaci učitele, ž
e
jste připraveni semestrálku odevzdat, a kterou
+
verzi (commit hash nebo tag) semestrálky odevzdáváte.
+
+
Váš repozitář na GitLabu pak
musí obsahovat:
* zdrojové soubory,
* zdrojové soubory,
-
*
soubory popisující postup stavby programu:
''CMakeLists.txt'',
''Makefile'', nebo projektové soubory IDE (''.vcxproj'', apod.)
+
* ''CMakeLists.txt'',
dle kterého se dá semestrálka postavit
* vzorová vstupní data (pokud je program přijímá)
* vzorová vstupní data (pokud je program přijímá)
-
*
soubor readme (prostý
textový dokument,
markdown, případně slušně vypadající
PDF
), který obsahuje
+
*
Zpráva k vaší semestrálce v souboru Readme
+
* Povolené formáty pro zprávu jsou:
textový dokument,
Markdown nebo rozumné
PDF
* popis vašeho zadání,
* popis vašeho zadání,
* popis vaší implementace,
* popis vaší implementace,
Line 39:
Line 49:
Pokud je potřeba vysvětlit složité součásti návrhu (velká funkce, komplikovaná třída, složitá synchronizace), není nutné psát detaily do readme, raději je pište do komentářů v kódu.
Pokud je potřeba vysvětlit složité součásti návrhu (velká funkce, komplikovaná třída, složitá synchronizace), není nutné psát detaily do readme, raději je pište do komentářů v kódu.
-
**Termín odevzdání je konec 3. zkouškového týdne, neděle
4
. února 2018.**
+
**Termín odevzdání je konec 3. zkouškového týdne, neděle
3
. února 2018.**
Odevzdání je možné i 4. týden zkouškového období, ale již bude aplikována
Odevzdání je možné i 4. týden zkouškového období, ale již bude aplikována
penalizace ve výšce poloviny bodů z možného bodového maxima.
penalizace ve výšce poloviny bodů z možného bodového maxima.
-
Za semestrální práci je možné získat až
30
bodů
, z nichž
je potřeba alespoň
15 k získání zápočtu.
+
Za semestrální práci je možné získat až
20
bodů
. K získání zápočtu
je
-
Za velmi kvalitní práci m
ů
že cvičící přidat i bonusové body nad 30
.
+
potřeba
z ní získat
alespoň
10 bod
ů.
-
==== Příklady zadání ====
+
//Za velmi kvalitní práci
můž
ete získat i bonusové body nad b
ěžných
20
-
Protože občas
můž
e být t
ě
žké vymyslet si vlastní zadání, uvádíme několik mo
žných
příklad
ů.
Pozor na to, že i pokud si vyberete z následujícího seznamu, zadání vám musí schválit cvičící.
+
bod
ů.
//
-
=== Maticové algoritmy ===
-
V závislosti na zvoleném algoritmu či metodě paralelizace můžete (po domluvě) uvažovat vstupní data ve speciálním tvaru (např. pouze čtvercové matice; matice, které mají délku strany mocninu dvou, ...).
-
== Násobení matic ==
-
Násobení matic je jedna z výpočetně nejzajímavějších operací v lineární algebře. Zaprvé protože je velmi časté, zadruhé protože je to operace, která dobře naimplementovaná opravdu může dosáhnout limitu výpočetní rychlosti procesoru (narozdíl třeba od sčítání vektorů, které jsou omezeny rychlostí přístupu do paměti).
-
Očekáváme, že naimplementujete něco sofistikovanějšího než 3 for loopy dle definice maticového násobění.
+
==== Ukázka ====
-
== Výpočet determinantu čtvercové matice ==
+
Připravili jsme pro vás i ukázku zjednodušenné((Takto triviální zadání
-
Determinant lze jednoduše počítat dle definice nebo Laplaceovou expanzí, v praxi tyto algoritmy ale nejsou vhodné kvůli své časové složitosti
.
Efektivní implementace jsou založené
na [[https://
cs
.
wikipedia
.
org
/
wiki
/
Gaussova_eliminační_metoda
|
Gaussově eliminační mětodě
]]
(LU dekompozice). Očekáváme, že váš program bude schopen pracovat s maticemi 1000x1000 v rozumném čase (tj. řádově vteřiny, max. desítky vteřin). Aplikace na vstupu dostane čtvercovou matici, na výstupu vypíše hodnotu jejího determinantu
.
+
bychom nepřijali
.
)) semestrálky. Najdete ji
na
fakultní instanci GitLabu,
+
[[https://
gitlab
.
fel
.
cvut.cz
/
B6B36PJC
/
semestralka-priklad
|
zde
]].
-
== Řešení soustav lin. rovnic ==
+
Odpovídající email by pak vypadal zhruba takto:
-
Další z velmi důležitých úloh lineární algebry. Aplikace na vstupu dostane rozšířenou matici soustavy a na výstup vypíše vektor jejího řešení
,
případně zprávu o tom, že řešení neexistuje. Pokud je řešení nekonečně mnoho, program vypíše jedno partikulární řešení a bázi lineárního prostoru řešení přidružené homogenní soustavy. K implementaci je nejvýhodnější použít [[https://cs.wikipedia.org/wiki/Gaussova_eliminační_metoda|Gaussovu eliminaci]] se zpětným dosazením.
+
<code>
+
Dobrý den
,
-
=== Grafové algoritmy ===
+
odevzdávám semestrálku "Odhad Pí za pomoci Monte Carlo simulace".
+
Kód je na https://gitlab.fel.cvut.cz/horenmar/semestralka-priklad, hash
+
3993960587ec9f54cec7ca0469a2d1b5f9c7ae60.
-
Aplikace načte vstupní graf ze souboru, příp. standardního vstupu v libovolném vámi zvoleném formátu. Doporučujeme použít jednoduchý textový formát, např.
-
<code>
-
<počet-vrcholů> <počet-hran>
-
0 <počet hran z vrcholu 0> <cílový vrchol 1> <délka 1. hrany> <cílový vrchol 2> <délka 2. hrany> ...
-
1 <počet hran z vrcholu 1> <cílový vrchol 1> <délka 1. hrany> <cílový vrchol 2> <délka 2. hrany> ...
...
...
</code>
</code>
-
Pokud
byste si cht
ě
li grafy vizualizovat
,
je mo
ž
né použít nástroj ''dot'' z toolkitu [[http://www.graphviz.org/|Graphviz]] nebo C%%++%% knihovnu [[http://www.ogdf.net|OGDF]]
.
+
Pokud
forknete ukázkový repozitář a nechcete, aby byl váš kód viditelný sv
ě
tu
,
+
nastavte Visibility((Settings -> General -> Permissions)) na Internal. Pokud
+
budete chtít z pokročilejších vlastností gitlabu vyu
ž
ívat merge requesty,
+
bude muset odstranit vztah se zdrojovým repozitářem (Settings -> General ->
+
Advanced -> Remove fork relationship)
.
+
Ukázkový repozitář obsahuje i příklad automatizovaných testů (tzv. Continuous
+
Integration), které můžete (ale nemusíte) využít. Pokud forknete ukázkový
+
repozitář, nemělo by být potřeba nic nastavovat. V případě, že si založíte
+
vlastní projekt, musíte přidat tzv. runner (Settings -> CI/CD -> Runners ->
+
Shared runners -> Enable shared runners).
-
==
Minimální kostra (minimum spanning tree)
==
+
==
=== Rady =====
+
==== Kompilace programů používající vlákna ==
==
-
Minimální kostry mají široké využití - od návrhů tras elektrického vedení
, př
es vytváření routovacích tabulek v počítačových sítích
+
Na některých paltformách (například Linux)
,
je potřeba
př
edat kompilátoru
-
a
ž
po shlukování (clustering) bodů v analýze dat či detekce útvarů v počítačovém vidění
.
+
''-pthread'', abyste mohli pou
ž
ívat vlákna
.
CMake to umí zařídit za vás,
-
Doporu
č
ujeme použít [[https://www.algoritmy.net/article/1396/Boruvkuv-algoritmus|Borůvkův algoritmus]].
+
sta
č
í
př
idat pár řádků kódu do va
š
eho ''CMakeLists
.
txt'':
-
Na výstupu programu bude seznam vrcholů minimální kostry a její cena nebo
př
ímo popis celého grafu pro Graphviz,
+
-
s barevně odli
š
enými vrcholy v kostře
.
+
-
== Nejkratší cesty mezi všemi vrcholy
(
shortest paths
)
==
+
<code cmake>
-
Další z velmi dobře prozkoumaných grafových algoritmů, které mají využití jak ve fyzickém světě, tak ve světě počítačů.
+
set
(
THREADS_PREFER_PTHREAD_FLAG ON
)
-
Na výstupu je seznam dvojic vrcholů s délkou minimální cesty mezi nimi
(
pokud existuje
)
a vypsanou cestou.
+
find_package(Threads REQUIRED)
+
target_link_libraries
(
semestralka Threads::Threads
)
+
</code>
-
== Problém obchodního cestujícího ==
+
Kde ''semestralka'' je název vašeho programu.
-
Problém obchodního cestujícího ([[https://en.wikipedia.org/wiki/Travelling_salesman_problem|Travelling salesman problem]]) spočívá v nalezení nejkratší (nejlevnější) hamiltonovské cesty v orientovaném grafu, tj. takové cesty, která obsahuje každý vrchol právě jednou. Je to NP těžký problém, který se při použití metody větví a mezí dobře paralelizuje. Možný algoritmus je popsaný v [[http://math.feld.cvut.cz/demlova/teaching/lgr/text_lgr_2016.pdf|materiálech]] k předmětu Logika a grafy v sekci Hledání nejkratší hamiltonovské cesty.
-
Na výstupu bude posloupnost vrcholů cesty a její cena nebo přímo popis celého grafu pro Graphviz, s barevně zvýrazněnými hranami v cestě.
+
==== Generátor náhodných čísel ====
+
Pokud potřebujete generátor náhodných čísel a jeho rychlost není až tak
+
důležitá, doporučujeme [[https://en.wikipedia.org/wiki/Mersenne_Twister|Mersenne Twister]]
+
[[http://en.cppreference.com/w/cpp/numeric/random|ze standardní knihovny]].
+
Minimální příklad použití pro získání double v rozsahu (-1000, 1000):
+
<code cpp>
+
double get_random_double() {
+
static std::mt19937 mt{ std::random_device{}() };
+
static std::uniform_real_distribution<> dist(-1000, 1000);
+
return dist(mt);
+
}
+
</code>
-
=== k-means (clustering) ===
+
Pokud
je
rychlost velmi d
ů
le
ž
itá
,
budete muset použít něco rychlejšího, nap
ř
íklad
[[
http
://
en
.
cppreference
.
com
/
w
/
cpp/numeric/random
|
std::minstd_rand
]].
-
[[https://cs.wikipedia.org/wiki/K-means|K-means]]
je
jednoduchý iterativní algoritmus pro shlukování množiny bod
ů
do //k// skupin (kde //k// je známé předem) s jednoduchou paralelizací. Vstupem je mno
ž
ina bodů (standardní vstup nebo soubor) a počet skupin (parametr na příkazové řádce)
,
na výstupu vrací seznam bodů a jejich p
ř
íslušnost do skupiny. Výsledek je vhodné vizualizovat výstupem do obrázku
[[
https
://
cs
.
wikipedia
.
org
/
wiki
/
Scalable_Vector_Graphics
|
SVG
]]
. Pro snadnou vizualizaci doporučujeme pracovat ve 2D
.
+
-
===
Výpo
č
etní geometrie (computational geometry)
===
+
===
= Měření uběhnutého
č
asu
===
=
+
Součástí zadání je porovnat čas běhu vašeho algoritmu využívajícího více vláken, s časem běhu jednoduchého algoritmu, který vlákna nepoužívá. K tomu vám poslouží hlavička ''<chrono>'', která se používá takto:
+
<code cpp>
+
template <typename TimePoint>
+
std::chrono::milliseconds to_ms(TimePoint tp) {
+
return std::chrono::duration_cast<std::chrono::milliseconds>(tp);
+
}
-
Úlohy z oblasti výpočetní geometrie se zabývají geometrickými výpočty v rovině a prostoru. Protože náročnost soudobých grafických aplikací stále stoupá, jsou známy dobře paralelizovatelné algoritmy.
-
=
= Konvexní obal množiny bodů v rovině
(
convex hull
) =
=
+
int main() {
+
auto start
=
std::chrono::high_resolution_clock::now
()
;
+
// do work
+
auto end
=
std::chrono::high_resolution_clock::now();
+
std::cout << "Needed " << to_ms(end - start).count() << " ms to finish.\n";
+
}
+
</code>
-
Konvexní obal ([[https://en.wikipedia.org/wiki/Convex_hull|convex hull]]) množiny bodů si lze jednoduše představit jako nejmenší konvexní mnohoúhelník, uvnitř kterého leží všechny body množiny. Jako konkrétní algoritmus je možné zvolit třeba [[https://en.wikipedia.org/wiki/Quickhull|Quickhull]].
+
==== Checklist
pro
odevzdání ====
-
Vstupem
pro
aplikaci bude textový soubor se souřadnicemi bodů, výstupem pak bude seznam vrcholů konvexního obalu. Doporučujeme si napsat jednoduchý generátor vstupních dat a program či skript pro převod vstupních a výstupních dat do obrázku [[https://cs.wikipedia.org/wiki/Scalable_Vector_Graphics|SVG]] pro snadnou vizualizaci a ověření správnosti řešení.
+
-
=== Kombinatorické problémy ===
+
Proto
ž
e
se
některé chyby
př
i odevzdávání semestrálních prací
č
asto
-
== Knapsack Problem solver ==
+
opakují
,
připravili jsme pro vás checklist, kde si m
ů
žete zkontrolovat,
-
[[https://en.wikipedia.org/wiki/Knapsack_problem|Knapsack problem]] (té
ž
známý jako [[https://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu|problém batohu]]) je NP-těžký problém z kombinatorické optimalizace, který
se
ale dá
př
ekvapivě dobře paralelizovat. Vstupní data doporu
č
ujeme generovat o požadované velikosti
,
aby bylo možné vyzkoušet různé velikosti problém
ů.
+
jestli jste před odevzdáním na něco nezapomněli
.
-
Nezapomeňte
, ž
e výstupem by
mě
la být nejenom optimální hodnota batohu
,
ale
i
jeho optimální slož
ení
.
+
<code>
+
* Kód
+
* Obsahuje váš kód CMakeLists.txt přes který se vaše semestrálka dá postavit?
+
* Používá váš kód více vláken když má k dispozici více jader?
+
* Obsahuje váš kód implementaci optimalizovanou pro jedno vlákno?
+
* Nepoužívá váš kód rozšíření jazyka? (Například OpenMP
,
VLA)
+
* Nepou
ž
ívá váš kód nepřenosné knihovny (Například POSIX, Win32)
+
* Měření
+
* Proběhlo
mě
ření nad optimalizovaným programem? (Byla binárka zkompilována v "Release" módu?)
+
* Vyšel běh využívající více vláken rychlejší?
+
* Vyšel běh využívající více vláken stejně jako běh v jednom vlákně?
+
* Zpráva
+
* Obsahuje vaše zpráva hash commitu (nebo tag)
,
vůč
i
kterému byla napsaná?
+
* Obsahuje vaše zpráva popis zadání?
+
* Obsahuje vaše zpráva popis naměřených výsledků?
+
* Obsahuje vaše zpráva popis prostředí, ve kterém jste prováděli měř
ení
?
+
</code>
-
===
Word Count souborů
===
+
===
= Šuplíkové zadání =
===
-
Typický problém s jednoduchou paralelizací. Na vstupu je sada soubor
ů,
na výstupu je se
ř
azený výpis obsa
ž
ených slov a jejich
č
etnost
.
+
Protože občas m
ů
že být těžké vymyslet si vlastní zadání
,
uvádíme několik
+
možných p
ř
íkladů. Pozor na to,
ž
e i pokud si vyberete z následujícího
+
seznamu, zadání vám musí schválit cvi
č
ící
.
-
Krom slov se dají po
č
ítat
i
tzv
.
[[https://en
.
wikipedia
.
org/wiki/N-gram|n-gramy]]
.
+
=== Maticové algoritmy ===
+
V závislosti na zvoleném algoritmu
či
metodě paralelizace můžete
+
(po domluvě) uvažovat vstupní data ve speciálním tvaru (např. pouze
+
čtvercové matice; matice, které mají délku strany mocninu dvou,
...
)
.
+
== Násobení matic ==
+
Násobení matic je jedna z výpočetně nejzajímavějších operací v lineární
+
algebře. Zaprvé protože je velmi časté, zadruhé protože je to operace,
+
která dobře naimplementovaná opravdu může dosáhnout limitu výpočetní
+
rychlosti procesoru (narozdíl třeba od sčítání vektorů, které jsou
+
omezeny rychlostí přístupu do paměti).
-
=== Autocorrect ===
+
O
č
ekáváme,
ž
e naimplementujete
něco
sofistikovan
ě
j
š
ího ne
ž
3 for loopy
-
Další
č
astý problém. U
ž
ivatel
něco
napíše a my chceme v
ě
dět, jestli to opravdu napsat chtěl, nebo jestli se přehmátl na klávesnici. Samozřejmě, bez technologie pro čtení my
š
lenek to perfektně nejde, ale mů
ž
eme porovnat napsané slovo se slovníkem, a pokud v něm není, zkusit najít n
ě
jaké [[https://en.wikipedia.org/wiki/Levenshtein_distance|blízké]] slovo
.
+
dle definice maticového násob
ě
ní
.
-
Na vstupu je slovník a slovo,
nebo
celá sada slov. Na výstupu je buďto samotné slovo
,
nebo mno
ž
ina nejbli
ž
ších, a tudíž pravd
ě
podobn
ě
zamýšlených slov
.
Slovník mů
ž
ete mít uložený
v
arbitrárním formátu
.
+
== Výpočet determinantu čtvercové matice ==
+
Determinant lze jednoduše počítat dle definice
nebo
Laplaceovou expanzí
,
+
v praxi tyto algoritmy ale nejsou vhodné kvůli své časové slo
ž
itosti.
+
Efektivní implementace jsou zalo
ž
ené na
+
[[https://cs.wikipedia.org/wiki/Gaussova_eliminační_metoda|Gaussov
ě
eliminační m
ě
todě]]
+
(LU dekompozice)
.
Očekáváme,
ž
e váš program bude schopen pracovat
+
s maticemi 1000x1000
v
rozumném čase (tj. řádově vteřiny, max. desítky
+
vteřin). Aplikace na vstupu dostane čtvercovou matici, na výstupu vypíše
+
hodnotu jejího determinantu
.
+
== Řešení soustav lin. rovnic ==
+
Další z velmi důležitých úloh lineární algebry. Aplikace na vstupu
+
dostane rozšířenou matici soustavy a na výstup vypíše vektor jejího
+
řešení, případně zprávu o tom, že řešení neexistuje. Pokud je řešení
+
nekonečně mnoho, program vypíše jedno partikulární řešení a bázi
+
lineárního prostoru řešení přidružené homogenní soustavy. K implementaci
+
je nejvýhodnější použít
+
[[https://cs.wikipedia.org/wiki/Gaussova_eliminační_metoda|Gaussovu eliminaci]]
+
se zpětným dosazením.
-
===
= Příklad průvodního Readme =
===
+
===
Grafové algoritmy
===
+
+
Aplikace načte vstupní graf ze souboru, příp. standardního vstupu
+
v libovolném vámi zvoleném formátu. Doporučujeme použít jednoduchý
+
textový formát, např.
<code>
<code>
-
# π
-
estimator
+
<počet
-
vrcholů> <počet-hran>
+
0 <počet hran z vrcholu 0> <cílový vrchol 1> <délka 1. hrany> <cílový vrchol 2> <délka 2. hrany> ...
+
1 <počet hran z vrcholu 1> <cílový vrchol 1> <délka 1. hrany> <cílový vrchol 2> <délka 2. hrany> ...
+
...
+
</code>
-
π-estimator
je
program pro aproximaci π za pomocí Monte Carlo simulace. V jedné iteraci je vygenerován náhodný bod
z [
0, 1]x
[
0, 1] a zjistí se, jestli vygenerovaný bod spadá do jednotkového kruhu
.
Po vygenerování N bodů se dá spočítat π jako 4 * <množství bodů uvnitř kruhu>
/
N
.
+
Pokud byste si chtěli grafy vizualizovat,
je
možné použít nástroj ''dot''
+
z
toolkitu
[[
http://www
.
graphviz.org
/
|Graphviz]] nebo C%%++%% knihovnu
+
[[http://www.ogdf.net|OGDF]]
.
-
## Implementace
-
Implementace pro jedno vlákno je triviální, vícevláknová implementace pak vydělí množství iterací množstvím spuštěných vláken a nechá každé vlákno provést implementaci pro jedno vlákno. Množství vláken je určeno dle množství jader počítače, jejich synchronizace je triviální, přes atomickou proměnnou.
-
Množství iterací je předáno jako druhý argument. Pokud druhý argument není předán, pak je použita defaultní hodnota 10M iterací.
+
== Minimální kostra (minimum spanning tree) ==
-
## Mě
ření
+
Minimální kostry mají široké využití - od návrhů tras elektrického
-
M
ě
řil jsem na 4 jádrovém i5-6600K CPU taktovaném na 3
.
5 GHz s vypnutým HT. Výsledekem bylo,
ž
e jsem namě
ř
il 458ms
pro
jednovláknovou variantu a 116ms pro 4-vláknovou variantu
,
do
š
lo tedy ke zhruba 4x zrychlení
.
+
vedení, přes vytvá
ření
routovacích tabulek v počítačových sítích
+
až po shlukování (clustering) bodů v analýze dat či detekce útvarů
+
v počítačovém vid
ě
ní
.
Doporučujeme pou
ž
ít
+
[[https://www.algoritmy.net/article/1396/Boruvkuv-algoritmus|Borůvkův algoritmus]].
+
Na výstupu programu bude seznam vrcholů minimální kostry a její cena
+
nebo p
ř
ímo popis celého grafu
pro
Graphviz
,
s barevně odli
š
enými vrcholy
+
v kostře
.
-
Výstup
z
mě
ř
ení
+
== Nejkratší cesty mezi všemi vrcholy (shortest paths) ==
-
```
+
Další
z
velmi dob
ř
e prozkoumaných grafových algoritmů, které mají využití
-
ST inside points: 7853087
+
jak ve fyzickém světě, tak ve světě počítačů
.
Na výstupu je seznam dvojic
-
MT inside points: 7853934
+
vrcholů s délkou minimální cesty mezi nimi (pokud existuje) a vypsanou
-
PI value: 3
.
14159
+
cestou
.
-
ST PI time needed: 458ms value: 3.14123
+
-
MT PI time needed: 116ms value: 3
.
14157
+
-
```
+
-
</code>
+
+
== Problém obchodního cestujícího ==
-
{{
:
courses
:
b6b36pjc:ukoly:semestralka-priklad
.
zip
|
P
ř
íklad odevzdaného kódu}}
+
Problém obchodního cestujícího
+
([[https
:
//en.wikipedia.org/wiki/Travelling_salesman_problem|Travelling salesman problem]])
+
spočívá v nalezení nejkratší (nejlevnější) hamiltonovské cesty
+
v orientovaném grafu, tj. takové cesty, která obsahuje každý vrchol právě
+
jednou. Je to NP těžký problém, který se při použití metody větví a mezí
+
dobře paralelizuje. Možný algoritmus je popsaný v
+
[[http
:
//math
.
feld.cvut.cz/demlova/teaching/lgr/text_lgr_2016.pdf
|
materiálech]]
+
k p
ř
edmětu Logika a grafy v sekci Hledání nejkratší hamiltonovské cesty.
+
Na výstupu bude posloupnost vrcholů cesty a její cena nebo přímo popis
+
celého grafu pro Graphviz, s barevně zvýrazněnými hranami v cestě.
-
//
Pozor, ukázka v
př
íloze
je
těsně na úrovni zápo
č
tu
,
ne-li pod ní
.//
+
=== k-means (clustering) ===
+
[[https:
//
cs.wikipedia.org/wiki/K-means|K-means]] je jednoduchý iterativní
+
algoritmus pro shlukování množiny bodů do //k// skupin (kde //k//
+
je známé
př
edem) s jednoduchou paralelizací. Vstupem
je
množina bodů
+
(standardní vstup nebo soubor) a po
č
et skupin (parametr na příkazové
+
řádce)
,
na výstupu vrací seznam bodů a jejich příslušnost do skupiny
.
+
Výsledek je vhodné vizualizovat výstupem do obrázku
+
[[https:
//
cs.wikipedia.org/wiki/Scalable_Vector_Graphics|SVG]]. Pro
+
snadnou vizualizaci doporučujeme pracovat ve 2D.
-
=====
Rady
=
====
+
===
Výpočetní geometrie (computational geometry)
===
-
==== Kompilace programů používající vlákna na Linuxu ====
+
-
Pokud pracujete na Linuxu a vidíte chybu s textem podobným ''undefined reference to `pthread_create''', váš program nepůjde zlinkovat, pokud kompilátoru nepředáte ''-pthread'', třeba takto:
+
-
<code>
+
Úlohy z oblasti výpočetní geometrie se zabývají geometrickými výpočty v
-
clang++ -std=c++14 -g -Wall -Wextra -pthread main
.
cpp
+
rovině a prostoru
.
Protože náročnost soudobých grafických aplikací stále
-
</code>
+
stoupá, jsou známy dobře paralelizovatelné algoritmy.
-
==
== Kompilace programů pou
ž
ívající vlákna v CLion IDE ====
+
==
Konvexní obal mno
ž
iny bod
ů v
rovin
ě (
convex hull
) =
=
-
Clion používá ''CMake'' a ''CMakeLists.txt'' pro kontrolu kompilace. Jako kompilátor ale používá buďto ''%%g++%%'' nebo ''Clang'', a tudíž je mu též potřeba říct, aby linkoval vlákna. Nejjednodušší zp
ů
sob je
v
''CMakeLists.txt'' zm
ě
nit ''set
(
CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++14"
)
'' na ''set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std
=
c++14 -pthread")''.
+
-
==== Generátor náhodných čísel ====
+
Konvexní obal (
[[https://en.wikipedia.org/wiki/
Convex_hull
|
convex hull
]]
)
-
Pokud potřebujete generátor náhodných čísel a jeho rychlost není až tak důležitá, doporučujeme
[[https://en.wikipedia.org/wiki/
Mersenne_Twister
|
Mersenne Twister
]] [[
http
://en.
cppreference
.
com
/
w
/
cpp/numeric/random
|
ze standardní knihovny
]].
+
množiny bodů si lze jednoduše představit jako nejmenší konvexní
-
Minimální p
ř
íklad použití pro získání double v rozsahu (-1000
,
1000):
+
mnohoúhelník, uvnitř kterého leží všechny body množiny. Jako konkrétní
-
<code cpp>
+
algoritmus je možné zvolit třeba
-
double get_random_double() {
+
[[
https
://en.
wikipedia
.
org
/
wiki
/
Quickhull
|
Quickhull
]].
Vstupem pro
-
static std::mt19937 mt{ std::random_device{}() };
+
aplikaci bude textový soubor se sou
ř
adnicemi bodů
,
výstupem pak bude
-
static std
:
:uniform_real_distribution<> dist(-1000, 1000);
+
seznam vrcholů konvexního obalu. Doporučujeme si napsat jednoduchý
-
return dist(mt);
+
generátor vstupních dat a program či skript pro převod vstupních
-
}
+
a výstupních dat do obrázku
-
<
/
code>
+
[[https
:/
/cs.wikipedia.org/wiki/Scalable_Vector_Graphics|SVG]] pro
+
snadnou vizualizaci a ověření správnosti řešení.
-
Pokud je rychlost velmi důležitá, budete muset použít něco rychlejšího, například
[[
http
://en.
cppreference
.
com
/
w
/
cpp
/
numeric
/
random
|
std::minstd_rand
]].
+
=== Kombinatorické problémy ===
+
== Knapsack Problem solver ==
+
[[
https
://en.
wikipedia
.
org
/
wiki
/
Knapsack_problem|Knapsack problem]]
+
(též známý jako
+
[[https:
//
cs.wikipedia.org/wiki/Probl%C3%A9m_batohu
|
problém batohu
]]
)
+
je NP-těžký problém z kombinatorické optimalizace, který se ale dá
+
překvapivě dobře paralelizovat. Vstupní data doporučujeme generovat
+
o požadované velikosti, aby bylo možné vyzkoušet různé velikosti problémů
.
-
==== Měření uběhnutého času ====
+
Nezapomeňte,
ž
e výstupem by m
ě
la být nejenom optimální hodnota batohu
,
-
Součástí zadání je porovnat čas běhu vašeho algoritmu vyu
ž
ívajícího více vláken, s časem b
ě
hu jednoduchého algoritmu
,
který vlákna nepou
ž
ívá
.
K tomu vám poslouží hlavička ''<chrono>'', která se používá takto:
+
ale i jeho optimální slo
ž
ení
.
-
<code cpp>
+
-
template <typename TimePoint>
+
-
std::chrono::milliseconds to_ms(TimePoint tp) {
+
-
return std::chrono::duration_cast<std::chrono::milliseconds>(tp);
+
-
}
+
-
int main() {
+
=
== Word Count souborů ===
-
auto start
=
std::chrono::high_resolution_clock::now();
+
Typický problém s jednoduchou paralelizací. Na vstupu je sada souborů,
-
//
do work
+
na výstupu je seřazený výpis obsažených slov a jejich četnost.
-
auto end
=
std::chrono::high_resolution_clock::now();
+
-
std::cout << "Needed " << to_ms(end - start)
.
count() << " ms
to
finish
.
\n";
+
Krom slov se dají počítat i tzv.
-
}
+
[[https:
//
en.wikipedia.org/wiki/N-gram|n-gramy]].
-
<
/
code>
+
+
+
=
== Autocorrect ===
+
Další častý problém
.
Uživatel něco napíše a my chceme vědět, jestli
to
+
opravdu napsat chtěl, nebo jestli se přehmátl na klávesnici
.
Samozřejmě,
+
bez technologie pro čtení myšlenek to perfektně nejde, ale můžeme
+
porovnat napsané slovo se slovníkem, a pokud v něm není, zkusit najít
+
nějaké [[https:
/
/en.wikipedia.org/wiki/Levenshtein_distance|blízké]]
+
slovo.
+
+
Na vstupu je slovník a slovo, nebo celá sada slov. Na výstupu je buďto
+
samotné slovo, nebo množina nejbližších, a tudíž pravděpodobně zamýšlených
+
slov. Slovník můžete mít uložený v libovolném formátu.
courses/b6b36pjc/ukoly/semestralka.txt
· Last modified: 2019/01/04 10:02 by
havlicr