Katedra Algorytmiki:
W Katedrze Algorytmiki realizowano zadania badawcze dotyczące algorytmów geometrii obliczeniowej, grafowych algorytmów on-line, algorytmów testujących izomorficzność struktur skończonych oraz teorii modeli skończonych prawa zerojedynkowe i gęstości asymptotyczne (projekt badawczy KBN Nr 2 P03A 031 09). Ponadto badania Katedry dotyczyły enumeracji algebraicznych struktur skończonych, złożoności generatywnej (projekt badawczy KBN Nr 5 P03A 040 21), złożoności obiektowej (projekt badawczy KBN Nr 7 T11C 022 21) i siły ekspresji logik zdaniowych (projekt badawczy KBN Nr 1 H01A 001 12). Do najważniejszych osiągnięć naukowych należy zaliczyć uzyskanie szybkich algorytmów liczących grupy homologii kompleksu kostkowego i odwzorowania symplicjalnego, podanie szybkich algorytmów typu on-line dla wyznaczania minimalnych pokryć klikowych w grafach interwałowych i łukowych oraz uzyskanie dolnych ograniczeń złożoności dla problemu testowania izomorfizmu skończonych grup nilpotentnych. Dokonano również klasyfikacji rozmaitości algebr z wielomianową (w zależności od liczby generatorów) ilością modeli, scharakteryzowano modularne rozmaitości algebr z pojedynczo wykładniczą ilością modeli, pokazano istnienie continuum niezależnych miar złożoności obiektowej, podano charakteryzację siły ekspresji Fregowskich logik zdaniowych w terminach semantycznych i wykazano brak praw zbieżności dla monadycznej logiki drugiego rzędu nad grupami skończonymi.
Katedra Informatyki Stosowanej:
W Katedrze Informatyki Stosowanej realizowano zadania badawcze dotyczące następujących zagadnień: konstrukcja efektywnych parserów języków grafowych i ich atrybutowanych rozszerzeń (gramatyki ETPL(k) i stochastyczne gramatyki ETLP(k)), konstrukcja efektywnych paserów języków ciągowych (gramatyki DPLL(k)), zastosowania modeli syntaktycznego rozpoznawania obrazów komputerowych w systemach monitoringu i diagnostyki złożonych systemów oraz konstrukcja hybrydowych systemów ekspertowych czasu rzeczywistego, wykorzystujących podsystemy syntaktycznego rozpoznawania obrazów. Ponadto badano zastosowania sieci neuronowych w diagnostyce i leczeniu chorób psychicznych, a także wykorzystanie architektur wielo-agentowych dla konstrukcji inteligentnych systemów monitorujących i diagnozujących. W wyniku realizacji zadań badawczych opracowano model hybrydowy systemu ekspertowego czasu rzeczywistego monitorującego i diagnozującego aparaturę typu przemysłowego, a następnie zaproponowano implementację takiego systemu i dokonano pozytywnej weryfikacji jego działania. Opracowany model bazuje na architekturze wieloagentowej i wykorzystuje różne metody sztucznej inteligencji w tym podejście regułowe oraz metody syntaktycznego rozpoznawania obrazów. Weryfikacja praktyczna modelu odbyła się poprzez projekt i implementację systemu ekspertowego ZEX (ZEUS Expart System) monitorującego w czasie rzeczywistym pracę detektora wysokich energii ZEUS w Deutsches Elektronen Synchrotron w Hamburgu. Badania były finansowane przez Stiftung fur deutsch-polnische Zusammenarbeit (1441/94/LN) w ramach grantu: Ein komplexes Computer-System zur Diagnose, Kontrolle und Analyse der Datenqualitat des ZEUS-Experiments am HERABeschleuniger. Główne wyniki badań naukowych w Katedrze Informatyki Stosowanej:
Katedra Metod Numerycznych:
W latach 2000-2002 Katedra Metod Numerycznych prowadziła badania w zagadnieniach dotyczących ścisłych metod numerycznych dla układów dynamicznych oraz równań różniczkowych, pozwalających na uzyskiwanie komputerowo wspieranych dowodów twierdzeń charakteryzujących zachowanie asymptotyczne równań różniczkowych: istnienie i lokalizacja trajektorii okresowych, heteroklinicznych oraz chaotycznych zbiorów niezmienniczych. Badania te wymagały w szczególności rozwinięcia algorytmicznego podejścia do metod topologii algebraicznej stosowanych w takich badaniach. W szczególności opracowano i zaimplementowano algorytmy wyznaczania homologii zbiorów kostkowych oraz homologii odwzorowań ciągłych pomiędzy zbiorami kostkowymi. Udowodniono poprawność działania tych algorytmów i przeanalizowano od strony praktycznej ich złożoność i użyteczność. Następnie na ich bazie opracowano algorytmy wyznaczające niezmienniki topologiczne układów dynamicznych co pozwoliło na konstrukcję nowych komputerowo wspieranych dowodów. W szczególności przeprowadzono dowód istnienia trajektorii okresowych w równaniach Rosslera dla wartości parametrów badanych metodami klasycznej analizy numerycznej przez Hale'a i Kocaka. Udowodniono też istnienie heteroklinicznych połączeń w równaniu Kuramoto-Shivasinsky'ego. Oprócz dziedzin opisanych powyżej, przedmiotem badań były zastosowania równań różniczkowych w technice oraz problemy teorii zagadnień brzegowych dla równań różniczkowych zwyczajnych. Wykazano istnienie i jednoznaczność rozwiązania problemu mieszanego dla równania nieliniowego typu parabolicznego modelującego proces filtracji, zbieżność metody Faedo-Galerkina dla tego równania oraz istnienie i jednoznaczność rozwiązania zagadnienia mieszanego dla równania hiperbolicznego o współczynnikach dystrybucyjnych, sprzężonego z układem równań zwyczajnych, opisującego drgania układu mechanicznego dyskretno ciągłego. Podano warunki istnienia rozwiązań zagadnień brzegowych dla równań zwyczajnych (rzędów dwa i wyższych) w przypadku gdy równania dopuszczają istnienie rozwiązań dolnych i górnych. Ponadto przedmiotem badań była matematyczna teoria nierówności hemiwariacyjnych. Z tego zakresu uzyskano wyniki egzystencjalne dla nierówności hemiwariacyjnych typu hiperbolicznego oraz rezultaty o istnieniu rozwiązań optymalnych w problemach sterowania dla układów opisywanych przez nierówności
hemiwariacyjne.
Katedra Optymalizacji i Sterowania:
W latach 2000-2002 w Katedrze Optymalizacji i Sterowania realizowano badania naukowe dotyczące problemów sterowania optymalnego dla układów opisywanych równaniami różniczkowymi cząstkowymi, nierównościami wariacyjnymi i hemiwariacyjnymi oraz badania dotyczące modelowania matematycznego zagadnień występujących w biologii, fizyce, informatyce, medycynie i ekonomii. W wyniku realizacji zadań dotyczących zagadnień sterowania optymalnego dla układów opisanych przez równania różniczkowe cząstkowe oraz nierówności wariacyjne i hemiwariacyjne, uzyskane rezultaty dotyczą kilku klas problemów sterowania optymalnego pojawiających się w modelach procesów fizycznych związanych ze zmianą fazy (równania z histerezą) oraz w zagadnieniach mechaniki i inżynierii opisywanych przez niegładkie i niewypukłe funkcjonały energii (nierówności hemiwariacyjne). Przeprowadzono badania dotyczące istnienia rozwiązań optymalnych w problemach sterowania, relaksacji problemów sterowania i charakteryzacji rozwiązań optymalnych. W szczególności zbadano zagadnienia optymalizacji kształtu, problemy identyfikacji parametrów fizycznych w ośrodkach niejednorodnych, równania z operatorami histerezy oraz zadania relaksacji w sterowaniu optymalnym, zadania wrażliwości układu sterowania na zaburzenia występujące w danych, a także podano warunki konieczne optymalności i rezultaty o zbieżności par optymalnych. W zakresie modelowania zagadnień biologicznych realizowano projekt dotyczący wyznaczania współczynników umieralności w modelach populacyjnych. Do interesujących rezultatów należy zaliczyć opracowanie matematycznych modeli mechaniki opisu dynamicznych zjawisk kontaktowych z tarciem i bez tarcia oraz zjawisk lepkościowych dla struktur lepkosprężystych. Uzyskano także wyniki dotyczące istnienia rozwiązań, ich jednoznaczności i ciągłej zależności rozwiązania od danych dla modeli ośrodków półprzepuszczalnych występujących w zadaniach przewodnictwa cieplnego, hydraulice i elektrostatyce oraz w modelowaniu tzw. materiałów inteligentnych. Zespół badawczy prowadził również badania dotyczące konstrukcji algorytmów równoległych w zadaniach optymalizacji globalnej oraz wykorzystania algorytmów genetycznych w zadaniach źle postawionych problemów odwrotnych parametrycznych. Podano metody aproksymacji numerycznych dla eliptycznych nierówności hemiwariacyjnych oraz opracowano technikę komputerowej reprezentacji kształtu w zadaniach numerycznego rozwiązywanie zadań optymalizacji kształtu. Przeprowadzono analizę wrażliwości modeli na zaburzenia występujące w danych. Analiza taka dostarcza informacji o tolerancji w specyfikacji danych w zagadnieniu oraz jest użyteczna przy tworzeniu algorytmów numerycznych. Na uwagę zasługuje fakt, że uzyskane wyniki mają nie tylko istotne znaczenie teoretyczne, ale posiadają istotną wartość z punktu widzenia zastosowań.
Zakład Humanistycznych Zastosowań Informatyki:
Zakład Humanistycznych Zastosowań Informatyki zrealizował następujące zadania badawcze: modele procesu projektowania, zastosowania metod ewolucyjnych w projektowaniu form przemysłowych oraz modele formalne projektowania z wykorzystaniem diagramów. W zakresie pierwszego z wymienionych zadań opracowano nowy model procesu projektowego wykorzystujący grafy hierarchiczne. Przy wykorzystaniu teorii kategorii udowodniono własności grafów hierarchicznych. Ponadto, zaproponowano nową klasę grafów hierarchicznych. Wyniki w tym zakresie były prezentowane na konferencji
"Advances in Intelligent Computing in Engineering" w sierpniu 2002 w Darmstadt. Do testowania zaproponowanego modelu zaimplementowano system komputerowy generowania rozkładów pomieszczeń. W ramach realizacji zadania
"Zastosowania metod ewolucyjnych w projektowaniu form przemysłowych" zaproponowano nowatorską reprezentację genotypów w postaci grafów. Grafowe operatory mutacji oraz krzyżowania wymagały nowych definicji oraz zbadania złożoności algorytmów, w których znalazły zastosowanie. Zaimplementowano także komputerowy system projektowania krzeseł i z jego wykorzystaniem dokonano weryfikacji modelu. W wyniku realizacji kolejnego zadania powstał model formalny projektowania z wykorzystaniem diagramów Model ten stanowi rozszerzenie istniejącego modelu logicznego wnioskowania z diagramami, np. diagramami Venna czy grafami Eulera. W modelu wykorzystano logikę modalną zaproponowano nowe definicje konwencji semantycznej, metody operacji oraz wymagań projektowych. Model ten stanowi podstawy teoretyczne systemów komputerowych wspomagających projektowanie i systemów opartych o struktury dynamiczne.
Zakład Matematyki Dyskretnej:
W latach 2000-2002 Zakład Matematyki Dyskretnej realizował zadania badawcze w zakresie kombinatorycznej teorii półgrup, kombinatoryki na słowach oraz teorii języków formalnych i algebraicznej teorii kodowania. Zadania dotyczące kombinatorycznej teorii półgrup i kombinatoryki na słowach były kontynuacją badań w zakresie retraktów wolnych monoidów, a także dotyczyły asymptotycznych własności słów otrzymywanych jako nieskończone iteraty homomorfizmów wolnych monoidów. W zakresie teorii języków formalnych i algebraicznej teorii kodowania badano kodowanie dwuwymiarowe i n-wymiarowe oraz rozmaitości języków. Wyniki otrzymane w powyższej tematyce są następujące:
Zakład Podstaw Informatyki:
Zakład Podstaw Informatyki prowadził prace nad teorią obliczeń, programowaniem funkcyjnym, lambda rachunkiem z typami, programowaniem w logice, automatycznym dowodzeniem twierdzeń, asymptotycznymi własnościami logik, zastosowaniami kombinatoryki w programowaniu funkcyjnym, sieciami komputerowymi, systemami rozproszonymi, systemami sztucznej inteligencji, algorytmami rozproszonymi, algorytmy grafowymi, zastosowaniem teorii kategorii i teorii dziedzin. Uzyskano wyniki w ramach grantów KBN 8 T11C 018 16
"Prosty Rachunek lambda jako podstawa do programowania wyższego rzędu". Uzyskano rezultaty dotyczące problemu zliczania dla logik zdaniowych. Pokazano, że dla jednej zmiennej zdaniowej wraz ze spójnikami implikacji i negacji obowiązuje prawo zbieżności dla tautologii. Pokazano, że istnieje granica ilorazu ilości tautologii do ilości wszystkich formuł. W ramach grantu ukończona została praca doktorska mgr Małgorzaty Moczurad, a w marcu 2000 odbyła się publiczna obrona. W ramach grantu KBN 7 T11C 022 21
"Złożoność obiektowa i asymptotyczna gęstość" uzyskano rezultaty dotyczące charakterystyki miar złożoności obiektów. Pokazano prawa zbieżności dla logik klasycznych. Pokazano także ilościową charakterystykę porównawczą logiki klasycznej z intuicjonizmem. Pokazano rozkład gęstości dla prostych tautologii klasycznych. Kontynuowano badania nad zastosowaniem teorii sieci Markowa do modelowania obliczeń rozproszonych. Kontynuowane były również badania nad sieciami pracującymi w czasie rzeczywistym, modelowaniem sieci komputerowych i ocena ich działania również dla obliczeń rozproszonych. Rozpoczęto badania nad ilościową teorią dziedzin, przestrzeniami semimetrycznymi, modelowaniem przestrzeni topologicznych przy pomocy n dziedzin. W ramach prac nad teorią obliczeń powstał podręcznik akademicki
"Wybrane zagadnienia z teorii rekursji".
Zakład Rozpoznawania i Przetwarzania Obrazów:
Zakład Rozpoznawania i Przetwarzania Obrazów prowadził badania w problematyce dotyczącej algorytmów równoległych, algorytmów genetycznych, sieci neuronowych, systemów agentowych oraz algorytmów rozpoznawania kształtów. Realizowane zadania badawcze obejmowały metody rozwiązywania źle postawionych problemów odwrotnych parametrycznych, algorytmy równoległe i rozpraszanie obliczeń w zadaniach optymalizacji, syntaktyczno-strukturalne kształtów planarnych. W zakresie sieci neuronowych zbadano następujące zagadnienia: reprezentacja danych wejściowych w warstwowych sieciach neuronowych, neuronowe algorytmy rozpoznawania twarzy, budowa hybrydowych systemów łączących w sobie zarówno typowe sieci neuronowe, jak i wcześniej znaną w postaci reguł wiedzę wbudowywaną w projekt, teoretyczne problemy definiowania warstwowych sieci neuronowych i ich nauczania przez formalizm grafów oraz zastosowanie sieci neuronowych dla budowy modeli statystycznych. W zakresie algorytmów genetycznych zbadano własności miar próbkowania w genetycznych algorytmach przeszukujących dziedziny metryzowalne, wykorzystano regularności miar próbkowania dla konstrukcji genetycznych algorytmów dwufazowych, opracowano hierarchiczne metody obliczeń genetycznych oraz zastosowano algorytmy genetyczne do rozwiązywania zadań identyfikacji i zadań projektowania optymalnego. Opracowane zostały również genetyczne metody klastrowania, podano twierdzenie aproksymacyjne dla punktów stałych heurystyki prostego algorytmu genetycznego oraz twierdzenia o zbieżności aproksymacji miar próbkowania dla stochastycznych algorytmów optymalizacji globalnej opartych o próbkowanie genetyczne i afiniczne kodowanie binarne. Opracowano również metody rozpoznawania centralnych części basenów przyciągania (klastrów) przy pomocy próby losowej przetwarzanej genetycznie. Ponadto zbadano efektywne techniki reprezentowania i poszukiwania klastrów w zadaniach o dużej liczbie wymiarów i dokonano weryfikacji poprawności warunku stopu dla tych strategii w oparciu o twierdzenie aproksymacyjne i twierdzenie o zbieżności miar próbkowania. W zakresie hierarchicznych obliczeń genetycznych skonstruowano nowe strategie hierarchiczne dla efektywnego rozwiązywania trudnych (wielomodalnych) zadań optymalizacji globalnej w dziedzinach metryzowalnych oraz zbadano wydajność tych strategii. Algorytmy genetyczne zastosowano do rozwiązywania zadań identyfikacji i zadań projektowania optymalnego. Dokonano identyfikacji nieliniowej przewodności w gruntach spoistych, znaleziono optymalne poprawki dla Coordinate Measuring Machine oraz wyznaczono optymalne napicia konstrukcji cięgnowych. W zakresie syntaktyczno-strukturalnego rozpoznawania kształtów planarnych dokonano praktycznej implementacji elementów formalizmu opisu kształtów Jakubowskiego, w tym rozszerzono istniejący formalizm na kształty o złożonej topologii, pokazano uniezależnienie formalizmu od położenia początkowego kształtu względem obrotu, opracowano wnioskowanie cech kształtu opisanych wyrażeniami regularnymi, opracowano i podano szkieletową realizację bazy wiedzy kształtów planarnych. Podstawowe wyniki z zakresu szeregowania prac i zarządzania obliczeniami rozproszonymi są następujące: opracowanie modelu formalnego przetwarzania współbieżnego wielkich zadań klasy CAE opartego o teorie śladów oraz model obliczeń rozproszonych Charron Delporte, opracowanie modelu stochastycznego obciążenia tła, opracowanie i testowanie wielopoziomowych strategii zarządzania aplikacjami rozproszonymi wykorzystującymi prognozy stochastyczne na najwyższym poziomie, algorytmy greedy na środkowym oraz migrację zadań na najniższym. Ponadto prace dotyczyły następujących zagadnień: szeregowanie prac i zarządzanie obliczeniami rozproszonymi, architektury obiektowo zorientowane i wieloagentowe rozproszonych systemów CAE, modelowanie geometryczne i optymalna dekompozycja geometryczna w zadaniach analizy struktur 3D, strategie generacji i adaptacji siatek obliczeniowych, modele przepływu krwi i modele ścianki w centralnym układzie krwionośnym człowieka.
Zakład Teorii Prawdopodobieństwa:
W latach 2000-2002 Zakład Teorii Prawdopodobieństwa prowadził badania w zakresie zastosowań procesów stochastycznych w opisie pracy sieci komputerowych, w zakresie istnienia absolutnie ciągłych miar niezmienniczych dla wielowymiarowych transformacji typu Markowa, zastosowań algorytmów genetycznych w złożonych obliczeniach oraz nad matematycznymi modelami niecek osiadania powstałych pod wpływem eksploatacji węgla.
Zakład Zastosowań Metod Numerycznych:
Zakład Zastosowań Metod Numerycznych realizował w latach 2000-2002 następujące zadania badawcze: wyznaczanie funkcji struktury fotonu, analiza strategii i potencjału detektorów LHC i Tevatron dla odkrycia cząstki Higgsa i konstrukcja generatora Monte Carlo dla potrzeb eksperymentów fizyki cząstek. W zakresie realizacji powyższych zadań osiągnięto następujące wyniki: wyznaczono funkcje struktury elektronu i wykonano ich opis teoretyczny oraz wzięto udział w pierwszym pomiarze doświadczalnym funkcji struktury elektronu w eksperymencie LEP w CERNie, Genewa oraz skonstruowano generator Monte Carlo AcerMC do symulacji procesów zderzeń proton-proton i proton-antyproton.