Kategoria: Seminarium

Prelegent: Weronika Skowrońska
Data i godzina:  8 czerwca 2021 r., g. 12:30

Streszczenie: In the talk, first we summarize known properties of the so-called V-shaped sequences. Next, we show how the sequences can be generated and applied to solving of some scheduling problems. We complete our presentation with results of numerical experiments with implementations of discussed algorithms.

Prelegent: Dr Marcin Żurowski (Pracownia Algorytmiki)
Data i godzina:  23 marca 2021 r., g. 12:30

Streszczenie: W referacie przedstawimy nowy model podzielności pozycyjno-zależnych zadań uszeregowanych na dwóch równoległych identycznych maszynach, w którym dzielimy jedno zadanie jednokrotnie. W tym modelu zadanie podzielone na pierwszej maszynie kontynuujemy na dowolnej pozycji na drugiej maszynie.

Prelegent: Dr Joanna Berlińska (Pracownia Algorytmiki)
Data i godzina:  15 grudnia 2020 r., g. 12:30

Streszczenie: W referacie przedstawione zostaną wyniki dotyczące szeregowania zadań w dwumaszynowym flowshopie ze zmieniającą się w czasie ilością dostępnej pamięci. Skupimy się na przypadku zadań z jednostkowymi czasami trwania operacji i różnymi wymaganiami pamięciowymi. Pokażemy, że problem minimalizacji długości uszeregowania jest silnie NP-trudny i przedstawimy dla niego wielomianowy schemat aproksymacji (PTAS). Zaprezentowany zostanie również algorytm dokładny oparty na całkowitoliczbowym programowaniu liniowym oraz algorytmy heurystyczne.

Prelegent: Prof. dr hab. Marta Szachniuk (Instytut Chemii Bioorganicznej PAN & Wydział Informatyki i Telekomunikacji Politechniki Poznańskiej)
Data i godzina:  8 grudnia 2020 r., g. 12:30

Streszczenie: Pseudowęzeł to motyw charakterystyczny dla cząsteczek RNA. Złożoność jego struktury można określić poprzez rzędowość, która jednocześnie wskazuje na moment jego utworzenia w procesie zwijania się cząsteczki. W naszych badaniach zadaliśmy pytanie o możliwość odtworzenia hierarchii zwijania zapętlonych cząsteczek RNA wyłącznie na podstawie ich struktury 3D. Podczas wykładu zaprezentowane zostaną wybrane rozwiązania tego zagadnienia, m. in. bazujące na modelu grafowym i problemie kolorowania grafu.

Prelegent: Dr hab. Piotr Faliszewski, prof. AGH (Akademia Górniczo-Hutnicza w Krakowie)
Data i godzina:  1 grudnia 2020 r., g. 12:30

Streszczenie: Reguły punktowania komitetów stanowią bogatą rodzinę systemów wyborczych pozwalających na wybór grupy osób kandydatów spełniających zadane cechy. Naturalne przykłady takich wyborów to wybory parlamentarne, wybory finalistów w zawodach sportowych (kandydatami są zawodnicy, a wyborcami sędziowie), czy wybór filmów, które zostaną udostępnione pasażerom w samolocie (kandydatami są filmy, a wyborcami przewidywane profile gustów pasażerów). Niestety, problem znalezienia zwycięzcy dla większości reguł punktowania komitetów jest NP-trudny, a dobór odpowiedniej reguły dla danego zadania nie zawsze oczywisty. W ramach referatu przedstawię formalizm reguł punktowania komitetów, podstawowe podejścia algorytmiczne, kilka ważnych własności tych reguł oraz wyniki symulacji.

Prelegent: Dr hab. Stanisław Gawiejnowicz, prof. UAM (Pracownia Algorytmiki)
Data i godzina:  17 listopada 2020 r., g. 12:30

Streszczenie: NP-trudny problem plecakowy jest badany od wielu lat ze względu na istotne zastosowania praktyczne. W literaturze znanych jest kilka różnych wariantów tego problemu, w najbardziej znanym wszystkie parametry problemu (pojemność plecaka, rozmiary i wartości elementów) są liczbami. W referacie przedstawimy dotychczasowe wyniki dotyczące głównych wariantów tego problemu oraz nowe wyniki dla trzech nowych jego wariantów, w których rozmiary i/lub wartości elementów zależą od pozycji tych elementów w sekwencji elementów już upakowanych.

