O obliczaniu skojarzeń w rozproszonym modelu obliczeń

Prelegent: dr hab. Michał Hanćkowiak, prof. UAM (Zakład Teorii Algorytmów i Bezpieczeństwa Danych)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  22 października 2019 r., g. 12:30

Streszczenie: Zamierzam pokazać postęp jaki się dokonał w ostatnich 15 latach, jeśli chodzi o obliczanie skojarzeń (i podobnych problemów) w rozproszonym modelu obliczeń. Jako przykłady przedstawię dwa rozproszone algorytmy obliczania skojarzeń: pierwszy, działający w czasie O(log^4(n)) oraz drugi, wykorzystujący do pewnego stopnia narzędzia użyte do konstrukcji pierwszego, o znacząco lepszym czasie działania.

Podzielne szeregowanie zadań z pozycyjno-zależnymi czasami wykonywania na dwóch równoległych identycznych maszynach (prezentacja wyników rozprawy doktorskiej)

Prelegent: mgr Marcin Żurowski (Zakład Algorytmiki i Metod Numerycznych)
Miejsce: Sala seminaryjna B1-37
Data i godzina:  14 maja 2019 r., g. 13:00

Streszczenie: Przedstawione zostaną własności pewnego problemu szeregowania podzielnych zadań pozycyjno-zależnych na dwu identycznych równoległych maszynach z kryterium minimalizacji długości uszeregowania oraz, na bazie tych własności, dwa algorytmy dokładne i dwa algorytmy heurystyczne dla rozważanego problemu

Rząd pewnych kombinacji macierzy

Prelegent: Prof. UAM Tomasz Szulc
Miejsce: B1-7/8
Data i godzina:  14 maja 2019 r., g. 12:30

Streszczenie: Przedstawione zostaną nowe wyniki, otrzymane wspólnie  z prof. Charlesem R. Johnsonem (College of William and Mary, Williamsburg, USA) oraz prof. Juanem M. Peną (Uniwesytet w Saragossie, Hiszpania), dotyczące problemu odporności rzędu macierzy na pewne zaburzenia jej elementów. Rozważa się pełność rzędu kwadratowych kombinacji trzech macierzy oraz pełność rzędu pewnych uogólnień tych kombinacji. Odpowiada się również na pytanie kiedy wszystkie wypukłe kombinacje dwóch macierzy rzędu 1 są rzędu 1.

Spectra of tridiagonal matrices

Prelegent: Professor Charles R. Johnson (College of William and Mary, Williamsburg, USA)
Miejsce: Sala posiedzeń Rady Wydziału
Data i godzina:  28 maja 2019 r., g. 12:00

Abstract: We discuss the possible spectra of tridiagonal matrices over a field and the possible Jordan structure. We also discuss „arrow matrices” and their Jordan structure by contrast.

Szeregowanie zadań czasowo-zależnych w systemie otwartym

Prelegent: prof. UAM Stanisław Gawiejnowicz
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  2 kwietnia 2019 r., g. 12:30

Streszczenie: System otwarty jest jednym z trzech głównych środowisk maszyn dedykowanych. W referacie przedstawione zostaną pewne nowe wyniki dotyczące szeregowania w tym środowisku zadań z czasowo-zależnymi proporcjonalnymi czasami wykonywania.

Scheduling in a data gathering network to minimize maximum lateness

Prelegent: dr Joanna Berlińska
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  12 marca 2019 r., g. 12:30

Abstract: We study scheduling in a data gathering network consisting of a set of worker nodes and a single base station. The workers produce datasets that have to be sent to the base station for processing. Each dataset can be released at a different moment. The time required to transfer a dataset to the base station, and the time necessary to process it, are proportional to the dataset size. At most one worker can communicate with the base station at a time, and hence, the network works in a flow shop mode. A dataset transfer or processing can be preempted at any time and resumed later at no cost. Each dataset is assigned a due date by which it should be fully processed by the base station. The scheduling problem is to organize the communication and computation in the network so that the maximum dataset lateness is minimized. We prove that this problem is strongly NP-hard, and show some special cases that can be solved in polynomial time. A branch-and-bound algorithm and several polynomial-time heuristics are proposed for the general version of the problem. The performance of the algorithms is tested in a series of computational experiments.

Kolorowanie kosztowe ważonych grafów dwudzielnych

Prelegent: mgr Tytus Pikies (Politechnika Gdańska)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina:  11 grudnia 2018 r., g. 12:30

