ODSYŁACZE

Link do zasobu (portal):

Link do zasobu (repozytorium):

https://id.e-science.pl/records/20933

ZGŁOSZENIE

Pola oznaczone gwiazdką (*) są wymagane
*
*
*
*
captcha

Typ zasobu: praca dyplomowa

Analiza metod probabilistycznych optymalizacji dyskretnej

Metadane zasobu

Tytuł Analiza metod probabilistycznych optymalizacji dyskretnej
Wariant tytułu: Analysis of probabilistic methods of discrete optimization
Osoby 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. (polski)
Opis w innym języku: The work formulates basic definitions regarding the evaluation of the computational complexity of discrete optimization problems in both the worst and the so-called average case. Various assessments of the quality of algorithms in these two cases are considered. The results of these theoretical considerations were applied in the case of the binary knapsack and two-dimensional bin-packing problems. Two algorithms for the binary task of loading were analyzed: greedy algorithm and the so-called simplest algorithm (blind greedy algorithm). These are two simple and computationally inexpensive algorithms belonging to the group of greedy algorithms that are widely used in discrete optimization. These algorithms differ only in that the greedy algorithm contains the initial phase of sorting variables in the problem, omitted in the case of the simplest algorithm. Examples of binary knapsack problems are presented, for which both algorithms may provide solutions arbitrarily far from the optimal solution. So, from the point of view of the worst-case methodology, both of these algorithms get low-quality solutions.
The dissertation presents results showing that, with weak assumptions about probabilistic distributions of the problem coefficients, the greedy algorithm, and its simplified (truncated) version, obtains almost everywhere the optimal solutions for the problem. For both greedy and simplest algorithms theorems were obtained presenting the average values of the solutions obtained by these algorithms as functions of problem size, values of the right side of the constraint and probabilistic distributions of the problem coefficients. (angielski)
Słowa kluczowe "best case and worst case analysis"@en , "accurate and approximate algorithms"@en , "discrete optimization"@en , "analiza najlepszego i najgorszego przypadku"@pl , "algorytmy dokładne i przybliżone"@pl , "optymalizacja dyskretna"@pl
Klasyfikacja Typ zasobu: praca dyplomowa
Dyscyplina naukowa: dziedzina nauk technicznych / automatyka i robotyka
Grupa docelowa: naukowcy, studenci, przedsiębiorcy
Informacja o zawartości szkodliwych treści : Nie
Charakterystyka Promotor: Stanisław Walukiewicz
Język zasobu: polski
Czas powstania: 1985
Lokalizacja: Warszawa
Miejsce powstania: Warszawa
Liczba stron: 127
Licencja CC BY-SA 4.0
Informacje techniczne Deponujący: Anna Wasilewska
Data udostępnienia : 15-10-2018
Kolekcje Kolekcja Instytutu Badań Systemowych PAN w Warszawie

elementy wygenerowane automatycznie

Cytowanie zasobu

Skopiowano

Krzysztof Marcin Szkatuła. Analiza metod probabilistycznych optymalizacji dyskretnej. [praca dyplomowa] Dostępny w Atlasie Zasobów Otwartej Nauki, . Licencja: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Data dostępu: DD.MM.RRRR.

Pliki (2)