Stránka archivována
(Algoritmy 1, 2023/2024, ZS)

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 2023/2024 vedu tato cvičení:

• Pondělí 15:00 - 16:30 STAG
• Pondělí 16:45 - 18:15 STAG
• Úterý 16:45 - 18:15 STAG

V případě jakýchkoliv dotazů ke cvičením nebo jejich obsahu mě neváhejte kontaktovat (kontakty zde).

Zápočtové podmínky

• První podmínkou na zápočet je získat alespoň 60% bodů ze zadaných úkolů (1 písemný test v druhé polovině semestru, 1 implementace algoritmů).
• Druhou podmínkou je aktivní docházka na alespoň 75% cvičení.

Zápočtový úkol

• Zá úkol lze získat maximálně 10 bodů.
• Zadání úkolu bylo zveřejněno zde 15.11.2023 okolo 17:00 CET.
• Termín odevzdání: 15.12.2023, 23:59 CET
• Za každou započatou hodinu zpoždění je penalizace 2 body.
• Odevzdávejte emailem na tomas.urbanec@upol.cz s předmětem ALGO1-zápočet
• Předmět emailu dodržujte pro autoamtické zpracování a potvrzení doručení emailu.

Zadání

1. V jazyce C implementujte funkce:

   • int insertion_sort_with_counting(int pole[], int velikost, int poradi),
   • int quick_sort_with_counting(int pole[], int velikost, int poradi),
   • int merge_sort_with_counting(int pole[], int velikost, int poradi),

   které setřídí dodané pole odpovídajícím algoritmem a přitom spočítají, kolik porovnání dvou prvků z pole algoritmus provedl - výslednou hodnotu funkce vrátí volajícímu. První argument pole je pole k setřídění, druhý argument velikost obsahuje počet prvků v poli pole a třetí argument poradi určuje, jak má být pole setřízeno - je-li poradi záporné číslo, tak sestupně, v jiném případě vzestupně.

   Za pomocí těchto funkcí poté napište malý program, který desetkrát provede následující:

   • Vygeneruje náhodné pole s 10 000 prvky;
   • Setřídí jej každou z dodaných funkcí vzestupně;
   • Na standardní výstup vypíše informaci o tom, kolik porovnání mezi prvky z pole každá z funkcí provedla;
   • Pozor, každá z funkcí musí mít v dané iteraci stejné výchozí pole (tj. stejné prvky ve stejném pořadí), aby výsledky mělo smysl porovnávat.

   (7 bodů)

2. Nalezněte a dokažte alespoň pět asymptotických vztahů mezi těmito funkcemi (vztahy k dokázaní si vyberte sami; vztah funkce k sobě samé se nepočítá):
   log(log(n)), n!, n²⁵, n^5/2, 25ⁿ, nⁿ

   (3 body)

Zápočtová písemka

• Zá písmeku lze získat maximálně 10 bodů.
• Písmeka bude na cvičení 27.11. a 28.11.2023. Opravná písemka bude 11.12. a 12.12.2023.
• Více informací k obsahu písemky bude sděleno na cvičení týden před písemkou.

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í

Obsah a odkazy budou doplnovány během semestru.

1. Cvičení 18. a 19.9.2023
2. Cvičení 25. a 26.9.2023
3. Cvičení 2. a 3.10.2023
4. Cvičení 9. a 10.10.2023
5. Cvičení 16. a 17.10.2023
6. Cvičení 23.10.2023 odpadá kvůli odpadlé přednášce a cvičení 24.10.2023 kvůli uzavřené budově. Nahradíme je v zápočtovém týdnu.
7. Cvičení 30. a 31.10.2023
8. Cvičení 6. a 7.11.2023
9. Cvičení 13. a 14.11.2023
10. Cvičení 20.11.2023
    • Cvičení 21.11.2023 odpadá kvůli děkanskému volnu.
11. Cvičení 27. a 28.11.2023
12. Cvičení 4. a 5.12.2023
13. Cvičení 11. a 12.12.2023