Programy naukowe
Poniżej przedstawiamy przykładowe programy w C, C++ oraz w Pythonie, wykonane przez nas w ramach pracy naukowej oraz nauczania akademickiego. Obrazują one rozmaite rozwiązania algorytmiczne oraz wykorzystują nowoczesne rozwiązania z dziedziny informatyki teoretycznej.
Balance - sieć neuronowa Kohonena
Aplikacja Balance rozwiązuje problem równoważenia słupa przy użyciu sieci neuronowej.
Problem polega na utrzymaniu w równowadze pionowego słupa, mając do
dyspozycji tylko wózek zamocowany do jego podstawy. O tym, jak ciężko
jest wykonać takie zadanie, można przekonać się, próbując utrzymać na
dłoni ustawiony pionowo kawałek pręta. Zastosowano w tym programie samouczącą
się sieć Kohonena. W sieci tej mamy do czynienia z uczeniem
konkurencyjnym. Oznacza to, że do dyspozycji przy uczeniu sieć ma tylko
dane wejściowe i nie zna najlepszych odpowiedzi. Zadaniem sieci w
trakcie procesu uczenia jest wytworzenie wzorców reakcji na bodźce. Dla danego
stanu belki sieć stara się uzyskać coraz lepsze przybliżenia siły potrzebnej do
zrównoważenia wychylenia poprzez subtelne zmiany znanych odwzorowań - jeśli
przyłożenie nowej siły skutkuje lepszą kontrolą nad belką, odwzorowanie jest modyfikowane. W ten sposób sieć sama uczy się, co należy robić, aby utrzymać belkę w pozycji pionowej i przeciwdziałać losowym zaburzeniom.
Program napisany w języku C++ oraz wykorzystujący framework QT dla systemów operacyjnych Windows i Linux.
Pożar Lasu - stochastyczny automat komórkowy
Program wykorzystujący stochastyczny automat komórkowy do modelowania rozprzestrzeniania się ognia w lesie.
Ogień rozprzestrzenia się szybciej w kierunku podmuchów wiatru i może samoczynnie zaniknąć w przypadku pogody bezwietrznej.
Podłoża charakteryzują się różną zapalnością: pożar wyschniętej trawy
jest błyskawiczny, natomiast drzewa potrzebują dłuższego czasu na podpalenie.
Płoną jednak dłużej i w wyższej temperaturze. Dodatkowo zastosowano generator losowego terenu,
Å‚Ä…cznie z rzekami i erozjÄ… gleby.
Program napisany w języku C++ dla systemu Windows.
Problem komiwojażera - algorytm brute force
Użycie algorytmu brute force dla słynnego problemu znalezienia najkrótszej drogi między zadanymi miastami - problemu komiwojażera. Jest to problem NP-zupełny, co oznacza, że rozwiązanie dokładne wymaga sprawdzenia wszystkich możliwości, co wykonalne jest jedynie dla bardzo małych grafów. Pomimo dobrej optymalizacji, dla N=12, program działa około minuty, natomiast dla N=13 już około 10 minut.
Program umożliwia dokładne rozwiazanie zadania określenia najkrótszej drogi między punktami w ukladzie X/Y z ustalonym punktem startu. Jako wynik generuje zestaw plików dla programu gnuplot w celu zobrazowania wyniku.
Pobierz komidoc.zipProblem komiwojażera - symulowane wyżarzanie
Innym sposobem na rozwiązanie problemu komiwojażera jest użycie algorytmu heurystycznego, pozwalającego na znalezienie w krótkim czasie rozwiązania bliskiego optymalnemu. Popularnym algorytmem heurystycznym, używanym do rozwiązania tego problemu jest algorytm symulowanego wyżarzania. Przyjmuje on najpierw losową konfigurację początkową, a następnie przeszukuje przestrzeń alternatywnych rozwiązań problemu w celu osiągnięcia najlepszego wyniku. Podczas pracy algorytmu testuje się podmiany losowych połączeń - jeśli otrzymana w ten sposób droga jest krótsza, pozostawia się ją, jeśli natomiast jest dłuższa, jej pozostawienie jest kwestią losową, uzależnioną od temperatury układu. Parametr temperatury pozwala określić, jak bardzo odległe połączenia mają szansę na losowe uzględnienie do grafu drogi. Losowe zmiany takie, mimo iż lokalnie psują ustaloną ścieżkę, pozwalają na odnalezienie rozwiązania bardziej globalnego. Wraz ze schładzaniem układu, możliwe stają jedynie zamiany poprawiające długość drogi, lub pogarszające ją bardzo nieznacznie.
Nazwa "symulowane wyżarzanie" związana jest z podobieństwem tego algorytmu do procesu wyżarzania metali, w którym poprzez powolne studzenie metal przechodzi od fazy płynnej do struktury krystalicznej o najniższej energii.
Uwzględniono zapis bieżącej pracy algorytmu (aktualnych wartości parametrów) jak i listę wyników.
Język: python, PyQt
Åšrodowisko: Linux/Windows
Gramatyka grafowa
Gramatyka grafowa służy jako narzędzie formalne do opisu alokacji
systemów planowania i kontroli procesów przemysłowych.
W przykładzie pokazano uproszczą wersję planowania zabudowy parku.
Budowa grafu oraz wygenerowany plan parku.
Język: python, PyQt
Åšrodowisko: Linux/Windows
Gramatyka kształtu
Zobrazowanie przestrzennej zabudowy wzdłuż ulicy.
Język: python, PyQt
Åšrodowisko: Linux/Windows