Politechnika Wrocławska, Wydział Elektroniki, Kierunek: Informatyka (1 rok)

Uwaga:    Przygotowane przez wykładowcę dr Zofię Kruczkiewicz: treści zadań wraz z przykładowymi programami sortowania i wyszukiwania (które można wykorzystać jako materiały pomocnicze) są dostępne w laboratoriach ICT 127L/127P/103/104 C-3, w katalogu: L:\kruczkiewicz\INF2001

LABORATORIUM nr 1

Powtórzenie wybranych algorytmów sortowania poznanych w poprzednim semestrze:
bąbelkowego, przez selekcję, przez wstawianie, przez zliczanie, pozycyjnego, szybkiego oraz kopcowego.

Należy wybrać 3 różne algorytmy sortowania np. bąbelkowe, przez wstawianie i kopcowe.
Wybrane algorytmy należy zaimplementować dla tablic struktur typu "TOsoba".
Sortowanie powinno przebiegać według wybranych pól struktury (np. wg pola nazwisko)
lub kryterium łączącego wartości kilku pól (np. najpierw wg nazwiska,
a w przypadku identycznych nazwisk dodatkowo wg imienia).

Wewnątrz algorytmów sortujących należy umieścić liczniki mierzące liczbę wystąpień
podstawowych operacji: porównań, dodawań, wywołań funkcji, przypisań, itp.

Wykonując badania porównawcze należy dla każdego algorytmu wypełniać tablice
identycznymi ciągami wylosowanych wartości (np. litery w nazwisku za pomocą losowania kodów ASCII)
rozpoczynając losowanie dla każdego z sortowań po ustawieniu generatora liczb losowych
za pomocą funkcji srand np.srand(3).
Taka inicjalizacja umożliwi porównanie liczby operacji (liczników) wybranych sortowań,
dla takich samych danych wejściowych.

LABORATORIUM nr 2

Kontynuacja badań algorytmów sortowania oraz algorytmów wyszukiwania.

1. Oprogramowanie algorytmów sortowania szybkiego oraz przez łączenie.
   Umiejscowienie wewnątrz kodu, liczników mierzących liczbę wystąpień  podstawowych operacji sortowania
   (porównanie, kopiowanie, zamiana) oraz przeprowadzenie pomiarów dla identycznych danych
   jak podczas laboratorium nr 1.
   Dodatkowo należy sprawdzić wpływ rodzaju danych wejściowych:
   nieposortowanych, posortowanych częściowo lub całkowicie posortowanych.
   
   
2. Wykonanie zwykłej i rekurencyjnej wersji wyszukiwania binarnego bez powtórzeń.
   Zastosowanie go w programie typu "baza danych" umożliwiającym wybór różnych opcji
   (wstawianie, wyświetlanie, sortowanie, wyszukiwanie).

Zalecenia związane z wykonaniem zadania: oprogramowanie powinno być wykonane w stylu ADT,
czyli operacje na tablicach jako funkcje wywoływane z funkcji nadrzędnych obsługujących interakcje z użytkownikiem
oraz zastosowanie przekazywania danych poprzez listy parametrów funkcji.

W zależności od poziomu zaawansowania uczestników laboratorium,
wykorzystywane reprezentacje danych mogą mieć różny stopień złożoności:

1. statyczne tablice struktur,
2. dynamiczne tablice struktur,
3. statyczne tablice wskaźników na dynamiczne struktury,
4. dynamiczne tablice wskaźników na dynamiczne struktury.

LABORATORIUM nr 3

Badania algorytmów sortowania danych w pamięci zewnętrznej - sortowania plików:

• naturalnego,

• wielokierunkowego

• polifazowego

Na podstawie wykładów (4 i 9) należy przystosować programy sortujące pliki liczb całkowitych
do sortowania plików zawierających struktury "TOsoba".
Podobnie jak w lab. 1 i 2, w kodzie programu należy umieścić liczniki umożliwiające
pomiar ilości podstawowych operacji na pamięci operacyjnej oraz dodatkowo zliczanie
podstawowych operacji na plikach (fwrite, fread, fclose, fopen itp).

Badania porównawcze należy przeprowadzić dla danych wejściowych:
nieposortowanych, uporządkowanych częściowo i  całkowicie posortowanych.

LABORATORIUM nr 4

Badania algorytmów wykorzystujących rekurencję i kolejki implementowane za pomocą list.

