Logika i teoria mnogości: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Zaionc (dyskusja | edycje)
37 edycji
Nie podano opisu zmian
Zaionc (dyskusja | edycje)
37 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
Spis treści
== Forma zajęć ==
[schowaj]
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.


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


[Edytuj]
=== Wymagania wstępne ===
Forma zajęć
* Brak


Wykład (30 godzin) + ćwiczenia (30 godzin)
=== Zawartość ===
[Edytuj]
* Podstawowe zasady analizy algorytmów:
Opis
** 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.


Podstawowe
=== Literatura ===
[Edytuj]
# ''Wprowadzenie do algorytmów'', Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
Sylabus
# ''Algorytmy i struktury danych'', L. Banachowski., K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
[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.  
· Rachunek zdań i rachunek predykatów.  
· Aksjomatyka teorii mnogości, aksjomaty sumy, ekstensjonalności, przecięcia, pary.  
· Aksjomatyka teorii mnogości, aksjomaty sumy, ekstensjonalności, przecięcia, pary.  

Wersja z 09:00, 9 cze 2006

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

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogości&oldid=1605”