SZCZEGÓŁOWE WYMAGANIA DOTYCZĄCE DOKUMENTACJI

1. Specyfikacja dokumentacji projektowej

1.1. Strona tytułowa

1.2. Opis projektu

1.3. Specyfikacja techniczna

1.4. Dziennik prac

1.5. Instrukcja użytkownika

1.6. Testowanie

1.7. Indywidualny wkład

1.8. Załączniki

2. Dokumentacja procesu

2.1. Regularne prezentacje postępów

2.2. Dokumentacja procesu rozwoju

2.3. Opcjonalne korzystanie z repozytorium kodu

2.4. Indywidualne rozmowy

3. Przykłady dobrej dokumentacji

3.1. Przykład opisu algorytmu

Algorytm: Wyszukiwanie najkrótszej ścieżki w labiryncie

Cel: Znalezienie najkrótszej drogi od wejścia do wyjścia w labiryncie reprezentowanym jako tablica 2D.

Implementacja: Algorytm przeszukiwania wszerz (BFS) z wykorzystaniem kolejki.

Pseudokod:
function znajdz_najkrotsza_sciezke(labirynt, start, koniec)
    kolejka = pusta_kolejka()
    odwiedzone = pusta_tablica_2D(rozmiar_labiryntu)
    poprzednik = pusta_tablica_2D(rozmiar_labiryntu)
    
    dodaj_do_kolejki(kolejka, start)
    oznacz_jako_odwiedzone(odwiedzone, start)
    
    dopóki kolejka nie jest pusta
        aktualna = pobierz_z_kolejki(kolejka)
        
        jeśli aktualna == koniec
            return odtwórz_ścieżkę(poprzednik, start, koniec)
        
        dla każdego sąsiada pozycji aktualna
            jeśli sąsiad jest prawidłowy i nie jest ścianą i nie był odwiedzony
                dodaj_do_kolejki(kolejka, sąsiad)
                oznacz_jako_odwiedzone(odwiedzone, sąsiad)
                poprzednik[sąsiad] = aktualna
    
    return "Nie znaleziono ścieżki"

function odtwórz_ścieżkę(poprzednik, start, koniec)
    ścieżka = pusta_lista()
    aktualna = koniec
    
    dopóki aktualna != start
        dodaj_na_początek(ścieżka, aktualna)
        aktualna = poprzednik[aktualna]
    
    dodaj_na_początek(ścieżka, start)
    return ścieżka

Złożoność:
- Czasowa: O(n*m) gdzie n,m - wymiary labiryntu (każda komórka jest odwiedzana co najwyżej raz)
- Pamięciowa: O(n*m) na tablice odwiedzonych komórek i poprzedników oraz kolejkę

Problemy napotkane podczas implementacji:
1. Problem z wykryciem, czy komórka była już odwiedzona - początkowo używaliśmy przeszukiwania liniowego, co było nieefektywne.
2. Trudność w odtworzeniu ścieżki po znalezieniu wyjścia.

Rozwiązanie:
Zastosowanie tablicy poprzedników, która dla każdej komórki zapamiętuje, z której komórki do niej doszliśmy. Pozwala to na efektywne odtworzenie ścieżki.

3.2. Przykład dziennika prac

Tydzień 1 (01.03-07.03)
- Spotkanie zespołu (02.03): Ustalenie koncepcji projektu, podział zadań wstępnych
- Jan: Przygotowanie szkieletu programu, definicja podstawowych struktur danych
- Anna: Research algorytmów potrzebnych do obsługi głównych funkcjonalności
- Michał: Implementacja podstawowych funkcji obsługi plików wejściowych

Napotkane problemy:
- Trudność w ustaleniu optymalnej struktury danych do reprezentacji grafu - rozważaliśmy macierz sąsiedztwa vs. listę sąsiedztwa
- Rozwiązanie: Zdecydowaliśmy się na listę sąsiedztwa ze względu na rzadki graf, mimo nieco bardziej skomplikowanej implementacji

Tydzień 2 (08.03-14.03)
- Spotkanie zespołu (10.03): Przegląd postępów, dostosowanie planu
- Jan: Implementacja algorytmu przeszukiwania grafu, naprawa błędów w strukturach danych
- Anna: Opracowanie interfejsu użytkownika w konsoli, parsowanie argumentów wiersza poleceń
- Michał: Implementacja algorytmu sortowania danych wejściowych, funkcje do generacji statystyk

