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 15: Linia 15:
* Podstawowe zasady analizy algorytmów:
* Podstawowe zasady analizy algorytmów:
** poprawność,
** 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 ===
=== Literatura ===
Linia 51: Linia 25:




 
* 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 i wymiernych:
** 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 i ich własności.
** Zbióry liczb całkowitych i wymiernych są 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ń


· Rachunek zdań i rachunek predykatów.  
· Rachunek zdań i rachunek predykatów.  

Wersja z 09:06, 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ść,


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 i wymiernych:
    • 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 i ich własności.
    • Zbióry liczb całkowitych i wymiernych są 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ń

· 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=1607”