Tytuł: Analiza metod probabilistycznych optymalizacji dyskretnej Wariant tytułu: Analysis of probabilistic methods of discrete optimization Autorzy: Krzysztof Marcin Szkatuła Partner: Instytut Badań Systemowych PAN w Warszawie Opis: W pracy sformułowano podstawowe definicje dotyczące oceny złożoności obliczeniowej zadań optymalizacji dyskretnej zarówno w najgorszym jak i w tzw. średnim przypadku. Omówiono różne oceny jakości algorytmów w tych dwóch przypadkach. Wyniki tych teoretycznych rozważań zastosowano dla binarnego zadania załadunku i dla zadania pakowania. Analizie poddano dwa algorytmy dla binarnego zadania załadunku: algorytm zachłanny (greedy algorithm) oraz algorytm najprostszy (blind greedy algorithm). Są to dwa proste i tanie w sensie obliczeniowym algorytmy należące do grupy szeroko stosowanych w optymalizacji dyskretnej algorytmów zachłannych. Algorytmy te różnią się tylko tym, że algorytm zachłanny zawiera wstępną fazę sortowania zmiennych w zadaniu, pominiętą w przypadku algorytmu najprostszego. Przedstawiono przykłady binarnych zadań załadunku, dla których algorytmy te mogą dawać rozwiązania dowolnie odległe od rozwiązania optymalnego. Oznacza to, że z punktu widzenia metodologii najgorszego przypadku oba te algorytmy uzyskują rozwiązania o niskiej jakości. W pracy uzyskano wyniki pokazujące, że przy słabych założeniach dotyczących rozkładów probabilistycznych współczynników zadania algorytm zachłanny, i, co więcej, również jego uproszczona (obcięta) wersja, uzyskuje prawie wszędzie rozwiązanie optymalne zadania. Dla algorytmów: zachłannego oraz najprostszego uzyskano twierdzenia pozwalające obliczyć wartości średnie uzyskiwanych przez te algorytmy rozwiązań jako funkcje rozmiaru zadania, wartości prawej strony ograniczenia oraz rozkładów probabilistycznych współczynników zadania. Słowa kluczowe: "algorytmy dokładne"@pl, "algorytmy przybliżone"@pl, "optymalizacja dyskretna"@pl, "programowanie całkowitoliczbowe"@pl, "optymalizacja"@pl, "analiza najlepszego i najgorszego przypadku"@pl Typ zasobu: praca dyplomowa Dyscyplina naukowa: dziedzina nauk technicznych / automatyka i robotyka (2011) Grupa docelowa: naukowcy, studenci, przedsiębiorcy Szkodliwe treści: Nie Promotor: Stanisław Walukiewicz (10277) Język zasobu: Polski Czas powstania: 1985 Lokalizacja: Warszawa Miejsce powstania: Warszawa Liczba stron: 127 Prawa/licencja: CC BY-SA 4.0 Deponujący: Anna Wasilewska Data udostępnienia: 15-10-2018 Link do zasobu (portal): https://zasobynauki.pl/zasoby/analiza-metod-probabilistycznych-optymalizacji-dyskretnej,20933/ Link do zasobu (repozytorium): https://id.e-science.pl/records/20933