20515

nazwylnterfejsów] {/ nagłówki metod /} • Przykład interfejsu: interface OperacjeGraficzne {/ void rysowanie(); / void usuwanie(); /}. Implementacja interfejsu • Definicja metod umieszczonych w interfejsach umieszczana jest w klasach implementujących dany interfejs. • ... class nazwaKlasy extends... implements Listalnterfejsów • klasa implementująca interfejs musi zawierać definicje wszystkich metod zadeklarowanych w interfejsie (w przeciwnym przypadku staje się klasą abstrakcyjną) • klasa może implementować wiele interfejsów. Zastosowanie interfeisówwskazuie na właściwości pewnego abstrakcyjnego pojęcia •definiowanie związków pomiędzy klasami - wszystkie klasy implementujące interfejs posiadają wspólne właściwości (mogą realizować operacje określone w interfejsie) *nazwa interfejsu może funkcjonować jako nazwa typu. INTERFEJS ITERATOR Public interface Iterator {/ boolean hasNext(); / Object next(); / void remove(); /}

Wykorzystanie iteratora do usuwania elementów Collection collection = ...; / Iterator iterator = collection.iterator(); / while (iterator.hasNext()) {/ Object element = iterator.next(); / if (removalCheck(element)) {/ iterator.remove(); /} / }

WYMAGANIA WOBEC ALGORYTMÓW* poprawność - algorytm generuje prawidłowe rezultaty (nie zawiera błędów),* wydajność - realizacja algorytmu wymaga użycia akceptowalnej ilości zasobow:-czasu,- pamięci.

Pojecie błędu* niezgodność z obowiązującymi regułami pisania, liczenia, wymowy itp.; odstępstwo od normy; pomyłka* postępek, działanie, które przynosi komuś złe skutki; niewłaściwe posunięcie, przedsięwzięcie* mylne, fałszywe mniemanie o czymś (przestarz.)

Błędy w programowaniu* błędy logiczne - na etapie projektowania algorytmu (środki zaradcze: stosowanie sprawdzonych algorytmów, formalne dowodzenie poprawności algorytmu, testowanie programu)* błędy wykonania programu - ujawniające się w trakcie realizacji algorytmu zapisanego w postaci programu (ujawniające się w postaci wyjątków)* błędy syntaktyczne - polegające na niezgodności tekstu programu z gramatyką języka programowania (wykrywane przez kompilator)

ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU - ilość zasobow systemu komputerowego niezbędnych do jego realizacji. • Zasoby systemu komputerowego niezbędne do realizacji algorytmu: - czas pracy procesora (złożoność czasowa algorytmu), - pamięć operacyjna (złożoność pamięciowa algorytmu). • Złożoność obliczeniowa jest uzależniona od wielkości zadania. Oszacowanie czasu realizacji algorytmu • Analiza powyższych danych pozwala stwierdzić, że czas obliczeń uzależniony jest przede wszystkim od składnika: 0,000002 n2 Składnik ten nazywany jest składnikiem dominującym.* Po pominięciu stałych współczynników można stwierdzić, że zależność pomiędzy czasem wykonania a wielkością zadania ma charakter funkcji kwadratowej. Kwadratowy charakter zależności uwidacznia się w coraz większym stopniu wraz ze wzrostem wielkości zadania. CECHY EMPIRYCZNEGO OKREŚLANIA ZŁOŻONOŚCI •Zalety:

-    otrzymane czasy obliczeń są proste w interpretacji • Wady: - konieczność wielokrotnego uruchamiania programu (dla złożonych algorytmów może to być bardzo czasochłonne), - uzyskane wyniki dotyczą zastosowanego w obliczeniach zestawu danych (trudno jest określić czas realizacji dla przypadku „najlepszego", najgorszego" oraz „przeciętnego"), - wyniki dotyczą zwykle stosunkowo niewielkich zbiorow danych - nie wiadomo, czy dla zbiorow o większym rozmiarze charakter zależności się nie zmieni,

-    czas jest uzależniony od szybkości i architektury komputera, języka programowanie, techniki translacji, systemu operacyjnego - trudna porównywalność wyników - z uwagi na wielozadaniowy charakter systemów operacyjnych trudno jest określić, jaka część czasu była rzeczywiście przeznaczona na realizację analizowanego programu.

BEZPOŚREDNIA ANALIZA ALGORYTMÓW dotyczy: • charakteru zależności (np. zależność liniowa lub kwadratowa), a nie jej dokładnej postaci (wzór funkcji) - uwzględniany jest element dominujący, pomijane są współczynniki stałe • górnego i dolnego ograniczenia czasu realizacji algorytmu (a nie czasu realizacji algorytmu) - górne ograniczenie - czas realizacji algorytmu jest nie większy niż ... (ale może być krótszy) - przypadek pesymistyczny, - dolne ograniczenie - czas realizacji algorytmu jest nie mniejszy niż ... (ale może być dłuższy) - przypadek optymistyczny, • zachowania się algorytmu dla zbiorow danych o dużej wielkości (czyli dla wszystkich n większych od pewnej wartości nO)

GÓRNE OGRANICZENIE CZASU REALIZACJI ALGORYTMU • f(n) - czas realizacji algorytmu (zależny od n) • f(n) zależy od wielu czynników i podanie dokładnego charakteru zależności jest trudne • łatwiej jest