Simple view
Full metadata view
Authors
Statistics
Problem wydawania reszty - eksperymentalna ewaluacja algorytmów.
Change-making problem - experimental evaluation of algorithms.
problem wydawania reszty, szybka transformata Fouriera, programowanie dynamiczne
change-making problem, fast Fourier transform, dynamic programming
W problemie wydawania reszty dla danego zbioru monet pytamy, jaka jest ich minimalna liczba potrzebna do wydania danej reszty t. W ostatnich latach Timothy M. Chan oraz Qizheng He zaproponowali nowe algorytmy rozwiązujące ten problem, w większości oparte na splotach ciągów i działające w złożoności O˜(t).W tej pracy przedstawiona została implementacja tych algorytmów w języku C++ oraz porównane zostały ich czasy działania na różnych danych testowych.
In the change-making problem, for a given set of coins we are asking for the minimum number of coins needed to change a given value t. In the last few years, Timothy M. Chan and Qizheng He proposed new algorithms for solving this problem, which are mostly based on convolution and have complexity O˜(t).This thesis presents implementation of these algorithms in C++ language and compares their running time on various test sets.
| dc.abstract.en | In the change-making problem, for a given set of coins we are asking for the minimum number of coins needed to change a given value t. In the last few years, Timothy M. Chan and Qizheng He proposed new algorithms for solving this problem, which are mostly based on convolution and have complexity O˜(t).This thesis presents implementation of these algorithms in C++ language and compares their running time on various test sets. | pl |
| dc.abstract.pl | W problemie wydawania reszty dla danego zbioru monet pytamy, jaka jest ich minimalna liczba potrzebna do wydania danej reszty t. W ostatnich latach Timothy M. Chan oraz Qizheng He zaproponowali nowe algorytmy rozwiązujące ten problem, w większości oparte na splotach ciągów i działające w złożoności O˜(t).W tej pracy przedstawiona została implementacja tych algorytmów w języku C++ oraz porównane zostały ich czasy działania na różnych danych testowych. | pl |
| dc.affiliation | Wydział Matematyki i Informatyki | pl |
| dc.area | obszar nauk ścisłych | pl |
| dc.contributor.advisor | Polak, Adam | pl |
| dc.contributor.author | Gawryał, Grzegorz | pl |
| dc.contributor.departmentbycode | UJK/WMI2 | pl |
| dc.contributor.reviewer | Polak, Adam | pl |
| dc.contributor.reviewer | Ślusarek, Maciej - 132329 | pl |
| dc.date.accessioned | 2023-09-06T21:31:28Z | |
| dc.date.available | 2023-09-06T21:31:28Z | |
| dc.date.submitted | 2021-07-09 | pl |
| dc.fieldofstudy | informatyka analityczna | pl |
| dc.identifier.apd | diploma-152021-259657 | pl |
| dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/318410 | |
| dc.language | pol | pl |
| dc.subject.en | change-making problem, fast Fourier transform, dynamic programming | pl |
| dc.subject.pl | problem wydawania reszty, szybka transformata Fouriera, programowanie dynamiczne | pl |
| dc.title | Problem wydawania reszty - eksperymentalna ewaluacja algorytmów. | pl |
| dc.title.alternative | Change-making problem - experimental evaluation of algorithms. | pl |
| dc.type | licenciate | pl |
| dspace.entity.type | Publication |