{"id":303,"date":"2013-05-07T02:02:46","date_gmt":"2013-05-07T02:02:46","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/?page_id=303"},"modified":"2013-06-18T19:01:33","modified_gmt":"2013-06-18T19:01:33","slug":"wybrane-zagadnienia-algorytmiki-201213","status":"publish","type":"page","link":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/?page_id=303","title":{"rendered":"Wybrane Zagadnienia Algorytmiki 2012\/13"},"content":{"rendered":"<h1>Notatki<\/h1>\n<p>Poni\u017cej udost\u0119pnione s\u0105 notatki do wyk\u0142ad\u00f3w, przygotowane przez student\u00f3w. Notatki do ka\u017cdego wyk\u0142adu znajduj\u0105 si\u0119 w osobnym pliku pdf, mo\u017cna te\u017c \u015bci\u0105gn\u0105\u0107 <a href=\"wza.zip\">archiwum<\/a> zawieraj\u0105ce komplet notatek oraz zadania z wybranych \u0107wicze\u0144.<br \/>\n<br \/>\nNotatki na stronie umieszczamy po uprzednim sprawdzeniu ich, co nie musi jednak znaczy\u0107, \u017ce nie ma w nich b\u0142\u0119d\u00f3w. W przypadku znalezienia takowych prosimy o kontakt. Osoby bior\u0105ce udzia\u0142 w zaj\u0119ciach mog\u0105 te\u017c same wprowadzi\u0107 zmiany w repozytorium (tam te\u017c znajduj\u0105 si\u0119 najnowsze wersje notatek). Prosimy jednak o korzystanie z tej metody nanoszenia poprawek tylko w sytuacjach, kiedy b\u0142\u0105d jest ewidentny.<br \/>\n<br \/>\nCz\u0119\u015bci notatek nie otrzymali\u015bmy i zapewne przed egzaminem nie otrzymamy. Do tych wyk\u0142ad\u00f3w proponujemy inne \u017ar\u00f3d\u0142a, w miar\u0119 mo\u017cliwo\u015bci zbli\u017cone do wyk\u0142adu pod wzgl\u0119dem sposobu prezentacji. U\u017cywane tam skr\u00f3ty bibliograficzne:<\/p>\n<ul>\n<li>[LRS] Lap Chi Lau, R. Ravi, Mohit Singh <a href=\"http:\/\/research.microsoft.com\/en-us\/um\/people\/mohits\/book\/book.pdf\">Iterative Methods in Combinatorial Optimization<\/a> <\/li>\n<li>[SW] David Shmoys, David Williamson <a href=\"http:\/\/www.designofapproxalgs.com\/book.pdf\">Design of Approximation Algorithms<\/a> <\/li>\n<\/ul>\n<p>Przy okazji te dwie pozycje najlepiej pasuj\u0105 tematycznie do wyk\u0142adu.<br \/>\n<strong> Uwaga: <\/strong> Niekt\u00f3re z link\u00f3w poni\u017cej prowadz\u0105 do artyku\u0142\u00f3w Springera i w zwi\u0105zku z tym s\u0105 dost\u0119pne tylko z wydzia\u0142u. Alternatyw\u0105 jest dopisanie przed adresem &#8220;https:\/\/han.buw.uw.edu.pl\/han\/atoz&#8221; i zalogowanie si\u0119 numerem karty bibliotecznej, np. &#8220;https:\/\/han.buw.uw.edu.pl\/han\/atoz\/link.springer.com\/content\/pdf\/10.1007\/3-540-44985-X_19.pdf&#8221;<br \/>\n<\/p>\n<table>\n<tr>\n<td width=\"80\"> <a href=\"wza\/01_algebraic_methods.pdf\">Wyk\u0142ad 1<\/a> <\/td>\n<td> Metody algebraiczne <\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/02_apsp.pdf\">Wyk\u0142ad 2 <\/a> <\/td>\n<td> Metody algebraiczne, c.d. &#8211; najkr\u00f3tsze \u015bcie\u017cki <\/td>\n<\/tr>\n<tr>\n<td> Wyk\u0142ad 3 <\/td>\n<td> Local search. Zamiast notatek: o k-medianie rozdzia\u0142 4 w tych <a href=\"http:\/\/www.cs.umd.edu\/~hajiagha\/NetDsgn11\/scribe-05-10-2011.pdf\"> notatkach<\/a>, dla niewa\u017conych skojarze\u0144 w hipergrafach nie ma dobrego \u017ar\u00f3d\u0142a, wa\u017cone s\u0105 w tej <a href=\"http:\/\/link.springer.com\/chapter\/10.1007\/3-540-44985-X_19\"> pracy<\/a> (link dzia\u0142a tylko z wydzia\u0142u).<\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/04_linear_programs.pdf\">Wyk\u0142ad 4 <\/a> <\/td>\n<td> Iterowane zaokr\u0105glanie <\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/05_rounding.pdf\">Wyk\u0142ad 5 <\/a> <\/td>\n<td> Iterowane zaokr\u0105glanie, c.d. + zaokr\u0105glanie zale\u017cne <\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/06_rounding.pdf\">Wyk\u0142ad 6 <\/a> <\/td>\n<td> Zaokr\u0105glanie zale\u017cne, c.d. + zapowied\u017a zanurze\u0144 metrycznych<\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/07_metric_embedding.pdf\">Wyk\u0142ad 7<\/a><\/td>\n<td> Zanurzenia w metryki drzewowe<\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/08_semidefinite_programming.pdf\">Wyk\u0142ad 8<\/a><\/td>\n<td> Programowanie p\u00f3\u0142okre\u015blone <\/td>\n<\/tr>\n<tr>\n<td> Wyk\u0142ad 9 <\/td>\n<td> Hierarchie program\u00f3w liniowych. Zamiast notatek: Rozdzia\u0142 2 z tej <a href=\"http:\/\/www.cs.princeton.edu\/~chlamtac\/sdpchapter.pdf\">monografii <\/a>, twierdzenie o dekompozycji z tej <a href=\"http:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-20807-2_24\">pracy<\/a> (link dzia\u0142a tylko z wydzia\u0142u), prostsza wersja wyst\u0119puje (jako lemat 2.1) w tej <a href=\"http:\/\/www.idsia.ch\/~grandoni\/Pubblicazioni\/CGM13soda.pdf\">pracy<\/a>.<br \/>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/10_hardness.pdf\">Wyk\u0142ad 10<\/a><\/td>\n<td> Trudno\u015b\u0107 aproksymacji<\/td>\n<\/tr>\n<tr>\n<td> Wyk\u0142ad 11 <\/td>\n<td> Trudno\u015b\u0107 aproksymacji &#8211; hipoteza Unique Games. Zamiast notatek: Szcz\u0105tkowy opis w rozdziale 14.5 w [SW] <\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/12_mwu.pdf\">Wyk\u0142ad 12<\/a><\/td>\n<td> Algorytm Multiplicative Weights Update<\/td>\n<\/tr>\n<tr>\n<td> Wyk\u0142ad 13 <\/a> <\/td>\n<td> LP konfiguracji na przyk\u0142adzie algorytmu Karmarkara-Karpa. Zamiast notatek: rozdzia\u0142 4.6 w [SW], ew. 13.5 w [LRS] (nieco inne grupowanie i nieco inna analiza).<\/td>\n<\/tr>\n<\/table>\n<p><\/p>\n<h1>Zadania z \u0107wicze\u0144<\/h1>\n<p>Poni\u017cej mo\u017cna znale\u017a\u0107 zadania z niekt\u00f3rych \u0107wicze\u0144.<br \/>\n<\/p>\n<table>\n<tr>\n<td> <a href=\"wza\/cwiczenia1.pdf\">\u0106wiczenia 1<\/a> <\/td>\n<td> Metody algebraiczne <\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/cwiczenia2.pdf\">\u0106wiczenia 2 <\/a> <\/td>\n<td> Metody algebraiczne, c.d. &#8211; najkr\u00f3tsze \u015bcie\u017cki <\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/cwiczenia10.pdf\">\u0106wiczenia 10 <\/a> <\/td>\n<td> Trudno\u015b\u0107 aproksymacji<\/td>\n<\/tr>\n<tr>\n<td> <a href=\"wza\/cwiczenia11.pdf\">\u0106wiczenia 11 <\/a> <\/td>\n<td> Hipoteza Unique Games <\/td>\n<\/tr>\n<\/table>\n<p><\/p>\n<h1>Praca domowa 2<\/h1>\n<p>Oto <a href=\"wza\/zadania2.pdf\">druga seria zada\u0144<\/a>. Rozwi\u0105zania nale\u017cy odda\u0107 do ko\u0144ca zaj\u0119\u0107 w dniu 12.06.2013 w formie papierowej lub elektronicznej. W przypadku formy papierowej prosimy o dostarczanie rozwi\u0105za\u0144 na osobnych kartkach. <\/p>\n<h1>Praca domowa 1<\/h1>\n<p>Oto <a href=\"wza\/zadania1.pdf\">pierwsza seria zada\u0144<\/a>. Rozwi\u0105zania nale\u017cy odda\u0107 do ko\u0144ca zaj\u0119\u0107 w dniu 15.05.2013 w formie papierowej lub elektronicznej. W przypadku formy papierowej prosimy o dostarczanie rozwi\u0105za\u0144 na osobnych kartkach. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Notatki Poni\u017cej udost\u0119pnione s\u0105 notatki do wyk\u0142ad\u00f3w, przygotowane przez student\u00f3w. Notatki do ka\u017cdego wyk\u0142adu znajduj\u0105 si\u0119 w osobnym pliku pdf, mo\u017cna te\u017c \u015bci\u0105gn\u0105\u0107 archiwum zawieraj\u0105ce komplet notatek oraz zadania z wybranych \u0107wicze\u0144. Notatki na stronie umieszczamy po uprzednim sprawdzeniu ich, &hellip; <a href=\"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/?page_id=303\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/303"}],"collection":[{"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=303"}],"version-history":[{"count":44,"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/303\/revisions"}],"predecessor-version":[{"id":307,"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/303\/revisions\/307"}],"wp:attachment":[{"href":"https:\/\/duch.mimuw.edu.pl\/~mucha\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=303"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}