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

Laboratorium

INE 2001 - ALGORYTMY I STRUKTURY DANYCH 2

prow. dr Marek Piasecki

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:

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)

    1. 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:

  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ć:


Ostatnia modyfikacja: 10.05.2005