Matematyka dyskretna 2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Idziak (dyskusja | edycje)
14 edycji
Pitab (dyskusja | edycje)
2030 edycji
Linia 19: Linia 19:


=== Zawartość ===
=== Zawartość ===
* Efekty mini-maxowe
*Efekty mini-maxowe
** twierdzenie Mengera
**skojarzenia
** twierdzenie Dilwortha
**pokrycia wierzchołkowe i krawędziowe
** twierdzenie Forda-Fulkersona
**twierdzenia Gallai, Koniga, Frobeniusa, Halla
** twierdzenie Koeniga-Egervary'ego
*Porzadki częsciowe i twierdzenie Dilwortha
** twierdzenie Spernera
**pokrycie łąncuchowe
* Własności podziałowe i twierdzenie Ramseya
**twierdzenie Dilwortha
* Teoria liczb
**rodziny Spernera
** twierdzenie Eulera
*Własności podziałowe
** RSA
**zasada podziałowa
** testowanie pierwszości
**twierdzenie Ramseya
* Grupy i twierdzenie Polya
**liczby Ramseya
* Ciała skończone
*Elementy teorii grup
* Kody korygujące błędy
**grupy cykliczne i rząd elementu grupy
**grupy symetrii wielokątów
**twierdzenie Lagrange’a
*Zastosowania teorii grup w zliczaniu obiektów kombinatorycznych
**działanie grupy na zbiorze
**twierdzenie Polya
*Ciała skończone
**Pierścienie wielomianów
**Konstrukcja ciał skończonych
**Jednoznaczność ciał skończonych
*Zastosowanie teorii liczb w kryptografii
**kryptosystem RSA
**test pierwszości Fermata
**ticzby Carmichaela
**test pierwszości Millera-Rabina


=== Literatura ===
=== Literatura ===

Wersja z 22:58, 20 sie 2006

Forma zajęć

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

Opis

Wykład rozwija aparat matematyczny niezbędny do konstruowania i analizy algorytmów. Składa się z elementów teorii grafów, teorii liczb i algebry.

Sylabus

Autorzy

  • Paweł Idziak
  • Bartłomiej Bosek
  • Piotr Micek

Wymagania wstępne

  • Logika i teoria mnogości
  • Algebra liniowa z geometrią analityczną
  • Analiza matematyczna 1
  • Matematyka dyskretna 1

Zawartość

  • Efekty mini-maxowe
    • skojarzenia
    • pokrycia wierzchołkowe i krawędziowe
    • twierdzenia Gallai, Koniga, Frobeniusa, Halla
  • Porzadki częsciowe i twierdzenie Dilwortha
    • pokrycie łąncuchowe
    • twierdzenie Dilwortha
    • rodziny Spernera
  • Własności podziałowe
    • zasada podziałowa
    • twierdzenie Ramseya
    • liczby Ramseya
  • Elementy teorii grup
    • grupy cykliczne i rząd elementu grupy
    • grupy symetrii wielokątów
    • twierdzenie Lagrange’a
  • Zastosowania teorii grup w zliczaniu obiektów kombinatorycznych
    • działanie grupy na zbiorze
    • twierdzenie Polya
  • Ciała skończone
    • Pierścienie wielomianów
    • Konstrukcja ciał skończonych
    • Jednoznaczność ciał skończonych
  • Zastosowanie teorii liczb w kryptografii
    • kryptosystem RSA
    • test pierwszości Fermata
    • ticzby Carmichaela
    • test pierwszości Millera-Rabina

Literatura

  1. V.Bryant, Aspekty kombinatoryki, WNT 1977,
  2. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, PWN 1996
  3. W.Lipski, Kombinatoryka dla programistów
  4. W.Lipski, W.Marek, Analiza kombinatoryczna, PWN 1986
  5. K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna, PWN 1996
  6. Z.Pałka, A.Ruciński, Wykłady z kombinatoryki, WNT 1998
  7. R.J.Wilson, Wprowadzenie do teorii grafów, PWN 1985

Moduły

  1. tytuł (ćwiczenia)
  2. tytuł (ćwiczenia)
  3. tytuł (ćwiczenia)
  4. tytuł (ćwiczenia)
  5. tytuł (ćwiczenia)
  6. tytuł (ćwiczenia)
  7. tytuł (ćwiczenia)

Literatura uzupełniająca

  1. N.L.Biggs, Discrete Mathematics, Oxford University Press 1989
  2. B.Bollobas, Modern Graph Theory, Springer 1998
  3. Th.H.Cormen, Ch.E.Leiserson, R.L.Rivest, C.Stein,Wprowadzenie do algorytmów, WNT, 2004
  4. R.Diestel, Graph Theory, Springer 1997
  5. G.Polya, R.E.Tarjan, D.R.Woods, Notes on Introductory Combinatorics, Birkhauser 1983
  6. J.Riordan, An Introduction to Combinatorial Analysis, Princeton University Press 1978
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_2&oldid=21578”