Algoritmy 1 Mgr. Tomáš Urbanec

Informace o předmětu na stránkách přednášejícího a ve STAGu.

Zápočet

Zadání zápočtového úkolu:

  1. 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ů:
    Počet provedených porovnání
    Algo. \ # prvků 10 100 1000 10000
    Insertion-sort
    Quick-sort
    Heap-sort

    Počet provedených výměn prvků
    Algo. \ # prvků 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í 27.10. a 4.11.
    • 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í zahrnující prvek z pole. Tj. nepočítejte například porovnávání v hlavičce for cyklů atp.

  • Navrhněte algoritmy pro následující problémy, popište je pseudokódem a implementujte v jazyce C. Uveďte časovou složitost navržených algoritmů v nejhorším případě (oboustrannou mez) .
    1. V poli je uloženo n čísel. Vypište True, jsou-li všechna čísla vzájemně různá (žádné číslo se v poli nevyskytuje vícekrát), a False v opačném případě.
    2. V poli je uloženo n přirozených čísel. Vypište počet lichých čísel obsažených v poli.
    3. Pro zadané čísla A a B vypište posloupnost, která začne číslem A a následující prvky se sníží vždy o hodnotu B. Pokud by následující prvek měl být menší než 0, začne posloupnost růst o hodnotu B. Algoritmus končí, když vypíše podruhé hodnotu A. Například pro vstup A=10, B=3 algoritmus vypíše: 10,7,4,1,4,7,10). Navrhněte iterativní (cykly) i rekurzivní algoritmus.
  • Odevzdávání

    Mezní termín pro odevzdání je 20.12.2020 . Úkoly odevzdávejte emailem. Do předmětu uveďte "algoritmy-prijmeni-jmeno" a do přílohy dejte tři soubory "prijmeni-1.c" pro první úkol a "prijmeni-2.pdf" (s pseudokódy a složitostmi) a "prijmeni-2.c" (s implementacemi) pro druhý úkol. Úkoly vypracujte samostatně (vizte studijní řád).

    Distanční výuka

    Vzhledem k situaci probíhají cvičení distanční formou. Každý týden bude zveřejněn odkaz na video (níže u cvičení) a cvičení proběhnou přes zoom v časech cvičení. Odkazy pro jednotlivá cvičení jste dostali emailem. Na video se podívejte před začátkem online cvičení.

    Účast na online cvičení je povinná!

    Cvičení

    Správce stránky: Tomáš Urbanec