Archivovaná stránka (Algoritmy 1, 2021/2022)
Základní informace
Zdroje:
- Stránky předmětu ve STAGu.
- Slidy z přednášek a další zdroje na stránkách přednášejícího.
V akademickém roce 2021/2022 vedu tato cvičení:
V případě jakýchkoliv dotazů ke cvičením nebo jejich obsahu mě neváhejte kontaktovat (kontakty zde).
Zápočtové podmínky
Pro získání zápočtu musí student získat alespoň 60% bodů ze zadaných úkolů (1 písemný test v druhé polovině semestru, 1 implementace algoritmů).
Zápočtový úkol
Implementujte v jazyce C algoritmy Insertion-sort, Quick-sort a Heap-sort a vypište následující vyplněné tabulky pro pole náhodných hodnot (v rozsahu 0 až 1000) o velikosti 10, 100, 1000 a 10000 prvků:
1, Počet provedených porovnání prvků v poli
| počet porovnání | 10 | 100 | 1000 | 10000 |
|---|---|---|---|---|
| Insertion-sort | ||||
| Quick-sort | ||||
| Heap-sort |
2, Počet provedených přesunů prvků v poli
| počet přesunů | 10 | 100 | 1000 | 10000 |
|---|---|---|---|---|
| Insertion-sort | ||||
| Quick-sort | ||||
| Heap-sort |
Upřesnění
- Tyto tabulky program vypíše na výstup a poté skončí. Není nutné řešit přesné formátování, stačí když bude zřejmé, co kam patří.
- Pro generování náhodných polí můžete využít kód ze šablony dodané na cvičení.
- Z principu implementovaných algoritmů nás zajímá hlavně porovnávání dat (prvků v poli). Do tabulky tedy počítejte pouze porovnávání mezi prvky pole. Tj. nepočítejte například porovnávání v hlavičce for cyklů atp.
- Podobně nás zajímá pouze, kdy se nějaký prvek z pole přesune jinam v poli.
Odevzdávání
- Mezní termín pro odevzdání je 14.12.2020.
- Úkoly odevzdávejte emailem.
- Do předmětu uveďte “algoritmy-prijmeni-jmeno” a do přílohy dejte jeden soubor “prijmeni.c” s kódem (používáte-li hlavičkový soubor pro deklarace, tak přidejte i ten s názvem prijmeni.h).
- Úkoly vypracujte samostatně (vizte studijní řád a poznámky níže).
Bodování
- Za každý algoritmus lze získat 3 body (1 bod funkční implementace, 1 bod správné počítání porovnávání, 1 bod správné počítání přesunů).
- Jeden bod je za celkovou funkčnost programu (výpisy, generování polí, …).
- Celkem tedy maximálně 10 bodů.
Zápočtová písemka
- Písemka bude 30.11.2021.
- Lze získat maximálně 10 bodů.
- Opravná písemka bude 14.12.2021.
- Na písemce budou úkoly podobné těm, co jsme dělali na cvičení (návrhy algoritmů pro zadaný problém, počítání složitosti, asymptotické meze, psaní pseudokódu, provádění algoritmu zadaného pseudokódem a určení jeho funkcionality, …).
Plagiátorství
Z webu katedry:
“Pokud se student dopustí plagiátorství, opisování při písemném testu, opisování při práci na domácím úkolu nebo se jiným způsobem pokusí o podvod, zahájí s ním vedoucí katedry kárné řízení. Pokud se takové jednání studenta opakuje, vedoucí katedry navrhne děkanovi fakulty vyloučit studenta ze studia.”
Všechny úkoly budou mimo automatických testů kontrolovány i vyučujícím a MOSSem. Pokud bude odhalena příliš velká shoda, budou všichni studenti, kterých se to týká, nahlášeni vedení katedry.
Seznam cvičení
- Cvičení 21.9.2021
- Cvičení 28.9.2021. Státní svátek, cvičení se nekonalo.
- Cvičení 5.10.2021
- Cvičení 12.10.2021
- Cvičení 19.10.2021
- Cvičení 26.10.2021
- Cvičení 2.11.2021
- Cvičení 9.11.2021
- Cvičení 16.11.2021
- Cvičení 23.11.2021
- Cvičení 30.11.2021
- Cvičení 7.12.2021