Implementation and analysis of algorithms solving chosen problems of class P and NP

Tematem niniejszej pracy licencjackiej jest implementacja i analiza złożoności czasowej wybranych algorytmów sortowania oraz analiza problemu plecakowego. Jej celem było porównanie wybranych algorytmów rozwiązujących powyższe problemy.Praca składa się z czterech rozdziałów. Pierwszy został poświęcony wstępnym informacjom związanym z tematem algorytmów: złożoności obliczeniowej, klas oraz metod rozwiązywania problemów. Zostały w nim przedstawione algorytmy sortowania: sortowanie bąbelkowe, sortowanie przez wybieranie oraz sortowanie przez scalanie. Opisane zostały również dwa rodzaje rozwiązania problemu plecakowego: algorytm zachłanny i dynamiczny.Drugi rozdział omawia metody badawcze wykorzystane w trakcie analizy oraz przedstawia stanowisko pracy. Wyniki zostały przedstawione w rozdziale trzecim, który jest podzielony na trzy zasadnicze części: przedstawienie wyników analizy złożoności czasowej algorytmów sortowania, podsumowanie porównania algorytmów rozwiązujących problem plecakowy oraz sformułowanie wniosków z obu analiz. W ostatnim rozdziale znajduje się podsumowanie całej pracy.Zakładaną analizę udało się wykonać w całości, a autor nie napotkał problemów badawczych. Celem było zaprezentowanie, jak przy określonych warunkach wybrać odpowiedni algorytm. Przykładowo wybór algorytmu sortowania przez scalanie może skrócić długość wykonywania obliczeń w skrajnych przypadkach nawet kilkadziesiąt razy.The topic of this BA dissertation is implementation and analysis of time complexity of selected sorting algorithms and analysis of knapsack problem. The aim was to compare chosen algorithms solving these problems.The dissertation consists of four chapters. The first one contains the introduction to the topic of algorithms: computing complexity, classes and methods of solving issues. The sorting algorithms were described: bubble sort, select sort and merge sort. Two algorithms solving knapsack problem were also described: greedy algorithm and dynamic programming.The second chapter describes test methods used during analysis and workplace. The results are contained in chapter three, which is divided into three main parts: presentation of results of sorting algorithms time complexity analysis, summary of comparison of knapsack issue solving algorithms and conclusions to both analysis. In the last chapter there is the summary of the whole dissertation.The whole assumed analysis was completed successfully and the author did not have any obstacles. The aim was to show how to choose the best algorithm assuming some conditions. For instance, choosing merge sort can decrease the time of computing by dozens of times