»   informatyka analityczna

»   studia II stopnia

Program studiów II stopnia

Przedmioty fakultatywne (do wyboru)

Seminaria (do wyboru)

Język angielski

Kurs BHK

Ochrona własności intelektualnej

Złożoność obliczeniowa

Przedmioty fakultatywne (do wyboru)

Seminaria (do wyboru)

Filozofia

Przedmioty fakultatywne (do wyboru)

Seminaria (do wyboru)

Przedmioty fakultatywne (do wyboru)

Seminaria (do wyboru)

Praca magisterska oraz przygotowanie do egzaminu

Przedmioty obieralne w toku studiów II stopnia

Przedmioty fakultatywne

Algorytmy aproksymacyjne

Algorytmy geometryczne

Algorytmy grafowe

Algorytmy probabilistyczne

Algorytmy równoległe

Algorytmy tekstowe

Algorytmiczna teoria gier

Finite model theory

Implementacja algorytmów

Kodowanie informacji

Przedmioty fakultatywne (c.d.)

Kompilatory

Laboratorium sieci neuronowych

Optymalizacja dyskretna

Programowanie funkcyjne

SAT solvery

Strukturalna teoria grafów

Teoria informacji

Teoria programowania w logice

Uczenie maszynowe

Weryfikacja oprogramowania

Seminaria

Algebra i logika w informatyce

Algorytmika

Alg. randomizowane i aproksymacyjne

Optymalizacja kombinatoryczna

Paradygmaty języków programowania

Podstawy informatyki

Krótkie opisy niektórych kursów

Algorytmy aproksymacyjne

Każdy z nas chce rozwiązywać problemy szybko i dokładnie. Niestety czasem tak się nie da. Przykładem takiej sytuacji jest problem komiwojażera. W problemie tym obwoźny sprzedawca poszukuje najkrótszej trasy, która pozwoli mu odwiedzić każde miasto dokładnie raz. Niestety nie jest znany algorytm, który w szybkim czasie wyznaczy optymalną najkrótszą trasę dla sprzedawcy. W takich sytuacjach albo decydujemy się bardzo długo czekać na dokładne rozwiązanie problemu (zwykle podejście nieakceptowalne) albo wykorzystujemy algorytm aproksymacyjny, który działa szybko, ale zwraca nam wynik przybliżony. W ramach kursu nauczysz się konstruować takie algorytmy i mierzyć ich efektywność.

Algorytmy grafowe

Grafy są wszechobecne – opisują różne obiekty oraz relacje między nimi. Aby przeanalizować zadany graf stosujemy najczęściej przeglądanie grafu w szerz albo w głąb. Okazuje się, że są inne użyteczne metody, na przykład algorytm LexBFS. Poznamy jego różne zastosowania, w szczególności magiczny algorytm rozpoznający, czy podany graf ma reprezentację przedziałową. A teraz zapytajmy się czy dany graf jest planarny, tzn. czy da się go narysować tak, aby żadne jego krawędzie się nie przecinały. Napisanie algorytmu, który odpowiada na to pytanie nie jest łatwe. Jednakże przy odrobinie wysiłku napiszemy algorytm, który w szybkim czasie narysuje nasz graf bez przecięć albo powie, że się nie da. Dowiemy się także jak narysować graf planarny na możliwie małej powierzchni.

Teoria programowania

Znajomość ograniczeń jakie niesie ze sobą informatyka pozwala trafnie ocenić skalę trudności zadawanych informatycznych pytań. Zobaczysz, że problem „czy program się zatrzymuje” wykracza poza metodykę informatyki. Na wykładzie poznasz tezę Churcha–Turinga, oraz formalizmy, które ją potwierdzają. Poznasz problemy informatyczne i matematyczne, których nie da się rozwiązać metodami informatycznymi. Co więcej, poznasz techniki wskazywania, jak takie problemy znaleźć i jak pokazać, że mają pozainformatyczną naturę. Poznasz też hierarchię trudności takich problemów.

Laboratorium sieci neuronowych

Wyobraź sobie, że masz napisać program rozpoznający jaka cyfra jest narysowana w obrazku podanym na wejściu. Nawet jeśli obrazki są bardzo jednorodne (ta sama wielkość, cyfry wycentrowane wszystkie napisane czarnym markerem na białym tle), to wciąż nie bardzo wiadomo jak zacząć. A co jeśli na wejściu mamy zdjęcia jednego z dziesięciu rodzajów obiektów: kota, psa, żaby, samolotu, itp? Podane przykłady to standardowe problemy klasyfikacji obrazów. W ciągu ostatnich kilku lat nastąpiła rewolucja w efektywności programów rozwiązujących takie problemy. U podstaw tej rewolucji leżą sieci neuronowe. Ich orędownicy opowiadają, że taka sieć działa (i uczy się) jak mózg człowieka! Chcesz się dowiedzieć więcej? Zapraszam na kurs.