Napotkane problemy:
- Wykrycie błędu w algorytmie przeszukiwania - nieskończona pętla przy cyklach w grafie
- Rozwiązanie: Dodanie tablicy odwiedzonych wierzchołków i sprawdzanie jej przed każdym rekurencyjnym wywołaniem

4. Przykłady elementów, które należy uwzględnić w dokumentacji procesu

4.1. Przykład opisu napotkanych problemów

Problem: Wycieki pamięci przy przetwarzaniu dużych plików wejściowych

Opis: Podczas testowania programu na dużych plikach wejściowych (>100MB) zauważyliśmy, że zużycie pamięci stale rośnie, co ostatecznie prowadzi do błędu "out of memory". Analiza programu wykazała, że pamięć alokowana dynamicznie (malloc) nie była prawidłowo zwalniana we wszystkich ścieżkach wykonania.

Podejścia rozważane:
1. Ręczne śledzenie wszystkich alokacji pamięci:
   - Dodanie komentarzy przy każdym malloc/free
   - Manualne sprawdzenie każdej ścieżki wykonania
   
2. Użycie narzędzi do wykrywania wycieków pamięci:
   - Valgrind (nie był dostępny na wszystkich platformach testowych)
   - Własna prosta implementacja licznika alokacji
   
3. Przeprojektowanie algorytmu, aby używał mniej dynamicznej alokacji:
   - Wykorzystanie buforów o stałym rozmiarze
   - Przetwarzanie pliku w mniejszych fragmentach

Rozwiązanie:
Zastosowaliśmy kombinację podejść 1 i 3:
- Dodaliśmy funkcję opakowującą dla malloc, która zlicza aktywne alokacje
- Zaimplementowaliśmy przetwarzanie pliku wejściowego w blokach o stałym rozmiarze
- Wprowadziliśmy wszechstronną funkcję czyszczącą, wywoływaną na końcu każdej funkcji, która mogła alokować pamięć

Wyniki:
- Przed optymalizacją: program zużywał >2GB RAM dla pliku 200MB
- Po optymalizacji: zużycie pamięci stabilizuje się na poziomie ~50MB niezależnie od rozmiaru pliku wejściowego

4.2. Przykład dokumentacji decyzji projektowej

Decyzja: Struktura danych do przechowywania słownika

Rozważane opcje:
1. Tablica dynamiczna (dynamicznie alokowany array)
   Zalety: Prosta implementacja, szybki dostęp sekwencyjny
   Wady: Wolne wyszukiwanie O(n), powolne wstawianie/usuwanie

2. Drzewo binarne
   Zalety: Szybsze wyszukiwanie O(log n), możliwość zachowania uporządkowania
   Wady: Bardziej skomplikowana implementacja, możliwość degradacji do listy

3. Tablica z haszowaniem
   Zalety: Stały czas dostępu O(1) w przypadku średnim
   Wady: Konieczność radzenia sobie z kolizjami, rozproszenie danych

Analiza:
Nasz program słownikowy wymaga szybkiego wyszukiwania słów oraz częstego dodawania nowych słów. Słownik może zawierać dziesiątki tysięcy wpisów. Ważna jest także oszczędność pamięci.

Decyzja i uzasadnienie:
Wybraliśmy tablicę z haszowaniem ze względu na:
- Stały czas dostępu, co jest kluczowe dla interaktywnej aplikacji słownikowej
- Akceptowalny kompromis między złożonością implementacji a wydajnością
- Możliwość łatwego rozszerzania słownika bez reorganizacji całej struktury

Szczegóły implementacji:
- Funkcja haszująca: suma ASCII znaków słowa modulo rozmiar tablicy
- Metoda rozwiązywania kolizji: łańcuchowanie (lista jednokierunkowa dla każdego wpisu)
- Współczynnik wypełnienia: utrzymywany poniżej 0.7 poprzez rehaszowanie

Skutki decyzji:
- Potrzeba zaimplementowania własnej funkcji haszującej i mechanizmu rozwiązywania kolizji
- Konieczność rehaszowania przy przekroczeniu współczynnika wypełnienia
- Znaczny wzrost wydajności wyszukiwania w porównaniu do pierwotnego rozwiązania z tablicą dynamiczną (z 3s do 0.05s dla 50000 wyszukiwań)