Istebna lezy w Beskidach niedaleko zrodel Wisly.
Adres:
43 - 470 Istebna 670
Dom "Maria"
tel. (0 - 33) 55-61-25
To jest w dolinie Olzy, ponizej miejsca gdzie bylismy 2 lata temu.
PRAM z wadami procesorow: symulacje wydajne wzgledem pracy
Rozwazalismy znany model obliczen rownoleglych PRAM w sytuacji gdy czesc procesorow jest zepsuta. Chcielibysmy moc symulowac sprawny model na takiej zepsutej maszynie. Przy projektowaniu metod symulacji zasadnicze znaczenie maja kryteria efektywnosci. Dla nas byla nim laczna praca procesorow, to znaczy, kazdy sprawny procesor w kazdym kroku gdy jest dostepny doklada jednostke do kosztu. Jest to przypadek istotnie rozny od takiego, w ktorym najwazniejszym kryterium jest czas symulacji. Rozwazalismy zarowno sytuacje gdy zepsute procesory nigdy nie "ozywaja" jak i trudniejszy przypadek restartow. Przedstawilem kilka algorytmow zaproponowanych przez Kanellakisa i Shvartsmana, wraz ze szkicem analizy.
Rozglaszanie w sieciach anonimowych
O matroidach
Matroidy sa matematycznym obiektem, podobnie jak grupy, ciala, topologie etc. Maja one zaskakujaco duzo zwiazanych ze soba operatorow i co jest ciekawe kazdy z tych operatorow moze byc uzyty do zdefiniowania czym matroid naprawde jest. Jedna z czesciej spotykanych definicji jest nastepujaca:
Matroid M jest to skonczony zbior E oraz rodzina jego podzbiorow I o
nastepujacych wlasnosciach:
1. zbior pusty nalezy do I
2. Jesli X nalezy do I to rowniez kazdy jego podzbior.
3. Jesli dwa zbiory X i Y naleza do I oraz |X| jest wieksze niz |Y| wtedy
istnieje element x nalezacy do zbioru X\Y, taki ze Y powiekszony o x nalezy
do I.
Zbiory nalezace do I nazywamy zbiorami niezaleznymi.
Zbiory niezalezne o maksymalnej mocy nazywamy bazami matroidu. Jesli
nasuwa sie podobienstwo do liniowej niezaleznosci wektorow - slusznie.
Teoria matroidow ma wiele wspolnego z wektorami i przestrzeniami wektorowymi,
ale co zaskakujace ma ona tez wiele wspolnego z wieloma innymi galeziami
matematyki (czesto dosc odleglymi od siebie). Matroidy staly sie tez przedmiotem
zainteresowania informatykow, kiedy okazalo sie ze tak zwane algorytmy
zachlanne znajduja optymalne rozwiazanie dla pewnych problemow wttw gdy
struktura, na ktorej dzialaja jest matroidem.
Dwa najbardziej znane przyklady matroidow to: matroidy wektorowe i matroidy grafowe. Poznamy tez inne matroidy. Udowodnimy twierdzenie o algorytmach zachlannych, znajdujacych baze matroidu o najwiekszej wadze. Pokazemy alternatywny dowod twierdzenia Kuratowskiego dotyczacego grafow planarnych oparty o matroidy.
Ile wystarczy pamietac, zeby wygrac?
W trakcie referatu przedstawilem prosty dowod twierdzenia o determinacji
dla pewnego rodzaju gier rozgrywanych w nieskonczonosc przez dwoch graczy
na (nie)skonczonych grafach pokolorowanych skonczona liczba kolorow. Dowod
ten pochodzi od W. Zielonki.
W referacie skupilem szczegolna uwage na oszacowaniu zlozonosci strategii
wygrywajacych dla obu graczy. Pokazalem w szczegolnosci optymalne gorne
ograniczenie na rozmiar (skonczonej) pamieci wystarczajacej dla strategii
wygrywajacych w grach z zadanym
warunkiem wygrywajacym. Dowod optymalnosci mozna znalezc w [1]. Wyniki
przedstawione w referacie wchodza w sklad mojej pracy magisterskiej [2].
Gry nieskonczone o ktorych mowilem znajduja zastosowania w automatycznej syntezie programow oraz w teorii automatow na nieskonczonych drzewach.
Formalne modele wspolbieznosci w ujeciu kategoryjnym
Efektywny algorytm dla metody sledzenia promieni
Metoda sledzenia promieni jest technika generacji wysokiej jakosci obrazow przez symulowanie rozchodzenia sie swiatla wzdluz wybranych promieni. Glowna wada tej metody jest duzy koszt zwiazany z koniecznoscia znajdowania przeciec milionow promieni z tysiacami obiektow.
Przedstawiony algorytm jest jednym z wielu algorytmow, ktore staraja sie zminimalizowac koszt tej metody. Jak pokazuja dane eksperymentalne jest to jeden z najszybszych algorytmow, ktorego dodatkowa zaleta sa male wymagania pamieciowe (liniowe wzgledem ilosci obiektow sceny). Dzieki temu mozliwe jest generowanie w rozsadnym czasie obrazow scen zawierajacych milion obiektow uzywajac stacji roboczych.
Podstawowymo cechami algorytmu jest uzycie drzew BSP do budowy hierarchi bryl otaczajacych i metody trawersowania plaszczyzn do poszukiwania najblizszego punktu przeciecia.
Twierdzenie Razborova
Wykazalismy nastepujacy fakt: na to, by ciag monotonicznych obwodow logicznych poprawnie testowal, czy w grafie o n^4 wierzcholkach istnieje klika n-elementowa, konieczne jest, by rozmiar obwodow rosl co najmniej wykladniczo wzgledem rozmiaru testowanego wejscia.
Jest to jedno z najsilnieszych dowiedzionych do tej pory dolnych ograniczen
w teorii zlozonosci, ktore bylo uwazane za powazny krok w kierunku
dowodu hipotezy P =/= NP. (Jesli opuscimy zalozenie o monotonicznosci
obwodow, otrzymamy hipoteze mocniejsza od hipotezy P =/= NP.)
Wiezy mnogosciowe w dowolnych strukturach
Wiezy mnogosciowe w dowolnych strukturach, zwane tez wiezami Tarskiego sa uogolnieniem pojecia wiezow mnogosciowych otrzymanym poprzez zastapienie uniwesum Herbranda przez dowolna strukture oraz przez dopuszczenie dodatkowych operacji punktu stalego.
Referat byl poswiecony przedstawieniu stanu wiedzy na temat zlozonosci obliczeniowej problemu rozwiazywania takich wiezow. W szczegolnosci zostaly przedstawione wczesniejsze wyniki D. McAllestera i D. Kozena na temat wiezow z operatorem punktu stalego oraz nowe wyniki P. Mielniczuka i autora referatu na temat wiezow bez takich operatorow.
Glowny wynik orzeka, ze problem niesprzecznosci wiezow Tarskiego jest w NEXPTIME
Slow kilka o prostych algorytmach rozwiazywania rownan na slowach
Wyszukiwanie wzorcow w skompresowanych obrazach
O kryptografii
Logiki monadyczne drugiego rzedu
O znajdowaniu maksymalnego trojkata w wielokacie wypuklym
Referat traktowal o typowym zagadnieniu z dziedziny geometrii obliczeniowej. Dany jest wielokat wypukly na plaszczyznie, problem polega na znalezieniu trojkata o maksymalnym polu zawartego w tym wielokacie. Poprzez fakt, ze istnieje trojkat o tej wlasnosci majacy wierzcholki w wierzcholkach wielokata, zagadnienie sprowadza sie do algorytmicznego problemu dyskretnego. Zakladajac, ze wielokat zdefiniowany jest za pomoca ciagu swoich wierzcholkow uporzadkowanego zgodnie z kolejnoscia wystepowania na brzegu, istnieje algorytm znajdujacy maksymalny trojkat o optymalnej zlozonosci liniowej. Oparty jest on na prostym fakcie matematycznym, ktory ograniczna liniowo ilosc trojkatow, ktore moga posiadac maksymalne pole. Algorytm przeglada tylko te trojkaty i porownuje ich pola. Glownym tematem referatu bylo przedstawienie tego algorytmu i uzasadnienie jego poprawnosci oraz zlozonosci.
Oboz byl finansowany z funduszu Rady Kol Naukowych UW.