Plan seminariów w roku akademickim 2008/2009

Semestr letni

2009.02.19 Krzysztof Choromański
Zastosowania klasteryzacji grafów

2009.02.26 Piotr Truszkowski
Najciekawsze zadania II etapu XVI Olimpiady Informatycznej

2009.03.05 Jakub Łącki
Skojarzenia w grafach dwudzielnych 3-regularnych

Streszczenie: Prosty algorytm liniowy znajdujący doskonałe skojarzenie w grafach kubicznych. Prosty dowód, że każdy taki graf zawiera (4/3)^n doskonałych skojarzeń.
Prezentacja: [PDF]

2009.03.05 Jakub Łącki
Skojarzenia w grafach dowolnych: techniki algebraiczne

Streszczenie: Macierz Tutte -- testowanie istnienia doskonałego skojarzenia przez obliczanie wyznacznikia. Zliczanie doskonałych skojarzeń w grafach planarnych (orientacje Kasteleyna-de Brujina).
Prezentacja: [PDF]

2009.03.19 Łukasz Bieniasz-Krzywiec
Generowanie kombinacji (,,Cool-lex'')

Streszczenie: Tematem referatu będzie elegancka metoda generowania wszystkich (s,t)-kombinacji, czyli słów składajšcych się z s zer i t jedynek. Przedstawię bardzo prosty algorytm o następujących właściwościach:

2009.03.26 Szymon Bargłowski
Testowanie planarnosci grafu

Prezentacja: [PDF]

2009.04.02 Piotr Mikulski
Uproszczony algorytm testowania planarnosci grafu

Zainspirowany wczesniejszym seminarium, Piotr Mikulski zaproponowal wlasny algorytm, o latwym do zrozumienia dowodzie poprawnosci.

2009.04.16 Paweł Gora
Matematyczny opis symulacji ruchu drogowego przy pomocy automatów komórkowych

Na seminarium omówię matematyczne i algorytmiczne podstawy, które kryją się za tworzonym przeze mnie symulatorem ruchu drogowego. Opowiem o najlepszych znanych modelach symulacji wykorzystujących teorię automatów komórkowych oraz zaprezentuję mój własny model, stworzony na potrzeby symulatora. Przedstawię również wnioski, wynikające z tych modeli na drodze analitycznych i probabilistycznych rozważań, które będą przydatne w dalszej pracy do wykrywania procesów powstawania korków na drodze oraz planowania unikania tych zagrożeń. Zaprezentuję także najnowsze zmiany, które wprowadziłem w samym symulatorze.
Prezentacja: [PDF]

2009.04.23 Paweł Brach

2009.04.30 Piotr Butryn
Generowanie permutacji

2009.05.07 Dariusz Leniowski
Równoważność automatów wielotaśmowych

Rownowaznosc automatow skonczonych jest istotnym problemem w teorii obliczen. Wiadomo, ze dla deterministycznych automatow jednotasnowych (niedeterministyczne sa rownowazne z deterministycznymi) problem ten jest rozwiazywalny wielomianowo, natomiast dla niedeterministycznych automatow wielotasmowych jest w ogole nierozstrzygalny. Do niedawna, status deterministycznych automatow wielotasmowych byl problemem otwartym. Na przykladzie automatow probabilistycznych zostanie wprowadzone pojecie rownowaznosci w sensie krotnosci, ktore wraz z niekonwencjonalnym zastosowaniem algebry liniowej zostanie uzyte do rozstrzygniecia wspomnianego zagadnienia.
Prezentacja: [PDF]

2009.05.14 Kamil Lenartowicz
Kopce parujace

2009.05.21 Piotr Mikulski

2009.05.28 Bartlomiej Romanski
Transformata Burrowsa-Wheelera i jej strukturalne wlasnoci dla pewnych klas grafow.

2009.06.04 Piotr Cerobski
System sterowania ruchem w miescie
Zostanie przedstawione wlasne rozwiazanie pewnego zlozonego problemu optymalizacyjnego zwiazanego ze sterowaniem ruchem pojazdow w miescie. Prezentacja bedzie zilustrowana symulacjami.
Zobacz teaser (wlaczyc glosniki!)

Semestr zimowy

2008.10.02 Omówienie propozycji referatów

2008.10.09 Łukasz Bieniasz-Krzywiec
Prawo Haczykowe

