ASD - kolokwium 1 - zagadnienia

  1. Algorytmy rekurencyjne i iteracyjne: podstawy teoretyczne, wady i zalety rekurencji i iteracji, zasady działania i umiejętność budowy algorytmów rekurencyjnych i iteracyjnych, metoda „dziel i zwyciężaj” konstruowania algorytmów
  2. Kolejki i stosy: zasada działania, konstrukcja algorytmów w oparciu o te struktury danych, ONP
  3. Algorytmy sortowania: bąbelkowe, przez wybór, przez wstawianie, przez zliczanie, pozycyjne, przez scalanie, quicksort.
    1. Zasada działania
    2. Złożoność obliczeniowa i pamięciowa
    3. Ograniczenia stosowania
    4. Stabilność
    5. Podstawowe możliwości optymalizacji
    6. Podział na algorytmy działające w oparciu o porównania i pozostałe
    7. Przypadek optymistyczny i pesymistyczny
  4. Złożoność obliczeniowa
    1. Pojęcie operacji dominującej i jej wykorzystanie do szacowania złożoności obliczeniowej
    2. Złożoność czasowa i pamięciowa
    3. Notacje złożoności: O, Ω, Θ
    4. Klasy złożoności
    5. Przykłady algorytmów należących do danej klasy w określonej notacji
    6. Szacowanie złożoności obliczeniowej algorytmów: przez podstawianie, metoda rekurscji uniwersalnej




:!: UWAGA: w sekcji przyklady pojawiły się materiały dotyczące obliczania złożoności - pochodzące z „Wprowadzenia do algorytmów” Cormena, do którego Państwa odsyłamy!

pl/dydaktyka/asd/cwiczenia/2012-kol1zagadnienia.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0