{"id":126,"date":"2021-02-04T14:54:37","date_gmt":"2021-02-04T13:54:37","guid":{"rendered":"http:\/\/localhost\/mSzachniuk\/?page_id=126"},"modified":"2024-10-07T10:12:00","modified_gmt":"2024-10-07T08:12:00","slug":"zadania-kolokwium","status":"publish","type":"page","link":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/teaching\/algorytmy-i-struktury-danych\/zadania-kolokwium\/","title":{"rendered":"ASD-zadania kolokwium"},"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<h2 class=\"wp-block-heading\">Zadania egzaminacyjne<\/h2>\n\n\n\n<p align=\"left\"><a href=\"#Temat 1\">Temat 1<\/a> | <a href=\"#Temat 2\">Temat 2<\/a> | <a href=\"#Temat 3\">Temat 3<\/a> | <a href=\"#Temat 4\">Temat 4<\/a> | <a href=\"#Temat 5\">Temat 5<\/a> <\/p>\n\n<a name=\"Temat 1\"><\/a><h3>Temat 1: Algorytmy sortowania<\/h3>\n<ol>\n<li><p>Podaj jaki jest \u015bredni i najgorszy czas <em>O<\/em>(?) dzia\u0142ania algorytmu szybkiego sortowania (QS) dla <em>m<\/em> liczb.<\/p><\/li>\n<li><p>Czy ci\u0105g &lt;50,20,8,8,20,10,4,8,8,8,8,1&gt; jest kopcem? Odpowied\u017a uzasadnij.<\/p><\/li>\n<li><p>Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa <em>O<\/em>(?) algorytmu sortowania przez proste wybieranie (Selection sort)?<\/p><\/li>\n<li><p>Kt\u00f3re spo\u015br\u00f3d podanych algorytm\u00f3w sortowania sortuj\u0105 w miejscu: szybkie (QS), przez proste wstawianie (IS), pozycyjne (RS), przez zliczanie (CS), stogowe (HS), przez prost\u0105 zamian\u0119 (BS)?<\/p><\/li>\n<li><p>Kt\u00f3re algorytmy sortowania najlepiej nadaj\u0105 si\u0119 do posortowania ci\u0105gu liczbowego odwrotnie uporz\u0105dkowanego i dlaczego?<\/p><\/li>\n<li><p>Poka\u017c kolejne kroki procedury sortuj\u0105cej rosn\u0105co ci\u0105g liczbowy A:12,1,5,4,15,10,8,2,7,5,13,11,3 metod\u0105 malej\u0105cych przyrost\u00f3w z przyrostami (a) Knutha, (b) Shella.<\/p><\/li>\n<li><p>Czy stopie\u0144 uporz\u0105dkowania danych wej\u015bciowych wp\u0142ywa na z\u0142o\u017cono\u015b\u0107 obliczeniow\u0105 algorytmu sortowania przez proste wybieranie (SS)?<\/p><\/li>\n<li><p>Przedstaw jak b\u0119dzie wygl\u0105da\u0142 ci\u0105g liczb &lt;23,1,4,13,90,57,2,18,105&gt; po pierwszej, drugiej i trzeciej iteracji procedury sortuj\u0105cej ten ci\u0105g w porz\u0105dku malej\u0105cym wed\u0142ug metody szybkiego sortowania (QS) ze \u015brodkowym elementem wyboru. W ka\u017cdym kroku zaznacz wybrany element i miejsce podzia\u0142u.<\/p><\/li>\n<li><p>Dany jest 10-elementowy wektor liczbowy [2,10,8,11,15,16,31,5,16,6]. Skonstruuj kopiec zawieraj\u0105cy wszystkie elementy wektora i przedstaw go w postaci grafu (stogu) oraz w postaci tablicy jednowymiarowej. Podaj definicj\u0119 struktury kopca.<\/p><\/li>\n<li><p>Dla kopca z zadania powy\u017cej poka\u017c dwa kroki sortowania liczb w porz\u0105dku rosn\u0105cym zgodnie z procedur\u0105 sortowania przez kopcowanie (HS). Przedstaw zawarto\u015b\u0107 tablicy oraz st\u00f3g po ka\u017cdym kroku procedury sortowania.<\/p><\/li>\n<li><p>Jaki jest czas <em>O<\/em>(?) dzia\u0142ania algorytmu szybkiego sortowania (QS) oraz algorytmu sortowania przez proste wstawianie (IS) dla tablicy wej\u015bciowej odwrotnie posortowanej?<\/p><\/li>\n<li><p>Dana jest jednowymiarowa tablica liczb [10,11,12,3,17,8,1,5]. Przedstaw zawarto\u015b\u0107 tej tablicy po ka\u017cdej iteracji procedury sortuj\u0105cej liczby w porz\u0105dku malej\u0105cym metod\u0105 b\u0105belkow\u0105 (=sortowania przez prost\u0105 zamian\u0119 \/ BS).<\/p><\/li>\n<li><p>Posortuj ci\u0105g [14,15,4,11,19,3,57,23,15,17,9] metod\u0105 sortowania stogowego (HS) do momentu uporz\u0105dkowania dw\u00f3ch kolejnych element\u00f3w ci\u0105gu ilustruj\u0105c spos\u00f3b por\u00f3wnywania element\u00f3w na stogu. W tym celu nale\u017cy narysowa\u0107 st\u00f3g i zaznacza\u0107, kt\u00f3re elementy s\u0105 zamieniane.<\/p><\/li>\n<li><p>Podaj funkcj\u0119 z\u0142o\u017cono\u015bci obliczeniowej <em>O<\/em>(?) procedury sortowania <em>n<\/em>-elementowego ci\u0105gu liczbowego w \u015brednim i najgorszym przypadku dla nast\u0119puj\u0105cych algorytm\u00f3w sortowania: szybkiego (QS), przez kopcowanie (HS), przez proste wybieranie (SS), przez prost\u0105 zamian\u0119 (BS) i przez zliczanie (CS).<\/p><\/li>\n<li><p>Posortuj ci\u0105g z tablicy [2,3,4,1,3,4,2,5,1,6,7,1] metod\u0105 sortowania przez zliczanie (CS) wyja\u015bniaj\u0105c kolejne etapy sortowania. Podaj i uzasadnij pami\u0119ciow\u0105 i czasow\u0105 z\u0142o\u017cono\u015b\u0107 obliczeniow\u0105 <em>O<\/em>(?) tej metody sortowania.<\/p><\/li>\n<li><p>Dany jest ci\u0105g liczb naturalnych &lt;45,56,11,47,92,20,8,61,39&gt;. Zbuduj kopiec zawieraj\u0105cy wszystkie elementy tego ci\u0105gu, stosuj\u0105c standardow\u0105 metod\u0119 przywracania w\u0142asno\u015bci kopca (wykorzystywan\u0105 w algorytmie Heapsort; najmniejszy element jako korze\u0144). Przedstaw kopiec w reprezentacji tablicowej. Nast\u0119pnie podziel tablic\u0119 zawieraj\u0105c\u0105 kopiec po 5-tym elemencie i scal tak powsta\u0142e dwa podci\u0105gi u\u017cywaj\u0105c procedury scalania z algorytmu Merge Sort.<\/p><\/li>\n<li><p>Czy algorytm sortowania przez zliczanie (CS) jest stabilny? Czym charakteryzuje si\u0119 w\u0142asno\u015b\u0107 stabilno\u015bci algorytmu sortowania?<\/p><\/li>\n<li><p>Liczby z tablicy [12,7,9,1,3,5] posortowano w porz\u0105dku rosn\u0105cym wykorzystuj\u0105c standardow\u0105 procedur\u0119 sortowania stogowego (HS). Podczas sortowania kolejno\u015b\u0107 liczb w tablicy zmienia si\u0119 po ka\u017cdym elementarnym kroku procedury sortuj\u0105cej. Poni\u017cej podano 6 permutacji liczb z tablicy. Wska\u017c, kt\u00f3re z nich nie wyst\u0105pi\u0105 podczas dzia\u0142ania procedury sortujacej:<br>\n        [1] 5,7,9,1,3,12 &nbsp;&nbsp;&nbsp;[2] 5,3,1,7,12,9 &nbsp;&nbsp;&nbsp;[3] 1,7,3,5,9,12<br> [4] 7,3,5,1,9,12 &nbsp;&nbsp;&nbsp;[5] 5,9,7,1,3,12 &nbsp;&nbsp;&nbsp;[6] 9,7,5,1,3,12<\/p><\/li>\n<\/ol>\n<p align=\"right\"><a href=\"#\" target=\"_self\" rel=\"noopener noreferrer\">w g\u00f3r\u0119<\/a><\/p>\n<a name=\"Temat 2\"><\/a><h3>Temat 2: Z\u0142o\u017cone struktury danych<\/h3>\n<ol>\n<li><p>Utw\u00f3rz drzewo BST, do kt\u00f3rego wczytywane s\u0105 kolejno warto\u015bci kluczy &lt;10,3,15,17,9,12,16&gt;. Jaka b\u0119dzie kolejno\u015b\u0107 przechodzenia w\u0119z\u0142\u00f3w tego drzewa metod\u0105 wzd\u0142u\u017cn\u0105 (preorder)?<\/p><\/li>\n<li><p>Zbuduj drzewa poszukiwa\u0144 binarnych (BST) o wysoko\u015bci 2 i 4 zawieraj\u0105ce zbi\u00f3r kluczy {2,2,7,17,20,21,32}.<\/p><\/li>\n<li><p>Podaj kolejno\u015b\u0107 przechodzenia w\u0119z\u0142\u00f3w drzewa o wysoko\u015bci 2 z zadania (2) metod\u0105 poprzeczn\u0105 (inorder).<\/p><\/li>\n<li><p>Utw\u00f3rz drzewo poszukiwa\u0144 binarnych (BST), do kt\u00f3rego wczytywane s\u0105 kolejno warto\u015bci kluczy &lt;9,21,7,11,3,5,32&gt;. Kt\u00f3ry w\u0119ze\u0142 tego drzewa jest jednocze\u015bnie swoim potomkiem i przodkiem w\u0142a\u015bciwym?<\/p><\/li>\n<li><p>Zbuduj drzewo poszukiwa\u0144 binarnych o wysoko\u015bci 3 zawieraj\u0105ce ca\u0142y zbi\u00f3r kluczy {110,3,29,108,230,71,20,351}. Czy mo\u017cna zbudowa\u0107 kopiec zawieraj\u0105cy wszystkie klucze z tego zbioru?<\/p><\/li>\n<li><p>Utw\u00f3rz drzewo poszukiwa\u0144 binarnych (BST) o wysoko\u015bci &gt;2 zawieraj\u0105ce wszystkie klucze ze zbioru {10,41,45,50,67,72,99,107,215,218,320}. Nast\u0119pnie usu\u0144 z niego dowolny w\u0119ze\u0142, kt\u00f3ry nie jest li\u015bciem i poka\u017c drzewo wynikowe.<\/p><\/li>\n<li><p>Podczas przechodzenia poni\u017cszych drzew ponumerowano w\u0119z\u0142y zgodnie z kolejno\u015bci\u0105 ich odwiedzenia. Podaj w jakim porz\u0105dku (pre-order, in-order, post-order, level-order) przeszukiwano ka\u017cde drzewo.<\/p>\n        <p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphD.png\"><\/p><p><\/p><\/li>\n<li><p>Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa <em>O<\/em>(?) procedury wyszukiwania elementu:<br>\n          a) w zdegenerowanym drzewie poszukiwa\u0144 binarnych,<br>\n          b) w dok\u0142adnie wywa\u017conym drzewie poszukiwa\u0144 binarnych?\n<\/p><\/li>\n<li><p>Podczas przechodzenia poni\u017cszych drzew ponumerowano w\u0119z\u0142y zgodnie z kolejno\u015bci\u0105 ich odwiedzenia. Podaj w jakim porz\u0105dku (pre-order, in-order, post-order, level-order) przeszukiwano ka\u017cde drzewo.<\/p>\n        <p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphE.png\"><\/p><p><\/p><\/li>\n<li><p>Jaka jest wysoko\u015b\u0107 (<em>h<\/em>=?) drzewa poszukiwa\u0144 binarnych:<br>\n          a) zdegenerowanego,<br>\n          b) dok\u0142adnie wywa\u017conego<br>\n          sk\u0142adaj\u0105cego si\u0119 z <em>n<\/em> w\u0119z\u0142\u00f3w? Podaj wysoko\u015b\u0107 w funkcji liczby element\u00f3w (w\u0119z\u0142\u00f3w).\n        <\/p><\/li>\n<li><p>Utw\u00f3rz dok\u0142adnie wywa\u017cone drzewo poszukiwa\u0144 binarnych wczytuj\u0105c kolejno klucze z ci\u0105gu &lt;41,15,50,48,58,5,1,20,38,17,49,100&gt;. Nast\u0119pnie przedstaw proces wstawiania do tego drzewa elementu o kluczu r\u00f3wnym &#8222;18&#8221;. Po wstawieniu elementu drzewo powinno zachowa\u0107 w\u0142asno\u015b\u0107 drzewa dok\u0142adnie wywa\u017conego. Poka\u017c drzewo z wstawionym w\u0119z\u0142em.<\/p><\/li>\n<li><p>Dane jest drzewo BST o wysoko\u015bci <em>h<\/em>=7, zawieraj\u0105ce <em>m<\/em> liczb z przedzia\u0142u &lt;1,500&gt;. W tym drzewie chcemy wyszuka\u0107 klucz <em>k<\/em>=245 zgodnie ze standardow\u0105 procedur\u0105 wyszukiwania elementu w drzewie BST. Kt\u00f3re z poni\u017cszych ci\u0105g\u00f3w liczbowych mog\u0105 zosta\u0107 sprawdzone podczas poszukiwania klucza <em>k<\/em>:<br>\n  a) 5,401,348,17,309,245<br>\n  b) 488,1,377,132,310,147,293,182,245<br>\n  c) 100,133,500,184,252,199,117,245<br>\n  d) 150,498,211,486,324,221,245?\n <\/p><\/li>\n<li><p>Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa <em>O<\/em>(?) procedury wyszukiwania klucza o minimalej warto\u015bci w dok\u0142adnie zr\u00f3wnowa\u017conym drzewie poszukiwa\u0144 binarnych? Podaj odpowied\u017a w funkcji liczby element\u00f3w drzewa.<\/p><\/li>\n<li><p>Ile r\u00f3\u017cnych drzew poszukiwa\u0144 binarnych mo\u017cna utworzy\u0107 z 3 liczb o r\u00f3\u017cnych warto\u015bciach?<\/p><\/li>\n<li><p>Zbuduj drzewo poszukiwa\u0144 binarnych (BST) dodaj\u0105c do niego kolejno nast\u0119puj\u0105ce elementy: 10,14,5,7,12,4,6,2,13,16,11,15,9,1,3,8,18,17. Czy tak utworzona struktura jest drzewem wywa\u017conym (AVL)? Uzasadnij odpowied\u017a.<\/p><\/li>\n<li><p>Podaj kolejno\u015b\u0107 przechodzenia w\u0119z\u0142\u00f3w poni\u017cszego drzewa w porz\u0105dkach pre-oder i post-order.\n<\/p><p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphH.png\"><\/p><p><\/p><\/li>\n<li><p>Jaka jest maksymalna liczba element\u00f3w <em>n<\/em> w dok\u0142adnie wywa\u017conym drzewie BST o wysoko\u015bci <em>h<\/em>? Odpowied\u017a sformu\u0142uj w postaci funkcji <em>n<\/em>=f(<em>h<\/em>).<\/p><\/li>\n<li><p>Poni\u017cszy rysunek przedstawia drzewo BST (a) oraz 3 winoro\u015ble (b),(c),(d). Kt\u00f3ra winoro\u015bl powsta\u0142a z drzewa (a) w wyniku zastosowania rotacji w prawo (algorytm DSW)?\n<\/p><p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphI.png\"><\/p><p><\/p><\/li>\n<\/ol>\n<p align=\"right\"><a href=\"#\" target=\"_self\" rel=\"noopener noreferrer\">w g\u00f3r\u0119<\/a><\/p>\n<a name=\"Temat 3\"><\/a><h3>Temat 3: Algorytmy grafowe<\/h3>\n<ol>\n<li><p>Wymie\u0144 5 r\u00f3\u017cnych reprezentacji maszynowych grafu i podaj ich z\u0142o\u017cono\u015b\u0107 pami\u0119ciow\u0105 <em>O<\/em>(?) stosuj\u0105c nast\u0119puj\u0105ce oznaczenia: <em>n<\/em>-liczba wierzcho\u0142k\u00f3w, <em>m<\/em>-liczba kraw\u0119dzi grafu.<\/p><\/li>\n<li><p>Ile pami\u0119ci <em>O<\/em>(?) wymaga zapisanie macierzy incydencji grafu pe\u0142nego o <em>k <\/em> wierzcho\u0142kach?<\/p><\/li>\n<li><p>Podaj kolejno\u015b\u0107 przechodzenia wierzcho\u0142k\u00f3w poni\u017cszego grafu metod\u0105 przeszukiwania wszerz (BFS). Wierzcho\u0142ek <em>a<\/em> jest wierzcho\u0142kiem startowym procedury. W procedurze przechodzenia wybieraj nast\u0119pniki w porz\u0105dku alfabetycznym.\n        <\/p><p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphA.png\"><\/p><p><\/p><\/li>\n<li><p>Podaj kolejno\u015b\u0107 przechodzenia wierzcho\u0142k\u00f3w poni\u017cszego grafu metod\u0105 przeszukiwania wszerz (BFS). Wierzcho\u0142ek <em>b <\/em>potraktuj jako wierzcho\u0142ek startowy procedury, wybieraj nast\u0119pniki w porz\u0105dku alfabetycznym.<\/p>\n        <p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphB.png\"><\/p><p><\/p><\/li>\n<li><p>Jaka jest z\u0142o\u017cono\u015b\u0107 pami\u0119ciowa <em>O<\/em>(?) macierzy s\u0105siedztwa reprezentuj\u0105cej graf skierowany o <em>k<\/em> wierzcho\u0142kach i <em>m<\/em> kraw\u0119dziach?<\/p><\/li>\n<li><p>Podaj kolejno\u015b\u0107 przechodzenia wierzcho\u0142k\u00f3w poni\u017cszego grafu metod\u0105 przeszukiwania w g\u0142\u0105b (DFS). Wierzcho\u0142ek <em>b <\/em>potraktuj jako wierzcho\u0142ek startowy procedury, wybieraj nast\u0119pniki w porz\u0105dku alfabetycznym.<\/p>\n        <p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphC.png\"><\/p><p><\/p><\/li>\n<li><p>Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa procedury przegl\u0105dania grafu wszerz (BFS) zaimplementowanej z u\u017cyciem listy nast\u0119pnik\u00f3w, a jaka z u\u017cyciem macierzy s\u0105siedztwa? Podaj odpowied\u017a w notacji <em>O<\/em> stosuj\u0105c nast\u0119puj\u0105ce oznaczenia: <em>n<\/em>-liczba wierzcho\u0142k\u00f3w, <em>m<\/em>-liczba kraw\u0119dzi grafu.<\/p><\/li>\n<li><p>Podana macierz g\u00f3rnotr\u00f3jk\u0105tna reprezentuje nieskierowany graf z 10-elementowym zbiorem wierzcho\u0142k\u00f3w. Warto\u015b\u0107 &#8222;1&#8221; oznacza kraw\u0119d\u017a mi\u0119dzy wierzcho\u0142kami. Wypisz sekwencj\u0119 wierzcho\u0142k\u00f3w otrzyman\u0105 w wyniku przegl\u0105dania grafu w g\u0142\u0105b (DFS) i przedstaw stos obrazuj\u0105cy przebieg oblicze\u0144. <\/p>\n\n        <table class=\"matrix\" width=\"330\">\n          <tbody><tr>\n            <th scope=\"col\" width=\"30\">&nbsp;<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">1<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">2<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">3<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">4<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">5<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">6<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">7<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">8<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">9<\/th>\n            <th scope=\"col\" width=\"30\" align=\"center\">10<\/th>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">1<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n            <td align=\"center\">1<\/td>\n            <td align=\"center\">1<\/td>\n            <td align=\"center\">1<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">2<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n            <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n            <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">3<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n           <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n            <td align=\"center\">1<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">4<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n            <td align=\"center\">1<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">5<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n\t     <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n\t     <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">6<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n\t     <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n\t     <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">7<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n\t     <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n\t     <td>&nbsp;<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">8<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">9<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td> \n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n\t     <td>&nbsp;<\/td>\n            <td align=\"center\">1<\/td>\n          <\/tr>\n          <tr>\n            <th scope=\"row\" width=\"30\">10<\/th>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n            <td>&nbsp;<\/td> <td>&nbsp;<\/td>\n          <\/tr>\n        <\/tbody><\/table>\n\n<p><\/p><\/li><\/ol>\n\n\n\n<li><p>Narysuj dowolny graf skierowany acykliczny o 6-ciu wierzcho\u0142kach i 80%-wym nasyceniu grafu kraw\u0119dziami. Posortuj topologicznie wierzcho\u0142ki tego grafu. Wykorzystaj algorytm sortowania z przechodzeniem grafu metod\u0105 DFS. \nPodaj czasy odwiedzenia i przetworzenia wierzcho\u0142k\u00f3w grafu oraz sekwencj\u0119 wierzcho\u0142k\u00f3w posortowanych w porz\u0105dku topologicznym.<\/p><\/li>\n<li><p>Podaj i uzasadnij z\u0142o\u017cono\u015b\u0107 obliczeniow\u0105 <em>O<\/em>(?) algorytmu sortowania topologicznego grafu G, wykorzystuj\u0105cego metod\u0119 DFS.<\/p><\/li>\n<li><p>Posortuj topologicznie wierzcho\u0142ki poni\u017cszego grafu stosuj\u0105c metod\u0119 usuwania wierzcho\u0142k\u00f3w o zerowym stopniu wej\u015bciowym. W procedurze zastosuj porz\u0105dek alfabetyczny wyboru wierzcho\u0142k\u00f3w.\n      <\/p><p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphG.png\"><\/p><p><\/p><\/li>\n<li><p>Utw\u00f3rz list\u0119 incydencji poprzednik\u00f3w dla poni\u017cszego grafu. Czy wierzcho\u0142ki tego grafu mo\u017cna posortowa\u0107 topologicznie?<\/p>        \n        <div align=\"justify\"><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphF.png\"><br><p><\/p><\/div><\/li>\n<li><p>Dany jest skierowany graf acykliczny (DAG) reprezentowany w postaci macierzy grafu, listy nat\u0119pnik\u00f3w, listy poprzednik\u00f3w oraz macierzy s\u0105siedztwa. \nDla ka\u017cdej reprezentacji grafu podaj jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa <em>O<\/em>(?) nast\u0119puj\u0105cych operacji:<br>\n(a) sprawdzenie czy w grafie istnieje \u0142uk (v<sub>i<\/sub>,v<sub>j<\/sub>)<br>\n(b) wyznaczenie zbioru poprzednik\u00f3w wierzcho\u0142ka v<sub>i<\/sub> <br>\n(c) wyznaczenie zbioru nast\u0119pnik\u00f3w wierzcho\u0142ka v<sub>i<\/sub> <br>\n(d) wyznaczenie zbioru wierzcho\u0142k\u00f3w, kt\u00f3re nie s\u0105siaduj\u0105 z v<sub>i<\/sub>. <br>\nZastosuj nast\u0119puj\u0105ce oznaczenia: <em>n<\/em>-liczba wierzcho\u0142k\u00f3w grafu G, <em>m<\/em>-liczba kraw\u0119dzi grafu G, <em>p<sub>i<\/sub><\/em>-liczba poprzednik\u00f3w wierzcho\u0142ka v<sub>i<\/sub>, \n<em>s<sub>i<\/sub><\/em>-liczba nat\u0119pnik\u00f3w wierzcho\u0142ka v<sub>i<\/sub>, <em>u<sub>i<\/sub><\/em>-liczba wierzcho\u0142k\u00f3w, kt\u00f3re nie s\u0105siaduj\u0105 z v<sub>i<\/sub>.\n<\/p><\/li>\n\n<p align=\"right\"><a href=\"#\" target=\"_self\" rel=\"noopener noreferrer\">w g\u00f3r\u0119<\/a><\/p>\n<a name=\"Temat 4\"><\/a><h3>Temat 4: Algorytmy z powracaniem<\/h3>\n<ol>\n<li><p>Jakie s\u0105 warunki istnienia cyklu Eulera w grafie skierowanym, a jakie w grafie nieskierowanym?<\/p><\/li>\n<li><p>Do jakiej klasy z\u0142o\u017cono\u015bci obliczeniowej nale\u017cy wersja decyzyjna problemu poszukiwania cyklu Hamiltona w grafie?<\/p><\/li>\n<li><p>Do jakiej klasy z\u0142o\u017cono\u015bci obliczeniowej nale\u017cy problem poszukiwania cyklu Eulera w grafie? Czy jest to problem decyzyjny czy optymalizacyjny?<\/p><\/li>\n<li><p>Warunkiem koniecznym i wystarczaj\u0105cym istnienia cyklu Eulera w grafie nieskierowanym jest (zaznacz jedno poprawne stwierdzenie):<br>\n(a) nie jest znany odpowiedni warunek<br>\n(b) sp\u00f3jno\u015b\u0107 grafu<br>\n(c) sp\u00f3jno\u015b\u0107 grafu i parzysty stopie\u0144 ka\u017cdego wierzcho\u0142ka<br>\n(d) sp\u00f3jno\u015b\u0107 grafu i parzysty stopie\u0144 przynajmniej po\u0142owy wierzcho\u0142k\u00f3w<br>\n(e) w tego typu grafie nie mo\u017ce istnie\u0107 cykl Eulera  <\/p><\/li>\n<li><p>Podaj minimaln\u0105 liczb\u0119 operacji (dodanie\/usuni\u0119cie wierzcho\u0142ka\/kraw\u0119dzi) jakie nale\u017cy wykona\u0107, aby poni\u017cszy graf przekszta\u0142ci\u0107 w graf Eulerowski.\n<\/p><p><img decoding=\"async\" src=\"..\/..\/..\/wp-content\/uploads\/2021\/02\/graphJ.png\"><\/p><p><\/p><\/li>\n<li><p>Przedstaw krok po kroku dzia\u0142anie algorytmu Fleury&#8217;ego na przyk\u0142adowym grafie nieskierowanym. Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa tego algorytmu dla grafu reprezentowanego w postaci macierzy s\u0105siedztwa?<\/p><\/li>\n<li>Algorytm z powracaniem dla problemu komiwoja\u017cera ma z\u0142o\u017cono\u015b\u0107 obliczeniow\u0105 (zaznacz jedno poprawne stwierdzenie):<br>\n(a) wielomianow\u0105 <br> \n(b) logarytmiczn\u0105 <br>\n(c) termin &#8222;z\u0142o\u017cono\u015b\u0107 obliczeniowa&#8221; jest zarezerwowany dla problem\u00f3w i nie mo\u017cna m\u00f3wic o z\u0142o\u017cono\u015bci algorytmu <br>\n(d) wyk\u0142adnicz\u0105 <br>\n(e) pseudowielomianow\u0105 <p><\/p><\/li>\n<li><p>Czy istnieje wielomianowy algorytm znajduj\u0105cy cykl Hamiltona w dowolnym grafie skierowanym? Odpowied\u017a kr\u00f3tko uzasadnij.<\/p><\/li>\n<li><p>Dany jest graf G reprezentowany w postaci listy nast\u0119pnik\u00f3w:<br>\n1: 2,4<br>2: 6<br>3: 1<br>4: 7<br>5: 1,3<br>6: 5,8<br>7: 8<br>8: 5<br>\nCzy ten graf jest grafem Eulerowskim? Uzasadnij odpowied\u017a.<\/p><\/li>\n<li><p>Czy graf z powy\u017cszego zadania jest Hamiltonowski lub p\u00f3\u0142-Hamiltonowski? Je\u015bli tak, wypisz odpowiedni\u0105 sekwencj\u0119 wierzcho\u0142k\u00f3w.<\/p><\/li>\n<li><p>Czy prawdziwe s\u0105 zdania &#8222;Cykl Eulera przechodzi przez ka\u017cd\u0105 kraw\u0119d\u017a grafu nieskierowanego dok\u0142adnie jeden raz. Cykl Hamiltona przechodzi przez \nka\u017cdy wierzcho\u0142ek grafu nieskierowanego dok\u0142adnie jeden raz, a tym samym przez ka\u017cd\u0105 kraw\u0119d\u017a tego grafu co najwy\u017cej jeden raz.&#8221;?<\/p><\/li>\n<li><p>Narysuj:<br>\na) eulerowski graf skierowany,<br> \nb) p\u00f3\u0142-eulerowski graf nieskierowany,<br>\nc) hamiltonowski graf nieskierowany,<br>\nd) p\u00f3\u0142-hamiltonowski graf skierowany o 5-ciu wierzcho\u0142kach i dowolnie dobranej liczbie kraw\u0119dzi.<\/p><\/li>\n<\/ol>\n<p align=\"right\"><a href=\"#\" target=\"_self\" rel=\"noopener noreferrer\">w g\u00f3r\u0119<\/a><\/p>\n<a name=\"Temat 5\"><\/a><h3>Temat 5: Programowanie dynamiczne<\/h3>\n<ol>\n<li><p>(5 punkt\u00f3w) Kurier Bonifacy ma do rozwiezienia 6 przesy\u0142ek. Dysponuje on plecakiem o ograniczonej pojemno\u015bci b=8. \nKa\u017cda z przesy\u0142ek zajmuje odpowiednio s=[2,1,4,1,4,3] pojemno\u015bci plecaka. Za dostarczenie przesy\u0142ek kurier otrzyma \nwynagrodzenie odpowiednio w = [7,4,5,1,4,9] Euro. Przesy\u0142ki, kt\u00f3re nie zmieszcz\u0105 si\u0119 do plecaka Bonifacego \ndostarczy kurier Bonawentura pracuj\u0105cy na drug\u0105 zmian\u0119. Korzystaj\u0105c z metody programowania dynamicznego pom\u00f3\u017c Bonifacemu \npodj\u0105\u0107 decyzj\u0119, kt\u00f3re z przesy\u0142ek powinien zabra\u0107, aby zmaksymalizowa\u0107 otrzymane wynagrodzenie.\n<\/p><ul><li>Jakie b\u0119dzie maksymalne wynagrodzenie i kt\u00f3re przesy\u0142ki zabierze Bonifacy?<\/li>\n<li>Podaj warto\u015bci z wybranych kom\u00f3rek tablicy koszt\u00f3w V[i,j] i tablicy decyzyjnej Q[i,j] \n(gdzie <em>i<\/em> oznacza przesy\u0142k\u0119, <em>j<\/em> oznacza pojemno\u015b\u0107 plecaka): V[2,1], V[3,3], V[4,8], V[5,7], V[6,4], Q[3,1], Q[3,5], Q[4,7], Q[6,4], Q[6,6].<\/li>\n<\/ul>\n<p><\/p><\/li>\n<li><p>Podaj algorytm programowania dynamicznego rozwi\u0105zujacy problem podzia\u0142u zbioru. Zastosuj ten algorytm do znalezienia podzia\u0142u zbioru A=[1,9,5,3,8]. Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa tego algorytmu?<\/p><\/li>\n<li><p>Napisz og\u00f3lny wz\u00f3r (funkcj\u0119 rekurencyjn\u0105) programowania dynamicznego dla problemu plecakowego.<\/p><\/li>\n<li><p>Do jakiej klasy problem\u00f3w, ze wzgl\u0119du na z\u0142o\u017cono\u015b\u0107 obliczeniow\u0105, nale\u017cy wersja decyzyjna problemu plecakowego?<\/p><\/li>\n<li><p>Zdefiniuj dyskretny problem plecakowy podaj\u0105c i obja\u015bniaj\u0105c funkcj\u0119 kryterialn\u0105 oraz parametry problemu. \nDo jakiej klasy problem\u00f3w, ze wzgl\u0119du na z\u0142o\u017cono\u015b\u0107 obliczeniow\u0105, nale\u017cy wersja optymalizacyjna tego problemu? <\/p><\/li>\n<li><p> Dana jest instancja problemu plecakowego dla pojemno\u015bci plecaka b=8:<\/p><\/li><\/ol>\n\n\n\n<div class=\"wp-block-columns has-2-columns is-layout-flex wp-container-core-columns-is-layout-1 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<div class=\"wp-block-group is-layout-flow wp-block-group-is-layout-flow\"><div class=\"wp-block-group__inner-container\">\n\n<\/div><\/div>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n<\/div>\n\n\n\nWype\u0142nij tabel\u0119 rozwi\u0105za\u0144 dla tak danego problemu. Zaznacz rozwi\u0105zanie optymalne i wypisz, kt\u00f3re elementy wchodz\u0105 do plecaka oraz podaj ich \u0142\u0105czn\u0105 warto\u015b\u0107.\n<p><\/p>\n<li><p>Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa O(?) algorytmu dok\u0142adnego (&#8222;brute force&#8221;) przeszukuj\u0105cego wyczerpuj\u0105co przestrze\u0144 rozwi\u0105za\u0144 dla dyskretnego problemu plecakowego?<\/p><\/li>\n<li><p>Jaka jest z\u0142o\u017cono\u015b\u0107 obliczeniowa O(?) algorytmu programowania dynamicznego dla dyskretnego problemu plecakowego z plecakiem o rozmiarze <em>R<\/em> oraz liczbie element\u00f3w <em>n<\/em>?<\/p><\/li>\n    \n<p align=\"right\"><a href=\"#\" target=\"_self\" rel=\"noopener noreferrer\">w g\u00f3r\u0119<\/a><\/p>\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-126","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/126","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=126"}],"version-history":[{"count":5,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/126\/revisions"}],"predecessor-version":[{"id":2283,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/126\/revisions\/2283"}],"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=126"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}