SAT solvery

Problem spełnialności formuł rachunku zdań (w skrócie SAT) jest jednym z najważniejszych problemów informatyki. Jego uniwersalność polega na tym, że da się w nim zapisać wiele innych problemów: np. problem komiwojażera. Można również skonstruować formułę rachunku zdań, która jest spełnialna wtedy i tylko wtedy, gdy dany układ cyfrowy lub program jest sprawny. Programów rozwiązujących instancje problemu SAT (ang. SAT solvers) używa się również m.in. w szeregowaniu zadań, systemach wieloagentowych i e-commerce. Celem kursu jest napisanie współczesnego SAT solvera.

Algorytmy probabilistyczne

Zdawać by się mogło, że Informatyka i Prawdopodobieństwo to dziedziny jak najbardziej odległe. Wszak tam, gdzie króluje niezawodność i precyzja, nie powinno być miejsca na przypadkowość. Tymczasem okazuje się, że umiejętne wykorzystanie zjawisk losowych pozwala konstruować świetnie działające algorytmy rozwiązujące istotne problemy, często najskuteczniej jak to tylko możliwe.  Na tym kursie dowiesz się jak ujarzmiony przypadek służy kryptografii, statystyce, czy grafice komputerowej. Poznasz algorytmy losowe typu Las Vegas i Monte Carlo wykorzystywane do sprawdzania pierwszości liczb, szybkiego sortowania, czy znajdowania minimalnego przekroju w grafach.

Teoria programowania w logice

Wprowadzona zostanie logika formalna i powstały na jej bazie język programowania PROLOG oraz zręby programowania w językach funkcyjnych. Zobaczysz jak działają metody automatycznego dowodzenia twierdzeń i jak można ich użyć do badania własności baz danych. Poznasz budowę semantyki dla programów logicznych.

Finite model theory

Teoria złożoności obliczeniowej dzieli problemy obliczeniowe na klasy ze względu na zasoby potrzebne do ich rozwiązania.  W tym kontekście najbardziej znane jest pytanie o to, czy P = NP. Na gruncie logiki matematycznej pyta się o najsłabszy formalizm (logikę) potrzebną aby wyrazić rozważany problem. Rozpatruje się logikę pierwszego rzędu, która ma bardzo ograniczoną siłę wyrazu, mniejszą niż znany z baz danych SQL (w istocie SQL powstał jako uogólnienie tejże), logikę drugiego rzędu, która zawiera wszystkie problemy z NP itd. itp.  Uczestnik kursu uczy się wyrafinowanych metod, które pozwalają na  badanie złożoności problemów obliczeniowych z punktu widzenia logiki matematycznej.

Seminarium: Algebra i logika w informatyce

Problem spełnialności więzów jest jednym z najważniejszych problemów zarówno informatyki teoretycznej jak i zastosowań informatyki. Ze względu na to, że problem ten jest obliczeniowo trudny, rozważa się jego prostsze wersje poprzez nakładanie ograniczeń na relacje wykorzystywane w więzach lub na kształt wejścia. Pełną klasyfikację złożoności obliczeniowej w pierwszej wersji (problem jest w P lub jest NP-zupełny) udało się uzyskać dzięki metodom algebry uniwersalnej, w drugim przypadku dzięki logice matematycznej. Na seminarium rozważamy problemy podobne do problemów spełnialności więzów i szukamy odpowiednich klasyfikacji.

Seminarium: Podstawy informatyki

Jest to seminarium badawcze. Prezentowane są współczesne prace dotyczące teorii obliczeń, rachunku lambda, logik programów, programowania w logice, programowania funkcyjnego, problemów zliczania w rachunkach logicznych i związaną z tym problematyką asymptotycznej gęstości.

Strukturalna teoria grafów

Twierdzenie Roberstona-Seymoura jest jednym z najgłębszych wyników w teorii grafów. Mówi ono, że w każdej nieskończonej rodzinie skończonych grafów znajdziemy takie dwa, że jeden z nich zawiera drugi jako minor. Oryginalny dowód tego twierdzenia jest zawarty w serii ponad 20 prac i zajmuje około 750 stron. Prace nad tym dowodem dały początek zupełnie nowej teorii, która znalazła wiele zastosowań i jest aktualnym tematem badawczym w kombinatoryce i informatyce teoretycznej. Na kursie poznasz wybrane zagadnienia tej teorii, między innymi strukturalne parametry grafowe i ich związki z zabronionymi minorami, własność Erdősa-Pósy, czy zastosowanie matroidów w teorii grafów.

© 2018 Theoretical Computer Science @ UJ

web design by