{"id":173,"date":"2021-02-04T16:28:02","date_gmt":"2021-02-04T15:28:02","guid":{"rendered":"http:\/\/localhost\/mSzachniuk\/?page_id=173"},"modified":"2024-10-07T10:11:23","modified_gmt":"2024-10-07T08:11:23","slug":"tematyka","status":"publish","type":"page","link":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/teaching\/algorytmy-i-struktury-danych\/tematyka\/","title":{"rendered":"ASD-tematyka"},"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\"><strong>Tematyka zaj\u0119\u0107 laboratoryjnych<\/strong><\/h1>\n\n\n\n<table style=\"text-align: left; width: 100%;\" cellspacing=\"0\" cellpadding=\"2\" border=\"0\">\n  <tbody>\n    <tr>\n      <td style=\"vertical-align: top; width: 10%;\"><span style=\"font-style: italic;\">temat I<\/span> <br>      <\/td>\n      <td style=\"vertical-align: top; width: 90%; text-align: justify;\"> <em>Algorytmy sortowania <\/em><br>\n\n<ol>\n   <li>Naiwne algorytmy sortowania:\n    <ul>\n        <li>Sortowanie przez proste wybieranie (Selection Sort)<\/li>\n        <li>Sortowanie przez proste wstawianie (Insertion Sort)<\/li>\n        <li>Sortowanie przez prost\u0105 zamian\u0119 (Bubble Sort)<\/li>\n    <\/ul><\/li>\n    <li>Z\u0142o\u017cono\u015b\u0107 pami\u0119ciowa algorytm\u00f3w sortowania<\/li>\n    <li>Podstawowe operacje w sortowaniu<\/li>\n    <li>Z\u0142o\u017cono\u015b\u0107 obliczeniowa algorytm\u00f3w sortowania<\/li>\n    <li>Analiza z\u0142o\u017cono\u015bci obliczeniowej dla r\u00f3\u017cnych rozk\u0142ad\u00f3w danych wej\u015bciowych<\/li>\n    <li>Algorytmy sortowania oparte na podej\u015bciu &#8222;dziel i zwyci\u0119\u017caj&#8221;\n    <ul>\n        <li>Sortowanie szybkie (Quick sort)<\/li>\n        <li>Sortowanie stogowe (Heap Sort)<\/li>\n        <li>Sortowanie przez scalanie (Merge Sort)<\/li>\n    <\/ul><\/li>\n    <li>Co oznacza stabilno\u015b\u0107 sortowania<\/li>\n    <li>W\u0142a\u015bciwo\u015b\u0107 sortowania w miejscu<\/li>\n    <li>Inne przyk\u0142ady algorytm\u00f3w sortowania\n    <ul>\n        <li>Sortowanie za pomoc\u0105 malej\u0105cych przyrost\u00f3w (Shell Sort)<\/li>\n        <li>Sortowanie przez zliczanie (Counting sort)<\/li>\n    <\/ul><\/li>\n<\/ol>\n     <\/td><\/tr>\n    <tr>\n      <td style=\"vertical-align: top; width: 10%;\"><span style=\"font-style: italic;\">temat II <\/span><br>\n      <\/td>\n      <td style=\"vertical-align: top; width: 90%; text-align: justify;\"><div align=\"justify\"><em>Z\u0142o\u017cone struktury danych<\/em><br> \n         \n<ol>\n    <li>Struktura listy jedno- i dwukierunkowej<\/li>\n    <li>Struktura drzewa poszukiwa\u0144 binarnych (BST)<\/li>\n    <li>Drzewo zr\u00f3wnowa\u017cone (AVL), drzewo dok\u0142adnie wywa\u017cone (DDW), drzewo zdegenerowane (winoro\u015bl)<\/li>\n    <li>W\u0142asno\u015bci r\u00f3\u017cnych drzew BST<\/li>\n    <li>Tworzenie i usuwanie listy\/drzewa<\/li>\n    <li>Metoda przeszukiwania binarnego w tworzeniu drzewa AVL<\/li>\n    <li>Wyszukiwanie elementu na li\u015bcie\/w drzewie<\/li>\n    <li>Usuwanie pojedynczych element\u00f3w listy\/drzewa<\/li>\n    <li>Przegl\u0105danie drzewa w porz\u0105dku wzd\u0142u\u017cnym (preorder), poprzecznym (inorder) i wstecznym (postorder)<\/li>\n    <li>Rotacje w drzewie binarnym<\/li>\n    <li>R\u00f3wnowa\u017cenie drzewa metod\u0105 DSW (Day-Stout-Warren)<\/li>\n    <li>R\u00f3wnowa\u017cenie drzewa metod\u0105 z usuwaniem korzeni niezbalansowanych poddrzew<\/li>\n<\/ol>\n      <\/div><\/td>\n    <\/tr>\n    <tr>\n      <td style=\"vertical-align: top;\"><span style=\"font-style: italic;\">temat III<\/span><\/td>\n      <td style=\"vertical-align: top; text-align: justify;\"><div align=\"justify\"><em>Algorytmy grafowe<\/em><br> \n\n<ol>\n    <li>Wybrane poj\u0119cia z teorii graf\u00f3w<\/li>\n    <li>Reprezentacje maszynowe grafu: lista kraw\u0119dzi, macierz s\u0105siedztwa, macierz incydencji, lista s\u0105siedztwa, lista nast\u0119pnik\u00f3w, lista poprzednik\u00f3w, macierz grafu<\/li>\n    <li>W\u0142asno\u015bci r\u00f3\u017cnych reprezentacji maszynowych grafu<\/li>\n    <li>Z\u0142o\u017cono\u015b\u0107 pami\u0119ciowa i z\u0142o\u017cono\u015b\u0107 pozyskiwania informacji o grafie dla r\u00f3\u017cnych reprezentacji maszynowych<\/li>\n    <li>Algorytmy przeszukiwania grafu w g\u0142\u0105b (Depth First Search = DFS) i wszerz (Breadth First Search = BFS)<\/li>\n    <li>Algorytm sortowania topologicznego metod\u0105 Kahna<\/li>\n    <li>Algorytm sortowania topologicznego z wykorzystaniem przechodzenia w g\u0142\u0105b<\/li>\n<\/ol>\n\n     <\/div><\/td>\n    <\/tr>\n    <tr>\n      <td style=\"vertical-align: top;\"><span style=\"font-style: italic;\">temat IV<\/span><\/td>\n      <td style=\"vertical-align: top; text-align: justify;\"><div align=\"justify\"><em>Algorytmy z powracaniem <\/em><br>\n\n<ol>\n    <li>Idea dzia\u0142ania algorytm\u00f3w z powracaniem<\/li>\n    <li>Problem znajdowania \u015bcie\u017cki i cyklu Hamiltona w grafie<\/li>\n    <li>Problem znajdowania \u015bcie\u017cki i cyklu Eulera w grafie<\/li>\n    <li>Wersja przeszukiwania i wersja decyzyjna problemu \u015bcie\u017cki Hamiltona i \u015bcie\u017cki Eulera<\/li>\n    <li>Algorytm z powracaniem dla problemu poszukiwania cyklu Hamiltona<\/li>\n    <li>Algorytm z powracaniem dla problemu poszukiwania cyklu Eulera<\/li>\n    <li>Przynale\u017cno\u015b\u0107 obydwu problem\u00f3w do klas z\u0142o\u017cono\u015bci<\/li>\n    <li>Z\u0142o\u017cono\u015b\u0107 obliczeniowa algorytm\u00f3w poszukiwania cyklu Hamiltona i cyklu Eulera<\/li>\n<\/ol>\n\n      <\/div><\/td>\n    <\/tr>\n    <tr>\n      <td style=\"vertical-align: top;\"><span style=\"font-style: italic;\">temat V<\/span><\/td>\n      <td style=\"vertical-align: top; text-align: justify;\"><div align=\"justify\"><em>Programowanie dynamiczne<\/em><br>\n\n<ol>\n    <li>Problem plecakowy i jego r\u00f3\u017cne wersje<\/li>\n    <li>Sformu\u0142owanie 0-1 problemu plecakowego<\/li>\n    <li>Algorytm wyczerpuj\u0105cy dla 0-1 problemu plecakowego<\/li>\n    <li>Algorytm zach\u0142anny dla 0-1 problemu plecakowego<\/li>\n    <li>Metodyka programowania dynamicznego<\/li>\n    <li>Algorytm programowania dynamicznego dla 0-1 problemu plecakowego<\/li>\n    <li>Klasa z\u0142o\u017cono\u015bci problemu plecakowego<\/li>\n    <li>Z\u0142o\u017cono\u015b\u0107 obliczeniowa algorytm\u00f3w wyczerpuj\u0105cego, zach\u0142annego i programowania dynamicznego dla 0-1 problemu plecakowego<\/li>\n<\/ol>\n\n      <\/div><\/td>\n    <\/tr>\n\n  <\/tbody>\n<\/table>\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-173","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/173","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=173"}],"version-history":[{"count":16,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/173\/revisions"}],"predecessor-version":[{"id":2281,"href":"https:\/\/www.cs.put.poznan.pl\/mszachniuk\/site\/wp-json\/wp\/v2\/pages\/173\/revisions\/2281"}],"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=173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}