Materiały pomocnicze do zajęć

Wyjątki z wykładów

Optymalizacja kombinatoryczna
° Combinatorial Optimization for AI (pdf, passwd: number of the 1st lecture room lowercase letters no spaces)
° Optymalizacja kombinatoryczna skanowane folie (pdf, hasło: nr sali wykładowej w której zajęcia ma informatyka + w budynku "??", małe litery). Uwaga: 1) folie nie są ułożone dokładnie w kolejności omawiania, 2) niektóre zagadnienia które są na foliach nie są omawiane na wykładzie i na odwrót, 3) do zaliczenia obowiązuje materiał przedstawiony na wykładzie, 4) folie w języku polskim od 2018r. nie są uaktualniane, zachęcam do korzystania z prezentacji w j.angielskim (powyżej), 5) polskie folie i angielskie slajdy mają nieco różniące się zawartości.
° Nagrania wykładów online z OK z roku akademickiego 2021-22. Pliki mp4, ≈ 1.1GB. Hasło - ell zero 2 dziewięć be te (razem 6 znaków).
° Przykłady wyznaczania maksymalnego przepływu w sieci: 1, 2, 3, 4 (jpg, 140-160kB, 2440ptx3445pt)
° Przykład wyznaczania przepływu o minimalnym koszcie (pdf, 43k)
° Przykład wyznaczania ścieżki krytycznej (CPM)
° Przykład kolorowania algorytmem Browna

Artykuły do optymalizacji kombinatorycznej (lektura uzupełniająca)
° Jakie warunki musi spełniać system monetarny, aby algorytm zachłanny wydawał resztę w minimalnej liczbie jednostek monetarnych (monet lub banknotów) analizuje np. artykuł Xuan Cai, Canonical Coin Systems for Change-Making Problems arXiv:0809.0400 [cs.DS] z 2009r. Zachęcam aby przeczytać chociaż rozdział "1.B Related work" i Theorem 2.
° Anliza złożoności struktury/algorytmu union-find można znaleźć tu 1, tu 2, tu 3, i tu 4. Dostęp do artykułu SIAM J.on Computing jest możliwy z sieci PP przez bibliotekę PP.
° Jak uzyskać odległości w grafie przez sprowadzenie do mnożenia macierzy? Mówi o tym np. Artykuł Uri Zwicka: All pairs shortest paths using bridging sets and rectangular matrix multiplication , Journal of the ACM, 49(3), 2002, pp.289-317. Dostęp do artykułu jest możliwy z sieci PP przez bibliotekę PP (E-zasoby → Lista czasopism pełnotekstowych A-to-Z, etc). Można też poszukać materiałów na temat "all pairs shortest path matrix multiplication".
° Artykuł o odkryciach metod do rozwiązywania problemu przydziału (skojarzenia o minimalnym koszcie w grafie dwudzielnym): Harold W. Kuhn, A tale of three eras: The discovery and rediscovery of the Hungarian Method, European Journal of Operational Research, Volume 219, Issue 3, 16 June 2012, Pages 641–651. Czasopismo EJOR jest dostępne przez bibliotekę PP.
° Alexander Schrijver, On the history of the transportation and maximum flow problems, February 2002, Volume 91, Issue 3, pp 437–445. Tytył wyjaśnia o czym jest artykuł. Szczególnej uwadze polecam rysynek 2. Wnioski? Kopia tego artykułu jest dostępna za darmo ze strony Autora, o tutaj .
° Artykuł o wyznaczaniu odległości w grafach i mapach (np. 2,3- wymiarowych). Opisuje algorytm A*, różne rozszerzenia problemu wyznaczania odległości i ścieżek. W końcu przestawiony został algorytm "cross-entropy". To może się przydać w kontekście algorytmów mrówkowych (ant colonies). N.b. algorytmy o mniejszej złożoności niż prezentowane na wykładzie nie są zaskakujące, gdy założymy że ścieżka jest budowana w przestrzeni o pewnych właściwościach, np. w przestrzeni Euklidesowej. Źródło: D.Drusinsky, J.B.Michael, Multiagent Pathfinding Under Rigid, Optimization, and Uncertainty Constraints, in Computer, vol. 54, no. 07, pp. 111-118, 2021.
° Artykuł o kontrowaersjach i trudności porównania różnych rozwiązań wielokryterialnego problemu umieszczania elementów logicznych i pamięci w zastosowaniu do elektronicznej automatyzacji projektowania (placement problem, electronic design automation). Trudność wynika z: wielokryterialności, (nie-)kompletności użytych benchmarków (instancji testowych), odtwarzalności wyników (reproducibility), użycia uczenia maszynowego które ucząc się na przykładach staje się stronnicze bo może zapamiętywać widziane przykłady. Samuel K. Moore, Ending an Ugly Chapter in Chip Design, IEEE Spectrum, June 2023 (online: 04 Apr 2023)
Można mnie poprosić o powyższe artykuły jeżeli nie są dostępne w bibliotece PP.
Jeszcze więcej do czytania na końcu tej strony poniżej.→

