Logika i teoria mnogości

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Zapoznanie się z podstawowymi pojęciami i narzędziami matematyki. Wprowadzenie fundamentalnych obiektów matematycznych i opis ich własnoœci.

Sylabus

Autorzy

• Marek Zaionc

Wymagania wstępne

• Brak

Zawartość

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

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