Strona główna > Archiwalny program seminarium > 2016/2017
2016/2017
14.06 (godz. 10.15, sala 431)
Jakub Przybyło (Akademia Górniczo-Hutnicza)
Jak rozróżnić sąsiadów losując kolory krawędzi z zadanych list?Streszczenie.
09.06 (godz. 10.15, sala 213)
Karolina Okrasa
Kolorowania odróżniające sąsiadujące wierzchołki
Problemy rozróżniania sąsiadujących wierzchołków w grafie po multizbiorach kolorów są pewnym uogólnieniem problemu poprawnego wierzchołkowego kolorowania grafu. Podczas referatu przykładowe zagadnienia tego typu zostaną sprowadzone do odpowiednio zdefiniowanego kolorowania hipergrafu. Znalezienie ograniczenia na minimalną długość list kolorów gwarantujących istnienie takiego kolorowania pozwoli wyprowadzić wiele wniosków dotyczących zdefiniowanych wcześniej problemów grafowych.
07.06 (godz. 10.15, sala 431)
Michał Ziembowski
O radykałach pierścieni wielomianów z różniczkowaniem
Streszczenie:
Podczas wystąpienia opowiem o pierścieniach wielomianów z różniczkowaniem i pewnym problemie związanym z lokalnie nilpotentnym radykałem tych pierścieni. Zaprezentuję rozwiązanie wspomnianego problemu z wykorzystaniem Lematu Königa.
Podczas wystąpienia opowiem o pierścieniach wielomianów z różniczkowaniem i pewnym problemie związanym z lokalnie nilpotentnym radykałem tych pierścieni. Zaprezentuję rozwiązanie wspomnianego problemu z wykorzystaniem Lematu Königa.
02.06 (godz. 12.15, sala 213)
Paweł Rzążewski
Złożoność kolorowania obiektów geometrycznych, część II: grubi i chudzi
Streszczenie:
Wyniki dotyczące kolorowania dysków (istnienie algorytmów działających w czasie podwykładniczym oraz dolne ograniczenie oparte na ETH) dają się uogólnić na dwa sposoby:
a) do pokazania analogicznych wyników dotyczących kolorowania d-wymiarowych kul, tym razem właściwą złożonością okazuje się być 2^O(n^{d-1/d} k^{1/d})
b) do pokazania tych samych ograniczeń dla rodzin "grubych" kształtów wypukłych.
Część b) nie da się uogólnić na kształty, które nie są grube (np. odcinki). Istnieje jednak rodzina problemów (3-kolorowanie, zbiór niezależny, pokrycie wierzchołkowe), które dają się rozwiązać w czasie 2^O(n^{2/3}) w grafach przecięć dowolnych krzywych.
Wyniki dotyczące kolorowania dysków (istnienie algorytmów działających w czasie podwykładniczym oraz dolne ograniczenie oparte na ETH) dają się uogólnić na dwa sposoby:
a) do pokazania analogicznych wyników dotyczących kolorowania d-wymiarowych kul, tym razem właściwą złożonością okazuje się być 2^O(n^{d-1/d} k^{1/d})
b) do pokazania tych samych ograniczeń dla rodzin "grubych" kształtów wypukłych.
Część b) nie da się uogólnić na kształty, które nie są grube (np. odcinki). Istnieje jednak rodzina problemów (3-kolorowanie, zbiór niezależny, pokrycie wierzchołkowe), które dają się rozwiązać w czasie 2^O(n^{2/3}) w grafach przecięć dowolnych krzywych.
31.05 (godz. 11.15)
Barbara Pilat
Niespodzianka
31.05 (godz. 10.15)
Oskar Górniewicz
O rybach
29.05 (godz. 12.15)
Urszula Pastwa
Coś o kulawym koniku
26.05 (godz. 13.15, sala 536)
Krzysztof Rejmer
Lokalizowanie w sieci
26.05 (godz. 12.15, sala 536)
Angelika Nicgorska-Miśkiewicz
Liczba hydra grafów niespójnych
24.05
Krzysztof Węsek
O kolorowaniach płaszczyzny unikających pewnych zbiorów skończonych
19.05 (godzina 11.15)
Andrzej Ruciński (Uniwersytet Adama Mickiewicza)
Andrzej Ruciński (Uniwersytet Adama Mickiewicza)
Liczby Ramseya dla $k$-jednostajnych luźnych ścieżek długości $3$.
17.05
Joanna Polcyn-Lewandowska (Uniwersytet Adama Mickiewicza)
Joanna Polcyn-Lewandowska (Uniwersytet Adama Mickiewicza)
Twierdzenia o rozkładzie dla hipergrafów bez pewnych przecięć
10.05
Bartłomiej Bosek (Uniwersytet Jagielloński)
Maksymalne skojarzenia w drzewach metodą najkrótszych ścieżek
26.04
Paweł Rzążewski
Paweł Rzążewski
Złożoność kolorowania obiektów geometrycznych, część I: dyski na płaszczyźnie
Abstrakt:
Zastosowanie standardowych technik pozwala stwierdzić, czy istnieje $k$-kolorowanie grafu przecięć $n$ dysków w czasie $n^O(sqrt(nk))$. Okazuje się, że (zakładając ETH), tego algorytmu nie da się znacząco ulepszyć.
Dokładniej, jeśli ETH jest prawdziwa, problemu nie da się rozwiązać w czasie $2^o(sqrt(nk))$.
Zastosowanie standardowych technik pozwala stwierdzić, czy istnieje $k$-kolorowanie grafu przecięć $n$ dysków w czasie $n^O(sqrt(nk))$. Okazuje się, że (zakładając ETH), tego algorytmu nie da się znacząco ulepszyć.
Dokładniej, jeśli ETH jest prawdziwa, problemu nie da się rozwiązać w czasie $2^o(sqrt(nk))$.
19.04
Paweł Rzążewski
Paweł Rzążewski
Program optymalności
Abstrakt:
Jednym z nurtów w algorytmice, który zyskał znaczna popularność w ostatnich latach, jest poszukiwanie szybkich (tj. jak najszybszych) algorytmów dla problemów trudnych obliczeniowo. Na przykład kolorowanie grafu najmniejszą możliwą liczbą kolorów można znaleźć w czasie 2^n * poly(n), istnienie 3-kolorowania grafu planarnego można stwierdzić w czasie 2^O(sqrt(n)) itp.
Standardowe założenie teorii złożoności, czyli P jest różne od NP, nie wyklucza istnienia znacznie szybszych algorytmów dla tych problemów - o złożoności na przykład 2^(n/1000) albo wręcz 2^(log^2 n).
Silniejszym założeniem, używanym zazwyczaj do rozważania dolnych ograniczeń dla algorytmów rozwiązujących problemy NP-trudne, jest ETH (Exponential Time Hypothesis), która mówi, że 3-SATu o n zmiennych nie da się rozwiązać w czasie 2^o(n).
Podczas referatu zaprezentowane zostaną dolne ograniczenia złożoności oparte na ETH, a także inne założenia, pozwalające na dowodzenie tego typu wyników.
Jednym z nurtów w algorytmice, który zyskał znaczna popularność w ostatnich latach, jest poszukiwanie szybkich (tj. jak najszybszych) algorytmów dla problemów trudnych obliczeniowo. Na przykład kolorowanie grafu najmniejszą możliwą liczbą kolorów można znaleźć w czasie 2^n * poly(n), istnienie 3-kolorowania grafu planarnego można stwierdzić w czasie 2^O(sqrt(n)) itp.
Standardowe założenie teorii złożoności, czyli P jest różne od NP, nie wyklucza istnienia znacznie szybszych algorytmów dla tych problemów - o złożoności na przykład 2^(n/1000) albo wręcz 2^(log^2 n).
Silniejszym założeniem, używanym zazwyczaj do rozważania dolnych ograniczeń dla algorytmów rozwiązujących problemy NP-trudne, jest ETH (Exponential Time Hypothesis), która mówi, że 3-SATu o n zmiennych nie da się rozwiązać w czasie 2^o(n).
Podczas referatu zaprezentowane zostaną dolne ograniczenia złożoności oparte na ETH, a także inne założenia, pozwalające na dowodzenie tego typu wyników.
05.04
seminarium odwołane
29.03
Grzegorz Rządkowski
Grzegorz Rządkowski
Liczby specjalne i ich zastosowania
22.03
Zbigniew Lonc
Zbigniew Lonc
Dowód pewnej hipotezy o podziale kraty boolowskiej na izomorficzne części
15.03
Seminarium łączone z Seminarium z Probablilistyki. Odbędzie się w sali 317.
Jacek Wesołowski
Markowskie struktury grafoweSeminarium łączone z Seminarium z Probablilistyki. Odbędzie się w sali 317.
Jacek Wesołowski
08.03
Mark Pankov (Uniwersytet Warmińsko-Mazurski)
Mark Pankov (Uniwersytet Warmińsko-Mazurski)
Graf niezdegenerowanych kodów liniowych
01.03
Mariusz Felisiak (Uniwersytet Mikołaja Kopernika w Toruniu)
Mariusz Felisiak (Uniwersytet Mikołaja Kopernika w Toruniu)
Problemy spektralnej klasyfikacji Coxetera grafów oznakowanych z zastosowaniem algorytmów symbolicznych i numerycznych
22.02
Bartłomiej Bosek (Uniwersytet Jagielloński)
Bartłomiej Bosek (Uniwersytet Jagielloński)
O hipotezie "1/3-2/3"
25.01
Przemysław Gordinowicz (Politechnika Łódzka)
Przemysław Gordinowicz (Politechnika Łódzka)
Referat pod strasznym tytułem: Wolna, gęsta, 2-generowalna podgrupa grupy automorfizmów przeliczalnego, uniwersalnego, jednorodnego zbioru częściowo uporządkowanego
18.01
Sylwia Cichacz (Akademia Górniczo-Hutnicza)
23.11
Jarosław Grytczuk
02.11
Bartłomiej Kielak (Polska Akademia Nauk)
Dynamiczne monopole
02.11
Paweł Naroski
Lokalizacja w grafach z kolorowymi krawędziami
18.01
Sylwia Cichacz (Akademia Górniczo-Hutnicza)
Survey on group distance magic graphs
07.12
Marcin Wrochna (Uniwersytet Warszawski)
Marcin Wrochna (Uniwersytet Warszawski)
Kolorowanie produktów grafów przez skojarzenie na przestrzenie kolorowań
30.11
Monika Rosicka (Uniwersytet Gdański)
Monika Rosicka (Uniwersytet Gdański)
Grafy permutacyjne i ich własności
23.11
Jarosław Grytczuk
Kolorowanie większościowe grafów, digrafów i hipergrafów
02.11
Bartłomiej Kielak (Polska Akademia Nauk)
Dynamiczne monopole
02.11
Paweł Naroski
Lokalizacja w grafach z kolorowymi krawędziami
26.10
Joanna Sokół
Kolorowanie online grafów przedziałowych
19.10
Kostek Szaniawski
Algorytm znajdujący minimalny tropikalny podgraf spójny
Kostek Szaniawski
Algorytm znajdujący minimalny tropikalny podgraf spójny
12.10
Michał Dębski
Silny indeks chromatyczny grafów przecięć dysków
Michał Dębski
Silny indeks chromatyczny grafów przecięć dysków
05.10
spotkanie organizacyjne