{"id":171,"date":"2021-02-04T16:26:40","date_gmt":"2021-02-04T15:26:40","guid":{"rendered":"http:\/\/localhost\/mSzachniuk\/?page_id=171"},"modified":"2026-06-02T16:15:16","modified_gmt":"2026-06-02T14:15:16","slug":"zadania-zaliczeniowe","status":"publish","type":"page","link":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/teaching\/algorytmy-i-struktury-danych\/zadania-zaliczeniowe\/","title":{"rendered":"ASD-zadania zaliczeniowe"},"content":{"rendered":"\n<script>\ndocument.getElementById(\"menu-item-188\").classList.add(\"current_page_item\");\n<\/script>\n<a href=\"..\/..\/\">Informacje dla student\u00f3w<\/a> << <a href=\"..\/\">Algorytmy i struktury danych<\/a> <<\n\n\n\n<h1 class=\"wp-block-heading\">Zadania zaliczeniowe<\/h1>\n\n\n\n<p align=\"left\"><a href=\"#Zadanie 1\">Zadanie 1<\/a> | <a href=\"#Zadanie 2\">Zadanie 2<\/a> | <a href=\"#Zadanie 3\">Zadanie 3<\/a> | <a href=\"#Zadanie 4\">Zadanie 4<\/a> | <a href=\"#Zadanie 5\">Zadanie 5<\/a> <\/p>\n\n<p align=\"justify\">\nUwagi og\u00f3lne:\n<\/p><ol>\n<li align=\"justify\">Terminem zaliczenia programu jest dzie\u0144 wyszczeg\u00f3lniony w <a href=\"..\/plan-zajec\/\">terminarzu zaj\u0119\u0107<\/a>.\nTylko w tym dniu mo\u017cna uzyska\u0107 maksymaln\u0105 punktacj\u0119 za program (w przypadku niemo\u017cno\u015bci zaliczenia programu na wyznaczonych zaj\u0119ciach\nnale\u017cy umowi\u0107 si\u0119 na zaliczenie indywidualne). <\/li>\n<li align=\"justify\">Sprawozdanie z danego tematu powinno by\u0107 zapisane w pliku *.pdf i wys\u0142ane przez <strong>USOSMAIL<\/strong> w ci\u0105gu 6 dni po zaliczeniu programu (tylko za sprawozdania wys\u0142ane przed tym terminem mo\u017cna uzyska\u0107 maksymaln\u0105 liczb\u0119 punkt\u00f3w).<\/li>\n<li align=\"justify\">W sprawozdaniu osie wykres\u00f3w powinny by\u0107 opisane (jakie dane na kt\u00f3rej osi, jednostki pomiaru). Ka\u017cdy punkt na wykresie powinien by\u0107 obliczony jako \u015brednia z 10 pomiar\u00f3w. Na wykresie nale\u017cy przedstawi\u0107 b\u0142\u0105d pomiaru (odchylenie standardowe) dla ka\u017cdego punktu, a je\u015bli b\u0142\u0119dy s\u0105 nieznaczne poda\u0107 te dane w postaci tabelarycznej.<\/li>\n<li align=\"justify\">Ka\u017cde sprawozdanie powinno zawiera\u0107 informacj\u0119 o tym, w jakim j\u0119zyku programowania zakodowano poszczeg\u00f3lne algorytmy, na jakiej platformie wykonano testy (sprz\u0119t i system operacyjny) oraz kto jest autorem sprawozdania.<\/li>\n<\/ol>\n<p><\/p>\n\n<p align=\"justify\">\nZadania zaliczeniowe:\n<\/p><ul>\n<li align=\"justify\"><a name=\"Zadanie 1\"><\/a><strong>Zadanie 1: Algorytmy sortowania<\/strong><br>\nCelem zadania jest implementacja wybranych algorytm\u00f3w sortowania, przeprowadzenie systematycznych eksperyment\u00f3w por\u00f3wnawczych oraz analiza ich z\u0142o\u017cono\u015bci obliczeniowej w praktyce (<a href=\"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-content\/uploads\/2026\/03\/AiSD-zad-1-2026.pdf\" target=\"blank\" rel=\"noopener noreferrer\">zobacz zadanie<\/a>).<\/li><br>\n\n<li align=\"justify\"><a name=\"Zadanie 2\"><\/a><strong>Zadanie 2: Z\u0142o\u017cone struktury danych<\/strong><br>\nZadanie obejmuje implementacj\u0119 oraz eksperymentalne por\u00f3wnanie wybranych dynamicznych struktur danych, a tak\u017ce analiz\u0119 ich zachowania w zale\u017cno\u015bci od sposobu budowy oraz rozmiaru danych wej\u015bciowych. Projekt ma na celu umo\u017cliwienie zrozumienia r\u00f3\u017cnic mi\u0119dzy strukturami zr\u00f3wnowa\u017conymi i niezr\u00f3wnowa\u017conymi, wp\u0142ywu danych wej\u015bciowych na degeneracj\u0119 drzewa, zale\u017cno\u015bci mi\u0119dzy wysoko\u015bci\u0105 drzewa a kosztem operacji oraz znaczenia z\u0142o\u017cono\u015bci asymptotycznej w praktycznej analizie algorytm\u00f3w. Dodatkowo pozwala por\u00f3wna\u0107 w\u0142a\u015bciwo\u015bci drzewa BST i kopca jako odmiennych struktur hierarchicznych (<a href=\"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-content\/uploads\/2026\/04\/AiSD-zad-2-2026.pdf\" target=\"blank\" rel=\"noopener noreferrer\">zobacz zadanie<\/a>).\n<\/li><br>\n\n<li align=\"justify\"><a name=\"Zadanie 3\"><\/a><strong>Zadanie 3: Algorytmy grafowe<\/strong><br>\nZadanie obejmuje implementacj\u0119 algorytm\u00f3w sortowania topologicznego oraz ich eksperymentalne por\u00f3wnanie dla r\u00f3\u017cnych reprezentacji grafu. Projekt ma na celu zrozumienie wp\u0142ywu sposobu reprezentacji grafu na efektywno\u015b\u0107 dzia\u0142ania algorytm\u00f3w, analiz\u0119 zale\u017cno\u015bci mi\u0119dzy g\u0119sto\u015bci\u0105 grafu a kosztami oblicze\u0144, a tak\u017ce rozwini\u0119cie umiej\u0119tno\u015bci interpretacji wynik\u00f3w eksperymentalnych w kontek\u015bcie z\u0142o\u017cono\u015bci obliczeniowej (<a href=\"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-content\/uploads\/2026\/05\/AiSD-zad-3-2026.pdf\" target=\"blank\" rel=\"noopener noreferrer\">zobacz zadanie<\/a>).\n<\/li><br>\n\n<li align=\"justify\"><a name=\"Zadanie 4\"><\/a><strong>Zadanie 4: Algorytmy z powracaniem<\/strong><br>\nZadanie obejmuje implementacj\u0119 oraz eksperymentalne por\u00f3wnanie algorytm\u00f3w przeszukiwania z wykorzystaniem techniki powracania dla wybranych problem\u00f3w grafowych oraz analiz\u0119 ich zachowania w zale\u017cno\u015bci od rozmiaru i struktury danych wej\u015bciowych. Projekt ma na celu zrozumienie r\u00f3\u017cnic mi\u0119dzy problemami o r\u00f3\u017cnej z\u0142o\u017cono\u015bci obliczeniowej, wp\u0142ywu przestrzeni rozwi\u0105za\u0144 na koszt przeszukiwania oraz znaczenia z\u0142o\u017cono\u015bci asymptotycznej w praktyce. Dodatkowo pozwala por\u00f3wna\u0107 efektywno\u015b\u0107 tej samej techniki (backtracking) dla problem\u00f3w \u0142atwych i trudnych obliczeniowo (<a href=\"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-content\/uploads\/2026\/05\/AiSD-zad-4-2026.pdf\" target=\"blank\" rel=\"noopener noreferrer\">zobacz zadanie<\/a>).\n<\/li><br>\n\n<li align=\"justify\"><a name=\"Zadanie 5\"><\/a><strong>Zadanie 5: Algorytmy dok\u0142adne i heurystyczne dla problemu plecakowego<\/strong><br>\nZadanie obejmuje implementacj\u0119 oraz eksperymentalne por\u00f3wnanie trzech podej\u015b\u0107 algorytmicznych dla problemu plecakowego, a tak\u017ce analiz\u0119 ich efektywno\u015bci w zale\u017cno\u015bci od liczby dost\u0119pnych element\u00f3w i pojemno\u015bci. Projekt ma na celu zrozumienie r\u00f3\u017cnic mi\u0119dzy metodami dok\u0142adnymi a heurystycznymi, zbadanie wp\u0142ywu parametr\u00f3w instancji na koszt oblicze\u0144 oraz ocen\u0119 jako\u015bci rozwi\u0105za\u0144 suboptymalnych wzgl\u0119dem wyznaczonego optimum, pozwala w praktyce przeanalizowa\u0107 kompromis pomi\u0119dzy szybko\u015bci\u0105 dzia\u0142ania algorytmu a jako\u015bci\u0105 uzyskanego wyniku (<a href=\"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-content\/uploads\/2026\/06\/AiSD-zad-5-2026.pdf\" target=\"blank\" rel=\"noopener noreferrer\">zobacz zadanie<\/a>).\n<\/li>\n<\/ol>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Informacje dla student\u00f3w<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":114,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"custom-page.php","meta":{"footnotes":""},"class_list":["post-171","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/171","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/comments?post=171"}],"version-history":[{"count":259,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/171\/revisions"}],"predecessor-version":[{"id":3122,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/171\/revisions\/3122"}],"up":[{"embeddable":true,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/114"}],"wp:attachment":[{"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/media?parent=171"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}