Stránka archivována (Algoritmy 1 - 2022/2023 ZS)

Základní informace

Zdroje:

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

Zápočtový úkol

Zadání 1 (více teorie)

  1. Dokažte, že O(f(n)+g(n)) = O(max(f(n),g(n))) pro f, g : ℕ → ℕ. (2 body)

  2. Navrhněte a v pseudokódu zapište dva různé algoritmy pro výpočet hodnoty výrazu n(nn), kde n ∈ ℕ.

    • První nevyužívající pomocných funkcí ani rekurze.
    • Druhý, který pro výpočet nk (k ∈ ℕ) používá pomocnou rekurzivní funkci - tu rovněž navrhněte a zapište pseudokódem. U obou algoritmů určete složitost a její co nejlepší asymptotický odhad (i s postupem). (5 bodů)

  3. V jazyce C nebo Python proveďte následující:

    • Ve funkci

      • sort_1(pole) pro Python
      • nebo int sort_1(int pole[], int velikost) pro C

      implementujte 1 z algoritmů:

      • bubble sort,
      • selection sort,
      • insertion sort.

      Třiďte vzestupně.

    • Ve funkci

      • sort_2(pole) pro Python
      • nebo int sort_2(int pole[], int velikost) pro C

      implementujte 1 z algoritmů:

      • quick sort,
      • merge sort,
      • heap sort.

      Třiďte vzestupně.

    • Argument pole je pole k setřízení. V C je navíc i argument velikost obsahující počet prvků v poli pole.

    • Za pomocí těchto funkcí poté napište malý program, který vygeneruje náhodné pole s 1000 prvků. To následně setřídí každou z dodaných funkcí a přitom změří čas běhu pro každou funkci.

    • Měření času v C:

    	#include <time.h>
	int main(){
		clock_t start, end;
		double cpu_time_used;
		start = clock();

		// kód k změření
		printf("Jak dlouho běžím?");

		end = clock();
		cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

		// výpis naměřeného času
		printf("%f", cpu_time_used); 
	}
    • Měření času v Pythonu:
    	import time
	t = time.process_time()

	#kód k změření
	print("jak dlouho běžím?")

	elapsed_time = time.process_time() - t

	# výpis naměřeného času
	print(elapsed_time)

    (3 body)

Zadání 2 (více programvání)

  1. V jazyce C nebo Python implementujte funkce:

    • int insertion_sort_with_counting(int pole[], int velikost, int poradi) pro C; insertion_sort_with_counting(pole, poradi) pro Python ,
    • int quick_sort_with_counting(int pole[], int velikost, int poradi) pro C; quick_sort_with_counting(pole, poradi) pro Python,
    • int merge_sort_with_counting(int pole[], int velikost, int poradi) pro C; merge_sort_with_counting(pole, poradi) pro Python,

    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.

    • Argument pole je pole k setřízení,
    • Argument poradi určuje, jak má být pole setřízeno - je-li poradi záporné číslo, třiďte sestupně, v jiném případě třiďte vzestupně.
    • V C je navíc i argument velikost obsahující počet prvků v poli pole.

    Za pomocí těchto funkcí poté napište malý program, který vygeneruje náhodné pole s 1000 prvků. To následně setřídí každou z dodaných funkcí vzestupně a na standardní výstup vypíše informaci o tom, kolik porovnání mezi prvky z pole každá z funkcí provedla.

    (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!,
    • n3/2,
    • 10n,
    • nn.

    (3 body)

Zápočtová písemka

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í

  1. Cvičení 20. a 26.9.2022
    • Cvičení 19.9.2022 neproběhlo kvůli přednášce o úvodu do studia.
  2. Cvičení 27.9 a 3.10.2022
  3. Cvičení 4. a 10.10.202
  4. Cvičení 11. a 17.10.2022
  5. Cvičení 18. a 24.10.2022
  6. Cvičení 25. a 31.10.2022
  7. Cvičení 1. a 7.11.2022
  8. Cvičení 8. a 14.11.2022
  9. Cvičení 15. a 21.11.2022
  10. Cvičení 22. a 28.11.2022
  11. Cvičení 29.11. a 5.12.2022
  12. Cvičení 6. a 12.12.2022
  13. Cvičení 13.12.2022