Uniwersytet Jagielloński w Krakowie - Punkt LogowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Introduction to order theory

Informacje ogólne

Kod przedmiotu: WMI.TCS.WTCP.S Kod Erasmus / ISCED: (brak danych) / (0588) Interdyscyplinarne programy i kwalifikacje obejmujące nauki przyrodnicze, matematykę i statystykę
Nazwa przedmiotu: Introduction to order theory
Jednostka: Instytut Informatyki Analitycznej
Grupy:
Punkty ECTS i inne: 8.00
zobacz reguły punktacji
Język prowadzenia: angielski

Zajęcia w cyklu "Semestr zimowy 2020/2021" (jeszcze nie rozpoczęty)

Okres: 2020-10-01 - 2021-01-28

Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 60 godzin więcej informacji
Koordynatorzy: Stefan Felsner, Piotr Micek
Prowadzący grup: Piotr Micek
Strona przedmiotu: https://piotrmicek.staff.tcs.uj.edu.pl/introduction-to-order-theory-2020/
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ocena wliczana do średniej:

tak

Wymagania wstępne:

Matematyka Dyskretna

Forma i warunki zaliczenia:

Zaliczenie z ćwiczeń będzie wystawiane na podstawie rozwiązań zadań domowych. W trakcie kursu będą publikowane zestawy zadań domowych. Liczba zestawów będzie równa Z. Zestawy będą ukazywać się (zazwyczaj) co tydzień. Rozwiązania zadań studenci przekazują w formie pisemnej (emailem) prowadzącym w wyznaczonych terminach (najczęściej na dzień przed kolejną sesją ćwiczeń). Za rozwiązanie zadań pojedynczego zestawu będzie można uzyskać co najwyżej

100/Z punktów. Zadania w pojedynczym zestawie będą miały zróżnicowany poziom trudności i zazwyczaj będą tak samo punktowane. Studenci mogą rozwiązywać zadania samodzielnie lub w grupach dwuosobowych. Każda dwójka studentów może rozwiązywać wspólnie co najwyżej dwa zestawy.


Kodeks honorowy. Studenci nie mogą wyszukiwać, rozwiązań czy wskazówek do zadań domowych w internecie, książkach, pracach naukowych, czy też dyskutować zadania z osobami trzecimi. W sytuacjach wątpliwych najlepiej spytać. Każde rozwiązanie powinno zawierać oświadczenie o samodzielności wykonania (indywidualnie lub w grupie).


Ćwiczenia. W ramach ćwiczeń będziemy wspólnie rozwiązywać zadania. Zestawy zadań na ćwiczenia będą publikowane z niewielkim wyprzedzeniem lub rozdawane podczas zajęć. Studenci nie będą ewaluowani za pracę podczas ćwiczeń, a więc w ramach ćwiczeń nie będą przyznawane punkty.


Oceny z ćwiczeń wystawiane będą względem następujących progów:

5,0 -- (90,100]

4,5 -- (80,90]

4,0 -- (70,80]

3,5 -- (60,70]

3,0 -- (50,60]

2,0 -- (25,50]

NZAL -- [0,25]


Studenci, którzy otrzymają ocenę co najmniej 3,0 z ćwiczeń przystąpią do egzaminu końcowego w pierwszym terminie w formie ustnej. Studenci, którzy otrzymają ocenę co najmniej 3,0 z egzaminu w pierwszym terminie otrzymają ocenę końcową z kursu równą średniej arytmetycznej ocen z ćwiczeń i egzaminu. Studenci, którzy otrzymali ocenę 2,0 lub NZAL z egzaminu w pierwszym terminie mogą przystąpić do egzaminu w drugim terminie w sesji poprawkowej. Studenci, którzy otrzymali ocenę 2,0 lub NZAL z ćwiczeń nie zaliczą kursu.

Sylabus przedmiotu dla studentów rozpoczynających studia od roku akademickiego 19/20:

(tylko po angielsku) * Fundamentals

--- Fundamental examples

--- Chains and antichains

--- Linear extensions and dimension

* Boolean Lattice

--- Symmetric chains

--- Shadows and intersecting families

--- Gray codes

* First Steps in Dimension Theory

--- Alternating cycles

--- Families of posets with unbounded dimension

--- Dimension and planarity

* Interval Orders

--- Characterizations and semi-orders

--- Doubly logarithmic upper bound for dimension

--- Forbidden subposets and dimension

* Extremal problems

--- Applications of Dilworth theorem to problems in geometry

--- Forcing standard examples

--- Bipartite analogue of Dilworth

--- Hasse diagrams with large chromatic numbers

* Greene-Kleitmann Theory

--- Duality for l-antichains and k-chains

--- Young Tableaux and RSK correspondence

--- Viennot's skeletons of 2-d orders

* Dimension and Sparse Cover Graphs

--- Dimension and weak coloring numbers

--- Scott-Wood proof for bounded degree posets

* Order Polytopes

--- Order- and Chain-Polytopes

--- Thm of Stanley

* Counting Linear Extensions

--- An inequality for # lin extensions of 2-dim orders

--- Sidorenko's inequality

--- Markov chains

* perhaps more

Skrócony opis: (tylko po angielsku)

A partial order (poset) is a set equipped with a transitive order relation. Posets are widely used models in applications and also within mathematics and computer science. In this course we cover the basics of combinatorial order theory but we also add some more advanced and recent topics. A good fraction of the material will deal with poset dimension, an important measure for the complexity of posets. Other chapters will deal with Boolean lattices, aspects of planarity and enumeration problems related to posets.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Jagielloński w Krakowie.