Logika i teoria mnogości

Algorytmy i struktury danych From OSIwiki Jump to: navigation, search Spis treści [schowaj]

   * 1 Forma zajęć
   * 2 Opis
   * 3 Sylabus
         o 3.1 Autorzy
         o 3.2 Wymagania wstępne
         o 3.3 Zawartość
         o 3.4 Literatura

[Edytuj] Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin) [Edytuj] Opis

Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. [Edytuj] Sylabus [Edytuj] Autorzy

   * Wojciech Rytter,
   * Krzysztof Diks 

[Edytuj] Wymagania wstępne

   * Wstęp do programowania
   * Metody programowania
   * Matematyka dyskretna
   * Logika i teoria mnogości 

[Edytuj] Zawartość

   * Podstawowe zasady analizy algorytmów:
         o poprawność,
         o złożoność obliczeniowa (pesymistyczna, oczekiwana),
         o złożoność problemu algorytmicznego. 
   * Sortowanie:
         o sortowanie przez porównania (InsertionSort, QuickSort, MergeSort),
         o HeapSort i kopce binarne,
         o złożoność problemu sortowania. 
   * Selekcja:
         o minimum i maximum,
         o algorytm Hoare'a,
         o algorytm magicznych piątek. 
   * Wyszukiwanie:
         o liniowe,
         o binarne,
         o drzewa wyszukiwań binarnych,
         o zrównoważone drzewa wyszukiwań binarnych,
         o B-drzewa,
         o haszowanie. 
   * Złożone struktury danych:
         o kolejki priorytetowe,
         o struktury danych dla zbiorów rozłącznych. 
   * Algorytmy grafowe:
         o DFS i jego zastosowania,
         o problemy ścieżkowe -- Algorytm Dijkstry,
         o najmniejsze drzewo rozpinające. 
   * Algorytmy tekstowe:
         o algorytm Knutha-Morisa-Pratta,
         o drzewa sufiksowe. 

[Edytuj] Literatura

  1. Wprowadzenie do algorytmów, Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
  2. Algorytmy i struktury danych, L. Banachowski., K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006. 

· Rachunek zdań i rachunek predykatów. · Aksjomatyka teorii mnogości, aksjomaty sumy, ekstensjonalności, przecięcia, pary. · Iloczyn Kartezjański, relacje, relacja równoważności, rozkłady zbiorów. · Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, własności liczb. Definiowanie przez indukcje. Zasada minimum, Zasada maksimum. · Konstrukcja liczb całkowitych, działania na liczbach całkowitych. Konstrukcja liczb wymiernych. · Konstrukcja Cantora liczb rzeczywistych, działania i porządek. · Funkcje, twierdzenie o faktoryzacji. Obrazy i przeciwobrazy zbiorów. · Teoria mocy. Zbiory przeliczalne, własności. Zbiór liczb całkowitych i wymiernych jest przeliczalny. · Zbiór liczb rzeczywistych jest nieprzeliczalny. Zbiory {0, 1}N i NN nie są przeliczalne. Zbiór 2N ~ R. · Twierdzenie Knastera - Tarskiego (dla zbiorów). Lemat Banacha. Twierdzenie Cantora-Bernsteina, (warunki równoważne). Twierdzenie Cantora. · Zbiory mocy kontinuum. Zbiory uporządkowane. Lemat Kuratowskiego Zorna. Przykłady dowodów przy pomocy lematu. · Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości. R jest ciągła. · Zbiory dobrze uporządkowane. Twierdzenie o indukcji. Liczby porządkowe. Własności. · Zbiory liczb porządkowych. · Twierdzenie o definiowaniu przez indukcje pozaskończoną. Twierdzenie Zermelo. Lemat Kuratowskiego Zorna. · Rezolucja i automatyczne dowodzenie twierdzeń Literatura · H. Rasiowa, Wstęp do matematyki, PWN, Warszawa 1971, 1984, 1998 · K. Kuratowski, A. Mostowski, Teoria mnogości, PWN, Warszawa, 1978