Prelegent: Dr Bartłomiej Przybylski (Pracownia Algorytmiki)
Data i godzina:  23 czerwca 2020 r., g. 12:30

Streszczenie: W pierwszej części seminarium zaprezentuję efekty początkowych prac nad biblioteką do numerycznego wspomagania rozwiązywania problemów szeregowania zadań — Scheduling.jl. W drugiej części seminarium skupię się na wynikach dotyczących jedno- i wielomaszynowych problemów szeregowania zadań, w których zmienne czasy wykonywania zadań zależą nie tylko od pozycji zadania w uszeregowaniu, ale także – w dowolny sposób – od samego zadania i maszyny, do której zadanie zostało przydzielone. Dla takiej mieszanej zależności oraz wybranych funkcji celu (maksymalny czas zakończenia i łączny czas zakończenia) przedstawię pełną klasyfikację złożoności obliczeniowej. Przypomnę także wyniki dotyczące analogicznych problemów, w których zadania muszą być wykonywane w określonej kolejności (ograniczenia w postaci łańcucha), a także rozpocznę dyskusję na temat analizy problemów, w których ograniczenia kolejnościowe są opisane bardziej złożonymi grafami.

Prelegent: dr hab. Marta Szachniuk, prof. IChB PAN (Instytut Chemii Bioorganicznej PAN & Wydział Informatyki i Telekomunikacji Politechniki Poznańskiej)
Miejsce: B1-7/8
Data i godzina:  21 kwietnia 2020 r., g. 12:30

Streszczenie: Pseudowęzeł to motyw charakterystyczny dla cząsteczek RNA. Złożoność jego struktury można określić poprzez rzędowość, która jednocześnie wskazuje na moment jego utworzenia w procesie zwijania się cząsteczki. W naszych badaniach zadaliśmy pytanie o możliwość odtworzenia hierarchii zwijania zapętlonych cząsteczek RNA wyłącznie na podstawie ich struktury 3D. Podczas wykładu zaprezentowane zostaną wybrane rozwiązania tego zagadnienia, m. in. bazujące na modelu grafowym i problemie kolorowania grafu.

W związku z zarządzeniem Rektora UAM nr 431/2019/2020 z dnia 11 marca 2020 roku w sprawie działań podejmowanych w celu przeciwdziałania rozprzestrzenianiu się wirusa COVID-19 wśród członków społeczności Uniwersytetu im. Adama Mickiewicza w Poznaniu wykład dr hab. Marty Szachniuk został odwołany. 

Prelegent: dr hab. Piotr Faliszewski, prof. AGH (Akademia Górniczo-Hutnicza w Krakowie)
Miejsce: B1-7/8
Data i godzina:  31 marca 2020 r., g. 12:30

Streszczenie: Reguły punktowania komitetów stanowią bogatą rodzinę systemów wyborczych pozwalających na wybór grupy osób kandydatów spełniających zadane cechy. Naturalne przykłady takich wyborów to wybory parlamentarne, wybory finalistów w zawodach sportowych (kandydatami są zawodnicy, a wyborcami sedziowie), czy wybór filmów, które zostaną udostępnione pasażerom w samolocie (kandydatami są filmy, a wyborcami przewidywane profile gustów pasażerów). Niestety, problem znalezienia zwycięzcy dla większości reguł punktowania komitetów jest NP-trudny, a dobór odpowiedniej reguły dla danego zadania nie zawsze oczywisty. W ramach referatu przedstawię formalizm reguł punktowania komitetów, podstawowe podejścia algorytmiczne, kilka ważnych własności tych reguł oraz wyniki symulacji.

W związku z zarządzeniem Rektora UAM nr 431/2019/2020 z dnia 11 marca 2020 roku w sprawie działań podejmowanych w celu przeciwdziałania rozprzestrzenianiu się wirusa COVID-19 wśród członków społeczności Uniwersytetu im. Adama Mickiewicza w Poznaniu wykład dra hab. Piotr Faliszewskiego został odwołany. 

Prelegent: Stanisław Gawiejnowicz (Pracownia Algorytmiki)
Miejsce: B4-6
Data i godzina:  3 marca 2020 r., g. 12:30

Streszczenie: W referacie przedstawione zostaną wybrane wyniki dotyczące szeregowania zadań czasowo-zależnych, otrzymane w ciągu ostatnich 10 lat, ze szczególnym uwzględnieniem stosowanych metod oraz technik dowodowych.