Algoritmy 1

(2024/2025, 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 2024/2025 vedu cvičení

• Pondělí 17:30 - 19:00 STAG
• Úterý 18:30 - 20:00 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 zápočtový úkol).
• Druhou podmínkou je aktivní docházka na alespoň 75% cvičení.

Zápočtová písemka

• Zá písmeku lze získat maximálně 10 bodů.
• Písmeka bude na cvičení 2. a 3.12.2024. Opravná písemka bude v zápočtovém týdnu.
• Více informací k obsahu písemky bude sděleno na cvičení týden před písemkou.
• Výsledky písemek

Zápočtový úkol

• Zá úkol lze získat maximálně 10 bodů.
• Zadání úkolu bylo zveřejněno zde 20.11.2024.
• Termín odevzdání: 18.12.2024, 23:59 CET
• Za každou započatou hodinu zpoždění je penalizace 2 body.
• Studenti mých skuppin
  • Odevzdávejte emailem na tomas.urbanec@upol.cz s předmětem ALGO1-zápočet
  • Předmět emailu dodržujte pro automatické zpracování a potvrzení doručení emailu.
  • Výsledky úkolů
• Studneti skupiny kolegyně Olejkové
  • Odevzdávejte dle domluvy s kolegyní Olejkovou.

Zadání

1. V jazyce C nebo Pythonu implementujte funkce s hlavičkami:

   • pro C:
     • int insertion_sort_with_counting(int pole[], int velikost, int poradi),
     • int merge_sort_with_counting(int pole[], int velikost, int poradi),
     • int merge_insertion_sort_with_counting(int pole[], int velikost, int poradi, int mezni_velikost),
   • pro Python:
     • insertion_sort_with_counting(pole, poradi),
     • merge_sort_with_counting(pole, poradi),
     • merge_insertion_sort_with_counting(pole, poradi, mezni_velikost),
   • DODATEČNÉ INFORMACE: u insert sortu v C nemusí na počet porovnání stačit typ int, klidně jako návratovou hodnotu u procedur v C použijte long long.

   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. Třetí funkce (merge_insertion_sort_with_counting) implementuje myšlenku kombinování merge a insertion sortu popsanou na slidu 86 z druhé části prezentací prof. Bělohlávka (tj. slidy z přednášek).

   Význam a typ argumentů:

   • pole je pole celých čísel k setřídění (v Pythonu seznam),
   • velikost je přirozené číslo vyjadřující počet prvků v poli pole (v Pythonu nepotřebujeme)
   • poradi určuje, jak má být pole setřízeno,
     • je-li poradi záporné číslo, tak sestupně,
     • v jiném případě vzestupně.
   • mezni_velikost u kombinace merge a insertion sortu je maximální velikost pole (přirozené číslo), pro kterou se použije insertion sort.
   • Poznámka: přirozená i celá čísla stačí uvažovat z rozsahu typu integer.

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

   • Vygeneruje náhodné pole s 100 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.
   • Pro kombinaci merge a insertion sortu zkuste nalézt optimální nastavení pro mezni_velikost.
   • Pozor, každá z funkcí musí mít 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^1/4, 4ⁿ, nⁿ

   (3 body)

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 doplňovány během semestru.

1. Cvičení 23. a 24,9.2024
   • opakování ze střední školy
2. Cvičení 30.9. a 1.10.2024
   • problém, algoritmus, pseudokód
3. Cvičení 7. a 8.10.2024
   • složitost algoritmu
   • implementace algoritmu v jazyce C/Pythonu
4. Cvičení 14. a 15.10.2024
   • Selection sort
5. Cvičení 21. a 22.10.2024
   • Asymptotické meze
   • Insertion sort
6. Cvičení 29.10.2024 a 4.11.2024
   • 28.10.2024 - Den vzniku samostatného československého státu
   • Asymptotické meze podruhé
   • Bubble sort
7. Cvičení 5. a 11.11.2024
   • Rekurze a rekurence
   • Quick sort
8. Cvičení 12. a 18.11.2024
   • Merge sort
9. Cvičení 19. a 25.11.2024
   • Heap sort
10. Cvičení 26.11.
    • Counting sort
11. Cvičení 2. a 3.12.2024
    • Písemka
12. Cvičení 9. a 10.12.2024
    • Pořádkové statistiky
    • Master teorém
    • Zpětná vazba
13. Cvičení 16. a 17.12.2024
    • Opravné písemky
    • Konzultace