Mariusz Borkowski - strona prywatna
Algorytmy i struktury danych

Table of Contents

Strona główna   Dydaktyka   O mnie/dane adresowe   Blog

Informacje organizacyjne

O mnie

Projekty

Zasady rozliczenia zajęć projektowych - uwagi ogólne:

  1. Projekty jednoosobowe.

  2. Projekt składa się z 2 części:

    a. Zadanie programistyczne

    b. Prezentacja na zadany temat

  3. Tematyka oraz terminy oddania i obrony kolejnych zadań projektowych:
    • ustalane z prowadzącym.
  4. Ocena końcowa to średnia z ocen otrzymanych za zadania projektowe (ocena pozytywna pod warunkiem zaliczenia każdego zadania na min. 3.0).

Prezentacje

  1. Czas trwania 10/15 min. (10/15 slajdów/przedstawienie przykładów na tablicy).
  2. Wykonanie prezentacji w LaTeX'u (Beamer) będzie mile widziane.

Tematy prezentacji

  1. Schematy blokowe - zasady tworzenia…
  2. Zasady dobrego programowania (wraz z przykładami): podział programu na funkcje, sensowne nazwy, komentarze komentarze i komentarze, poprawna interpretacja komunikatów interpretera/kompilatora, testowanie, debugowanie, najczęstsze błędy popełnianie w trakcie pisania programów (przepełnienie pamięci, wyciek pamięci, niepoprawne argumenty funkcji, użycie niepoprawnego wskaźnika, wartości niemieszczące się w zmiennych…).
  3. Złożoność obliczeniowa (przykłady, przykłady szacowania itd. itp.)
  4. System git / github/ gitlab (prezentacja "na żywo")
  5. Metody sprawdzania poprawności algorytmu
  6. Metoda niezmienników i półniezmienników, metoda szufladkowania Dirichleta
  7. Rachunek lambda i jego zastosowanie
  8. Problemy klasy P, NP, NPC
  9. Problemy nierozstrzygalne
  10. Maszyna Turinga i jej odmiany
  11. Automaty skończone
  12. Heurystyka - heurystyczne techniki projektowania algorytmów
  13. Heurystyka: przeszukiwanie lokalne
  14. Heurystyka: algorytmy zachłanne
  15. Heurystyka: symulowane wyżarzanie
  16. Heurystyka: przeszukiwanie tabu
  17. Heurystyka: algorytmy genetyczne
  18. Algorytmy probabilistyczne
  19. Algorytmy zachłanne
  20. Metoda "dziel i zwyciężaj"
  21. Programowanie dynamiczne i metoda spamiętywania (najdłuższy wspólny podciąg, problem plecakowy)
  22. Drzewa BST
  23. Drzewa czerwono-czarne
  24. Grafy
  25. Algorytmy przeszukiwania grafów
  26. Słowniki
  27. Kryptografia (kodowanie symetryczne, asymetryczne, łamanie szyfrów)
  28. Prezentacja możliwości bibloteki STL standardu C++ (prezentacja "na żywo")
  29. Algorytmy geometryczne (problem przynależności, otoczka wypukła, metoda zamiatania…)
  30. Kolejka priorytetowa
  31. Kopiec binarny
  32. Minimalne drzewo rozpinające
  33. System składu tekstu LaTeX (+ Beamer).

Zalecana literatura:

  1. Jacek Krzaczkowski - Algorytmika dla początkujących
  2. Donald E. Knuth - Sztuka programowania
  3. Rytter Wojciech, Diks Krzysztof, Banachowski Lech - Algorytmy i struktury danych
  4. Thomas H. Cormen, Charles E. Leiserson, Roland L. Rivest, Clifford Stein - Wprowadzenie do algorytmów
  5. Piotr Wróblewski - Algorytmy, struktury danych i techniki programowania
  6. David Harel - Rzecz o istocie informatyki - Algorytmika
  7. Christos H. Papadimitriou - Computational Complexity

Zasady rozliczenia zadań projektowych programistycznych/algorytmicznych

  1. Programy powinny zostać napisane w środowisku Code::Blocks IDE w języku C/C++.
  2. W celu zaliczenia zadania projektowego należy
    • dostarczyć kod programu i sprawozdanie:
      • przesłać mailowo sprawozdanie (wersja elektroniczna) i przesłać działający kod programu (spakowany). Ww. pliki powinny być wysłane jako załącznik będący spakowanym archiwum w formacie .zip (UWAGA! Plików spakowanych w formacie .rar poczta uczelniana nie przepuści!) o nazwie ''PXX Nazwisko Imie'', gdzie ''XX'' to numer grupy projektowej, przykład ''P03 Kowalski Jan.zip'', lub
      • zamieścić kod programu i sprawozdanie w jednym ze znanych repozytoriów (GitHub, GitLab, itp.) i podesłać mi link do niego
    • obrona wybranego projektu osobiście (UWAGA: Na obronę przynosimy wydrukowane wersje sprawozdania.)

  3. Sprawozdanie powinno:

    • być w formacie PDF (!!!)
    • zawierać: stronę tytułową, wstęp, opis problemu, opis podstaw teoretycznych zagadnienia, opis szczegółów implementacji problemu, schemat blokowy algorytmu (a nie całego programu!!!) oraz sam algorytm zapisany w pseudokodzie, rezultaty testów wykonanych przy pomocy napisanego programu -> wykresy!!! (złożoność czasowa, obliczeniowa, czasy obliczeń), wnioski i podsumowanie. Jako appendix należy dodać kod programu.
    • być napisane poprawną polszczyzną, z dbałościa o formatowanie tekstu (tekst wyjustowany(!!!), marginesy zachowane, strony ponumerowane, odnośniki do źródeł, rysunki/tabele podpisane etc.)

    Wzory przyzwoicie sformatowanych dokumentów (na dole strony) - zacząć od tego (LaTeX!)

  4. Za nieoddanie zadania projektowego w ustalonym terminie ocena będzie adekwatnie obniżona.
  5. Wykonanie projektu z wykorzystaniem git/Githuba/Gitlaba itp. będzie mile widziane. (Dla osób zainteresowanych wykonaniem projektu z wykorzystaniem systemu Git - podstawy git).
  6. Wykonanie sprawozdania w LaTeXu będzie mile widziane.

  7. Kod programu powinien zawierać przynajmniej dwie funkcje:

    • główny kod programu powinien być zaimplementowany w oddzielnej funkcji, którą powina być wywoływana wewnątrz programu
    • w głównym programie powinno zostać wykonane kilka testów sprawdzających działanie funkcji
    • program powinien mieć możliwość odczytywania danych wejściowych i zapisu wyników do plików tekstowych
    • kod powinien być opatrzony stosownymi komentarzami
    • UWAGA: Jeśli w treści zadania nie jest wyraźnie napisane, że dane wejściowe należy posortować, to zadany problem należy rozwiązać bez wykorzystania algorytmów sortujących.

    Jak poprawnie rozwiązać zadanie 1 - przykład