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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Zaionc (dyskusja | edycje)
37 edycji
Nie podano opisu zmian
Rogoda (dyskusja | edycje)
1875 edycji
 
(Nie pokazano 64 wersji utworzonych przez 9 użytkowników)
Linia 1: Linia 1:
Spis treści
== Forma zajęć ==
[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) + ćwiczenia (30 godzin)
Wykład (30 godzin) + ćwiczenia (30 godzin)
[Edytuj]
== Opis ==
Opis
Zapoznanie się z podstawowymi pojęciami i narzędziami matematyki.
 
Wprowadzenie fundamentalnych obiektów matematycznych i opis ich własności.
Podstawowe
[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]
== Sylabus ==
Zawartość
=== Autorzy ===
* Marek Zaionc — Uniwersytet Jagielloński
* Jakub Kozik  — Uniwersytet Jagielloński
* Marcin Kozik — Uniwersytet Jagielloński


    * Podstawowe zasady analizy algorytmów:
=== Zawartość ===
          o poprawność,
* Rachunek zdań i rachunek predykatów
          o złożoność obliczeniowa (pesymistyczna, oczekiwana),
* Aksjomatyka teorii mnogości ZFC
          o złożoność problemu algorytmicznego.
* Iloczyn kartezjański, relacje, relacja równoważności, rozkłady zbiorów
    * Sortowanie:
* Konstrukcja von Neumanna liczb naturalnych:
          o sortowanie przez porównania (InsertionSort, QuickSort, MergeSort),
** twierdzenie o indukcji
          o HeapSort i kopce binarne,
** własności liczb
          o złożoność problemu sortowania.
** definiowanie przez indukcję
    * Selekcja:
** zasada minimum
          o minimum i maximum,
** zasada maksimum
          o algorytm Hoare'a,
* Konstrukcja i działania na liczbach całkowitych
          o algorytm magicznych piątek.
* Konstrukcja i działania na liczbach wymiernych
    * Wyszukiwanie:
* Konstrukcja Cantora liczb rzeczywistych:
          o liniowe,
**  działania i porządek
          o binarne,
* Funkcje, twierdzenie o faktoryzacji:
          o drzewa wyszukiwań binarnych,
**  obrazy i przeciwobrazy zbiorów
          o zrównoważone drzewa wyszukiwań binarnych,
* Teoria mocy:
          o B-drzewa,
** zbiory przeliczalne i ich własności
          o haszowanie.
** zbiory liczb całkowitych i wymiernych są przeliczalne
    * Złożone struktury danych:
** zbiór liczb rzeczywistych jest nieprzeliczalny
          o kolejki priorytetowe,
** zbiory <math>\{0, 1\}^N</math> i <math>N^N</math> nie są przeliczalne. Zbiór <math>2^N \sim R</math>
          o struktury danych dla zbiorów rozłącznych.
** twierdzenie Knastera - Tarskiego (dla zbiorów)
    * Algorytmy grafowe:
** lemat Banacha
          o DFS i jego zastosowania,
** twierdzenie Cantora-Bernsteina, (warunki równoważne)
          o problemy ścieżkowe -- Algorytm Dijkstry,
** twierdzenie Cantora
          o najmniejsze drzewo rozpinające.
** zbiory mocy kontinuum
    * Algorytmy tekstowe:
* Zbiory uporządkowane:
          o algorytm Knutha-Morisa-Pratta,
** lemat Kuratowskiego Zorna
          o drzewa sufiksowe.
** przykłady dowodów przy pomocy lematu Kuratowskiego Zorna
** dowód lemat Kuratowskiego Zorna
* Zbiory liniowo uporządkowane:
** pojęcia gęstości i ciągłości
** porządek na <math>R</math> jest ciągły
* Zbiory dobrze uporządkowane:
** twierdzenie o indukcji
** liczby porządkowe
** zbiory liczb porządkowych
** twierdzenie o definiowaniu przez indukcje pozaskończoną
** twierdzenie Zermelo


