Centrum Studiów Zaawansowanych oraz Centrum Informatyzacji Politechniki Warszawskiej zapraszają na seminaria semestru zimowego z cyklu: Wyzwania modelowania inżynierskiego i biznesowego.
Temat wykładu: Złamanie niedeterminizmu problemów NP-zupełnych – przyszłość modelowania matematycznego i obliczeń równoległych.
Pojęcie niedeterminizmu w algorytmice jest związane z powszechnie akceptowanym modelem obliczeń – maszyną Turinga. Potraktowanie problemów jako obiektów pozwoliło opisywać i analizować je metodami matematycznymi. Efektem takich badań, będących domeną teorii złożoności, jest szereg rezultatów udowodnionych, bądź będących hipotezami, ale także wiele pytań pozostających na dziś bez odpowiedzi. Do niewątpliwych osiągnięć teorii złożoności należy odkrycie klasyfikacji problemów wg kryterium trudności obliczeniowej. W uszeregowaniu tym istotną rolę odgrywa tytułowy niedeterminizm, będąc przy tym źródłem porażek teorii złożoności. Narracja walki odzwierciedla zmagania z fundamentalną kwestią P versus NP - pytaniem o charakter relacji między klasami problemów praktycznie rozwiązywalnych i problemów kwalifikowanych do trudnych.
Pozostające ciągle aktualnym pytanie o znaczenie obliczeń oraz naturę i ograniczenia algorytmów, prowokuje potrzebę refleksji nad statusem badań w tym zakresie. Przede wszystkim warto podjąć próbę określenia przyczyn niepowodzeń, a w kontekście kwestii P v NP, próbę określenia przyszłości informatyki w możliwej przecież erze post-niedeterministycznej.
Przedstawione w prezentacji, oparte o nowe modele, szkice koncepcji i rozwiązań kilku wybranych problemów, o spektakularnym znaczeniu dla przyszłości zastosowań informatyki – problemu spełnialności SAT, szczególnego przypadku problemu faktoryzacji mult(n), problemu nwd(a,b) i problemu pierwszości primes – mogą stanowić dobry przyczynek do takiej dyskusji, do której zaproszeniem jest tytuł prezentacji.
Autor: mgr inż. Marek Malinowski, Wydział Budownictwa, Mechaniki i Petrochemii w Płocku.
Organizatorzy: Centrum Studiów Zaawansowanych oraz Centrum Informatyzacji Politechniki Warszawskiej.
Koordynatorzy: mgr Ilona Sadowska (CSZ), dr hab. inż. Janusz Zawiła-Niedźwiecki, prof. nzw. PW (CI).
Gdzie?
Centrum Zarządzania Innowacjami i Transferem Technologii Politechniki Warszawskiej,
ul. Rektorska, 00-614 Warszawa, sala 4.01 (budynek obok Wydziału Inżynierii Lądowej PW, ul. Armii Ludowej 16).