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:
    1. Zadanie programistyczne.
    2. 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).

Zasady rozliczenia zadań projektowych programistyczny/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

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. 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…).
  2. Złożoność obliczeniowa (przykłady, przykłady szacowania itd. itp.)
  3. System git / github/ gitlab (prezentacja "na żywo")
  4. Metody sprawdzania poprawności algorytmu
  5. Metoda niezmienników i półniezmienników, metoda szufladkowania Dirichleta
  6. Problemy klasy P, NP, NPC
  7. Problemy nierozstrzygalne
  8. Maszyna Turinga i jej odmiany
  9. Automaty skończone
  10. Heurystyka - heurystyczne techniki projektowania algorytmów
  11. Heurystyka: przeszukiwanie lokalne
  12. Heurystyka: algorytmy zachłanne
  13. Heurystyka: symulowane wyżarzanie
  14. Heurystyka: przeszukiwanie tabu
  15. Heurystyka: algorytmy genetyczne
  16. Algorytmy probabilistyczne
  17. Algorytmy zachłanne
  18. Metoda "dziel i zwyciężaj"
  19. Programowanie dynamiczne i metoda spamiętywania (najdłuższy wspólny podciąg, problem plecakowy)
  20. Drzewa BST
  21. Drzewa czerwono-czarne
  22. Grafy
  23. Algorytmy przeszukiwania grafów
  24. Słowniki
  25. Kryptografia (kodowanie symetryczne, asymetryczne, łamanie szyfrów)
  26. Prezentacja możliwości bibloteki STL standardu C++ (prezentacja "na żywo")
  27. Algorytmy geometryczne (problem przynależności, otoczka wypukła, metoda zamiatania…)
  28. Kolejka priorytetowa
  29. Kopiec binarny
  30. Minimalne drzewo rozpinające
  31. 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

Author: mb

Date: 2025-02-25 Tue 19:25

Emacs 29.4 (Org mode 9.6.15)