1. Zadanie ćwiczące definiowanie funkcji rekurencyjnych
   1. Należy przekształcić funkcje zawierające pętle na postać rekurencyjna
      np. wyświetlającą elementy tablicy na ekran od najmniejszego indeksu
      oraz drugi egzemplarz od największego indeksu.
      Określić eksperymentalnie, dla ilu elementów nastąpi przepełnienie stosu
      (zakłada się, ze liczba wywołań rekurencyjnych funkcji jest liniowo zależna od liczby elementów).
              Analizując drzewo algorytmu dla wyszukiwania binarnego z powtórzeniami elementów w tablicy
      należy określić, dla ilu elementów może nastąpić przepełnienie stosu przy zastosowaniu tego algorytmu
      (zakłada się, ze liczba wywołań funkcji jest proporcjonalna do liczby testowanych węzłów (lgn)).

   lub alternatywnie do zadania nr (a)

   2. Wykonać rekurencyjnie wyszukiwanie sekwencyjne i określić,
      dla ilu elementów tablicy wypełnionej losowo może nastąpić przepełnienie stosu
      (zakłada się, ze liczba wywołań rekurencyjnych funkcji jest liniowo zależna od liczby elementów,
      gdy szukamy elementu większego od największego elementu w tablicy).
              Analizując drzewo algorytmu dla wyszukiwania binarnego z powtórzeniami elementów w tablicy
      należy określić, dla ilu elementów może nastąpić przepełnienie stosu przy zastosowaniu tego algorytmu
      (zakłada się, ze liczba wywołań funkcji jest proporcjonalna do liczby testowanych węzłów (lgn)).

   Uwagi do zadań 1.a i 1.b:

   • Funkcje te powinny wystąpić w programie, który zawiera inne funkcje:
     wypełniająca tablice o dowolnym rozmiarze (dynamiczna lub zmiana wymiaru tablicy statycznej,
     ponownej kompilacji i linkowaniu programu) i sortującą dla przypadku programu 1.b)
   • Eksperyment może polegać na:
     • zmianie wymiaru tablicy statycznej, ponownej kompilacji i linkowaniu programu
     • lub na automatycznym tworzeniu coraz większej tablicy (po usunięciu mniejszej tablicy, wypełnieniem jej)
       i uruchomieniem funkcji rekurencyjnej liczącej liczbę wywołań funkcji.
       Liczba wywołań funkcji może być wyświetlana na ekranie lub zapisywana w pliku.
       Eksperyment ma pokazać, kiedy rekurencja ze względu na możliwość przepełnienia stosu
       powinna być zastąpiona iteracyjnymi rozwiązaniami.
       Nie rozważa się na razie innych przeciwskazań rekurencji dotyczących np.
       pogorszenia złożoności obliczeniowej algorytmu np. rekurencyjne obliczanie wartości liczb Fibonacciego
       
       
2. Zadanie dotyczące programu "bazodanowego". Napisz program zawierający następujące elementy:
   1. funkcje tworzące kolejkę priorytetowa, czyli funkcje wstawiająca w sposób uporządkowany
      i funkcje usuwająca największy element (implementację wykonaj stosując listy wiązane:
      nieuporządkowane jednokierunkowe lub dwukierunkowe - zalecane)
   2. funkcje wyświetlającą zawartość listy na ekranie
   3. wykorzystanie w/w kolejki priorytetowej do wielokierunkowe sortowanie plikowe
      wg wybranej składowej: ( z zapisem danych z listy do pliku)
   4. wyświetlanie zawartości pliku na ekranie.

LABORATORIUM nr 5

Badania algorytmów stosujących reprezentację danych w postaci drzew (niewyważonych i wyważonych).

1. Napisz program, który liczy liczbę operacji w pamięci (porównań, przypisań, arytmetycznych,
   wyłuskań, wywołań funkcji itp) dla następujących zadań:

   1. Budowa niewyważonego drzewa binarnego dla 1000 elementów
      ze wstawianiem nowego elementu jako liść

   2. Budowa wyważonego drzewa binarnego dla danych j.w.
      

2. Napisz program, który powinien zawierać:

   1. Funkcje operujące na kolejce priorytetowej - funkcje wstawiającą i pasującą do niej
      funkcje usuwającą największy element, stosując drzewo binarne: niewyważone lub wyważone.

   2. Funkcję wyświetlającą zawartość drzewa na ekranie: przedrostkowo,
      w sposób uporządkowany oraz przyrostkowo

   3. Wykorzystanie w/w kolejki priorytetowej do wielokierunkowego sortowania plików
      wg wybranej składowej; zapis danych z listy do pliku
      w sposób przedrostkowy lub przyrostkowy i posortowany.

   4. Wyświetlanie zawartości pliku na ekranie.

LABORATORIUM nr 6

Badania algorytmów wykorzystujących grafową reprezentację danych.

Napisz program pozwalający przechowywać informacje o planie ulic dowolnego osiedla.
Układ tych ulic (jedno lub dwukierunkowych) powinien być reprezentowany za pomocą  macierzy incydencji grafu
składającego się ze skrzyżowań (węzły) i ulic (łuki). Macierz ta może być zaimplementowana za pomocą:

1. dynamicznej listy dynamicznych pod-list, 

2. dynamicznej tablicy wskaźników na dynamiczne pod-listy

W/w listy i pod-listy mogą być zaimplementowane jako: jednokierunkowe, dwukierunkowe, cykliczne, itp.
Program powinien umożliwiać:

• wczytanie i zapisanie planu miasta w pliku,

• wyświetlenie fragmentu planu miasta na ekranie
  (np. w postaci listy ulic dochodzących do danego skrzyżowania,
   lub skrzyżowań dotyczących tej ulicy)

• wyszukiwanie połączeń pomiędzy zadanymi skrzyżowaniami (wierzchołkami)

Ostatnia modyfikacja: 10.05.2005