[Edytuj]
===Literatura===
Literatura
# H. Rasiowa, ''Wstęp do matematyki'', Państwowe Wydawnictwo Naukowe, Warszawa 1971, 1984, 1998.
# K. Kuratowski, A. Mostowski, ''Teoria mnogości'', Państwowe Wydawnictwo Naukowe, Warszawa 1978.
# W. Marek, J. Onyszkiewicz, ''Elementy logiki i teorii mnogosci w zadaniach'', Wydawnictwo Naukowe PWN, Warszawa 1996.


  1. Wprowadzenie do algorytmów, Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
== Moduły ==
  2. Algorytmy i struktury danych, L. Banachowski., K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.  
# [[Logika i teoria mnogości/Wykład 1: Po co nam teoria mnogości? Naiwna teoria mnogości, naiwna indukcja, naiwne dowody niewprost|Po co nam teoria mnogości? Naiwna teoria mnogości, naiwna indukcja, naiwne dowody niewprost]] ([[Logika i teoria mnogości/Test 1: Po co nam teoria mnogości? Naiwna teoria mnogości, naiwna indukcja, naiwne dowody niewprost|test]])
· Rachunek zdań i rachunek predykatów.
# [[Logika i teoria mnogości/Wykład 2: Rachunek zdań|Rachunek zdań]] ([[Logika i teoria mnogości/Test 2: Rachunek zdań|test]])
· Aksjomatyka teorii mnogości, aksjomaty sumy, ekstensjonalności, przecięcia, pary.
# [[Logika i teoria mnogości/Wykład 3: Rachunek predykatów, przykład teorii w rachunku predykatów|Rachunek predykatów, przykład teorii w rachunku predykatów]] ([[Logika i teoria mnogości/Test 3: Rachunek predykatów, przykład teorii w rachunku predykatów|test]])
· Iloczyn Kartezjański, relacje, relacja równoważności, rozkłady zbiorów.  
# [[Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach|Teoria mnogości ZFC. Operacje na zbiorach]] ([[Logika i teoria mnogości/Test 4: Teoria mnogości ZFC. Operacje na zbiorach|test]])
· Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, własności liczb. Definiowanie przez indukcje. Zasada minimum, Zasada maksimum.
# Iloczyn kartezjański i relacje ([[Iloczyn kartezjański i relacje/Test 5|test]])
· Konstrukcja liczb całkowitych, działania na liczbach całkowitych. Konstrukcja liczb wymiernych.
## [[Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów|Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów]]
· Konstrukcja Cantora liczb rzeczywistych, działania i porządek.
##[[Logika i teoria mnogości/Wykład 5.2| Iloczyn kartezjański i aksjomat wyróżniania (dla dociekliwych)]]
· Funkcje, twierdzenie o faktoryzacji. Obrazy i przeciwobrazy zbiorów.
# [[Logika i teoria mnogości/Wykład 6: Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha|Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha]] ([[Logika i teoria mnogości/Test 6: Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha|test]])
· Teoria mocy. Zbiory przeliczalne, własności. Zbiór liczb całkowitych i wymiernych jest przeliczalny.
# [[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje|Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje]] ([[Logika i teoria mnogości/Test 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje|test]])
· Zbiór liczb rzeczywistych jest nieprzeliczalny. Zbiory {0, 1}N i NN nie są przeliczalne. Zbiór 2N ~ R.
# [[Logika i teoria mnogości/Wykład 8: Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek|Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek]] ([[Logika i teoria mnogości/Test 8: Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek|test]])
· Twierdzenie Knastera - Tarskiego (dla zbiorów). Lemat Banacha. Twierdzenie Cantora-Bernsteina, (warunki równoważne). Twierdzenie Cantora.  
# [[Logika i teoria mnogości/Wykład 9: Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum|Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy continuum]] ([[Logika i teoria mnogości/Test 9: Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum|test]])
· Zbiory mocy kontinuum. Zbiory uporządkowane. Lemat Kuratowskiego Zorna. Przykłady dowodów przy pomocy lematu.  
# Zbiory uporządkowane. ([[Zbiory uporządkowane/Test 10|test]])
· Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości. R jest ciągła.  
## [[Logika i teoria mnogości/Wykład 10: Zbiory uporządkowane. Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości|Zbiory uporządkowane. Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości]]
· Zbiory dobrze uporządkowane. Twierdzenie o indukcji. Liczby porządkowe. Własności.
## [[Logika i teoria mnogości/Wykład 10.2| Twierdzenie Bourbakiego-Witta (dla dociekliwych)]]
· Zbiory liczb porządkowych.  
# [[Logika i teoria mnogości/Wykład 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady|Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady]] ([[Logika i teoria mnogości/Test 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady|test]])
· Twierdzenie o definiowaniu przez indukcje pozaskończoną. Twierdzenie Zermelo. Lemat Kuratowskiego Zorna.  
# [[Logika i teoria mnogości/Wykład 12: Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcje pozaskończoną|Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcję pozaskończoną]] ([[Logika i teoria mnogości/Test 12: Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcje pozaskończoną|test]])
· 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