Ocena efektywności systemów komputerowych
° Ocena efektywności (pdf, hasło: numer sali w której odbywa się laboratorium małe litery),
° Dror G. Feitelson, Workload Modeling for Computer Systems Performance Evaluation, Cambridge University Press, 2015. Książka o badaniu i modelowaniu obciążeń. A tutaj jest kopia za darmo od Autora.

Materiały (pre)historyczne
° Wyklady dla studiów doktoranckich PP, 2013: pierwszy 2. 3. i 4. 4. cd. (pdfy, hasło - nr sali w której były 2.zajęcia +bt)
° Algorytmy i środowiska równoległe (pdf, hasło: inicjały szefa/opiekuna specjalizacji, 2000-2008),
° "Wyobraźnia może być przydatna, ale nie jest konieczna" (wg słów kolegi Studenta), czyli Narzędzia przetwarzania współbieżnego - konspekty z 2001r. (zip. ok 670k)
° Szeregowanie zadań (SZS420) - folie z 2000r.
° Przetwarzanie równoległe - wyjątki i konspekt z wykładu z 1997-2000r.(pdf, hasło: numer sali w której odbywa się laboratorium z przetwarzania równoległego dla III roku, małe litery)
° Algorytmy i Struktury Danych - konspekt wykładu z 1999r. Piła/Gniezno (~1MB)
° Złożoność obl. i Opt. kombinatoryczna - konspekt wykładu z 1997r. (270kB)

Pomoce

° Divisible load portal
° Symulator algorytmów równoważenia obciążeń (prototyp)

Warte przeczytania

° “Free” Online Services and Gonzo Capitalism Computer, Vol. 56, Issue: 7, July 2023, doi: 10.1109/MC.2023.3271449. Jak się finansują darmowe serwisy internetowe? Jeśli nie potrafisz odpowiedzieć którędy płyną pieniądze, to znaczy że nie jesteś przy stole, tylko w menu.
° Good Ideas, Through the Looking Glass, Niklaus Wirth, 2005. Interesujące w kontekście rozwoju technologii, także aby pamiętać heroiczne czasy i nie robić tych samych błędów ponownie.
° Long Tail Hardware: Turning Device Concepts Into Viable Low Volume Products (DOI: 10.1109/MPRV.2019.2947966) o trudności przejścia od sprzętowego prototypu ("I have one that works") do produktu ("anyone can buy one"). Dla wszystkich sprzętowych startuperów. Dostępne przez bibliotekę PP. Alternative source (bez rejestracji).
° Książka o niczym. Od pustki Greków, przez zero Babilończyków i nicość Hindusów, po próżnię kwantową współczesnej nauki, John D.Barrow, Copernicus Center Press Kraków 2015, (wyd. ang. The Book of Nothing John D. Barrow, fist published by Jonathan Cape, one of the Publishers in The Random House Group Ltd.)
° Pi razy oko, komedia matematycznych pomyłek, Matt Parker, 2021, ang. Humble Pi. A Comedy of Math Errors Penguin 2019. Książka o błędach obliczeniowych popełnianych w życiu codziennym, w technologiach informatycznych i w inżynierii.

Last modified :