Streszczenie: Problem kolorowania kosztowego polega na znalezieniu kolorowania wierzchołkowego danego grafu o minimalnym łącznym koszcie dla zadanych kosztów kolorów. Podczas wystąpienia zostanie przedstawiona analiza tego problemu względem ważonych grafów dwudzielnych. Zostaną scharakteryzowane sekwencje kosztów dla których problem jest NP-trudny. Zostanie również przedstawiony wielomianowy algorytm optymalny dla pozostałych przypadków.

Algorytmiczne aspekty analizy danych spektrometrycznych

Prelegent: prof. dr hab. inż. Piotr Formanowicz (Politechnika Poznańska)
Miejsce: Sala seminaryjna B2-8/9
Data i godzina: 4 grudnia 2018 r., g. 12:30

Streszczenie: Spektrometria masowa jest jedną z najważniejszych technik wysokoprzepustowych wykorzystywanych do badania cząsteczek związków biochemicznych. Standardowym podejściem stosowanym przy analizie uzyskiwanych widm, zwłaszcza w przypadku badania peptydów, jest porównywanie otrzymanego widma z wcześniej otrzymanymi i zidentyfikowanymi widmami, przechowywanymi w publicznie dostępnych bazach danych. Podejście to ma jednak wiele ograniczeń. Stąd, istotne znaczenie mają metody de novo. Metody takie umożliwiają m.in. analizę nieznanych wcześniej cząsteczek. Pojawia się przy tym wiele interesujących problemów algorytmicznych, które należy rozwiązać, by zidentyfikować badany związek chemiczny. W ramach referatu zostaną omówione niektóre z tego typu problemów.

Badania operacyjne na WE PWr

Prelegent: prof. dr hab. Czesław Smutnicki (Politechnika Wrocławska)
Miejsce: Sala seminaryjna B2-8/9
Data i godzina: 6 listopada 2018 r., g. 12:30

Streszczenie: Problemy planowania i sterowania w dyskretnych systemach wytwarzania, problemy rozmieszczenia, pakowania, cięcia, kolekcjonowania, transportu, dystrybucji produktów, dostarczania towarów, planowania zajęć dydaktycznych, harmonogramowania pracy personelu, planowania tras robotów, etc. stanowią szczególnie trudną klasę zadań optymalizacji kombinatorycznej. Wśród wielu narzędzi dedykowanych do modelowania i optymalizacji wymienia się te zaliczane do dziedziny badań operacyjnych, która charakteryzuje się znaczną rozmaitością modeli i algorytmów rozwiązywania. Ograniczenie ogólności modeli ma na celu wykrycie tych szczególnych własności problemu, których umiejętne wykorzystanie w algorytmie zdecydowanie poprawia jego cechy numeryczne takie, jak czas obliczeń, szybkość zbiegania do rozwiązania optymalnego, lub bliskiego optymalnemu. Badania prowadzone od lat na WE PWr dotyczą problemów generowanych przez praktykę systemów wytwarzania, transportu, magazynowania, etc. Odwołują się m.in do do pewnych analiz teoretycznych, modeli grafowych, metaheurystyk, obliczeń równoległych, analizy wielokryterialnej.  Przedstawione zostaną główne wyniki zespołu zajmującego się tą tematyką na WE PWr, na tle tendencji zmian w dziedzinie obserwowanej w ostatnich latach.

40 lat szeregowania zadań czasowo-zależnych

Prelegent: prof. UAM dr hab. Stanisław Gawiejnowicz
Miejsce: Sala seminaryjna B2-8/9
Data i godzina: 16 października 2018 r., g. 12:30

Streszczenie: W referacie zostanie przedstawiony przegląd tematyki jednej z istotnych gałęzi współczesnej teorii szeregowania zadań zwanej szeregowaniem zadań czasowo-zależnych. Omówione zostaną główne wyniki dotyczące środowisk maszyn równoległych i dedykowanych, jak również najistotniejsze rezultaty dotyczące wybranych nowych kierunków w tej teorii, takich jak szeregowanie zadań czasowo-zależnych na maszynach z ograniczoną dostępnościa, dwukryterialne szeregowanie zadań czasowo-zależnych, klasy wzajemnie powiązanych problemów szeregowania zadań czasowo-zależnych czy dwu-agentowe szeregowanie zadań czasowo-zależnych. Referat zostanie zakończony przedstawieniem głównych otwartych problemów z omawianej dziedziny.