Seminarium magisterskie

LOGIKA, TEORIA OBLICZEŃ I KRYPTOGRAFIA

Tradycyjnie, logika zajmowała się prawami myślenia. Współcześnie, informatyka stwarza możliwości przetwarzania informacji na wielką skalę również poza umysłem człowieka. Nic więc dziwnego, że rozwój informatyki stawia przed logiką nowe wyzwania i fascynujące problemy. Spośród wielu możliowści, wybraliśmy następujące zagadnienia.

Protokoły kryptograficzne Trudność obliczeniowa może być wykorzystywana pozytywnie, jako pewnego rodzaju energia zmagazynowana w problemie. Na problemach trudnych obliczeniowo oparte jest bezpieczeństwo ogromnej większości szyfrów stosowanych w praktyce. Jednym z najbardziej popularnych problemów tego typu jest problem faktoryzacji iloczynów dużych liczb pierwszych. Mamy do zaproponowania kilka tematów wokół zagadnienia faktoryzacji, w szczególności pytanie, jak wiele (szacunkowo) liczb potrafimy faktoryzować za pomocą już znanych algorytmów. Na seminarium zajmiemy się także innymi niż szyfrowanie protokołami kryptograficznym.  Konkretnie, chodzi o protokoły wykonywane przez grupy nieufających sobie nawzajem podmiotów (ang. secure multiparty computations).  Przykładem takich protokołów są protokoły głosowania elektronicznego. Możliwe są prace magisterskie o charakterze implementacyjnym polegające na zaprojektowaniu protokołu dla jakiejś konkretnej sytuacji lub prace teoretyczne.

Teoria złożoności opisowej Pytania o zależności między różnymi klasami złożoności (jak np. P, NP, PSPACE ) są podstawowymi pytaniami informatyki teoretycznej. Okazuje się, że problemy te są równoważne pytaniom o siłę wyrazu pewnych logik. Są to przeważnie rozszerzenia logiki pierwszego rzędu o różnego rodzaju operatory punktu stałego. Takie rozszerzone logiki mają też zastosowanie jako języki zapytań w bazach danych, a określenie siły wyrazu takich logik mówi o sile odpowiedniego języka zapytań.

Temporalne własności programów Oprogramowanie (np. systemy operacyjne) oraz sprzęt komputerowy (np. mikroprocesory) stały się na tyle skomplikowane, że przestaje być możliwe przekonanie się o ich poprawności tylko przy pomocy serii testów. Niezbędna staje się weryfikacja takich systemów oparta na bardziej niezawodnych metodach. Poszukuje się zatem sposobów matematycznego modelowania systemów, czego przykładem jest gra, potencjalnie nieskończona, systemu ,,przeciwko'' środowisku. W ramach tej tematyki będziemy zajmować się teorią automatów, terią gier nieskończonych, własnościami operatorów stałopunktowyh, rozstrzygalnymi teoriami logicznymi, logikami programów.

Stefan Dziembowski
Last modified: Sunday 13 April 17:11:58 CET 2003