Materiały pomocnicze do zajęć

Wyjątki z wykładów

Optymalizacja kombinatoryczna
° Combinatorial Optimization for AI (pdf, passwd: number of the AI 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
° Drugi 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 kontrowersjach 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)
° Krytyka milionów zainspirowanych naturą (nature-inspired) metaheurystyk: Kenneth Sörensen, Metaheuristics-the metaphor exposed, International Transactions in Operational Research, vol.22, No.1, 3-18, doi: https://doi.org/10.1111/itor.12001. A tutaj jest darmowa kopia Autora.
° Artykuł o nieadekwatności metod uczenia maszynowego w optymalizacji kombinatorycznej: S.Majumdar U.Mallappa, H.Mostafa, AI Alone Isn’t Ready for Chip Design IEEE Spectrum, vol.61, Dec. 2024, 38-43. DOI: 10.1109/MSPEC.2024.10779342

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.→
Egzegeza punktów

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

° Yuval Noah Harari, Nexus. Krótka historia informacji Od epoki kamienia do sztucznej inteligencji (ang. Nexus: A Brief History of Information Networks from the Stone Age to AI ) -- książka opisuje historię sieci informacyjnych tworzonych przez ludzi, naturę prawdy i jej wpływu na osiągnięcie mądrości i sprawczości, mówi o mechanizmach samonaprawczych w ludzkich sieciach informacyjnych, mitologiach szerzonych w tych sieciach w imię porządku społecznego, o tym jak w sieciach informacyjnych pierwotnie tworzonych przez ludzi odnajdują się komputery i sztuczna inteligencja. Pojawienie się sieci społecznościowych i sztucznej inteligencji powoduje szereg jakościowo nowych zjawisk. W odróżnieniu od prasy drukarskiej, telegrafu i telefonu, które potrzebują ludzi do działania, interpretowania dokumentów i opowieści oraz tworzenia nowych dokumentów i opowieści, komputery same potrafią tworzyć dokumenty, interpretować je i w systemie ludzkich sieci informacyjnych tworzą nowych nadawców, którzy są nieludzką inteligencją.

° Derek C. Schuurman, "A Tribute to the Z80", IEEE Computer, Sept. 2024, pp. 94-95, vol. 57 DOI: 10.1109/MC.2024.3402508. Artykuł pożegnalny dedykowany procesorowi Z80, którego produkcję wstrzymano po 48 latach (sic!), a na którym oparto szereg komputerów domowych z lat 80. Chociaż to miały być tylko zabawki, to na tych komputerach moje pokolenie uczyło się informatyki i pisało na nich swoje prace magisterskie. Przykładowe komputery to ZX Spectrum , Amstrad , a nawet próbowano zbudować komputer dla szkół Elwro 800 Junior , jako rozszerzonego klona ZX Spectrum. To jest ważne bo: "Widziałem rzeczy, którym wy, ludzie, nie dalibyście wiary ... Wszystkie te chwile znikną w czasie jak łzy w deszczu."

° D.Calacci, "The GIG Workers Who Fought an Algorithm", IEEE Spectrum, vol. 61, no. 8, pp. 42-47, August 2024, doi: 10.1109/MSPEC.2024.10622066. Jak inżynierowie mogą pomóc GIG workerom/pracownikom dorywczym przełamać niekorzystną dla nich asymetrię informacyjną. Hmm . . ., chyba każdy student/-ka informatyki powinien to potrafić :)
° “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.
° 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).
° 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.
° 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.)
° Good Ideas, Through the Looking Glass, autor: Niklaus Wirth, 2005. Niklaus Wirth to jeden z twórców fundamentów współczesnej informatyki. Interesujące w kontekście rozwoju technologii, także aby pamiętać heroiczne czasy i nie robić tych samych błędów ponownie.

Last modified :