| Prelegent: | Piotr Borowiecki, dr hab. inż., prof. UZ, Zakład Systemów Informatycznych i Cyberbezpieczeństwa, Instytut Sterowania i Systemów Informatycznych, Wydział Informatyki, Elektrotechniki i Automatyki, Uniwersytet Zielonogórski, e-mail: P.Borowiecki@issi.uz.zgora.pl. |
| Tytuł: | Problemy podziałów i niezależności na grafach |
| Streszczenie: | W referacie przedstawione zostaną problemy podziałów i niezależności na grafach, stanowiące dwa ściśle ze sobą powiązane, centralne zagadnienia optymalizacji dyskretnej. W szczególności, omówiona zostanie metoda projektowania nowych klas grafów wraz z działającymi na nich algorytmami przybliżonymi, wykorzystująca podziały generowane przez algorytm zachłanny. W kontekście trudności obliczeniowej problemów podziału i niezależności, podane zostaną podstawowe własności tzw. funkcji potencjału i jej zastosowania w szacowaniu efektywności algorytmów. Dla problemu podziałów przedstawione zostaną również wyniki dotyczące trybu dynamicznego, w którym rozwiązania problemu generowane są dla grafów, których struktura zmienia się podczas działania algorytmu, wymuszając sekwencję adaptacji rozwiązań. |
