[WikiDyd] [TitleIndex] [WordIndex

Laboratorium: "Algorytmy i struktury danych" (Informatyka, semestr 3)

Zasady zaliczenia

  1. Zajęcia odbywają się co tydzień. Obecność na zajęciach jest obowiązkowa.
  2. Laboratorium składa się z trzech części. Pierwsza część składa się z 3 ćwiczeń wykonywanych podczas zajęć. Druga część polega na wykonaniu zadania indywidualnego. Trzecia część stanowi zadanie grupowe.
  3. Na wykonanie ćwiczenia przeznaczone są tylko jedne zajęcia. Rezultatem wykonania ćwiczenia jest działający program w języku Java oddany podczas tych samych zajęć. Do wykonania ćwiczenia należy się przygotować przez zajęciami. Podczas zajęć nie można korzystać z żadnych pomocy na papierze oraz w formie elektronicznej.
  4. Na wykonanie zadania indywidualnego oraz zadania grupowego przeznaczone są zajęcia w drugiej części semestru. Rezultatem wykonania zadania jest sprawozdanie oraz działający program w Javie.
  5. Terminem oddania sprawozdania z zadania indywidualnego są trzecie od końca zajęcia w semestrze. Terminem oddania sprawozdania z zadania grupowego są ostatnie zajęcia w semestrze.
  6. Przekroczenie terminu oddania sprawozdania jest jednoznaczne z niezaliczeniem danego zadania i otrzymaniem za nie 0 punktów.
  7. Za wykonanie wszystkich ćwiczeń i zadanie indywidualne można otrzymać w sumie maksimum 30 punktów. Za ćwiczenia można uzyskać 9 pkt. (po 3 pkt. za ćwiczenie). Za zadanie indywidualne można otrzymać 12 pkt. Za zadanie grupowe można otrzymać 9 pkt.
  8. Końcowe punkty są przekazywane do kierownika przedmiotu - prof. Jacka Starzyńskiego

Program zajęć

Zajęcia wstępne i ćwiczenia:

Uwagi ogólne:

Zajęcia wstępne:

  1. Rozpoznanie środowiska pracy: opracowanie problemu ,,0": klasa implementująca interfejs StrStack (stos napisów):

   1 public interface StrStack {
   2    public void put( String s ); // puts s on the top of stack
   3    public String pop();         // returns the top-most element or null if Stack is empty
   4    public boolean isEmpty();
   5    public int getHeight();      // returns current number of elements on the Stack
   6 }

Ćwiczenia:

  1. Abstrakcyjne typy danych a struktury danych: implementacja kolejki priorytetowej za pomocą kopca (własna implementacja)

   1 public interface PQueue<T extends Comparable<T>> {
   2    public void insert( T o );  // inserts o into the queue
   3    public T remove();                      // removes object with highest priority (by natural order)
   4 }
  1. Wykorzystanie bibliotecznych implementacji AiSD: implementacja kolejki priorytetowej PQueue (por. wyżej) za pomocą Multimap (http://code.google.com/p/google-collections/ , http://www.factorypattern.com/multimap-in-google-collections-library/)

  2. Porównywanie szybkości działania algorytmów: implementacja i testowanie klasy-kontenera metod zawierającej dwie metody sortowania tablic zawierających liczby double: sortowanie przez wstawianie i sortowanie szybkie. Testowanie powinno obejmować przygotowanie dowolnie dużej tablicy z danymi testowymi i zmierzenie czasu sortowania tej tablicy (http://java.sun.com/j2se/1.5.0/docs/api/java/lang/System.html#nanoTime()) różnymi algorytmami.

   1 public class Sorter4double {
   2    public static insort( double [] a ) { // sorts a incrementally using insertion sorting algorithm
   3        // put your code here
   4    }
   5 
   6    public static qsort( double [] a ) {  // sorts a incrementally using quicksort algorithm
   7         // put your code here
   8    }
   9 }

Projekt indywidualny:

Uwagi ogólne:

Temat: proszę napisać program wyznaczający najkrótszą trasę przejazdu pomiędzy zadanymi punktami. Program ma czytać mapę składającą się z listy węzłów i listy krawędzi:

Nodes:
A
B
C
D
Edges:
A B 5
A C 9
A D 3
B C 4

Projekt zespołowy:

Uwagi ogólne: jak wyżej

Temat: Proszę napisać system zarządzający dużą mapą na wzór projektu indywidualnego. System powinien umożliwiać dodawanie nowych i modyfikowanie starych kawałków mapy (administrator) i jednoczesne wyszukiwanie różnych dróg przez wielu użytkowników na raz.

Literatura


2015-09-23 06:32