Implementacja oraz analiza algorytmów rozwiązujących wybrane problemy klasy P i NP

licenciate
dc.abstract.enThe 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.pl
dc.abstract.plTematem 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.pl
dc.affiliationWydział Fizyki, Astronomii i Informatyki Stosowanejpl
dc.areaobszar nauk ścisłychpl
dc.contributor.advisorPaszyńska, Anna - 160672 pl
dc.contributor.authorSmolarek, Dominikpl
dc.contributor.departmentbycodeUJK/WFAISpl
dc.contributor.reviewerPaszyńska, Anna - 160672 pl
dc.contributor.reviewerGrzesiak-Kopeć, Katarzyna - 102580 pl
dc.date.accessioned2020-07-27T12:57:16Z
dc.date.available2020-07-27T12:57:16Z
dc.date.submitted2017-10-24pl
dc.fieldofstudyinformatykapl
dc.identifier.apddiploma-120142-161151pl
dc.identifier.projectAPD / Opl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/225095
dc.languagepolpl
dc.subject.enalgorithms, analysis, python, sorting, mergesort, selectionsort, bubblesort, knapsack problempl
dc.subject.plalgorytmy, analiza, python, sortowanie, sortowanie bąbelkowe, sortowanie przez wybieranie, sortowanie przez scalanie, problem plecakowypl
dc.titleImplementacja oraz analiza algorytmów rozwiązujących wybrane problemy klasy P i NPpl
dc.title.alternativeImplementation and analysis of algorithms solving chosen problems of class P and NPpl
dc.typelicenciatepl
dspace.entity.typePublication
dc.abstract.enpl
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.
dc.abstract.plpl
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.
dc.affiliationpl
Wydział Fizyki, Astronomii i Informatyki Stosowanej
dc.areapl
obszar nauk ścisłych
dc.contributor.advisorpl
Paszyńska, Anna - 160672
dc.contributor.authorpl
Smolarek, Dominik
dc.contributor.departmentbycodepl
UJK/WFAIS
dc.contributor.reviewerpl
Paszyńska, Anna - 160672
dc.contributor.reviewerpl
Grzesiak-Kopeć, Katarzyna - 102580
dc.date.accessioned
2020-07-27T12:57:16Z
dc.date.available
2020-07-27T12:57:16Z
dc.date.submittedpl
2017-10-24
dc.fieldofstudypl
informatyka
dc.identifier.apdpl
diploma-120142-161151
dc.identifier.projectpl
APD / O
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/225095
dc.languagepl
pol
dc.subject.enpl
algorithms, analysis, python, sorting, mergesort, selectionsort, bubblesort, knapsack problem
dc.subject.plpl
algorytmy, analiza, python, sortowanie, sortowanie bąbelkowe, sortowanie przez wybieranie, sortowanie przez scalanie, problem plecakowy
dc.titlepl
Implementacja oraz analiza algorytmów rozwiązujących wybrane problemy klasy P i NP
dc.title.alternativepl
Implementation and analysis of algorithms solving chosen problems of class P and NP
dc.typepl
licenciate
dspace.entity.type
Publication

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
48
Views per month
Views per city
Rzeszów
6
Warsaw
6
Gliwice
3
Poznan
3
Wroclaw
3
Bialystok
2
Żywiec
2
Dublin
1
Gdansk
1
Gorzów Wielkopolski
1

No access

No Thumbnail Available