Plan seminariów w roku akademickim 2009/2010

Semestr letni

2010.02.18 Spotkanie organizacyjne (obecność obowiązkowa)
Zaplanujemy referaty na nowy semestr i podyskutujemy o postępach w pracach magisterskich.

2010.02.25 Michał Pachucki
Liniowe jądro dla problemu Feedback Vertex Set w grafach planarnych

Streszczenie:

2010.03.03 Kamil Kawka
Automaty komórkowe

Streszczenie:

2010.03.10 Wojtek Tyczyński
Automaty Boyera-Moore'a

Streszczenie:

2010.03.17 Juliusz Kopczewski
Wyrocznia osiągalności i odległości w grafach planarnych

Konspekt: [PDF]

2010.03.24 Paweł Gora
Posety

Streszczenie:

2010.04.01 Jakub Łącki
tba

Streszczenie:

2010.04.08 Przemysław Dębiak
Independent Chip Model z wykorzystaniem symulacji w przod.

Streszczenie:

2010.04.15 Kamill Lenartowicz
konik szachowy

Streszczenie:

2010.04.22 Dariusz Leniowski
Analiza języka naturalnego

Streszczenie:

2010.05.06 Karolina Sołtys
Dlaczego tak trudno dowieść, że P != NP?

Streszczenie:

2010.05.13 Łukasz Bieniasz-Krzywiec
Maksymalny podgraf 2-kolorowalny-krawędziowo

Streszczenie: Nowy algorytm aproksymacyjny dla tego problemu.

2010.05.20 nie ma seminarium
(Wykłady o wykładach)

2010.05.27 Piotr Mikulski
Omówienie metod teselacji w architekturze CUDA

Streszczenie:

Semestr zimowy

2009.10.01 Omówienie propozycji referatów

2009.10.08 Marek Cygan, Marcin Pilipczuk, Łukasz Kowalik
Algorytmy parametryzowane

Streszczenie: Chodzi o problemy w stylu "sprawdzic czy istnieje pokrycie wierzcholkowe rozmiaru k w grafie o n-wierzcholkach i m krawedziach w czasie O(n^p+c^k), gdzie p,c są stałymi". Ta dziedzina wciaz sie bardzo szybko rozwija (np. w ciagu ostatnich 4 miesiecy byly 3 konferencje/warsztaty na ten temat). Dziedzina jest o tyle ciekawa, ze ciagle pojawiaja sie tam nowe wyniki w oparciu o proste, kombinatoryczne rozumowania -- stad wydaje nam sie ze jest to zrodlo ciekawych i przystepnych dla studentow referatow, z otwartymi problemami "w zasiegu" magistrantow.
Gorąco zachęcamy do zainteresowania się tą dziedziną!

2009.10.15 Jakub Łącki
Drzewa Gomory-Hu

Streszczenie: Zobacz w wikipedii
Slajdy: [pdf]

2009.10.22 Łukasz Bieniasz-Krzywiec
O dolnych i górnych granicach złożoności obliczeniowych kilku problemów NP-zupełnych

Streszczenie: Przyjrzymy się między innymi zagadnieniu spełnialności formuł logicznych w postaci CNF. Najszybsze znane algorytmy dla tego problemu działają w czasie O*(2^(n - o(n))), gdzie n to liczba zmiennych w formule. Jak dotąd nikomu nie udało się jeszcze stworzyć algorytmu o złożoności O*(2^(cn)), gdzie c < 1. Przedstawię kilka bardzo przekonywujących hipotez, które implikują istnienie takiego algorytmu. Rozpatrzymy także zagadnienie spełnialności więzów CSP. Pokażę, że złożoność obliczeniowa tego problemy rośnie wraz ze wzrostem rozmiaru dziedzin zmiennych.
Slajdy: [pdf]

2009.10.29 Bogdan Yakovenko

Streszczenie:

2009.11.05 Kamil Lenartowicz
Problem skoczka szachowego

Streszczenie:

2009.11.12 Dariusz Leniowski

Streszczenie:

2009.11.19 Wojtek Tyczyński
Problem k najkrótszych ścieżek

Streszczenie:

2009.11.26 Marian Kędzierski
Drzewa link-cut Tarjana

Slajdy: [pdf]

2009.12.03 Juliusz Kopczewski
Uoglnione drzewa Huffmana, czyli tzw. lopsided trees

Streszczenie: Problem kodowania zbioru symboli za pomocš cišgów nad pewnym alfabetem jest dobrze znany i posiada proste i eleganckie rozwišzanie w postaci algorytmu Huffmana. Okazuje się, że gdy problem nieco rozszerzymy: dopuścimy różne koszty liter alfabetu kodujšcego, wówczas problem staje się trudny. Otrzymane zagadnienie nosi miano konstrukcji optymalnych uogólnionych drzew Huffmana (ang. lopsided trees). Nie jest znany ani algorytm wielomianowy ani dowód NP-zupełności. Stšd referat koncentruje się na przedstawieniu jak najlepszego rozwišzania wykładniczego.
Slajdy: [pdf]

2009.12.17 Michał Pachucki
Jądro rozmiaru O(k^2) dla problemu Feedback Vertex Set

Slajdy: [PDF]

2010.01.07 Kamil Kawka
Rozpoznawanie wypukłych zbiorów pikseli.

Streszczenie: Zastosowanie algorytmów tekstowych w (dyskretnej) geometrii obliczeniowej.

2010.01.14 Karolina Sołtys
Nieaproksymowalność problemów kilki i kolorowania przez twierdzenie PCP.

Skrypt (!) [PDF]

2010.01.21 Piotr Butryn
O algorytmie Partition Search.

Streszczenie: Opowiem o algorytmie Partition Search (wykorzystywanym do znajdywania minimaxa w grach - np. ilości lew w rozdaniu brydżowym) oraz algorytmach używanych w grach z niepełną informacją.
slajdy (1.9M) [PDF]