Aktualna wersja na dzień 20:05, 29 wrz 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 — Uniwersytet Jagielloński
  • Jakub Kozik — Uniwersytet Jagielloński
  • Marcin Kozik — Uniwersytet Jagielloński

Zawartość

  • Rachunek zdań i rachunek predykatów
  • Aksjomatyka teorii mnogości ZFC
  • 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 indukcję
    • zasada minimum
    • zasada maksimum
  • Konstrukcja i działania na liczbach całkowitych
  • Konstrukcja i działania na liczbach wymiernych
  • Konstrukcja Cantora liczb rzeczywistych:
    • działania i porządek
  • Funkcje, twierdzenie o faktoryzacji:
    • obrazy i przeciwobrazy zbiorów
  • Teoria mocy:
    • zbiory przeliczalne i ich własności
    • zbiory liczb całkowitych i wymiernych są przeliczalne
    • 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 Kuratowskiego Zorna
    • dowód lemat Kuratowskiego Zorna
  • Zbiory liniowo uporządkowane:
    • pojęcia gęstości i ciągłości
    • porządek na R jest ciągły
  • Zbiory dobrze uporządkowane:
    • twierdzenie o indukcji
    • liczby porządkowe
    • zbiory liczb porządkowych
    • twierdzenie o definiowaniu przez indukcje pozaskończoną
    • twierdzenie Zermelo

Literatura

  1. H. Rasiowa, Wstęp do matematyki, Państwowe Wydawnictwo Naukowe, Warszawa 1971, 1984, 1998.
  2. K. Kuratowski, A. Mostowski, Teoria mnogości, Państwowe Wydawnictwo Naukowe, Warszawa 1978.
  3. W. Marek, J. Onyszkiewicz, Elementy logiki i teorii mnogosci w zadaniach, Wydawnictwo Naukowe PWN, Warszawa 1996.

Moduły

  1. Po co nam teoria mnogości? Naiwna teoria mnogości, naiwna indukcja, naiwne dowody niewprost (test)
  2. Rachunek zdań (test)
  3. Rachunek predykatów, przykład teorii w rachunku predykatów (test)
  4. Teoria mnogości ZFC. Operacje na zbiorach (test)
  5. Iloczyn kartezjański i relacje (test)
    1. Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów
    2. Iloczyn kartezjański i aksjomat wyróżniania (dla dociekliwych)
  6. Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha (test)
  7. Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje (test)
  8. Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek (test)
  9. Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy continuum (test)
  10. Zbiory uporządkowane. (test)
    1. Zbiory uporządkowane. Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości
    2. Twierdzenie Bourbakiego-Witta (dla dociekliwych)
  11. Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady (test)
  12. Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcję pozaskończoną (test)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogości&oldid=60011”