Streszczenie: Prawo Haczykowe mówi, że liczba wszystkich tableau Young'a dla ustalonego diagramu Ferrersa wynosi n! podzielone przez iloczyn długości wszystkich haczyków w diagramie.
Tematem referatu będzie elementarny dowód probabilistyczny Prawa Haczykowego zaproponowany w pracy autorstwa C. Greene'a, A. Nijenhuis'a oraz H. S. Wilf'a. Zdefiniuję diagramy Ferrersa, tableaux Young'a, haczyki i ich długości. Przedstawię rekurencyjny wzór na liczbę tableau Young'a. Udowodnię, że formuła haczykowa spełnia wzór rekurencyjny podając jej probabilistyczną interpretację. W tym celu zdefiniję eksperyment losowy, który jest jednocześnie algorytmem randomizowanym generującym wszystkie tableau Young'a z jednakowym prawdopodobieństwem.
Prezentacja: [PDF]

2008.10.16 Dariusz Leniowski
Listy z przeskokami jako zrównoważone drzewa wyszukiwań binarnych

Streszczenie: Lista z przeskokami jest jedna z implementacyjnie najprostszych struktur slownikowych umozliwiajacych wyszukiwanie w oczekiwanym czasie O(log n). Ale czy mozemy jej uzyc, gdy ograniczenie na czas oczekiwany nie wystarcza?
Podczas referatu sproboje zademonstrowac jak zmienne jest oblicze skip-listy, przedstawie roznorodne sposoby derandomizacji tej struktury oraz wynikajace z nich niebanalne analogie do drzew wyszukiwan.
Prezentacja: [PDF]

2008.10.30 Piotr Butryn
Gry ekonomiczne

2008.11.06 Kamil Lenartowicz
Znajdowanie skojarzeń na maszynie równoległej

Problem znalezienia najlepszego skojarzenia dla dowolnego grafu w czasie polilogarytmicznym przy wielomianowej liczbie procesorów jest jak do tej pory nierozwiązany. Istnieje jednak wiele ciekawych algorytmów dla określonych klas grafów oraz wersji problemu - przedstawię algorytm służący do szukania maksymalnego co do zawierania skojarzenia.
Prezentacja: [PDF]

2008.11.13 Paweł Papis
Transformaty Burrowsa-Wheelera (uogólnionych) słów Thuego-Morse'a

Prezentacja: [PDF]

2008.11.20 Paweł Gora
O klasie problemów #P

Streszczenie: Problemy decyzyjne z klasy NP polegają na pytaniu: czy istnieje obiekt o określonych własnościach? Problemy z klasy #P są od nich trudniejsze, gdyż pojawia się w nich pytanie: ile jest odpowiednich obiektów? Referat omawia klasę problemów #P oraz problemów #P-zupełnych, których rozwiązanie w czasie wielomianowym oznaczałoby, że P=NP, a jednak ich odpowiedniki decyzyjne mogą być bardzo łatwe. Omówiony zostanie problem zliczanie liniowych porządków zbioru częściowo uporządkowanego oraz algorytmy, które rozwiązują ten problem szybko oraz dają się uogólnić na inne problemy, np. zliczanie porządków, w których element występuje na ustalonej pozycji.
Prezentacja: [PDF]

2008.11.27, 2008.12.04 Szymon Acedański
Symulacja ruchu drogowego na karcie graficznej

2008.12.11 Kamil Lenartowicz
Znajdowanie skojarzeń na maszynie równoległej - kontynuacja

Streszczenie: Problem znalezienia najlepszego skojarzenia dla dowolnego grafu w czasie polilogarytmicznym przy wielomianowej liczbie procesorów jest jak do tej pory nierozwiązany. Istnieje jednak wiele ciekawych algorytmów dla określonych klas grafów oraz wersji problemu - przedstawię algorytmy służące do szukania najliczniejszego skojarzenia dla grafów: gęstych, drzew, dwudzielnych regularnych, claw-free graphs.
Prezentacja: [PDF]

2008.12.18 Wszyscy
Burza mózgów

Każdy uczestnik seminarium jest proszony o przygotowanie krótkiego (5-10min) wystąpienia na temat ciekawego problemu otwartego.

2009.01.08, 01.15 Krzysztof Choromański, Paweł Brach
Zastosowanie współczesnych metod spektralnych oraz algorytmów takich jak PageRank do efektywnej klasteryzacji grafu.