Zagadnienia na egzamin inżynierski

1. Wymień cechy algorytmu i sposoby jego reprezentacji.

Algorytm – skończona sekwencja reguł, działających na skończonej liczbie danych, pozwalająca rozwiązywać
określony problem (klasę problemów); dla poprawnych danych wejściowych produkuje poprawne wyniki.

cecha

Opis

Określoność (ang. definiteness)

Możliwość wykonania wszystkich operacji

Jednoznaczność (ang.uniqually determined)

Jednoznaczność wszystkich wykonywanych operacji

Skończoność (ang. finiteness)

Rozwiązanie problemu w skończonej liczbie kroków

Ogólność (ang. generality)

Wykorzystanie do rozwiązania określonej klasy zadań (założony
poziom ogólności)

Efektywność (ang. effectiveness)

Złożoność obliczeniowa

Zupełność (ang. complete)

Uwzględnienie wszystkich możliwych przypadków jakie mogą
wystąpić

+ poprawność (wyniki odzwierciedlają rzeczywistość)
+ sprawność (czasowa – szybkość; pamięciowa – zasobożerność)
+ prostota wykonania (operacje jak najprostsze)

Aby nasz algorytm rozwiązywał poprawnie pewne zagadnienia niezbędna są dane początkowe i zadanie
ograniczeń np. warunki brzegowe, jednym słowem należy przedstawić rzeczywistość poprzez:



zdefiniowanie zadania



wprowadzenie założeń i ograniczeń



algorytm rozwiązania

Sposoby realizacji algorytmu:



Opisowa, werbalna (dane, warunek, wynik, kroki ….)



Schemat blokowy/ sieć działań (graficzny opis działań+kolejność)



Pseudokod



Języki programowania



Drzewo algorytmu (określa złożoność obliczeniową i pesymistyczną; idziemy od korzenia do wierzchołków,
trochę to przypomina takie if-y)

2. Omówić zagadnienie asymptotycznej złożoności obliczeniowej algorytmów. Podać

standardowe notacje rzędu złożoności.

Złożoność obliczeniowa – miara porównania algorytmów, w wyniku której:



Porównuje się różne algorytmy rozwiązujące te same problemy



Przewiduje się wydajność algorytmów w nowym środowisku



Określa wartości parametrów algorytmów

Rodzaje złożoności:



Czasowa (czas wykonania w jednostkach czasu)



Pamięciowa (B, KB…)

Złożoność asymptotyczna przedstawia złożoność dla bardzo dużych, granicznych rozmiarów danych
wejściowych

Rodzaje notacji asymptotycznej:

notacja

opis

Rysunek

O-notacja
(omikron)

Funkcja f(n) jest co najwyżej rzędu g(n) :

f(n) = O(g(n))

jeżeli istnieją c, n

0

>0, że dla wszystkich

n n

0

zachodzi: f(n) cg(n)

cg(n) jest asymptotyczną granicą górną. Służy do
szacowania czasu działania algorytmu w przypadku
pesymistycznym

-notacja

Asymptotyczne ograniczenie dolne (czyli odwrotnie,
niż w O-notacji)



Asymptotyczna granica dolna. Służy do oszacowania
czasu działania algorytmu w przypadku
optymistycznym

-notacja

Funkcja f(n) jest rzędu (g(n)):

f(n) = (g(n))

jeżeli istnieją takie c

1

i c

2

>0, że dla wszystkich n n

0

zachodzi:
c

1

g(n) f(n) c

2

g(n)

Asymptotyczne oszacowanie dokładne

Asymptotyczna złożoność czasu i przestrzeni (zasoby obliczeniowe), złożoność układu i wskaźniki obliczeń
równoległych (liczba równoległych procesorów)

Notacje rzędu złożoności (oprócz notacji asymptotycznych) mają jeszcze notację małego o (f niższego rzędu niż
g) oraz małego omega (f jest wyższego rzędu niż g)

Kategorie złożoności:

3. Algorytmy sortowania oraz charakterystyka ich złożoności obliczeniowej.

Algorytmy sortowania są zazwyczaj klasyfikowane według:



złożoności (pesymistyczna, oczekiwana) – zależność liczby wykonanych operacji w stosunku od liczebności
sortowanego zbioru (n). Typową, dobrą złożonością jest średnia O(n log n) i pesymistyczna Ω(n²). Idealną
złożonością jest O(n). Algorytmy sortujące nie przyjmujące żadnych wstępnych założeń dla danych
wejściowych wykonują co najmniej O(n log n) operacji w modelu obliczeń, w którym wartości są

"przezroczyste" i dopuszczalne jest tylko ich porównywanie (w niektórych bardziej ograniczonych
modelach istnieją asymptotycznie szybsze algorytmy sortowania);



złożoność pamięciowa



sposób działania: algorytmy sortujące za pomocą porównań to takie algorytmy sortowania, których sposób
wyznaczania porządku jest oparty wyłącznie na wynikach porównań między elementami; Dla takich
algorytmów dolne ograniczenie złożoności wynosi Ω(n log n);



stabilność: stabilne algorytmy sortowania utrzymują kolejność występowania dla elementów o tym samym
kluczu (klucz – cecha charakterystyczna dla każdego elementu zbioru, względem której jest dokonywane
sortowanie). Oznacza to, że dla każdych dwóch elementów R i S o tym samym kluczu, jeśli R wystąpiło
przed S to po sortowaniu stabilnym R nadal będzie przed S;

Złożoność oznacza liczbę elementów do posortowania, liczbę różnych elementów.

sortowanie jest stabilne wtedy kiedy złożoność obliczeniowa nie zależy od rozłożenia elementów

nazwa

złożoność

Opis

Sortowanie bąbelkowe

(ang. bubble sort)

O(n

2

)

Porównuję kolejne pary elementów, po każdym porównaniu
mamy o 1 element mniej (bo jest on posortowany).

Sortowanie przez wstawianie

(ang. insertion sort)

O(n

2

)

Każdy od drugiego sprawdzany, gdzie pasuje na liście

Zakładamy, że pierwszy element tablicy jest posortowany.
Następnie sprawdzamy pozostałe (nieposortowane) elementy i
w zależności od tego, czy są mniejsze, czy większe, trafiają na
odpowiednie miejsce. Element z części nieposortowanej
wstawiamy do posortowanej tak, aby nie naruszyć dokonanego
posortowania (Inaczej mówiąc, trzeba badany element
sprawdzić z każdym elementem części posortowanej).

Sortowanie przez scalanie

(ang. merge sort)

O( nlog(n) )

Wymaga O(n) dodatkowej pamięci
Podział listy na podlisty, sortowanie podlist, łączenie
posortowanych podlist

Sortowanie szybkie

(ang. quick sort)

Optymistyczna:

O( nlog(n) )

Pesymistyczna:

O(n

2

)

Wyszukiwanie elementu średniego, mniejsze elementy idą na
lewo, a większe na prawo, aż do pojedynczych elementów
(rekurencja). Przykład sortowania niestabilnego; wpływ danych
wejściowych na złożoność obliczeniową;

Sortowanie przez wybieranie

(ang. selection sort)

O(n

2

)

Wybieramy najmniejszy element z tablicy i zamieniamy go z
pierwszym jej elementem. Z pozostałej, nieposortowanej części
robi to samo (element najmniejszy wymieniamy kolejno z
drugim ,trzecim itd.). Czynność powtarzamy n-1 razy.

4. Przedstawić iteracyjne oraz rekurencyjne struktury algorytmiczne. Dokonać

porównania.

iteracja

Rekurencja



technika powtarzająca pewną czynność
w pętli (określoną ilość razy lub do
spełnienia określonego warunku)



Konstruuje się też algorytmy iteracyjne
polegające na konstruowaniu ciągu
przybliżonych rozwiązań {x

k

}, zbieżnego

do rozwiązania dokładnego x

*



technika pozwalająca opisać problem za pomocą jego składowych
(umożliwia funkcji/procedurze/podprogramowi wywołać samą siebie)



W algorytmie rekurencyjnym mamy przypadek bazowy (obiekty
podstawowe) i ogólny (obiekty zbudowane z podstawowych).
Podstawowymi elementami przy układaniu algorytmów rekurencyjnych
są: warunek stopu i dekompozycja problemu.



W każdym wywołaniu rekurencyjnym do życia powoływany jest nowy
zestaw zmiennych lokalnych, zaś stare odkładane na stosie.



O wszystkim decyduje i o wszystko dba kompilator



Implementacja rekurencyjnej definicji funkcji wymaga tłumaczenia na
język programowania – rekord aktywacji (w stosie programu; parametry

wywołania, wartość zwracana, zmienne lokalne, dynamiczne dowiązanie
do rekordu wywołania procesu wywołującego, adres powrotu do procesu
wywołania)



Do obliczenia n+1-ej wartości
wykorzystuje poprzednią, n-tą iterację.



pozwalana na przejrzysty i zwarty opis algorytmu, wydajne struktury
danych kosztem złożoności wykonania



Dla obliczenia n-tej wartości potrzebuje zejść aż do pierwszej (tzw. drzewo
rekurencji).



Iteracyjne struktury danych: tablica

Elementarne konstrukcje algorytmiczne
(primitive constructions):



Bezpośrednie następstwo (instrukcja po
instrukcji)



Wybór warunkowy (if)



Iteracja warunkowa (while, do-while;
niejawna liczba iteracji)



Iteracja ograniczona (pętla for)



Iteracyjne struktury danych: kolejka,
stos, lista



Np. wywołanie funkcji, drzewa (katalogów)



Rekurencyjne struktury danych: drzewo, graf

Struktura

algorytmiczna

opis

Stos
(LIFO)

- Liniowa struktura danych
- Dostęp tylko do wierzchołka stosu, do pozostałych po zdjęciu elementów leżących między nimi, a

wierzchołkiem

Kolejka
(FIFO)

- Liniowa struktura danych
- Nowe dane dopisywane na końcu kolejki
- Z początku kolejki pobierane są dane do dalszego przetwarzania (bufor FIFO)
- Modyfikacja kolejki – kolejka priorytetowa (każde dane mają priorytet – na wyjściu pierwsze

pojawią się dane o najmniejszym priorytecie)

- Kolejka cykliczna – rodzaj kolejki (1-wszy element tablicy traktowany jest jako kolejny po

ostatnim; w praktyce taki indeks wylicza się z (N+1) mod WIelkoscTablicy)

- Zastosowanie: obsługa zdarzeń (np. kolejka priorytetowa w Systemach Operacyjnych –

przydzielanie sprzętu procesom)

lista

- Liniowo uporządkowany zbiór elementów
- W dowolnym miejscu można usunąć/dodać element
- Rodzaje: jednokierunkowa, dwukierunkowa, cykliczna
- Implementacja: tablicowa lub wskaźnikowa
- Pierwszy i ostatni element listy = końce listy

drzewo

- Hierarchiczne ułożenie danych
- Rodzaje: drzewo binarne, BST (ang. Binary Search Tree – binarne drzewo poszukiwań), czerwono-

czarne, AVL, B-drzewa

graf

- Zbiór wierzchołków połączonych krawędziami
- Każda krawędź kończy i zaczyna się w którymś z wierzchołków
- Wierzchołki grafu są numerowane
- Wierzchołek = obiekt
- Krawędź = relacja między obiektami
- Graf skierowany = krawędzie mają wyznaczony kierunek
- Krawędź może posiadać wagę (liczbę określającą np. odległość między wierzchołkami, gdy np.

graf = połączenia międzymiastowe)

- W grafie skierowanym waga zależy od kierunku przechodzenia przez krawędź (np. w mapach)

Tablica

- Kontener danych dostępnych, poszczególne komórki dostępne są za pomocą kluczy (o

wartościach numerycznych)

- Tablica statyczna -> rozmiar ustalony z góry
- Tablica dynamiczna -> rozmiar zmienia się w trakcie wykonywania programu

Rekord (struktura)

- Złożony typ danych w wielu językach programowania
- Grupuje logicznie powiązane ze sobą dane różnego typu w 1 obszarze pamięci
- Pola (składowe rekordu) są etykietowane (unikatowość nazw); podanie nazwy = dostęp do

danego pola

Techniki algorytmiczne:
Dziel i zwyciężaj - problem dzieli się rekurencyjnie na dwa lub więcej mniejszych pod problemów tego samego
typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania
otrzymane dla pod problemów scala się uzyskując rozwiązanie całego zadania.

Programowanie dynamiczne - rozszerzenie metody dziel i zwyciężaj; Jeżeli podproblemy, na które został
podzielony problem główny, nie są niezależne, to w różnych podproblemach, wiele razy wykonywane są te
same obliczenia.

Algorytm zachłanny – algorytm, dokonujący w każdym kroku, najlepiej rokującego w danym momencie wyboru
rozwiązania częściowego. Algorytm zachłanny nie patrzy, czy w kolejnych krokach jest sens wykonywać dane
działanie. Dokonuje wyboru wydającego się w danej chwili najlepszym.

5. Struktury drzewiaste, charakterystyka podstawowych typów drzew oraz przykłady ich

zastosowań.

Drzewo:



kolekcja węzłów, w którym jeden wyróżniony jest jako korzeń (Root) oraz łączących je krawędzi



reprezentuje hierarchię danych



ułatwia i przyspiesza wyszukiwanie



umożliwia łatwe operowanie posortowanymi danymi

Elementy drzewa



węzeł = element drzewa, korzeń = wyróżniony węzeł, liść = węzeł bez potomków, węzeł wewnętrzny węzeł
mający 1 lub więcej potomków



węzły powiązane są relacją rodzicielstwa (ang. parenthood)



węzły są siostrzane (ang. siblings), jeśli mają tego samego rodzica



wysokość węzła – liczba krawędzi na najdłuższej, prostej ścieżce prowadzącej od tego węzła do liścia



wysokość drzewa – wysokość korzenia; największa głębokość (poziom) drzewa



głębokość (poziom) węzła – długość ścieżki łączącej węzeł z korzeniem



długość = liczba krawędzi leżących na unikalnej ścieżce z korzenia do tego węzła



stopień węzła = liczba następników węzła



relacja przodek-potomek (ojciec-syn)



ścieżka – ciąg krawędzi łączących węzły; Istnieje 1 ścieżka łącząca korzeń z pozostałymi wierzchołkami

Rodzaje:



nieuporządkowane – kolejność węzłów dowolna



uporządkowane



etykietowane – etykiety przypisane do krawędzi lub węzła

Zastosowania drzew:



schematy organizacyjne



dane genealogii (drzewa genealogiczne dla węzłów, które mogą mieć więcej niż 2 potomków)



reprezentacja wyrażeń i składni kodu źródłowego w kompilatorach



analiza połączeń np. obwodów elektrycznych czy układów komunikacyjnych

podstawowe typy drzew

typ

opis

Rysunek

Drzewo
binarne BT

- każdy z węzłów posiada lewe i/lub prawe poddrzewo (gdy nie

posiada = puste)

- węzeł x takiego drzewa posiada atrybuty: x.key, x.left i x.right
- reprezentacja: tablicowa, rodzicielska, dowiązaniowa
- operacje: przeglądanie drzewa
- pełne drzewo binarne = wszystkie wewnętrzne węzły stopnia 2

i jednakowa głębokość wszystkich liści

- zrównoważone drzewo binarne = pełne drzewo binarne do

głębokości d-1, a wszystkie węzły na głębokości d po lewej
stronie; implementacja: kopiec (tablice)

- częściowo uporządkowane = węzeł rodzica ma wartość nie

mniejszą od dzieci, element korzenia poddrzewa największym
elementem tego poddrzewa

- implementacja: dwu lub trój odsyłaczowa

- zastosowanie: zapis historii turnieju tenisowego, wyrażenia

arytmetyczne z dwuargumentowymi operatorami (każdy
operator węzłem, a jego argumenty poddrzewami)

Drzewo
poszukiwań
binarnych BST

- dowolne drzewo binarne
- wierzchołki ułożone zgodnie z porządkiem symetrycznym

(mniejsze wartości w lewej części, większe w prawej)

- operacje: wyszukiwanie, wstawianie, usuwanie, min/max,

predecessor, successor

- złożoność obliczeniowa proporcjonalna do wysokości drzewa

- zastosowanie: zadania szybkiego sortowania/wyszukiwania

elementów np. słowniki czy kolejki priorytetowe

Zrównoważone
drzewo BST

- różnica wysokości obu poddrzew każdego węzła w drzewie

wynosi 0 lub 1

- jeśli wszystkie liście są na 1 lub 2-óch poziomach = drzewo w

pełni zrównoważone

- można zrównoważniać drzewa BST (rotacja prawa i lewa)

- zastosowanie – ciąg Finobacciego (?)

Zrównoważone
drzewo AVL

- drzewa równoważone lokalnie
- w każdym węźle wysokość jego poddrzew różni się max. o 1

poziom

- współczynniki zrównoważenia (różnice wysokości lewego i

prawego poddrzewa): 1,-1,0

- operacje: wstawianie węzła, usuwanie, rotacje
- nie zmieniają drzewa: serach, min, max, successor, predecessor

- zastosowanie: szybkie wyszukiwanie

Drzewo
czerwono-
czarne RB

- każdy węzeł jest czerwony lub czarny
- każdy liść (null) jest czarny
- gdy węzeł czerwony, to jego synowie czarni
- każda ścieżka z ustalonego węzła do liścia ma tyle samo

czarnych węzłów

- każdy węzeł zawiera pola: color, key, left, right i parent
- operacje – jak dla AVL
- pesymistyczna złożoność: O(lgn)

- specjalne znaczenie w informatyce, umożliwia szybkie

wyszukiwanie

6. Omówić sposoby implementacji list jednokierunkowej oraz dwukierunkowej. Podać

zestaw operacji wchodzących w skład interfejsu listy.

Lista
- skończona sekwencja elementów ułożonych w liniowym porządku
- struktura służąca do reprezentacji zbiorów dynamicznych
- Lista posiada głowę i ogon.
- Liniowo uporządkowany zbiór elementów
- W dowolnym miejscu można usunąć/dodać element
- Rodzaje: jednokierunkowa, dwukierunkowa, cykliczna
- Implementacja: tablicowa lub wskaźnikowa
Pierwszy i ostatni element listy = końce listy

Operacje podstawowe

Operacje złożone

Wstawianie, usuwanie, dostęp do elementu

Wyszukiwanie elementu, wstawianie za/ usunięcie k-
tego elementu, przestawienie k-tego na
początek/koniec listy, odwracanie/łączenie list

Lista jednokierunkowa

Lista dwukierunkowa

Implementacja wskaźnikowa

Implementacja tablicowa

- Każdy element listy składa się z co najmniej 2 pól: klucza

i pola wskazującego na następny element listy

- Listy dwukierunkowe posiadają dodatkowo pole

wskazujące na poprzedni element listy

- Wskaźniki = pola wskazujące na poprzedni/następny

element listy

Typy informacji:
- Klucz = informacja merytoryczna (widoczna na zewnątrz)
- Wskaźnik (widoczna wewnątrz)

x.key (wartość pola klucza elementu listy), x.next (wskaźnik
do następnika), L.head (wskazuje początek listy lub null gdy
lista jest pusta)

- Lista opiera się na tablicy obiektów (lub rekordów)

danego typu

- Tablica o rozmiarze wystarczającym do zapamiętania

najdłuższej listy

- Zmiennej last z pozycją ostatniego elementu


Dopisanie elementu do listy:
- Jeśli na końcu, to kolejny element tablicy
- Jeśli pomiędzy innymi elementami, to przesuwa się o 1

pole w prawo wszystkie elementy o indeksie wyższym niż
pole, na które będzie wstawiany obiekt; w lukę wpisuje
się nowy element

Dopisanie elementu (prosta lista 1-stronna):
- Gdy na końcu listy, to wskaźnik obiektu ostatniego

ustawia się na nowy obiekt danego typu

- Jeśli wewnątrz, to tworzy się nowy obiekt danego typu

ze wskaźnikiem wiążącym ustawionym na następnik
elementu, a następnie wskaźnik poprzednika ustawia się
na ten obiekt (ważna kolejność! Inaczej nie będzie znany
adres następnika)

Usunięcie elementu
- Odwrotne do wstawiania – zapisuje się wskaźnik do

usuwanego elementu, następnie wskaźnik poprzednika
przestawia się na następnik, następuje zwolnienie
pamięci po obiekcie usuwanym (wskaźnik tymczasowy)

Zalety: dobra elastyczność (brak ograniczeń co do rozmiaru
listy)

Wady: bardziej skomplikowana nawigacja, wymaga uwagi w
działaniu na wskaźnikach

Zastosowania: aplikacje obsługujące pocztę elektroniczną,
listy przewijane, zarządzanie pamięcią przez SO w sterowaniu
procesami

Usunięcie elementu pod danym indeksem tablicy:

- Przesunięcie o 1 pole w lewo wszystkich

elementów o indeksie wyższym

Lista dwukierunkowa może być reprezentowana przez wiele
tablic (mamy 3 tablice, każda o tej samej długości,
przechowują odpowiednio previous, key i next) lub w
pojedynczej tablicy (prev, key i next zajmują 3 kolejne pozycje
tablicy)

Zalety: prosta nawigacja wewnątrz listy, korzystanie z gotowej
struktury tablicy, szybki dostęp do elementu o konkretnym
numerze, większa odporność na błędy

Wady: niska elastyczność (zwłaszcza rozmiar tablicy, musimy
znać maksymalny jej rozmiar), liniowa złożoność operacji
wstawiania i usuwania (operacje te trwają dłużej), mniej
efektywna (statyczna pamięć)

7. Omówić algorytmy efektywnego poszukiwania najkrótszej ścieżki w grafie.

Problem wyszukania najkrótszej ścieżki polega na znalezieniu w grafie ważonym najkrótszego połączenia
pomiędzy danymi wierzchołkami np. problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych
oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków.

Nazwa

algorytmu

opis

Dijkstry



Dla grafów skierowanych i nieskierowanych



„docierać tam, gdzie można się dostać najmniejszym kosztem”, przykład algorytmu zachłannego



Znajduje najkrótszą drogę z wierzchołka p (źródło) do wszystkich innych lub wybranego wierzchołka k



Wszystkie krawędzie grafu mają nieujemne wagi (wtedy używa się Bellmana-Forda)



Polega na przypisaniu wierzchołkom pewnych wartości liczbowych (tzw. cechy wierzchołków)



Cecha wierzchołka v może być stała (gdy równa długości najkrótszej drogi z p do v) lub tymczasowa



Gdy graf nieważony (wszystkie wagi mają 1), zamiast Dijkstry stosuje się algorytm przeszukiwania grafu wszerz



Złożoność zależy od liczby wierzchołków V i E krawędzi grafu



O rzędzie złożoności decyduje implementacja kolejki priorytetowej (O(V

2

) przy implementacji tablicy, O(ElogV)

dla kopca, O(E+VlogV) dla kopca Finobacciego)

1) Wszystkie wierzchołki (oprócz p) otrzymują tymczasowe cechy , źródło p otrzymuje cechę stałą 0
2) Wszystkie wierzchołki połączone krawędzią z p otrzymują cechy tymczasowe (równe odległości od p)
3) Z wierzchołków z punktu 2 wybieramy ten o najmniejszej cesze tymczasowej, oznaczając go jako v i zmieniając

jego cechę na stałą

4) Przeglądamy wszystkie wierzchołki połączone z v
5) Gdy droga z p przechodząca przez v do któregoś z wierzchołków z pkt. 4 ma mniejszą długość od tymczasowej

cechy tego wierzchołka -> zmniejszamy tą cechę

6) Dopóki nie zamienimy cechy wierzchołka k (końcowego) na stałą, powracamy do punktu 3

Zachłanny



W celu wyznaczenia rozwiązania, w każdym kroku dokonuje najlepiej rokującego w danym momencie wyboru
rozwiązania częściowego (zachłannego)



Inaczej - nie patrzy czy w kolejnych krokach jest sens wykonywać działanie, dokonuje lokalnie optymalną (w
danej chwili najlepszą) decyzję, na podstawie której kontynuuje rozwiązanie pod-problemu

Bellmana-

Forda



Wolniejszy od algorytmu Dijkstry, ale bardziej ogólny



Możliwa praca na wartościach ujemnych wierzchołków



Służy do wyznaczania najmniejszej odległości od ustalonego wierzchołka s do wszystkich pozostałych w
skierowanym grafie bez cyklu o ujemnej długości (bo wówczas najmniejsza odległość między niektórymi
wierzchołkami jest nieokreślona, bo zależy od liczby przejść cyklu)



Przykład – statek podróżujący w przestrzeni kosmicznej, węzły – galaktyki, wartości ujemne – tunele
przestrzenne



Koszta można nadrobić za pomocą wartości ujemnych. Przy cyklach ujemnych (suma kosztów wychodzi
ujemna) koszt podróży może być nieskończenie mały, nie da się ustalić najmniejszej możliwości

1) Należy sprawdzić czy istnieje ujemny cykl, jak tak to zakończ algorytm z odpowiedzią „istnieje dowolna tania”.

W przeciwnym wypadku należy poszukać najtańszej ścieżki, ale z uwzględnieniem wartości ujemnych

2) Kontrolujemy, czy rozwiązania z punktu 1 nie da się poprawić, jeśli tak to znaczy że istnieje ścieżka z ujemnym

cyklem

3) Sprawdzamy długość ścieżki. Dla n wierzchołków nie może być dłuższa niż n-1 (bo brak cyklu)



Najtańsze ścieżki (między punktem początkowym i końcowym) korzystają z innych najtańszych ścieżek



Relaksacja krawędzi – jeżeli do wierzchołka A odległość wynosi x, a do B y i wierzchołki A i B połączone są
długością c to do B można poprowadzić ścieżkę wiodącą przez A, której długość wynosiłaby x+c
(pamiętamy, że wartości mogą być ujemne); poprawianie wyników sąsiadów z wykorzystaniem wyniku
wierzchołka; wystarczy relaksować kolejne wierzchołki, wchodzące w skład najkrótszej drogi



Ponieważ początkowo nie znamy krawędzi do najtańszej ścieżki, należy zrelaksować wszystkie krawędzie,
Czynność tą powtarzamy n-1 razy (w ten sposób w każdej iteracji tworzy się nam fragment ścieżki)



Złożoność przy prezentacji grafu za pomocą macierzy sąsiedztwa = 3 pętle for = O(n

3

). Gdy graf zapamiętany za

pomocą listy krawędzi = 2 pętle for z wszystkich wierzchołków zastępujemy jedną przebiegającą po
krawędziach = O(V*E)

Floyda-

Warshalla



dynamiczny



Służy do znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków w grafie ważonym



Jeśli najkrótsza ścieżka między wierzchołkami v1 i v2 prowadzi przez u, to jest ona połączeniem najkrótszych
ścieżek między v1 i u oraz u i v2



Złożoność obliczeniowa O(|V|

3

), pamięciowa: O(|V|

2

)

1) Inicjowanie tablicy długości najkrótszych ścieżek, tak, że dla każdej pary (v1, v2) odległość wynosi:



d[v1,v2]=0 gdy v1=v2



d[v1,v2]=w(v1,v2) gdy (v1,v2) E



d[v1,v2]= gdy (v1,v2) nie należy do E

2) włącz do swoich obliczeń ścieżki przechodzące przez kolejne wierzchołki
3) w k-tym kroku sprawdź, czy dla każdej pary wierzchołków można skrócić/utworzyć ścieżki między nimi

(przechodzącej przez k; kolejność wierzchołków obojętna, ale niezmienna w programie)

4) Po wykonaniu |V| takich kroków -> długości najkrótszych ścieżek są wyliczone

8. Procesy kompilacji i interpretacji w różnych językach programowania. Omów ich

przebieg, porównaj wady i zalety, wskaż przykłady implementacji w popularnych
językach.



Translator = program tłumaczący program na kod maszynowy, zrozumiały dla komputera



Kompilator = translator, który tłumaczy kod z 1 języka (źródłowego) na inny język (wynikowy)



Interpreter = inny typ translatora; program nie generuje programu wynikowego, tylko od razu wykonuje
instrukcje tego kodu; wykorzystanie: języki poleceń powłok SO, języków wysokiego poziomu, ;

implementacja szybsza i prostsza niż w przypadku kompilatora, można uruchamiać częściowo napisane
programy, możliwość częstej modyfikacji oprogramowania, maszyny wirtualne



Podejście hybrydowe = możliwość wykorzystania interpretera dla języków zwykle kompilowanych



Interpreter rzadziej wykonywany od kompilatorów (mała wydajność aplikacji), często wypierany też przez
mechanizmy sprzętowe (np. koprocesory z kodem Javy)

kompilacja

interpretacja



Wykonanie programu kompilatora następuje w czasie
tłumaczenia



Po przetłumaczeniu program jest niezmienny (statyczny)



Dane wejściowe = cały program źródłowy, przekształcanie
na postać wynikową



Skompilowane moduły są łączone przez linker w jeden
program wykonalny



Wyodrębnianie niewielkich jednostek programu źródłowego,
tłumaczeniu ich na postać wynikową, natychmiastowe ich
wykonanie



Proces interpretacji jest cykliczny



W czasie interpretacji przechowywany jest program
źródłowy



Program wynikowy wykonuje się szybciej



Do wykonania programu wynikowego nie potrzeba
kompilatora



Lepsza optymalizacja kodu (dedykowana pod daną
architekturę)



Łatwość zmian programu



Mniejsza zajętość pamięci zewnętrznej (tylko tekst źródłowy)



Możliwość pracy konserwacyjnej (zmiany w trakcie
wykonania programu)



Przenośność, zastosowania sieciowe

1) Plik edytowany jest w edytorze tekstowym
2) Proces kompilacji – z pliku źródłowego tworzony jest plik

obiektowy (kod binarny zawierający kod maszynowy

3) Konsolidacja – łącznie plików obiektowych z pkt. 2 i

bibliotecznych (plików binarnych); tworzy się plik
wynikowy (program) będący plikiem binarnym, o formacie
określonego typu

1) Plik edytowany jest w edytorze tekstowym
2) Proces interpretacji – interpretowane są pliki źródłowe

projektu oraz pliki biblioteczne (nie w postaci binarnej);
wynikiem jest wykonanie programu



Kompilowane języki programowania -> kody po kompilacji
to samodzielne programy, np. Delphi, Pascal, C, C++



Częściowo kompilowane – powstaje kod bajtowy (postać
pośrednia) wymagający platformy uruchomieniowej, np.
Java (JVM, Java RuntimeEnvironment), C# (.Net
Framework)



Języki wymagające interpretera



Przykłady: Javascript (interpreterem przeglądarka), Perl
(język ekstrakcji i raportowania), PHP (dynamiczne tworzenie
stron internetowych), Python, Ruby, VBA (Interpreterem
pakiet MS Office)

Kompilacja – c.d.



Proces 2-etapowy (etap analizy, etap syntezy)



Analiza – 1-wszy etap. Tutaj program źródłowy rozkładany na części składowe, generowana reprezentacja
pośrednia, oraz wykrywanie i zgłaszanie błędów

 Analiza leksykalna (liniowa, skanowana) – grupuje znaki strumienia wejściowego w znaki

leksykalne (tzw tokeny, czyli elementarne konstrukcje języka źródłowego, np. słowa, liczby,
identyfikatory czy operatory); używany do rozpoznawania nierekurencyjnych konstrukcji
języka

 Analiza składniowa (syntaktyczna lub hierarchiczna) – bada, czy jednostki leksykalne tworzą

poprawne konstrukcje języka źródłowego; rekurencyjne konstrukcje języka przetwarza parser

 Analiza semantyczna

- sprawdza program źródłowy pod względem semantycznej zgodności z definicją języka

źródłowego (kontrola zgodności typów), zbierane są informacje potrzebne do
generowania kodu

- kontrola przepływu sterowania (sprawdzana poprawność użycia instrukcji sterujących

przepływem sterowania, np. Goto - C,Pascal, break – C); kontrola poprawności deklaracji
obiektów (sprawdzanie poprawności deklaracji obiektów w kodzie źródłowym przed 1-
wszym użyciem



Synteza – na podstawie reprezentacji pośredniej generowany program wynikowy (w innym języku
źródłowym lub postacią kodu wykonywalnego)

 Generacja kodu pośredniego (języka/reprezentacji pośredniego/ej) – jest wiele rodzajów

(zorientowane na język/maszynę/uniwersalne); cel – redukcja kosztów
utrzymania/wytwarzania kompilatorów

 Optymalizacja kodu – poprawa efektywności kodu (przyspieszenie i redukcja rozmiarów);

może być wykonana na poziomie kodu źródłowego/pośredniego/wykonywalnego; jest to
złożony proces – dzięki technikom analizy przepływu danych i sterowania – wykonuje się
transformacje ulepszające (niezmieniające semantyki programu); przykład – optymalizacja
pętli w programie

 Generacja kodu wynikowego – wejściem dla niej zazwyczaj pośrednia reprezentacja

programu (proste kompilatory generują kod wynikowy bezpośrednio z kodu źródła); postać
kodu asemblerowego, przemieszczalnego kodu maszynowego lub gotowego programu
wykonywalnego; wykonywane są 2 czynności dla efektywności: wybór rozkazów i przydział
rejestrów

Język

programowania

Opis kompilacji

C/C++

Java



Uruchomienie programów w Javie = interpretowanie kodu pośredniego i wykonanie
odpowiednich instrukcji kodu maszynowego (binarny kod właściwy dla danego procesora i SO)



Do uruchomienia wykorzystuje się platformę Javy (środowisko uruchomieniowe aplikacji; JRE –
środowisko składające się z Java Virtual Machine+ Java Application Programming Interfaces)



Każda instrukcja kodu wynikowego (pośredniego) Javy jest interpretowana przez VM ->
spowalnianie działania aplikacji -> aby przyspieszyć kod pośredni wprowadzono kompilację JIT
(Just-in-time, kompilacja w locie = zamiana kodu pośredniego w kod binarny danego procesora i
SO w czasie rzeczywistym – przyspieszenie programu)



Jednokrotna kompilacja powtarzających się fragmentów kodu



Oprócz VM systemu operacyjnego, do interpretacji kodu pośredniego wymagane są biblioteki z
Java API)

.NET



Programy pod tą platformę nie zawierają kodu dla konkretnego procesora (*.exe zawierają kod
pośredni tzw CIL – common intermediate language, który przed wykonaniem jest tłumaczony na
kod maszynowy konkretnego procesora)



W Javie w kodzie pośrednim jest kod bajtowy (pliki wykonywalne z rozszerzeniem CLASS),
uruchomienie (wywołanie VM z nazwą programu jako parametrem, ); aplikacje w .NET
uruchamiają się jak zwykłe *.exe (które potrafią wykryć obecność platformy .NET i wyświetlić
ewentualnie komunikat); aplikacje Javy interpretowane wiersz po wierszu lub kompilowane na
kod maszynowy tuż przed wykonaniem , w .NET aplikacje zawsze kompilowane przed
wykonaniem (kompilacja w locie JIT)



Java i .NET podobne, wymagają rozszerzeń systemu do odczytania kodu pośredniego (VM dla
Javy, CLR – Common Language Runtime - dla .NET)

9. Mechanizm przeładowanie operatorów w językach obiektowych. Podaj przykład

praktycznego zastosowania.

Przeładowanie (przeciążanie) operatorów
- rodzaj polimorfizmu (1 interfejs, wiele metod) w niektórych językach programowania
- te same operatory są wykorzystywane do działania nad różnymi obiektami
- operator może mieć różne implementacje w zależności od typów operandów (argumentów)
- umożliwia posugiwanie się obiektami klas tak samo jak typami wbudowanymi (C++)
- poprawia czytelność kodu, umożliwiając zdefiniowanie większej części biblioteki standardowej na poziomie

języka (bez tricków)

- wada: może spowodować powstanie niejasnych konstrukcji

przykład – np. w C++ można zrobić klasy odzwierciedlające budowę wektorów. Dzięki przeciążeniu operatora
„+”, można dodać parametry obiektu wektora „A” i „B”, a po przeciążeniu instrukcji przypisania przepisać do C.

10. Mechanizm dziedziczenia. Dziedziczenie jedno i wielokrotne. Podaj przykład

wykorzystania.

Dziedziczenie



Dotyczy programowania obiektowego



Proces, w wyniku którego obiekt otrzymuje właściwości innego obiektu



Zasada klasyfikacji – np. dziedziczenie klas – nie trzeba od nowa wypisywać właściwości obiektu, obiekt
staje się specyficznym egzemplarzem ogólniejszej klasy)



Przykład klasy bazowej i klasy pochodnej (bazowa posiada wspólne elementy dla klas pochodnych, klasa
pochodna ma właściwości bazowej + własne rozszerzenia; posiadaja kompletny interfejs klasy bazowej)



Wielodziedziczenie (wielopoziomowa hierarchia klas, klasa pochodna dziedziczy kilka klas bazowych oraz
mieszane, które w C++ wykorzystują klasy wirtualne); języki, które wspierają, to: Eiffel, C++, Pytho, Perl itd.

Przykładem może być klasa bazowa figura i klasa pochodna trójkąt (figura posiada jakieś pole, obwód, tablicę
współrzędnych, a trójkąt precyzuje ile i jakie konkretnie współrzędne są mu potrzebne, może też wprowadzić
dodatkowo np. kąt)

11. Klasy abstrakcyjne i funkcje wirtualne w językach obiektowych. Podaj przykład

zastosowania.

Klasa abstrakcyjna



Klasa bez reprezentantów w postaci obiektów



Zależą od języka programowania



Definiuje pewien interfejs dla klas pochodnych



Uogólnienie innych klas, lecz sama jako taka nie istnieje



Przykład: klasa abstrakcyjna figura i dziedziczące po niej klasy koła, trójkąta i kwadratu (figury nie da się
określić, ale np. koło już tak)

język

Opis

C++



Klasa abstrakcyjna posiada zadeklarowaną co najmniej 1 metodę wirtualną



Klasa dziedzicząca musi implementować wszystkie odziedziczone metody czysto wirtualne



Zapobiega powstaniu 2 kopii w momencie, kiedy klasa D3 dziedziczy po D1 i D2, które dziedziczą po B (klasa
bazowa B odziedziczona jako funkcja wirtualna przez D1 i D2 powoduje powstanie tylko 1 kopii tej klasy w
klasie pochodnej; D1 i D2 mają identyczne kopie)



Jeśli chcemy zobaczyć zmienną składowej pochodnej typu virtual, to zobaczymy zmienną klasy bazowej



Różnica między zwykłą a wirtualną funkcją pojawia się gdy obiekt dziedziczy klasę bazową więcej niż 1 raz



Funkcja abstrakcyjna – prototyp funkcji wirtualnej, klasa pochodna powinna mieć swoją implementację
funkcji abstrakcyjnej; klasa abstrakcyjna = posiada co najmniej 1 funkcję abstrakcyjną

Java



Klasę abstrakcyjną tworzymy na 1 z 2 sposobów: za pomocą słowa kluczowego abstract (klasyczna klasa

abstrakcyjna) lub za interface (abstrakcyjny interfejs)



Klasa abstrakcyjna nie musi posiadać metod czysto wirtualnych (jednak takie podejście jest rzadsze – klasa
nieinstancjowalna)



Jeśli przynajmniej jedna metoda zadeklarowana jako wirtualna (abstrakcyjna), to klasa jest abstrakcyjna
(przy czym klasa abstrakcyjna może mieć również konkretne pola i metody)



Jeśli wszystkie metody są wirtualne, to klasę można zadeklarować jako interfejs (definicja posiadająca
jedynie operacje, bez danych)



Metody abstrakcyjne pełnią rolę symbolu zastępczego dla metod, które są implementowane w podklasach



Przy rozszerzaniu klasy abstrakcyjnej programista ma do wyboru jedną z dwóch opcji: może pozostawić
niezdefiniowane niektóre lub wszystkie metody nadklasy - wtedy podklasa również musi być abstrakcyjna,
albo zdefiniować wszystkie metody i wtedy podklasa nie jest abstrakcyjna.



Klasę można zdefiniować jako abstrakcyjną, nawet jeśli nie zawiera żadnych metod abstrakcyjnych.

C#



Klasa abstrakcyjna jest zadeklarowana za pomocą słowa kluczowego abstract

Funkcja wirtualna



Specjalna funkcja składowa (zadeklarowana w klasie bazowej, zdefiniowana w pochodnej)



Przydatne, gdy posługujemy się referencjami/wskaźnikami do obiektów



W klasie bazowej funkcje wirtualne definiują postać interfejsu. Każde (ponowne) definiowanie funkcji
wirtualnej w klasie pochodnej wyznacza specyficzną realizacje tej funkcji dla podanej klasy pochodnej



Dla zwykłych funkcji z identycznymi nazwami wywołanie (z klasy bazowej/pochodnej) zależy od typu
wskaźnika (a nie na to na co on wskazuje)



Prawdziwy polimorfizm (używanie metod klasy pochodnej tam, gdzie spodziewana jest klasa bazowa) –
korzystanie z metod klasy pochodnej korzystając ze wskaźnika, którego typ odnosi się do klasy
podstawowej



Polimorfizm dynamiczny (na etapie wykonania)

Przykład zastosowania funkcji wirtualnej i klasy abstrakcyjnej – biblioteki klas (klasa bazowa widzi tylko
składowe, które będą odziedziczone, pochodne zaś mają zdefiniowane realizacje metod wirtualnych dla
każdego obiektu)

12. Obsługa sytuacji wyjątkowych w językach obiektowych (np. C++, Java).

Wyjątek:



Mechanizm przepływu sterowania



Używany w mikroprocesorach i językach programowania



Do obsługi zdarzeń wyjątkowych (błędy)



W wyniku błędu generowany jest wyjątek, obsłużony (zapamiętanie stanu programu, przejście do
procedury jego obsługi; czasami po obsłudze wyjątku można powrócić do przerwanego kodu)



Np. Obsługa błędu braku strony (pobranie brakującej strony z pliku wymiany, kontynuacja pracy programu),
błąd dzielenia przez 0 (przerwanie obliczeń)

język

Opis

C++



W bloku try dajemy podejrzane instrukcje



Za blokiem try co najmniej 1 instrukcja catch



W catch umieszcza się typ wyjątku (czyli to co nas interesuje)



Nazwa typu nie jest konieczna, ale umożliwia odczytanie wartości



Bloków catch najczęściej tyle, ile możliwych typów do złapania



Przy wrzuceniu wyjątku konkretnego typu wpadnie on do 1-ego dobrego catch’a



Zawsze dobrze zabezpieczyć się blokiem Catach łapiącego wszystko



Rzucanie wyjątku throw – rzuca się jakiś obiekt; w tym momencie przerwane działanie funkcji i obiekt wędruje do bloków
catch



throw = obiekt

Java



Możemy sami rzucać wyjątki



Można rzucać wyjątki standardowe (instancje klas zdefiniowanych w bibliotece standardowej Java SE) ale można też

definiować i rzucać wyjątki własne



Definicja własnego typu wyjątku = implementacja klasy, będącej podklasą Throwable / Exceprion / RuntimeException



throw {obiekt}



throw New Exception(”wyjątek bla bla bla”);

13. Organizacja pamięci pomocniczej - metody przydziału miejsca na dysku.

Nazwa metody

opis

rysunek

System plików
zwartych
(przydział ciągły)



Wszystkie bloki przylegają do siebie (zajmują spójny
obszar)



Za 1-wszym mamy 2-gi itd. aż napotkamy wskaźnik
końca pliku



Wskazanie na plik zawiera wskazanie na 1-wszy blok i
długość pliku



Struktura katalogowa – do odwzorowania adresu



Najoszczędniejsze wykorzystanie przestrzeni danych –
całość na dane

Zalety:
+ Najbardziej elastyczna organizacja danych

(zniszczenie bloku -> lokalna utrata danych)

+ Dostęp bezpośredni do bloku (początek: offset)
+ Dodatkowy mechanizm innych systemów
+ Odpowiednie dla baz danych
+ Łatwo implementować dostęp swobodny i

sekwencyjny

Wady:
- Fragmentacja zewnętrzna (występuje tylko tutaj;

chodzi o to że dziury z nieprzydzielonymi blokami są
ułożone chaotycznie i może być problem z
wrzuceniem danych)

- Problemowe usunięcie lub wstawienie bloku

(przemieszczanie sąsiednich danych)

(wpis katalogowy – przydział ciągły)

Łańcuch
powiązanych
bloków
(przydział listowy)



Analogia listy jednokierunkowej



Każdy blok zawiera wskaźnik do następnego bloku



Ostatni blok zawiera adres pusty



Część przestrzeni danych przeznaczona na wskaźniki
do następnych bloków



Bloki zajmowane przez plik są porozrzucane (nie
zajmują wspólnego obszaru)



Koniec 1 bloku pliku wskazuje na początek
następnego



Katalog usera wskazuje na początek 1-ego bloku pliku
i ostatniego bloku pliku

Zalety:
+ Zastosowanie – sekwencyjne przetwarzanie plików

(dostęp = czytanie kolejnych bloków)

+ Brak fragmentacji zewnętrznej (bloki można w

dowolnym momencie wykorzystać)

+

Wady:
- Dostęp sekwencyjny = mało elastyczna metoda
- Duża liczba dostępów do dysku (odczytanie pliku)

- Duża liczba modyfikacji wskaźników (usuwanie pliku;

by odzyskać obszar trzeba przejść cały łańcuch –
znaleźć koniec)

- Mała elastyczność
- Uszkodzenie 1 bloku może wpłynąć i posadzić cały

system plikowy (dowiązanie odwrotne – zmniejszenie
ryzyka kosztem miejsca na dysku)

(przydział listowy)

Mapa plików
(tablica alokacji)



Stan dysku pamiętany w mapie plików



1 blok dysku = 1 pozycja w mapie



Bloki nieużywane = 0 w tablicy (sprawdzamy 0/1)



Pozycja w katalogu -> element mapy reprezentujący
1-wszy blok (ten element wskazuje na następny itd.)



Ostatni blok pliku = wskaźnik pusty



Jeśli uszkodzony system plikowy – pomocna
nadmiarowa informacja (nr ID pliku)



Sekwencyjny dostęp do pliku



Warto trzymać dane w kupie



Zapobieganie = kilka kopii FAT w różnych rejonach
dysku (a nie jak DOS w kupie)

Zalety:
+ Polepszenie czasu dostępu swobodnego

Wady:
- Uszkodzenie mapy plików = poważne straty danych
- 2 kopie mapy w różnych rejonach dysku

(minimalizacja utraty danych na wypadek awarii
sprzętu)

- Znaczny ruch głowic dyskowych (sięganie do mapy

plików)

- N bloków pliku = 2N dostępów do dysku (FAT + dane)

Bloki indeksów



Wskaźniki dowiązań do plików pamiętane w
odrębnych blokach indeksów na dysku



Duży plik = konieczność kilku bloków indeksów
powiązanych w łańcuch



Każdy blok ma wskaźnik do następnego bloku



Pozycja w katalogu -> pierwszy blok w łańcuchu
indeksów



Każda pozycja bloku indeksowanego wskazuej na
adres bloku plikowego



Ostatni blok indeksów nie jest zazwyczaj zapełniony
(utrata miejsca)



Uszkodzenie bloku indeksów = poważna strata
danych (przeciwdziałanie – kilka kopii)



Linuks – w i-węźle pamiętane są wszystkie adresy
bloków dyskowych zajmowanych przez plik

Zalety:
+ Swobodny (niesekwencyjny) dostęp do pliku (na

podstawie nazwy i odległości w bloku indeksów)

+ Brak fragmentacji zewnętrznej (bloki tracimy na bloki

indeksów)

Wady:
- Operacje wycinania/wstawiania w pliku –

Struktura bloku indeksu:

Schemat listowy:

Indeksowanie wielopoziomowe

czasochłonne

- Metoda nie nadaje się do systemów z częstą

modyfikacją plików

- Dla dużego dysku trzeba przeznaczyć kilka bloków

indeksowych na schemat listowy/indeks
wielopoziomowy/schemat kombinowany

Ind. Komb.

Metody dostępu:



Sekwencyjny – informacja w pliku przetwarzana po kolei, 1 rekord po drugim (np. edytory tekstu)



Bezpośredni – dyskowy model pliku (plik zawiera rekordy logiczne o stałej długości,
odczytywane/zapisywane bez zachowania jakiegoś porządku); dysk umożliwia swobodny dostęp do
dowolnego bloku



Indeksowy – baza do opracowywania innych metod dostępu, różna konstrukcja indeksów; indeks – sposób
dostępu do informacji (np. w Linuksie bloki pojedynczo/podwójnie/potrójnie pośrednie)

Wydajność:



metody przydzielania – różne w zależności od zapotrzebowania na pamięć i czas dostania do bloków
danych



przydział ciągły – pobranie danych wymaga 1 kontaktu z dyskiem (dostępność sekwencyjna i swobodna)



przydział listowy – liczba dostarczonych do i-tego bloku i operacji czytania z dysku – dostęp sekwencyjny



struktura pliku zależy od deklaracji typu dostępu



konwersja typu pliku- kopiowanie do nowego pliku o wymaganym typie

Określając obowiązujący w systemie rozmiar bloku bierze się pod uwagę poniższe kryteria:
•

Strata miejsca z powodu bloków nie zapełnionych całkowicie, która zwiększa się w miarę zwiększania
rozmiaru bloków (fragmentacja wewnętrzna).

•

Strata miejsca związana ze wskaźnikami – im mniejsze bloki, tym więcej użytych wskaźników.

•

Jednostki przesyłania danych z urządzeń zewnętrznych do pamięci głównej- rozmiar bloku powinien być
wielokrotnością tej jednostki.

•

Rozmiar obszaru pamięci głównej potrzebny do wykonania każdej operacji czytania lub pisania odnoszącej
się do pliku.

Struktura pliku zależy od dostępności, np. przy kopiowaniu do innego trzeba dokonać konwersji żeby można
było dokonać kopiowania

14. Omów i porównaj najczęściej stosowane systemy plików.

System

plikowy

opis

FAT32



Następca FAT16



Wykorzystuje tylko 28 bitów (nie 32) = możliwość

opisania 268 435 438 klastrów -> możliwość użycia na

dyskach 16TB z sektorami 512-bajtowymi



32-bitowe pole w boot sektorze (określa rozmiar partycji w sektorach; partition boot sector – pierwszy sektor
partycji z kodem ładowania SO) -> wielkość partycji nie może tu przekroczyć 2TB (512-bajtowe sektory) i 16TB (dla
4096)



Max rozmiar pliku – 4GB (wynika to z kompatybilności ze starszymi systemami i wielkości pola w tablicy katalogu
określającego rozmiar pliku)

Cechy:



Prostota



Brak mechanizmu zarządzania wolnymi sektorami dysku



Pliki porozrzucane na dysku = częste fragmentacje



Czasochłonne obliczanie wolnego miejsca



Obsługiwany niemal przez wszystkie SO -> stosowany w przenośnych nośnikach danych



Brak kontroli praw dostępu do danych

NTFS



Standardowy system plików od Windows NT w górę



Zastępca FAT, wykorzystał system HPFS



Ulepszenie w stosunku do FAT:

- Obsługa meta danych (np. prawa dostępu)
- Dodanie struktur poprawiających szybkość pracy z dużą liczbą plików i dyskami o dużej pojemności
- Brak ostrego ograniczenia maksymalnego rozmiaru pliku na dysku



Ulepszenia w stosunku do HPFS:

- Lista kontroli dostępu (ACL)
- Dziennik operacji dyskowych (ang. journal)

Cechy:



Wprowadzona quota



Kompresja woluminów



Obsługa rzadkich plików (plik rzadki – wypełniony zerami)



Możliwość montowania woluminu w katalogu



Volume shadow copy (copy on write) – przechowuje archiwalne wersje plików i katalogów



Linki symboliczne (Windows Vista)

Ext2



Wykorzystany w Linuksie



Następca ext



Rozpoznanie uszkodzenia systemu plików (np. po awarii) przy starcie systemu -> automatyczne naprawianie szkód
(programem e2fsck), uszkodzone pliki zapisywane w katalogu lost+fund



Posiada mechanizm zapobiegający znacznej fragmentacji danych (przydzielanie bliskich bloków przez prealokację)



Przy domyślnym rozmiarze bloku (4kb) obsługuje partycje do 16TB i pojedyncze pliki do 2TB



Nazwy plików mogą mieć do 255 znaków długości



Wolne pola w strukturach danych -> możliwość konwersji „w locie” do ext3 (w części z nich przechowywane dane
ext3)

Cechy:



Hierarchia plików i katalogów za pomocą i-węzłów



Każdy plik ma swój i-węzeł



Każdy i-węzeł ma unikatowy numer w systemie plików



Katalog = specjalny plik



Stabilny i dobrze przetestowany



Automatyczne sprawdzanie systemu po każdym niepoprawnym odmontowaniu i co jakiś czas



Wolne sprawdzanie systemu plików (po jego niepoprawnym odmontowaniu)



Niska wydajność dla bardzo małych plików

Ext3



Rozszerzenie i kompatybilność z ext2



Dodatkowo posiada mechanizm księgowania – dokładny zapis zmian na dysku (w razie awarii umożliwia szybsze
przywrócenie spójności systemu plików niż w przypadku ext2)



3 tryby księgowania



Brak możliwości odzyskania skasowanych plików (ext2 mógł)



Nowa cecha: indeksowanie katalogów przy dużej liczbie plików -> większa wydajność



Folder może posiadać maksymalnie do 32.000 podfolderów

Zalety:
+ niezawodność
+ prosta implementacja
+ znikoma fragmentacja plików
+ małe obciążenie procesora (w porównani udo ReiserFS i XFS)
+ kompatybilność i łatwa migracja do ext2

Wady:
- utrudnione odzyskanie usuniętych plików (zerowanie wskaźników do węzłów usuniętych plików)
- zmiana wielkości partycji bez utraty danych możliwa jedynie po odmontowaniu i zamianie na ext2 (ReiserFS =

możliwość zmiany pracującej partycji)

- niepełna powierzchnia dysku dla danych
- max rozmiar partycji - 32 TiB

Ext4



kompatybilność wsteczna (ext2, ext3), o ile nie włączono mechanizmu extent



większe limity rozmiaru (np. max rozmiar pliku – 16 TiB)



mechanizm extent = pliki przechowywane w ciągłym zbiorze bloków (możliwość rezerwacji obszaru dysku dla
danego pliku)



w i-węźle przechowywane max 4 informacje o extent (każdy taki zbiór może przechowywać do 128 MiB przy
rozmiarze bloku 4kiB – przy większym rozmiarze pliku stosowane jest pośrednie adresowanie; dane te zastępują
wskaźniki do bloków)



możliwość prealokacji bloków pliku



opóźniona alokacja – możliwość alokacji bloków dopiero w trakcie zapisu całego pliku na dysku



większa liczba obsługiwanych podfolderów: max 64.000



pozwala zredukować lub całkowicie wyeliminować fragmentację plików

Uzupełnienie do ext3:

Journaling



jest to dziennik położony w dodatkowym miejscu na dysku



przechowuje informacje na temat zmian danych i meta danych przed ich modyfikacją



wprowadzenie atomowych operacji zmian danych

- albo zmienimy wszystkie bloki i metadane, albo żadne



skraca czas testowania systemu plikowego

- czas przestaje zależeć od rozmiaru systemu plików

Journaling Block Device



miejsce księgowania realnie niezależnego od ext3



jest przechowywane w i-węźle



do właściwego journalingu służy interfejs JBD (interfejs niezależny od ext3, umożliwia dodatkowe
księgowanie do dowolnego systemu plików na urządzeniu blokowym)



interfejs JBD zachowuje w journalingu całe fizyczne bloki zamiast pojedynczych modyfikowanych bajtów



wada: większe zapotrzebowanie na powierzchnię dyskową



zaleta: uproszczenie systemu oraz ograniczenie wymuszeń na moc obliczeniową (blok zapisywany bez
żadnej obróbki)



ext3 ogranicza się do wywołania odpowiedniej funkcji JBD

Tryby journalingu



data = writeback

- księgowanie tylko meta-danych, największa wydajność (najczęstszy i najszybszy)
- spójność systemu plików
- na końcu plików zapisywanych przed awarią mogą pojawić się niepoprawne dane



data = journal (pełne księgowanie - metadane)

- 2 razy zapisuje bloki (journal i właściwa pozycja), pełne bezpieczeństwo (najwolniejszy)
- Wymaga wielu operacji dyskowych



data = ordered

- szybszy od pełnego kronikowania
- zapełnia tylko metadane, jednakże dzięki specjalnej postaci zachowuje się podobnie do pełnego

księgowania

- łączy modyfikacje danych i odpowiadające im meta-dane w logiczną całość w transakcje = atomowość

(zapis najpierw danych, potem meta-danych)

- dopiero po zapisaniu danych na dysku zapisuje do journala
- zapisuje na dysk (docelowe miejsce) dane
- wykorzystuje 3 techniki:

o pominięcie odtwarzania wskazanych bloków z wcześniejszych transakcji (modyfikacje

nieistniejących struktur nie mogą zamazać nowych danych)

o nowe dane nie otrzymują zwolnionych bloków (gdy operacja zwolnienia nie została

zatwierdzona w dzienniku; uniemożliwia zamazanie danych 1-ego pliku przed 2-gi)

o Prowadzenie listy osieroconych plików (pliki usunięte z katalogu, ale otwarte przez procesy;

możliwość odzyskania/usunięcie nawet po awarii systemu)

15. Metody zarządzania wolną przestrzenią pamięci dyskowej.

Zarządzanie wolną przestrzenią:



Trzeba dbać o wtórne zagospodarowanie dla nowych plików przestrzeni po plikach usuniętych



System utrzymuje listę wolnych obszarów



Odnotowane są wszystkie wolne bloki (nie przydzielone do żadnego pliku/katalogu)



Utworzenie/usunięcie pliku

Rozmiar bloku – wielokrotność jednostki wybranej dla SO (ustalony, zwykle 1024 lub wielokrotności)
Przy tworzeniu pliku SO sprawdza listę wolnych obszarów – gdy wystarcza miejsca, to przydziela obszary dla
pliku i wymazuje je z listy (analogia przy usuwaniu)

Metody zarządzania wolną przestrzenią (implementacja listy wolnych obszarów)

typ

opis

rysunek

Wektor
binarny

(bitowy)



Wektor bitowy umieszczony w superbloku informuje, który blok jest
zajęty (0), a który wolny (1)



Każdy blok dyskowy reprezentowany jest przez 1 bit w wektorze



Nr bloku = liczba bitów słowa x liczba wyzerowanych słów + pozycja 1-
ego bitu „1”

Wady:
- Mało wydajny
- Tylko dla małych dysków (sam wykaz bitowy zajmuje dużo miejsca)

Dla dysku 1,4 GB blok=512B, mapa bitowa 310kB

Lista

powiązana



Indeks 1-ego wolnego bloku jest w specjalnym miejscu na dysku i
pamięci (specjalne miejsce w systemie plików)



Sposób powiązania bloków - w bloku poprzednim (końcowe bajty)
znajduje się indeks bloku następnego

Wady:
- Metoda niewydajna – przejrzenie listy = odczyt KAŻDEGO bloku

(zazwyczaj szukany pierwszy blok)

- Trzeba przejść przez wszystkie elementy (tworzenie/usunięcie pliku)
- Przy tworzeniu szukamy 1-ego wolnego bloku

Grupowanie



W 1-szym bloku adresy wolnych bloków (indeks bloku 1-ej grupy
wolnych bloków)



Z pośród adresów n wolnych bloków, n-1 to bloki do alokacji a n-ty
zawiera n-1 indeksów kolejnych wolnych bloków



Ostatni z nich zawiera adresy następnych n wolnych bloków



W wybranym obszarze systemu blokowego znajduje się wskaźnik do
indeksu z n-1 wolnych bloków

Zalety:
+ Umożliwia szybkie odnajdywanie większej liczby wolnych bloków (dla

dużego pliku, który wymaga dużej liczby wolnych bloków)

zliczanie



Wykaz wolnych obszarów



Adres 1-ego wolnego bloku + licznik kolejnych wolnych



W przypadku kilku kolejnych (przylegających do siebie) wolnych bloków
pamiętany jest tylko adres 1-ego z nich oraz liczba wolnych bloków
znajdujących się bezpośrednio za nim



Wykaz wolnych obszarów jest ciągiem wpisów składających się z indeksu
bloku oraz licznika

Zalety:
+ Można jednocześnie zwalniać wiele bloków

W przypadku przydziału miejsca dla pliku na dysku są 3 podejścia: przydział ciągły, listowy i indeksowy

Katalog też ma przydzielane bloki (jak zwykły plik), ale jego struktura jest odpowiednio definiowana przez
system, specyficzne są operacje dostępu

16. Algorytmy planowania przydziału procesora.

nazwa

opis

FCFS

(ang. first

come first

served)



Proces, który pierwszy zamówił procesor, 1-wszy go otrzyma



Łatwa implementacja (kolejka FIFO)



Blok kontrolny procesu wchodzącego do kolejki procesów gotowych jest dołączany do końca



Wolny procesor przydziela się procesowi z czoła kolejki procesów gotowych



Długi średni czas oczekiwania (sumuje się czas trwania faz poszczególnych procesów z sumami częściowymi i
potem dzieli całość przez liczbę procesów)



Niewywłaszczające (nie oddaje procesora innemu procesowi, dopóki ten, co wszedł się nie skończy lub zamówi
operację we/wy)

SJF

(ang.

shortest Job

first)



Najpierw najkrótsze zadanie



Długość najbliższej z przyszłych faz procesora



Jeśli fazy są równe, wykorzystuje FCFS



Minimalny średni czas oczekiwania



Planowanie długoterminowe (problem z poznaniem długości następnej fazy)



Dobry do symulacji (minimalny średni czas oczekiwania), minimalny średni czas oczekiwania



Niewywłaszczający lub wywłaszczający (wtedy gdy do kolejki wejdzie proces o krótszej fazie)

Planowanie

priorytetowe



SFJ szczególnym przypadkiem planowania priorytetowego, gdzie PRI=1/długość fazy; priorytet zależny od
długości fazy procesora



Priorytet decyduje o wyborze procesu z kolejki procesów gotowych do wykonania



Priorytet definiowany wewnętrznie (limity czasu, wielkość pamięci, liczba otwartych plików)



Priorytet definiowany zewnętrznie (ważność procesu, opłaty, polityka)



Wywłaszczające lub niewywłaszczające (wszystko zależy czy jest wywłaszczenie w systemie; priorytet procesu
porównywany)



Problem – nieskończone blokowanie (głodzenie nisko-priorytetowych procesów); rozwiązaniem jest
postarzanie (aging), np. co 15 minut PRI+=1 (zwiększa się priorytet procesu)

Planowanie

rotacyjne

(ang. round

robin)



Specjalnie dla systemów z podziałem czasu



Kolejka procesów gotowych do wykonania traktowana jest jako kolejka cykliczna (składa się z bloków
kontrolnych; wiele kolejek, procesy przechodzą między nimi)



Planista przydziału procesora przegląda tę kolejkę i każdemu procesowi przydziela odcinek czasu nie dłuższy od
1-ego kwantu czasu (jeśli kwant jest duży to mamy algorytm FCFS, a jak krótki to mamy tzw. dzielenie
procesora – wrażenie, że n procesów ma własny procesor działający 1/n szybkości rzeczywistego procesora)



Gdy faza procesora w danym procesie przekracza 1 kwant czasu, to proces będzie wywłaszczony i wycofany do
kolejki procesów gotowych



Implementacja – kolejka FIFO



Długi średni czas oczekiwania



wywłaszczający

17. Algorytmy zastępowania stron.

Gdy brak wolnych stron, trzeba wytypować stronę-ofiarę, którą odsyła się na dysk (do zwolnionej ramki
wprowadza się wtedy brakująca strona i uaktualnia się tablica stron) – przykład odwołania się do strony, której
nie ma

Algorytmy zastępowania stron:



Powinny minimalizować częstotliwość braków stron (page-fault rate)



Ocenia się je na podstawie wykonania ich na pewnym ciągu odniesień (reference string) do pamięci (ciąg
adresów zredukowany do numerów kolejnych różnych stron) i sumowania braków stron (przy znanej
liczbie ramek)



Ciąg odniesień można tworzyć sztucznie lub na podstawie śledzenia danego systemu

Przy wzroście liczby ramek maleje logarytmicznie błąd braku stron

algorytm

opis

FIFO



Ofiarą staje się strona, która najdłużej przebywa w pamięci (kolejka FIFO)



Algorytm ten nie bierze pod uwagę właściwości obsługiwanych procesów i zastępuje strony na chybił-trafił



Prosta implementacja i niewielkie narzuty



Anomalia Belady’ego – liczba błędów braku stron przy wzroście liczby ramek zamiast maleć – wzrasta; dopiero przy
minimum 5-ciu ramkach stan jest ustalony

Optymalny

(teoretyczny)



Ofiarą staje się strona, która będzie nieużywana przez najdłuższy okres (problem z implementacją – nei wiadomo, do
jakich stron w przyszłości algorytm będzie się odwoływać)



Porównanie czysto-teoretyczne z innymi algorytmami



Najniższy współczynnik braków stron ze wszystkich algorytmów



Wolny od anomalii Belady’ego



Trudny do realizacji (wymaga wiedzy o przyszłej postaci ciągu odniesień)

LRU

(least

recently

used)



Ofiarą jest strona nieużywana od najdłuższego czasu



Algorytm zastępowania najdawniej używanych stron używa niedawnej historii do oszacowania najbliższej przyszłości



Lepszy od FIFO (mniej braków stron) i wolny od anomalii Belady’ego



Często stosowany



Trudności z zapamiętaniem historii użycia stron – może wymagać sporego zaplecza sprzętowego (oprogramowanie
zbyt wolne); każda strona powinna mieć swój proces licznika (przy wyborze ofiary wybieramy stronę, która ma
najmniejszą wartość licznika)



Podobnie jak OPT, LRU to algorytm stosowy (zbiór stron przy n ramkach jest zawsze podzbiorem zbioru stron w
pamięci przy n+1 ramkach)



Efektywna przy wykorzystaniu mikroprogramów

Określenie porządku ramek:



Liczniki

- W każdej pozycji tablicy stron rejestr czasu użycia
- Wymiana strony z najmniejszą wartością rejestru
- Wymaga przeglądania tablicy stron



Stos (2-kierunkowa lista ze wskaźnikami do czoła i końca

- Przy każdym odwołaniu do strony jej numer wyjmuje się ze stosu i umieszcza na jego szczycie
- Dno stosu – wskaźnik końcowy listy określa najdawniej używaną stronę

Algorytmy

przybliżające

LRU



Istnieje mało sprzętu do LRU – często stosuje się algorytmy przybliżające LRU

- Algorytm bitów odniesień

o Z każdą pozycją w tablicy stron związany jest bit odniesienia (ustawiony początkowo na 0)
o Przy odwołaniu do strony ustawia się naa 1
o Strona zastępowana w porządku FIFO, która ma bit odniesienia = 0

- Algorytm dodatkowych bitów odniesień

o Z każdą pozycją związany jest 8-bitowy rejestr ustawiony początkowo na 0000 0000
o W regularnych odstępach czasowych SO wprowadza na najbardziej znaczącą pozycję rejestru bit

odniesienia

o Wymieniana jest strona najdawniej używana – najmniejsza liczba w rejestrze
o Jeżeli kilka stron ma taką samą wartość rejestru – wymiana wszystkich lub FIFO

- Algorytm drugiej szansy

o Strony przeglądane w porządku FIFO
o Sprawdzenie bitów odniesienia (0-zastąpiona, 1-druga sznasa)
o 2-ga szansa = zerowanei bitu odniesienia, ustawienie czasu bieżącego (koniec kolejki)
o Cykliczne przewijanie stron
o Strona często eksploatowana nigdy nie będzie zastąpiona
o Ulepszony algorytm 2-ej szansy używa bitu odniesienia i modyfikacji

Oprócz tego są algorytmy zliczające (licznik odwołań do każdej strony, odwołanie = +1 do licznika; wykorzystują
algorytm LFU – zastępowanie strony o najmniejszym liczniku odwołań oraz MFU – odwrotnie; kosztowne) i
algorytmy buforowania stron (pula wolnych ramek, lista zmienionych stron na dysk

Szamotanie – zmniejszenie wykorzystania procesora przy zwiększeniu stopnia wieloprogramowości; gdy proces
ma za mało stron, wysoka częstotliwość braku stron (wtedy planista pobiera dodatkowe procesy)

18. Schematy RAID (Redundant Array of Independent Disks). Porównanie pod kątem

niezawodności i wydajności.

Macierz RAID



system umożliwiający łączenie 2 lub więcej urządzeń blokowych (dysków) w jedną przestrzeń logiczną
(wolumen)



zalety: zwiększenie niezawodności i/lub wydajności odczytu i zapisu



wady: konieczność stosowania prawie identycznych dysków (pojemność, czas dostępu)



kilka typów macierzy RAID

typ

opis

rysunek

Raid linear

JBOD



pojemność dysków w macierzy zsumowana



zapis liniowy, po przepełnieniu jednego dysku zapis danych na następnym



zalety:

 duża pojemność
 łączenie dysków o różnych pojemnościach
 mniejsze koszty



wady:

 brak zabezpieczonych danych
 czas odczytu i zapisu nie zmienia się



inne nazwy: NRAID (Non - RAID), append

Raid 0

(ang.

Stripping)



dane są dzielone na paski (stripe) o rozmiarze 4-128KB i przenoszone kolejno
naprzemiennie na poszczególne dyski



pojemność dyskowa macierzy = ilość dysków * pojemność najmniejszego dysku



zalety:

 duża pojemność
 duża szybkość odczytu/zapisu (proporcjonalnie do ilości dysków)



wady:



brak zabezpieczenia danych, awaria jednego dysku prowadzi do utraty
wszystkich danych (szansa na awarię rośnie wraz z N)

zastosowanie – duże i wydajne macierze do multimediów

Raid 1

(ang.

mirroring)



dyski łączy się parami



dane zapisywane na obu dyskach (sekwencyjny lub równoległy)



odczyt sekwencyjny z kolejnych dysków lub wyłącznie ze wskazanych dysków



zalety:



duża niezawodność, przy awarii jednego działa drugi



możliwy równoległy odczyt z dwóch dysków



możliwość zwiększenia szybkości odczytu i zmniejszenia czasu dostępu



odporność na awarię n-1 dysków przy n-dyskowej macierzy



wady:



zmniejszona szybkość zapisu - konieczność zapisu na dwóch dyskach
jednocześnie



utrata połączonej pojemności macierzy (jest taka, jak najmniejszego
dysku)

Raid 2



dane na dyskach są paskowane



zapis: 1 bit/pasek



potrzeba minimum 8 powierzchni do obsługi danych + dodatkowe dyski do
przechowywania informacji generowanych za pomocą kodu Hamminga
(korekcja błędów)



liczba dysków do przechowywania tych informacji proporcjonalna do logarytmu
liczby chroniących dysków



połączone dyski zachowują się jak 1 duży dysk



pojemność = suma pojemności dysków przechowujących dane

zalety:
+ każdy dowolny dysk (dane/kod Hamminga) w razie uszkodzenia może zostać

odbudowany przez pozostałe dyski

wady:
- konieczność dokładnej synchronizacji wszystkich dysków z kodem Hamminga

(inaczej dezorganizacja i nieprzydatność tych dysków)

- długotrwałe generowanie kodu Hamminga (wolna praca całego systemu)

Raid 3



dane składowane na N-1 dyskach



ostatni dysk = przechowuje sumy kontrolne



działa jak Raid 0, ale w macierzy na dodatkowym dysku przechowywane są kody
parzystości (obliczane przez specjalny procesor)

zalety:
+ odporność na awarię 1 dysku
+ zwiększona szybkość odczytu

wady:
- zmniejszona szybkość zapisu (kalkulowanie sum kontrolnych; eliminacja

poprzez sprzętowe kontrolery Raid)

- awaria dysku = spowolniony dostęp do danych(obliczenia sum kontrolnych)
- odbudowa macierzy po wymianie dysku = kosztowna obliczeniowo,

spowolnienie operacji odczytu i zapisu

- pojedynczy, wydzielony dysk na sumy kontrolne zazwyczaj jest wąskim gardłem

w wydajności całej macierzy

Raid 4



dane dzielone są na paski i przenoszone kolejno naprzemiennie na poszczególne
dyski; dane dzielone na większe bloki niż w raid 3



“w locie” obliczane są kody parzystości i zapisywane na dodatkowym,
dedykowanym dysku



zalety:



zwiększona niezawodność



lepsze wykorzystanie przestrzeni niż w mirroringu



dobre dla sekwencyjnego odczytu i zapisu danych (duże pliki)



wady:



ciągłe obciążenie jednego dysku



minimum 3 dyski



obliczanie parzystości



A xor B xor C xor D = P



P xor B xor C xor D = A

Raid 5



Wartość parzystości zapisywana na różnych dyskach



dane dzielone na paski o rozmiarze 4-128KB i przenoszone kolejno
naprzemiennie na poszczególne dyski



“w locie” obliczane są kody parzystości i zapisywane kolejno na każdym z
dysków



zalety:



zwiększenie niezawodności



równomierne wykorzystanie wszystkich dysków



zwiększony odczyt



wady:



skomplikowany i długotrwały proces odbudowania



zmniejszona szybkość zapisu (kalkulacja sum kontrolnych)



odbudowa macierzy po wymianie dysku – kosztowna (obliczeniowo, I/O)



minimum 3 dyski

Raid 6



jak w RAID-5, ale występują tu 2 nadmiarowe dyski



zalety:



zwiększenie niezawodności



odporność na awarię maksimum 2-óch dysków



ochrona systemu w momencie uszkodzenia jednego dysku podobna do
RAID-5, z Hot Spare ale ochrona w trakcie odbudowania systemu



wady:



skomplikowany i długotrwały proces odbudowy



minimum 4 dyski

19. Omów metody zarządzania pamięcią.

Metody przydziału PAO procesom użytkowym:



Brak podziału, wolna przestrzeń adresowa w danej chwili przydzielana 1-emu procesowi użytkowemu
(wieloprogramowanie można realizować przez wymiatanie (ang. swapping))



podział pamięci, wolna przestrzeń adresowa podzielona na części przydzielane pojedynczym procesom
użytkowym.

- podział statyczny- dzieli pamięć na stałe partycje o różnej długości lub na bloki o stałej długości zwane

ramami (ang. frames)

- podział dynamiczny- realizacja z wykorzystaniem struktur opisujących wolne bloki pamięci o różnych

długościach oraz mechanizm wymiatania.



wykorzystanie pamięci wirtualnej - istnieje jedna lub wiele wirtualnych przestrzeni adresowych
przydzielanych procesom użytkowym, a mających w niewielkim stopniu pokrycie w pamięci operacyjnej.

Zarządzanie PAO:



przemieszczanie procesów



ochrona zawartości pamięci



dostęp do obszarów dzielonych



organizacja fizyczna pamięci



organizacja logiczna pamięci

- adres logiczny – wytworzony przez procesor (adres wirtualny)
- adres fizyczny – umieszczony w rejestrze adresowym pamięci

Odwzorowanie adresów wirtualnych na fizyczne MMU (Memory Managment Unit – jednostka zarządzająca
pamięcią).

Przemieszczanie procesów:

opis

Ładowanie

dynamiczne



podprogram nie jest wprowadzany do pamięci dopóki nie zostanie wywołany



wszystkie podprogramy przechowywane są na dysku w postaci kodów przemieszczalnych (gotowe do załadowania)



podprogram sprawdza czy inny podprogram jest w pamięci (jeśli nie to używa programów łączących i ładujących
moduły przemieszczalne – wprowadzają do pamięci i uaktualniają tablicę adresów programu)

zalety:
+ lepsze wykorzystanie pamięci – nieużywany program nigdy nie zostanie załadowany
+ użyteczne kiedy od czasu do czasu trzeba wykonać duże fragmenty kodu (np. podprogram obsługi błędów)
+ nie wymaga specjalnego wsparcia ze strony systemu operacyjnego – użytkownicy są odpowiedzialni za odpowiednie

projektowanie programów

Wymiana

(swapping)



proces może być tymczasowo odesłany z pamięci operacyjnej do pamięci pomocniczej (po pewnym czasie może być
sprowadzony z powrotem)



wymagana pamięć pomocnicza – na ogół szybki dysk (pojemny, umożliwiający bezpośredni dostęp do tych adresów
pamięci)



wtaczanie i wytaczanie = proces o niższym priorytecie odsyłany z pamięci, by proces o wyższym priorytecie mógł być
załadowany i wykonany (algorytmy planowania priorytetowego)



czas przesłania proporcjonalny do ilości wymienianej pamięci (główna składowa czasu wymiany)



obecnie standardowa wymiana stosowana jest rzadko (zamiast tego stronicowanie)



jest wiele zmodyfikowanych wersji swappingu w różnych SO

nakładki



przechowywanie w pamięci tylko tych rozkazów i danych, które są stale potrzebne



inne wprowadzane w miarę zapotrzebowania, na miejsce zajmowane przez zbyteczne rozkazy i dane

zalety:
+ można uruchomić proces o rozmiarze większym od przydzielonej mu pamięci
+ mogą być w całości implementowane przez użytkownika, ale projektowanie i programowanie nakładek jest

skomplikowane – obecnie dość ograniczone w użyciu

+ nie wymagają wsparcia ze strony SO

Przydział

ciągły



procesy zawierają różną wielkość



przydział ciągły = blok za blokiem



pamięć poszatkowana = szachownica



problem – gdzie umieścić procedury?

Ochrona:
Kontrola dostępu programów, procesów i użytkowników do zasobów zdefiniowanych przez system
komputerowy.
- środki specyfikujące rodzaje wymaganej ochrony (polityka)
- środki ich wymuszenia (mechanizmu)
- miarą zaufania do systemu – ochrona i bezpieczeństwo
- kontrolowanie dostępu do programów, procesów lub użytkowników
- proces ma dostęp tylko do tych zasobów, do których został uprawniony
- ochrona kodu i danych SO przed procesami usera/ procesów wzajemnie przed sobą = rejestr graniczny i

rejestr przemieszczenia

- rejestr przemieszczenia = wartość najmniejszego adresu fizycznego
- rejestr graniczny = górny zakres adresów logicznych

Dynamiczny przydział pamięci



jak na podstawie listy wolnych dziur spełnić zamówienie na obszar o rozmiarze n?

Pierwsze dopasowanie

(First-Fit)

Najlepsze dopasowanie

(Best-Fit)

Najgorsze dopasowanie

(Worst-Fit)

- dziury uporządkowane malejąco pod

względem adresów bazowych

- szukamy najmniejszej dziury (są

uporządkowane rosnąco) do której

- uporządkowane malejąco
- segment umieszczamy w pierwszej

- szukamy najmniejszej dziury s<=xi
- po pewnym czasie wszystkie adresy małych

dziur będą na początku listy



przydziela się 1-wszą dziurę o
wystarczającej wielkości



wyszukiwanie od początku wykazu dziur
lub miejsca ostatniego wyszukiwania



dziury posortowane względem adresu



najszybsza

zmieści się nasz segment



przydział najmniejszej z pasujących
dziur



najmniejsze pozostałości kosztem
przeszukiwania całej listy



dziury posortowane względem
rozmiaru

dziurze, a pozostałe miejsce tworzy
nową dziurę



przydział największej dziury



wymaga przeszukiwania całej listy



czasami bardziej przydatne niż wiele
rozproszonych, małych dziur



duże zużycie czasu i pamięci

W pamięci występuje fragmentacja zewnętrzna - trzeba tak ułożyć dziury, żeby wszystkie małe tworzyły jedną
dużą (ale spada wydajność systemu). Rozwiązaniem segmentacja i stronicowanie.

segmentacja

stronicowanie

Schemat zarządzania pamięcią ukazujący sposób
widzenia pamięci przez użytkownika



przestrzeń adresów logicznych jest zbiorem
segmentów



segment = jednostka logiczna, np. program
główny, procedura, metoda



numeracja segmentów = łatwiejsza
implementacja



adres logiczny: <nr_segmentu, odległośc>



tablica segmentów (odwzorowanie 2-
wymiarowych adresów logicznych w 1-
dnowymiarowe fizyczne; każda pozycja = baza
segmentu (początkowy adres segmentu w
pamięci) + granica segmentu (jego długość);
przechowywana w pamięci )



czas dostępu do pamięci logicznej 2-krotnie
większy od dostępu do fizycznej; metody
zmniejszania tego czasu:

- liczba segmentów musi być

ograniczona (można wykorzystać
szybszą pamięć asocjacyjną – rejestry)

- wykorzystanie tablicy podręcznej

segmentu (informacje o ostatnim
zachowaniu segmentu (szybszy dostęp
niż do tablicy segmentu))



inne rozwiązanie problemu segmentacji zewnętrznej



przydział procesowi dowolnych dostępnych miejsc pamięci fizycznej ale
ustalonymi porcjami (dopuszczenie nieciągłości logicznej przestrzeni
adresowej)



pamięć fizyczna podzielona na równe bloki (ramki; rozmiar od 512 B)



pamięć logiczna podzielona na bloki takiego samego rozmiaru (strony)



system utrzymuje info o wolnych i przydzielonych ramkach (tablica ramek)
i do jakiego procesu są przydzielone



strony działającego procesu obecne w pamięci pomocniczej wprowadza
się do wolnych ramek PAO (n stron wymaga n ramek, porozrzucanych w
różnych miejscach PAO)



brak fragmentacji zewnętrznej kosztem fragmentacji wewnętrznej
(ostatnia strona nie jest w 100% zapełniona)



adres logiczny generowany przez procesor zawiera:

- numer strony s (index w tablicy stron)
- odległości na stronie o (o + adres bazowy = adres fizyczny

pamięci, wysyłany do jednostki pamięci)



rozmiar ramki = rozmiar strony



strony lądują do dowolnych ramek



dla procesu pamięć logiczna = spójny adres (gdy podział na strony, to
bardziej znaczące bity = strona, mniej = przesunięcie)



stronicowanie hierarchiczne – we współczesnych systemach
komputerowych (np. 2-poziomowe – tablica stron podzielona na strony)



duże strony = wzrost fragmentacji wewnętrznej, małe strony = wzrost
rozmiaru tablicy stron (mniejsza fragmentacja wewnętrzna)



cel: logiczny podział przestrzeni adresów



rozmiar segmentów różny



podział adresu programu na nr segmentu i bajtu
jest logiczny (przekroczenie zakresu nr bajtu nie
ma żadnego wpływu na nr. segmentu)



cel: fizyczny podział pamięci



identyczny rozmiar stron



podział adresu programu na nr stron i bajtu na stronie wykonywany
środkami sprzętowymi (przekroczenie zakresu = zwiększenie numeru
strony)

Pamięć wirtualna



umożliwia wykonywanie procesów nie przechowywanych w całości w PAO



abstrakcyjna pamięć główna (jednolita tablica, odseparowanie pamięci fizycznej i logicznej)



logiczna przestrzeń adresowa może być większa od fizycznej



możliwe wykonanie programu, który tylko w części jest w pamięci fizycznej



większa wieloprogramowość (więcej procesów wykonywanych w tym samym czasie – lepsze wykorzystanie
procka i przepustowości)



wydajne tworzenie i wymiana procesów



ułatwia programowanie



implementowania w formie stronicowania na żądanie (procesy podzielone na strony są w pamięci
pomocniczej i sprowadzane do PAO) i segmentacji na żądanie

20. Mechanizmy komunikacji międzyprocesowej IPC (Inter Process Communication).

Mechanizmy IPC (ang. Inter process communication) to grupa mechanizmów komunikacji i synchronizacji
procesów działających w ramach tego samego SO

Mechanizmy IPC obejmują:



Kolejki komunikatów (przekazywanie określonych porcji danych)



Pamięć współdzieloną (współdzielenie kilku procesom tego samego fragmentu wirtualnej przestrzeni
adresowej)



Semafory (synchronizacja procesów w dostępie do współdzielonych zasobów np. pamięci współdzielonej)

Mechanizmy IPC:



Część jądra systemowego (komunikacja przetwarzana w kontekście jądra – synchronizacja kosztem
wydajności – każda operacja IPC wymaga przełączenia kontekstu, spory narzut czasu; niezawodność –
atomowość operacji: niedopuszczenie do kolizji w dostępie czy wyścigu)



Może odnosić się do komunikacji w 1 SO, klastrze czy systemami odległymi (używa się wtedy numery
portów lub unikalnych nazw -RPC)



Polega na budowaniu w pamięci/nośnikach dynamicznych struktur (przesyłanie komunikatów
międzyprocesowych np. stan wątków)



Nie posiada sztywnej specyfikacji (SO posiada semafory, które można wykorzystać w aplikacji)



Wszystkie urządzenia IPC posiadają podobny interfejs (mechanizmy)



Najważniejszą wspólną cechą jest klucz urządzenia IPC



Klucz = liczba do identyfikacji obiektów IPC, umożliwiają wspólne użycie zasobów IPC przez kilka
niespokrewnionych procesów



Klucze różnych obiektów nie mogą się powtarzać



Do znajdowania unikalnego klucza zależnego od ścieżki pliku służy funkcja fork()



Użycie: rozbudowane wielowątkowe aplikacje (bazy danych, serwery WWW, serwery aplikacyjne…)

nazwa

opis

Piki i blokady



Najprostsza i najstarsza forma IPC



Pliki – nie stosuje się do komunikacji procesów współbieżnych (czytelnik może wyprzedzić pisarza –
rozwiązaniem łącza komunikacyjne)

sygnały



Przerwania programowe (DOS)

semafory



Używane do kontroli dostępu do zasobów systemu dzielonych przez kilka procesów (kontrola czasowa)



Implementowany w jądrze, procesy otrzymują id semafora (możliwość odwołania)



Problem synchronizacji czasowej – alternatywą rejony krytyczne i monitory (dla każdego języka
programowania)

Łącze

nienazwane

(komunikacyjne)



Nie są plikami ale mają swój i-węzeł; brak dowiązania



Uśpienie nadgorliwego pisarza, oczekiwanie nad-ambitnego czytelnika



Komunikacja tylko w 1 stronę (też łącza nazwane)



Łącza do których dostęp mają tylko procesy pokrewne (proces + potomkowie)



Potomkowie dziedziczą deskryptory plików, łącza nienazwane oparte są na deskryptorach



Jądro systemu na żądanie procesu tworzy łącze bez nazwy i umieszcza jego deskryptor w tablicy deskryptorów
plików otwartych w procesie (korzysta najpierw proces, potem potomkowie)



Gdy zrealizowany ostatni proces – zamknięcie łącza



powolne

Łącza nazwane



Wykorzystują FIFO



Łączą cechy pliku i łączy (1-kierunkowy przepływ danych)



Identyfikowane przez nazwę



Procesy niespokrewnione mogą przesyłać między sobą dane



Łącze to ma dowiązanie do systemu plików (istnieje w systemie jako plik w jakimś katalogu)



Pozostaje w systemie nawet po zakończeniu ostatniego używającego je procesu



powolne

Kolejki

komunikatów



niewielka liczba danych



stała/zmienna długość komunikatu



operacje nadaj/odbierz



procesy z uprawnieniami mogą pobierać komunikaty z tej kolejki



Komunikacja między procesami



Komunikaty umieszczone są w kolejce FIFO



Gdy komunikat pobrany przez odbiorcę – usuwany z kolejki

Pamięć dzielona

(segmenty

pamięci

dzielonej)



Obszar pamięci dzielony między kilkoma procesami



Dane umieszczane przez proces w segmentach (obszar adresowy procesu wywołującego)



Może z nich korzystać wiele procesów



Najszybszy rodzaj komunikacji między procesami



Komunikacja = obszar pamięci przydzielany kilku procesom (od razu procesy mogą korzystać z danych)

Gniazda



Wykorzystywane do komunikacji przez sieć (komunikacja międzyprocesowa)



Możliwość komunikacji dwukierunkowej (przesyłanie i odbiór danych)



Pojęcie abstrakcyjne (2-kierunkowy punkt końcowy połączenia)



Właściwości: posiadają typ (sposób wymiany danych), lokalny adres (adres IP – węzeł w sieci), port
(opcjonalnie; określa proces w węźle)



Komunikacja w obrębie 1-ego systemu (gniazda dziedziny Uniksa)



Komunikacja w wielu systemach

RPC



komunikacja w wielu systemach



protokół zdalnego wywoływania procedur



obsługiwany w bibliotekach języka Java



potrzebny:

- serwer (program z usługami, nasłuchujący na wybranym porcie czy ktoś się nie łączy)
- klient (program korzystający z usług serwera, łączność przez sieć)

21. Układy elektroniczne jako filtry. Klasyfikacja i przykłady zastosowań.

Kilka prawd ogólnych:



Urządzenie elektroniczne zasilane często z sieci energetycznej (zasilacze – transformacja napięcia 230 V
użyteczne 12V, które jest prostowane za pomocą prostownika dwupołówkowego – przebieg tętniący; gdy
podłączymy równolegle kondensator o odpowiedniej pojemności = zmniejszenie amplitudy tętnień =
proces filtrowania; im większa pojemność kondensatora, tym przebieg napięcia wyjściowego bardziej
przypomina przebieg stały)



Duże natężenie prądu = stosuje się cewki włączone szeregowo z odbiornikiem (tzw. dławnikiem) (zmiana
prądu w cewce = wygładzanie napięcia; powstaje napięcie przeciwdziałające zmianom)

Filtr



Fragment obwodu elektronicznego



Przepuszcza lub blokuje sygnały o określonym zakresie częstotliwości/zawierającego określone
harmoniczne



Podział filtrów – przeznaczenie:

- Dolnoprzepustowe
- Górnoprzepustowe
- Środkowoprzepustowe
- środkowozaporowe



podział filtrów – konstrukcja i rodzaj działania:

- pasywne
- aktywne



podział filtrów – typ obwodów (niewielkie różnice na poziomie konstrukcyjnym):

- analogowe
- cyfrowe (DSP – cyfrowe przetwarzanie sygnałów, ciągi liczb; użyte te same prawa co analogowe)

Typ filtru

opis

rysunek

pasywny



brak elementów dostarczających energii do obwodu drgającego



nie wnosi wzmocnienia, jedynie tłumi (zmniejsza) napięcie wejściowe



zawierają tylko pasywne elementy RLC (jedno i wielostopniowe)



można uzyskać wiele typów filtrów (połączenie elementów RLC)



często wykonany z materiałów piezoelektrycznych z odpowiednio napylonymi
elektrodami



analiza układu w dziedzinie częstotliwości - graficzna reprezentacja =charakterystyka
amplitudo-częstotliwościowa (tłumienie sygnału w zależności od częstotliwości;
skala logarytmiczna)



czas dojścia do stanu ustalonego: =RC



szeroko stosowany w elektronice



przykłady:

- filtr dolnoprzepustowy - kondensator o dużej pojemności połączony równolegle

do filtrowanego napięcia + ew. szeregowy opornik - > filtrowanie napięcia
(przebieg stały)

o dla dużych częstotliwości tłumienie układu, dla małych napięcie

wyjściowe równe wejściowemu (pasmo przepustowe i zaporowe)

- filtr górnoprzepustowy – do filtrowanego napięcia podłączenie kondensatora

szeregowo i opornika równolegle (odwrotnie niż w dolnoprzepustowym)

o odwrotnie niż w dolnoprzepustowym



dla dolno i górnoprzepustowego

- graniczna częstotliwość filtra : fs=1/(2 RC)
- charakterystyka amplitudowa w paśmie tłumienia: opadanie o 20db/dekadę



częstotliwość graniczna – między pasmem przepustowym, a zaporowym

- napięcie wyjściowe jest mniejsze o 3 dB dla częstotliwości z zakresu pasma

przepustowego

- dla prostych filtrów 1-nioogniowych RC i RL poszukuje się częstotliwości, żeby

amplituda napięcia wyjściowego stanowiła 0,7 wejściowego (-3 dB)

- pasmo przepustowe = zakres częstotliwości, w którym układ cechuje się

wzmocnieniem (albo brakiem tłumienia)



jeśli natężenie prądu duże = cewki łączone szeregowo z odbiornikiem (LC)



w zależności od podłączenia L i C można uzyskać:

- filtr środkowoprzepustowy (strojenie radiowych odbiorników AM)
- filtr środkowo zaporowy (tłumienie niepożądanego pasma częstotliwości)



wszystkie charakterystyki filtrów można uzyskać poprzez szeregowe/równoległe
połączenie kilku filtrów, jednakże:

- tłumienie sygnałów poza pasmem przenoszenia zbyt małe
- kaskadowe połączenie kilku filtrów = znaczne tłumienie amplitudy (też w paśmie

przenoszenia)

- lepiej zastosować filtr aktywny

Charakterystyka filtra

dolnoprzepustowego RC

aktywny



elementy RLC + elementy sterujące i dostarczające energię do filtrowanego układu
(wzmacniacze, układy nieliniowe)



składa się z szerokopasmowego wzmacniacza (operacyjnego) i członu sprzężenia
zwrotnego



przykłady:

- filtr dolnoprzepustowy
- filtr górnoprzepustowy
- filtr środkowo-przepustowy
- filtr środkowo-zaporowy
- filtry multiple feedback (struktury realizacji elektronicznej filtru)
- Czybyszewa, Butterwortha …



Filtr dolnoprzepustowy – ma pasmo przepustowe od strony niskich częstotliwości i

Przykład aktywnego filtru

górnoprzepustowego

(trójkąt = wzmacniacz

operacyjny)

zaporowe od wysokich



Filtr górnoprzepustowy – wzmocnione charakterystyki RC

- Wzmacniacz operacyjny = element aktywny (ma odrębne zasilanie i po części

dostarcza je do filtrowanego układu)



Filtr środkowo-przepustowy

- charakterystyka częstotliwościowa ostro obcięta po obu stronach



Lepsze tłumienie w paśmie tłumienia od pasywnych



Możliwość konstrukcji filtrów z użyciem techniki cyfrowej i sterowne
mikroprocesorowo

Dobroć filtru
- Stosunek częstotliwości środkowej filtru do jego szerokości pasma
- Gdy filtr ma większą szerokość pasma przenoszonego – określenie względnej szerokości pasma

(odwrotność dobroci, wyrażana w procentach częstotliwości środkowej)

22. Wzmacniacz operacyjny. Parametry charakterystyczne, zastosowania.

Wzmacniacz operacyjny



Analogowy układ scalony



Powszechnie traktowane jako wzmacniacze o sprzężeniach bezpośrednich i wejściu różnicowym



Typy wzmacniaczy:
- Z wejściami symetrycznymi
- Z wejściami asymetrycznymi



Zewnętrzny obwód sprzężenia zwrotnego = decydujący wpływ na ich sposób działania



Charakterystyka:

- Duża oporność wejściowa (różnicowa, jak też między poszczególnymi wejściami, a masą)
- Wielkie wzmocnienie przy otwartej pętli sprzężenia zwrotnego
- Mała oporność wyjściowa (zerowa dla idealnego wzmacniacza)
- Szerokie pasmo przenoszenia częstotliwości (ideał – nieskończenie szerokie)
- Znikome szumy
- Stabilność temperaturowa



Zasilany z zewnętrznego źródła napięcia (można pominąć na schemacie = czytelność), przeważnie stałym
napięciem symetrycznym (2 źródła napięcia: + i – względem masy)



Typowe wzmocnienia napięciowe: 3.000 do 1.000.000



Wzmacniacz operacyjny posiada 2 wejścia:

- Nieodwracające (+)
- Odwracające (-)



W zależności od tego, który potencjał będzie większy (na wejściu nieodwracającym czy odwracającym), taki
znak napięcia będzie na wyjściu



Niezależnie od konfiguracji pracy – ograniczony zakres zmian napięcia wyjściowego (nie większe od
napięcia zasilania)



Nasycenie = na wejście podane napięcie o wzmocnieniu przekraczającym zakres napięć zasilających, a
napięcie wyjściowe jest mu równe lub niewiele mniejsze; efekt niepożądany (zniekształcenia nieliniowe
sygnału)

Analiza działania wzmacniaczy opartych na WO:



Obwód wyjściowy wzmacniacza (z pętlą sprzężenia zwrotnego) stara się doprowadzić do zerowej różnicy
napięć między jego wejściami



Wejścia WO nie pobierają żadnego prądu z obwodów zewnętrznych

Zastosowania:



WO = punkt wyjścia dla analizy obwodów i producentów tych układów



Przykłady zastosowań:

- Wzmacniacz odwracający (odwrócona faza wyjściowa)
- Wzmacniacz nieodwracający (duża impedancja wejściowa)
- Wzmacniacz różnicowy

- Wzmacniacz sumujący
- Wzmacniacz różniczkujący
- Wzmacniacz całkujący
- Przesuwnik fazowy
- Komparator napięć (WO pracuje z otwartą pętlą wzmocnienia, przekazuje do wyjścia wzmocniony

sygnał)

o Różnica napięć na wejściach powoduje duże zmiany napięcia wyjściowego (ogromne

wzmocnienie WO)

o WO nasycony, napięcie wyjściowe ograniczone napięciem zasilania
o Napięcie niezrównoważenia – mimo, że napięcia wejściowe po zsumowaniu są równe 0, to

wyjściowe jest różne od 0; w celu wyzerowania wyjścia trzeba dać niewielkie napięcie na
wejście (miliwolty)

- Detektor przejścia przez 0 – sygnalizuje logiczną jedynką napięcie niższe od 0V podane na wejście

układu

- Detektor wartości szczytowej (kondensator w układzie zapamiętuje na dużej szczytową wartość

napięcia, szybko się ładuje prądem wyjściowym wzmacniacza, wolno rozładowuje)

- Ogranicznik amplitudy – ograniczanie amplitudy sygnału wyjściowego (napięcie wyjściowe nie osiągnie

wartości większej niż ustalona przez diody Zenera, wchodzące w skład układu)

- Filtry aktywne

Dodatkowe informacje:



Różnicowe wzmocnienie napięciowe Au – stosunek napięcia wyjściowego do różnicowego napięcia na
wejściu przy otwartej pętli sprzężenia zwrotnego.



Wejściowa rezystancja różnicowa RID – rezystancja występująca między wejściowymi zaciskami
wzmacniacza operacyjnego.



Rezystancja wyjściowa RO – rezystancja występująca między zaciskiem wyjściowym, a masą we
wzmacniaczu zrównoważonym z otwartą pętlą sprzężenia zwrotnego.



Częstotliwość graniczna fT – największa częstotliwość, przy której wzmocnienie różnicowe (pasmo
wzmocnienia jednostkowego) jest równe wzmocnieniu maksymalnemu (wzmocnieniu dla prądu stałego).

23. Bramki i funktory logiczne. Tabele prawdy. Minimalizacja funkcji.

Bramka logiczna



Element konstrukcyjny maszyn i mechanizmów (układ scalony)



Realizuje fizycznie pewną prostą funkcję logiczną (jej argumenty – zmienne logiczne - oraz wartości mogą
przyjmować 0 lub 1)



Podstawowe elementy logiczne (budujące układy logiczne, realizujące funkcje logiczne – wystarczą 2 z
wymienionych; tzw. układy zupełne)

- Suma (alternatywa, bramka OR)
- Iloczyn (koniunkcja, AND)
- Negacja (NOT)



Bramki funkcjonalnie pełne (można zbudować układ realizujący dowolną funkcję logiczną z samych
NANDów albo NORów)

- Negacja koniunkcji (NAND)
- Negacja sumy logicznej (NOR)



Bramka logiczna XOR stosowana w układach arytmetyki (sumatory, subtraktory)



Funktory logiczne rzadko występują pojedynczo, częściej tworzą złożone układy logiczne

Minimalizacja funkcji logicznych - przykład



Mam bramkę, która ma wejścia A,B i C oraz wyjście f, pytanie brzmi – jaką funkcje ona realizuje?

A

B

C

f

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

1

Metody minimalizacji funkcji logicznych:
- Metoda Karnaugh
- Metoda Quine’a-McCluskey’a
- Metoda iteracyjnego konsensusu
- Metoda espresso

Metoda Karnaugh – zasady (siatki, stany):



Tworzymy siatki o takim rozmiarze, by ilość opisujących je zmiennych była równa liczbie sygnałów
wejściowych



Tworzymy tyle siatek, ile układ posiada wyjść

Kanoniczna suma (dysjunkcyjna postać kanoniczna, AKPN):

f=~ABC+A~B~C+A~BC+AB~C+ABC // odczytuje argumenty dla wartości 1

Postać kanoniczna iloczynu (koniunkcyjna postać kanoniczna, KAPN)

f=(A+B+C)(A+B+~C)(A+~B+C)

// odczytuje te pola gdzie f = 0 i odwrotnie

UWAGA

F = ABC + AB~C = (AB)(C+~C)=AB



Wewnątrz kratek danej siatki wpisujemy stany wewnętrzne, jakie mają pojawiać się na danym wyjściu przy
odpowiadającej im kombinacji sygnałów wejściowych opisujących siatkę

Zasady zakreślania jedynek:
- Ilość zakreślonych w grupie kratek musi być wielokrotnością 2

k

, k=0,1,2,3…

- Zakreślona grupa musi być symetryczna względem którejś z głównych (bądź podgłównych) osi siatki
- Możliwość „sklejania” skrajnych wartości
- Tworzymy implikanty/implicenty o jak największej ilości jedynek/zer (przy zachowaniu 1-ego warunku); im

więcej kratek, tym mniej zmiennych

-

Tworzenie funkcji logicznej na podstawie stanów z siatki Karnaugh:



Zakodowane stany zakreślamy w grupy (np. same jedynki – suma iloczynów; gdy same 0 – iloczyn sum)



Odczyt funkcji wyjściowej

- należy popatrzeć na współrzędne zakreślonej grupy
- do wyrażenia iloczynowego wchodzą tylko zmienne niezmieniające się w obrębie grupy
- każda zakreślona grupa jedynkowa (tzw. implikant; grupy zerowe - implicent) jest 1-nym iloczynem w

postaci kanonicznej

Metoda Karnaugh – przykład:
a) ~ (p^qv~r^p)

p

q

r

~r

p^q

~r^p

p^qv~r^p

f

0

0

0

1

0

0

0

1

0

0

1

0

0

0

0

1

0

1

0

1

0

0

0

1

0

1

1

0

0

0

0

1

1

0

0

1

0

1

1

0

1

0

1

0

0

0

0

1

1

1

0

1

1

1

1

0

1

1

1

0

1

1

1

0



Postać AKPN: ~p~q~r+~p~qr+~pq~r+~pqr+p~qr



Z postaci AKPN należy zrobić tabele Karnaugh

- Należy użyć kodu greja dla argumentów
- Jeśli wyraz wystąpi to daj 1, jak nie to 0



Tabela Karnaugh:

pq\r

0

1

00

1

1

01

1

1

11

0

0

10

0

1



W tabeli Karaugh zaznaczamy maksymalnie duży prostokąt możliwy do stworzenia i funkcje sklejone:

pq\r

0

1

00

1

1

01

1

1

11

0

0

10

0

1



Na podstawie odpowiednio zaznaczonych prostokątów z tabeli odczytuję argumenty (argumenty muszą
być niezmienne):

Y(p,q,r) = ~p + ~qr

24. Układy sekwencyjne. Przykłady realizacji i obszary zastosowań.

Układ sekwencyjny:



Jednym z rodzajów układów cyfrowych (obok układów kombinacyjnych)



Stan wyjść zależy od stanu wejść i stanu poprzedniego (stanu wewnętrznego; zapamiętanego w rejestrach)



Stan stabilny = stan wewnętrzny nie ulega zmianie pod wpływem dania różnych sygnałów wejściowych



Może być opisany za pomocą 2-óch funkcji (A-stan wewnętrzny, X – wejście, Y - wyjście):

- Y = f(X,A) <- wyjście zależy od stanu wewnętrznego i wejść; automat Mealy’ego
- Y = f(A) <- wyjście zależy wyłącznie od stanu wewnętrznego; automat Moore’a



Opis układu sekwencyjnego:
- Słowny
- Przebieg czasowy (zależności czasowe między X i Y)
- Grafy przejść (zależy od rozpatrywanego automatu)
- Tablice przejść i wyjść

Typy układów sekwencyjnych

asynchroniczne

synchroniczne



Zmiana sygnałów wejściowych X powoduje natychmiastową
zmianę wyjść



Założenie: jednoczesna zmiana kilku sygnałów jest
niemożliwa



Budowane z przerzutników lub ze sprzężenia zwrotnego

+ Szybkie układy
- Podatność na hazard
- Wyścig (co najmniej 2 sygnały wejściowe zmieniają swój

stan w 1 chwili czasu; w praktyce niezerowy czas
przerzucania bramek i przerzutników – zmiana 1 sygnału
może być wcześniej; skutkuje w trudnych do wykrycia
błędach)



Zmiana wewnętrznego stanu (i wartości wyjściowej)
następuje wyłącznie w chwilach wyznaczonych przez sygnał
zegarowy clock



Posiada wejście zegarowe (clock, clk lub c)



Nawet, gdy stan wejść się nie zmienia, to stan wewnętrzny
może ulec zmianie (w kolejnych taktach zegara)



W automacie Moore’a wyjście układu jest funkcją stanu
wewnętrznego – możliwość zmiany jedynie w chwili
nadejścia taktu (gwarancja utrzymania się stanu wyjść przez
cały takt)



Automat Mealy’ego – zmiana wyjścia układu może nastąpić
też w momencie zmiany wejścia



Układ statyczny (wyzwalany poziomem) = reaguje na
określony stan logiczny zegara



Układ dynamiczny (wyzwalany zboczem) = reakcja na zmianę
sygnału zegarowego (wyzwalane zboczem narastającym
/opadającym / impulsem)



Układ autonomiczny = brak wejść, jedynie charakteryzuje go
stan wewnętrzny (liczniki stosowane w zegarkach
elektronicznych)

Przykłady:



Przerzutniki – układ z 2-ma stanami wyróżnionymi równowagi trwałej; przy przejściu z 1 stanu do 2 trzeba
doprowadzić sygnał zewnętrzny wyzwalający krótkotrwały proces generacji
- Bez sygnałów wejściowych zachowuje swój stan
- Ma 2 dopełniające się wzajemnie wyjścia: Q i ~Q

o Przerzutnik RS (syn i asyn; z bramek OR/NAND, ma stany niedozwolone – na wejściach nie

mogą być jednocześnie jedynki)

o JK (rozwinięty RS, brak stanów niedozwolonych; synchroniczny)
o D (synchroniczny; ma 1 wejście, przepisuje informacje z wejścia D do wyjścia Q z opóźnieniem

1 impulsu taktującego)



Rejestr = układ pamiętający (PI = wejście równoległe, SI – wejście szeregowe itd)

- Równoległe (PIPO)
- Przesuwne (SISO, SIPO, PISO)
- Zastosowanie przesuwne



Licznik

- Rewersyjny (liczy w przód i tył)

25. Sumator równoległy. Sumator a jednostka arytmetyczno- logiczna.

Sumator



Układ kombinacyjny



Wykonuje operację dodawania 2 lub więcej liczb dwójkowych

Sumator równoległy



wielopozycyjne



Jednocześnie dodaje bity ze wszystkich pozycji



Przeniesienie realizowane w zależności od połączenia sumatorów jednobitowych

Sumator równoległy – podział ze względu na sposób wytwarzania przeniesień:



Sumatory z przeniesieniem szeregowym (sumatory kaskadowe/iteracyjne)



Sumatory z przeniesieniem równoległym

Sumator kaskadowy n-bitowy

Sumator z przeniesieniem równoległym



Układ powstały przez połączenie n sumatorów 1-bitowych



Przy sumowaniu liczb dodatnich wejście przeniesienia
początkowego C0 nie jest wykorzystywane (C0=0)



Wszystkie cyfry dodawanych liczb 2-kowych podawane są
na sumator jednocześnie



Czas uformowania się wyniku zależy od prędkości propagacji
sygnału przeniesienia przez kolejne komórki sumatora



Najgorszy przypadek – sygnał C musi przejść przez wszystkie
komórki sumatora



Generuje wszystkie wartości przeniesień jednocześnie na
podstawie wartości na poszczególnych bitach obu operandów



Przy wzroście bitów przewaga nad sumatorem kaskadowym
(mniejszy czas, szybszy o 20-40%)



Zbudowany jest

o z bloków wyznaczających sumę Si + grupy generacyjne gi i

propagacyjne pi (liczone niezależnie)

o z bloku generującego przeniesienia (zgodnie z

rozwiniętymi wyrażeniami)



w praktyce – buduje się 4-bitowe sumatory tego typu

Jednostka arytmetyczno-logiczna



Proste operacje na liczbach całkowitych

- Operacje logiczne
- Dodawanie/odejmowanie
- Przesunięcie bitowe
- Czasem mnożenie i dzielenie modulo



Wykorzystywany często jako sumator (w rzeczywistości układ ten realizuje wiele innych funkcji – np.
porównywanie wartości bezwzględnych liczb)



Sumatory i ALU wykonują funkcje arytmetyczne w czasie od pojedynczych nanosekund do dziesiątków
nanosekund (sumator = układ arytmetyczny, możliwość wyboru funkcji; ALU = arytmetyczny + logiczny)

26. Budowa i zasada działania procesorów: potokowy, wektorowy, CISC, RISC.

typ

opis

RISC



stosunkowo niewiele rozkazów wykonywanych w pojedynczym cyklu rozkazowym,



stosunkowo niewiele trybów adresowania,



łatwe do zdekodowania, stałej długości formaty rozkazów



dostęp do pamięci ograniczony do rozkazów LOAD i STORE



stosunkowo obszerny zbiór uniwersalnych rejestrów



rozkazy działające zazwyczaj na argumentach zapisanych w rejestrach, a nie w PAO



układowo zrealizowana jednostka sterująca

to co jest unikalne w tych procesorach:



intensywne wykorzystanie przetwarzania potokowego, w tym potokowe wykonywanie rozkazów



kompilatory o dużych możliwościach optymalizacji kodu wykorzystujące architekturę potokową,



skompilowane funkcje zaimplementowane częściej programowo niż sprzętowo.

CISC



występowanie złożonych, specjalistycznych rozkazów (instrukcji) - do wykonania wymagają od kilku do kilkunastu cykli
zegara



szeroka gama trybów adresowania,



przeciwne niż w architekturze RISC rozkazy mogą operować bezpośrednio na pamięci (zamiast przesyłania wartości do
rejestrów i operowania na nich)



powyższe założenia powodują iż dekoder rozkazów jest skomplikowany



pojedynczy rozkaz mikroprocesora wykonuje kilka operacji niskiego poziomu (pobranie z pamięci, operacja
arytmetyczna, zapis do pamięci)

Wektorowy



w przeciwieństwie do skalarnego pozwala na przetwarzanie w pojedynczych cyklach całych wektorów danych



operandy instrukcji = wieloelementowe zbiory liczb (możliwość przyspieszenia obliczeń)



pracują na macierzy danych



koncepcja rejestru wektorowego (zbiór konwencjonalnych rejestrów, których wartości można załadować z pamięci 1-
nym rozkazem



stosowane we współczesnych superkomputerach

Potokowy



jedno z najlepszych rozwiązań



wcześniej: procesor jednocześnie pracował tylko nad 1 instrukcją = niska wydajność (tylko 1 jednostka procesora
zajmowała się działaniem, pozostałe elementy CPU oczekiwały lub nic nie robiły)



teraz: niepracujące jednostki i bloki procesora przetwarzają jednocześnie inne instrukcje



podział logiki procesora – wykonanie instrukcji - na wyspecjalizowane grupy; każda z grup wykonuje część pracy
związanej z rozkazem



grupy – połączenie sekwencyjne, praca równoległa (pobierają dane od poprzedniego elementu z sekwencji)



potok wykonawczy (ścieżka przetwarzania instrukcji wewnątrz procesora) = podział procesu wykonania instrukcji na
oddzielne, logiczne etapy



każdy etap wykonywany niezależnie na określonym stopniu potoku (1 takt zegara)



po pobraniu z pamięci instrukcja (1 po 2) przemieszczają się w potoku wykonawczym (przechodzenie przez kolejne
stopnie)



możliwość jednoczesnej pracy układów RISC nad wieloma instrukcjami (np. jednoczesne wczytywanie i zapis do
rejestru)



możliwość jednoczesnego wykorzystanie wszystkich bloków procesora (możliwość rozpoczęcia przetwarzania
kolejnych rozkazów przed zakończeniem wcześniejszych instrukcji)



po wykonaniu rozkazu w jednostce wykonawczej ma przygotowaną i oczekującą kolejną instrukcję (w przetwarzaniu
prostym trzeba było pobierać wszystko od nowa)



wzrost wydajności, przyspieszenie wykonywanych instrukcji



problem: rozkazy skoku (konieczność przeczyszczania całego potoku i wycofania rozkazów które nastąpiły zaraz po
instrukcji skoku; napełnianie potoku od początku do nowego adresu) – możliwość opóźnień (zależy od długości
potoku)



istnieją pewne metody przewidywania rozgałęzień (np. tablica historii czy przełącznik)



inny problem: różne czasy trwania 1-nych etapów powodują czekanie innych



postać rozkazu: pobranie, dekodowanie (określenie kodu operacji), obliczanie argumentów, pobranie argumentów,
wykonanie rozkazu i zapis argumentu (wyniku do pamięci)

27. Klasyfikacja architektur komputerowych.

Taksonomia Flynna



klasyfikacja architektur komputerowych, opierająca się na liczbie przetwarzanych strumieni danych i
strumieni rozkazów



wyróżnia się 4 grupy

nazwa

opis

SISD

(single

instruction,

single data)



1 wykonywany program = 1 strumień danych



Klasyczny komputer sekwencyjny (1 procesor + 1 blok PAO)



Ciąg instrukcji wykonywany sekwencyjnie, ale może zawierać elementy równoległości (przetwarzanie
potokowe)



Komputer z kilku procesorów wykonujących niezależnie od siebie programy = zestaw komputerów SISD



Komputery skalarne (sekwencyjne)



architektura von Neumanna

SIMD

(single

instruction,

multiple data)



1 program = wiele strumieni danych



1 wspólny układ sterowania dla wielu rozkazów



Procesory przetwarzają równolegle te same instrukcje dla różnych danych (kolejne instrukcje = pojedynczy
strumień)



Brak możliwości realizacji różnych instrukcji równolegle



Odpowiedni dla obliczeń równoległych z modelem równoległości danych (wymagana częsta synchronizacja)



Komputery wektorowe

MISD



Wiele równoległych programów = 1 wspólny strumień danych (architektura przetwarzania równoległo)



Odpowiednik: przetwarzanie potokowe(poszczególne instrukcje cząstkowe = te same dane)



Zastosowanie: systemy z redundancją (wielokrotne wykorzystanie tych samych obliczeń) = minimalizacja
błędów

MIMD



Wiele równoległych programów = każdy przetwarza własne strumienie danych



Oddzielne jednostki sterujące dla każdego z elementów przetwarzających



Możliwość realizacji instrukcji z różnych strumieni instrukcji dla różnych strumieni danych (w tym samym
czasie)



Możliwe wykorzystanie równoległości danych



Np. komputery wielo[procesorowe, klastry, gridy

28. Systemy przerwań. Aspekty sprzętowe i programowe.

Przerwanie



Sygnał powodujący zmianę przepływu sterowania (niezależnie od wykowanego programu)



Powoduje wstrzymanie aktualnie wykonywanego programu i wykonanie przez procesor kodu procedury
obsługi przerwania



Charakter atomowy – przerwanie nie może przerwać innego przerwania blokowanie przerwań)



Jedno z udogodnień sprzętowych (wymagania, jakie musi spełnić sprzęt) dla SO

Typy przerwań

sprzętowe

programowe

zewnętrzne

wewnętrzne



Sygnał przerwania pochodzi z
zewnętrznego układu
obsługującego przerwania
sprzętowe



Przerwania te służą do komunikacji
z urządzeniami zewnętrznymi
(klawiatura itd.)



Informuje o zdarzeniach we/wy



Urządzenie generuje sygnał



Inaczej wyjątki



Zgłaszane przez procesor dla sygnalizowania
sytuacji wyjątkowych (dzielenie przez 0)



Dzielą się na 3 grupy:

- Faults – gdy instrukcja powoduje błąd; gdy

powrót do przerwanego kodu wykonuje tą
samą instrukcję wywołującą wyjątek

- Traps – nie jest błędem, cel: wykonanie

określonego kodu; debugery itd.; po



Z kodu programu wywoływana
jest procedura obsługi przerwania



Pułapka obsługiwana przez SO



Wykorzystywane do komunikacji z
SO



SO w momencie obsługi
przerwania umieszcza kod
wywołujący odpowiednie funkcje
systemowe do odpowiednich

przerwania



Procesor przerywa wykonanie
instrukcji (odkłada na stos) i
obsługuje przerwanie



Koniec przerwania = powrót do
wykonywanego ciągu instrukcji

powrocie do przerwanego kodu
wykonywana jest następna instrukcja

- Aborts = błędy, których nie można naprawić



Zajmują część pozycji w tablicy wektorów
przerwań (pozostałe numer dowolnie
wykorzystane)

rejestrów ustawionych przez
program wywołujący lub
oprogramowaniem wbudowanym
(BIOS itd.)

Inny podział:



Blokowane



Nieblokowane



maskowane

Przerwania wielokrotne (inne przerwanie w momencie obsługi innego)



obsługa sekwencyjna (2-gie przerwanie czeka na zakończenie obsługi 1-ego)



obsługa zagnieżdżona (nowe przerwanie jest obsługiwane a stare wstrzymane; po wykonaniu nowszego
powrót do starszego przerwania)



obsługa priorytetowa (przerwanie o wyższym priorytecie jest wykonywane, nawet gdy było już jakieś
obsługiwane)

Metody rozróżniania przerwania:



Odpytywanie – procedura obsługi przerwania pytanie się kolejno wszystkich urządzeń czy to one
spowodowały przerwanie



Wektor przerwań – tablica systemowa, w każdej komórce określony rodzaj przerwania (obsługa) wraz z
odpowiadającym mu kodem

29. Omówić podstawowe tryby adresowania.



Podział słowa rozkazu (format rozkazu wewnętrznego): pola i sposób ich dekodowania (wyróżnienie pola
kodu operacji i pola adresowego)



Pole kodu operacji = wiele pól, każde określa 1 element kodu operacji rozkazu (sama operacja);



Pole adresowe = pochodzenie argumentów operacji, przeznaczenie wyniku; zawiera adres PAO, nr rejestru
lub daną umieszczoną w rozkazie

- Zawartość pola adresowego rozkazu nie jest bezpośrednio użyta jako adres danej/rozkazu – procesor

wykonuje na nim tzw. operacje adresujące (przekształcają go zanim zostanie wykorzystana jako
ostateczny adres argumentu rozkazu)

- Tryb adresowania = rodzaj operacji, którą procesor wykonuje na zawartości pola adresowego

(określony w 1 lub kilku polach należących do pola kodu operacji rozkazu; niekiedy tryb adresowania
wynika wprost z kodu operacji rozkazu)

Tryby adresowania:

tryb

opis

Natychmiastowy



Pole adresowe -> bezpośredni argument (dana dla rozkazu)



Długość argumentu (operandu) zależy od kodu operacji + ewentualnie dodatkowego pola sterującego w
rozkazie



Stosujemy, gdy chcemy bezpośrednio z rozkazu załadować do rejestru prostą daną (bez odwołania do
pamięci; bajt lub parę bajtów

Adresowanie

bezpośrednie



Najbardziej podstawowy tryb adresowania



Zawartość pola adresowego = finalny adres argumentu rozkazu w PAO (nie podlega przekształceniu)



Stosujemy, gdy nie zależy nam na przesuwalności programu w PAO (wykonanie przy zapisie w ściśle
określonym miejscu w PAO)

Adresowanie

pośrednie



Rozkaz zawiera adres komórki PAO (w niej finalny adres operandu rozkazu)



Komórka pamięci wskazana przez adres rozkazu pośredniczy w określeniu finalnego adresu



Stosujemy, gdy chcemy, by finalny adres operandu mógł być dynamicznie wstawiony do komórki
pośredniczącej w adresowaniu w czasie wykonania programu (gdy adres zależy od jakichś testów w yniku
operacji poprzedzającego rozkazu)

Adresowanie

indeksowe



Inaczej: modyfikacja adresu przez indeksowanie



Rejestry indeksowe = specjalne indeksy procesora (zawierają przesunięcie)



Adres finalny operandu = adres istniejący w rozkazie + przesunięcie (rejestry indeksowe)



Pozwala przesunąć adres zawarty w rozkazie o wartości rejestru indeksowego



Jeśli użyty ten tryb we wszystkich rozkazach programu = możliwość wykonania programu przy załadowaniu w
dowolne miejsce pamięci (trzeba napisać program wstawiając do rozkazów programu adresy umieszczenia 1-
ej instrukcji programu pod adresem 0-wym w pamięci, a następnie umieszczamy go w rejestrze indeksowym)



Operacja indeksowania rozkazów programu = wszystkie adresy operandów przesunięte o tą samą wartość
(zawartość rejestru indeksowego = przesunięcie)



Dynamiczna realokacja programu w pamięci



Rejestrów indeksowych w procesorze jest wiele(możliwość przydzielania różnym programom lub ich
fragmentom)



Rejestr indeksowy może być określony przy pomocy specjalnego pola wspomagającego kodowanie trybu
adresowania w innym polu rozkazu (przydział fragmentu programu)

Adresowanie

względne



Polega na modyfikacji adresu zawartego w rozkazie przez aktualną zawartość licznika rozkazów



Dynamiczna przesuwalność adresów dostępu do danych (gdy nie znamy przesunięcia całości programu w
stosunku do adresu zerowego)



Finalny adres danej wyliczany względem bieżącej zawartości licznika rozkazów (do rozkazu wstawiamy
przesunięcie danej w programie względem adresu następnego rozkazu np. komórek w przód lub tył)



Dana musi być umieszczona w spodziewanym miejscu w pamięci (odległości od rozkazu wykorzystującego ją)
– planowanie odległości obszaru danych programu od rozkazu

Adresowanie

pośrednie

indeksowe



Jednoczesna możliwość zastosowania adresowania pośredniego z modyfikacją adresu odczytanego z komórki
pośredniczącej (poprzez zawartość rejestru indeksowego)



Umieszczony w rozkazie adres wskazuje na komórkę przechowującą adres danej (możliwość dynamicznego
wstawiania przez program; następnie stosuje się indeksowanie poprzez zawartość rejestru indeksowego;
podprogram też może wstawiać jej zawartość)



zawartość rejestru indeksowego -> komórka z operandem



jest 2-poziomowe = dynamiczne określanie adresu danych + metoda wpisania adresu bazowego (modyfikacja
przez rejestr indeksowy)

Adresowanie

indeksowe

pośrednie



najpierw modyfikacja adresu w rozkazie (zawartość rejestru indeksowego), potem stosowany do wskazania
komórki pamięci (w niej finalny adres operandu rozkazu)



możliwość dynamicznego określania adresów danych w programie (gdy wykonywany program); zapewnienie
przesuwalności w obrębie całego programu (program pisze się od adresu 0-ego w pamięci – adresowanie
indeksowe do wszystkich rozkazów poza tymi, które działają na danych wybieranych dynamicznie)



rozkazy adresujemy używając adresowania pośredniego indeksowego (umieszczając adres komórki
pośredniczącej – z wyjątkiem 0 – w bieżącym rozkazie)



załadowanie programu do pamięci = wpisanie do rejestru indeksowego wartości przesunięcia początku
programu w stosunku do adresu zerowego (program ładujący)



modyfikacja wszystkich adresów programu w trakcie jego wykonania

Adresowanie

rejestrowe



stosuje się gdy dana dla rozkazu jest w rejestrze



część adresowa rejestru = 1 lub więcej pól z identyfikatorami rejestrów



często stosowane w tym samym rozkazie z innymi trybami adresowania PAO (rozkaz PAO i rejestrów
procesora)

Adresowanie

rejestrowe

pośrednie



rejestr procesora o id umieszczonym w polu adresowym rozkazu = miejsce pobrania finalnego adresu
operandu rozkazu



możliwość dynamicznego określenia finalnego adresu operandu (odpowiednie załadowanie zawartości
rejestru w zależności od programu)

Adresowanie wewnętrznej pamięci danych (mikrokontrolery):

natychmiastowe

bezpośrednie

pośrednie

bitowe

rejestrowe

bezpośrednie

rejestrowe

względne



dane od razu



w pamięci nie ma
danych



dana jest za
kodem rozkazu



np.

mov A,#32H
(A)<-32H

adres bitu np.
mov C,ACC.7
(C)<-(ACC.7)

adres określony
na sztywny, po
rejestrach np.
mov A,R1
(A)<-(R1)



„prawdziwie”
bezpośrednie



Za kodem rozkazów
podajemy adres z
miejscem w pamięci z
wartością



Np.

Mov A,32H
(A)<-32H

W rejestrach
mamy zapisany
adres np.
Mov A,@R1
(A)<-((R5))

przesunięcie
względem
jakiegoś adresu

Dodatkowo asemblery umożliwiają adresowanie symboliczne i definicji bloków

30. Formaty i typy rozkazów procesora, wpływ długości rozkazów procesora na wielkość

zajmowanej pamięci przez program oraz na jego czas wykonania.

Rozkaz (instrukcja maszynowa)



Najprostsza operacja do wykonania przez procesor



Programowanie za pomocą rozkazów = asembler



Lista rozkazów



Kod rozkazu = rodzaj (kod) operacji + operandy (i/lub) adresy operandów operacji (łącznie z ewentualnymi
argumentami)

- Kod operacji – określony w początkowej części kodu rozkazu (1-wszy bajt/jty); określa, w jaki

sposób ma przebiegać dalsza realizacja rozkazu przez mikroprocesor



Opis działania rozkazu:

- Wykonaj skok
- Pobierz kod rozkazu z komórki pamięci o adresie równym etykiety

Grupy rozkazów z listy rozkazów:

przesłań

arytmetyczne i

logiczne

sterujące

pozostałe



Najczęstsze



Brak zmiany
informacji, ale
przenoszą ją z
miejsca na
miejsce



Przykład: MOV



Przetwarzanie
informacji



Informacja jest
zmieniana



Np. ADD (+), SUBB (-),
inkrementacja,
dekrementacja, SWAP



Zmiana kolejności
wykonywania instrukcji
programu (rozkazy skoku,
bezwarunkowe i
warunkowe wywołania
programów, instrukcje pętli
itd.)



Charakterystyczne dla danego typu
procesora



Sterowanie pracą koprocesora,
rozkazy sterujące, operacje w trybie
chronionym itd.



Podprogramy i operacje na stosie
(PUSH, POP…)

Lista rozkazów procesora:



wszystkie rozkazy jakie potrafi wykonać dany procesor



rozkazy – postać binarna + zapis symboliczny (czytelność; mnemonik (np. JMP) + argument)



mnemonik = skrót (rodzaj operacji rozkazu), skrót angielskiej nazwy

format rozkazu:



zawiera: sposób rozmieszczenia informacji w kodzie + jej długość



określa rozkład bitów rozkazu w odniesieniu do jego części składowych (zawiera kod operacji + adresy
argumentów)



w sposób jawny lub domyślny określa tryb adresowania każdego argumentu



występuje więcej niż 1 format rozkazów (większość procesorów)



format: kod rozkazu, mnemonik i argument (etykieta-kod-argumenty)

długość rozkazu



im mniejszy rozkaz, tym zajmuje mniej pamięci i może być szybciej wczytany



długi rozkaz = więcej informacji/dłuższe adresy



wielokrotność jednostki transferu (słowa) – możliwe wyjątki



słowo = wielokrotność długości znaku (gdy operacje na znakach brane pod uwagę, np. maszyny do obliczeń
numerycznych)

Sposób realizacji rozkazu



Nie jest istotny dla użytkownika



Wyznaczony przez projektanta mikroprocesora

31. Typy i hierarchia pamięci w systemie komputerowym.

Hierarchia pamięci (od najszybszej i najdroższej):



pamięć rejestru (pamięć najbliżej procesora),



pamięć kieszeniowa (podręczna lub cache)

- informacje przejściowe



pamięć operacyjna (pamięć RAM)

- obszar bezpośrednio dostępny dla procesora
- rozkazy LOAD/STORE (komunikacja z procesorem poprzez rejestry)
- cykl rozkazowy: pobranie rozkazu z PAO do rejestrów, dekodowanie, realizacja (ew. pobranie

argumentów)

- mała i ulotna (przechowujemy bajty)



pamięć pomocnicza 9trwałe przechowywanie danych)

- pamięć masowa (dyski)
- pamięć zewnętrzna (CD, taśmy)

Podział ze względu na trwałość zapisu

długoterminowe

krótkoterminowe



stałe - zapis nie ulega zniszczeniu po
wyłączeniu zasilania (ROM)



ulotne – zapis ulega zniszczeniu (PAO,
cache, rejestrowe…)



pamięć statyczna – układy przerzutnikowe bistabilne (zawartość dopóty jest
zasilanie; duża szybkość działania, duży pobór mocy, koszt, złożoność)



pamięć dynamiczna – dynamiczne układy pamiętające MOS (czynnik pamiętający
= tranzystor MOS; zanika szybko; zajmuje więcej miejsca, ale mniejszy pobór
mocy i koszta; mała szybkość działania)

Podział ze względu na dostęp do pamięci:



pamięć o dostępie swobodnym (RAM; dostęp przez adres, jednakowa szybkość dla wszystkich komórek
pamięci)



cyklicznym – dostęp co pewien czas (pamięć dyskowa)



sekwencyjnym – dostęp do kolejnych komórek odbywa się w pewnej stałej kolejności (pamięć taśmowa



pamięć asocjacyjna – dostęp w sposób kierowany wewnętrznymi adresami ustalającymi kolejność
przeszukiwania komórek

pamięć podręczna



cache – posiada: bank danych (pamięć danych), katalog pamięci cache i sterownika



3 główne typy:

- Pamięć podręczna całkowicie asocjacyjna
- Z odwzorowaniem bezpośrednim
- Wielodrożną pamięć podręczną

32. Omów metody projektowania baz danych.

Metody projektowania bazy danych:

Wstępująca

(bottom-up)

Zstępująca

(top-down)

Strategia mieszana



Od szczegółu do ogółu



Początek na podstawowym poziomie z
atrybutami (tworzenie aktorów, analiza fazy
wymagań, usecasy)



następnie analiza powiązań = łączenie ich w
encje i związki między nimi



proste bazy danych z małą liczbą atrybutów



od ogółu do szczegółu



integracja istniejących baz danych (bazy
rozproszone)



początek od stworzenia modeli danych z niewielką
liczbą ogólnych encji/atrybutów/związków



metoda kolejnych uściśleń = wprowadzenie
encji/związków/atrybutów niższego poziomu



projektowanie złożonych baz danych



łączy cechy
metody
wstępującej i
zstępującej

Do projektowania potrzebny jest opis w języku naturalnym, na podstawie którego wyodrębnia się encje,
atrybuty i zależności. Encje i atrybuty to rzeczowniki, zależności to czasowniki itd

Tabele w bazie danych buduje się według określonych norm, dzięki którym baza będzie spójna, czytelna, dane
nie będą zajmować zbędnego miejsca na dysku

Prosty przepis na poprawny projekt bazy danych:
1. określenie zawartości BD
2. grupowanie danych z 1-ego punktu w tabelę (jednoznaczna charakterystyka danego obiektu)
3. każda tabela ma klucz główny (2 postać normalna)
4. kolumna = dane atomowe (1 postać normalna)
5. eliminacja zależności przechodnich (wykluczenie kolumn o wartościach nie zależnych bezpośrednio od

klucza głównego, lecz innej kolumny – 3 postać normalna)

6. połączyć (w miarę możliwości) kolumny z 1 tabeli z kolumnami 2-ej tabeli w sposób jednoznaczny

(jednoznaczna identyfikacja wierszy)

Ogólniej:
1. szukamy obiektów odzwierciedlających w rzeczywistości
2. wiążemy obiekty
3. uściślamy, szukamy atrybutów …

33. Omów relacyjny model danych.

Relacyjny model danych oparty jest tylko na 1 podstawowej strukturze danych (relacje)
Relacja = tabela zbudowana wierszy i kolumn (przy przecięciu każdej kolumny z każdym wierszem – wartość)
Stosowany dla większości systemów zarządzania bazą danych

Założenia relacyjnego modelu danych:



BD = prostokątne tablice (określona liczba kolumn + dowolna liczba wierszy (krotek))



Tablice = relacje; każda tablica posiada unikalną nazwę



Elementy krotek są atomowe (niepodzielne) i są wartościami



Nie można

- Tworzyć wskaźników do innych krotek
- Tworzyć krotki ze zbiorem wartości (1 postać normalna)



Porządek krotek/kolumn nie ma znaczenia



Użytkownik nie widzi reprezentacji relacji/usprawnień dostępu do relacji



Atrybuty = nazwy kolumn; wiersze = wartości atrybutów (w encjach)



Klucz = wyróżniony atrybut lub grupa atrybutów należący/ca do danej relacji

- Wartość klucza = identyfikacja krotki relacji
- Integralność relacji = każda relacja musi posiadać klucz główny
- Inna identyfikacja krotki (wewnętrzny identyfikator) niewidoczne dla użytkownika



Manipulacja relacjami = operatory algebry relacji (makroskopowo; przetwarzanie „krotka po krotce”
niedozwolone)
- Rachunek normalizacyjny
- Teoria normalizacji
- Algebra relacji np. selekcja, projekcja, złączenie, produkt kartezjański, unia

34. Na czym polega proces normalizacji baz danych

Normalizacja bazy danych
•

Proces identyfikowania logicznych związków między elementami danych

•

Proces projektowania baz danych, który będzie identyfikować takie związki - bez anomalii

•

Proces, podczas którego schematy relacji posiadające niepożądane cechy są dekomponowane na mniejsze
schematy o pożądanych właściwościach

•

Nie usuwa danych, tylko zmienia schemat BD

•

Właściwości:

- Żaden atrybut nie może zostać zagubiony w trakcie procesu normalizacji
- Dekompozycja (podział atrybutów) tabeli nie może prowadzić do utraty informacji
- Wszystkie zależności funkcyjne muszą być reprezentowane w pojedynczych schematach tabel

•

Celem jest minimalizacja fizycznego rozmiaru BD i uniknięcie anomalii baz nieznormalizowanych

Anomalia baz danych nienormalizowanych:



anomalia dołączania – wstawienie informacji pozostawia puste pola w wierszach tabeli



anomalia aktualizacji – zmiana 1 atrybutu pociąga konieczność zmian w wielu wierszach



anomalia usuwania – niepożądane usunięcie innych danych przy usuwaniu jakiejś danej

W celu wykonania normalizacji danych potrzebujemy:
•

zrozumienia zależności funkcyjnej – głównie pomiędzy kolumnami

•

zdrowego rozsądku

•

zrozumienia znaczenia danych ( definicja wymagań)

•

zrozumienia oczekiwań zleceniodawcy w stosunku do bazy danych

•

znajomości procesu normalizacji

postacie normalne:

1-wsza

2-ga

3-cia



każda wartość atrybutu tabeli jest
wartością atomową (pojedyncza
wartość, a nie zbiór)



zakaz definiowania złożonych
atrybutów



nie gwarantuje wyeliminowania
anomalii (redundancja)



Wszystkie kluczowe atrybuty muszą być
zdefiniowane



Wszystkie atrybuty muszą zależeć od
klucza głównego.



musi być w 1 PN



każda tabela ma klucz główny



klucz główny umożliwia
identyfikację danych tabeli



tabelę można rozbić na
pomniejsze tabele,
zawierające jakieś konkretne
informacje



Nie ma częściowych zależności



Żaden atrybut nie jest zależny
od części klucza głównego
(kompozytowy klucz)



Jeżeli klucz główny jest tylko
jednym atrybutem, tabela jest
w 2NF.



Musi być w 2 PN



wykluczenie kolumn o wartościach nie
zależnych bezpośrednio od klucza
głównego, lecz innej kolumny (eliminacja
wartości przechodnich)



eliminacja wszystkich pól niezwiązanych z
kluczem głównym



należy tak ułożyć strukturę, aby przy
odpowiednim złączeniu dało się
wyciągnąć odpowiednie dane

35. Przedstawić koncepcję transakcyjności w relacyjnych bazach danych.

Transakcja



pewna ilość poleceń przesłana do systemu zarządzania celem przetworzenia jako całość (niepodzielnie)



Sesja składa się z jednej lub większej liczby transakcji



Transakcje wykonywane są współbieżnie - jeżeli do bazy danych ma jednocześnie dostęp kilku
użytkowników



Transakcje współbieżne mogą być przeprowadzane na jeden z dwóch sposobów:

o Szeregowo - w momencie zakończenia jednej transakcji uruchamiamy następną
o Równolegle - wszystkie transakcje są realizowane jednocześnie - po jednej czynności na transakcję

Cechy transakcji
Każda transakcja powinna mieć następujące właściwości:



Niepodzielność (wszystkie operacje elementarne w transakcji muszą zakończyć się powodzeniem; jeśli nie,
to transakcja jest wycofywana, przywraca się wtedy stan bazy przed)



Spójność (integralność; baza danych musi być w stanie spójnym)



Izolacja (różne poziomy izolacji, faktyczne wzajemne oddziaływanie transakcji współbieżnie realizowanych;
czy dane z jednej transakcji widoczne w drugiej)



Trwałość (jeśli transakcja zakończy się sukcesem, to zmiany na trwałe zapisane w bazie)

Kończenie transakcji



Wszystkie transakcje kończą się na jeden z dwóch sposobów:

– sukcesem (trwałe wprowadzenie wszystkich modyfikacji do bazy danych)
– porażką (odwołanie transakcji i odtworzenie stanu bazy sprzed jej rozpoczęcia transakcji)



Z definicji, transakcja zakończona sukcesem nie może zostać odwołana



System zarządzania zapisuje wszystkie podejmowane przez transakcję czynności w rejestrze transakcji - aby
móc ją odwołać

Zakończenie transakcji
Status zakończenia:
- zatwierdzenie
- wycofanie

Zakończenie jawne:
- wykonanie poleceń kończących transakcję: COMMIT (zatwierdzenie) lub ROLLBACK (wycofanie)

Zakończenie niejawne:
- zakończenie sesji – zatwierdzenie
- wykonanie operacji DDL lub DCL – zatwierdzenie
- awaria – wycofanie

Wycofanie i zatwierdzenie transakcji



W trakcie wykonywania transakcja może być wycofana w dowolnym momencie (zignorowanie
wprowadzonych zmian)



Realizacja: ,,tymczasowe” wykonywanie transakcji.



Zmiany danych są tylko obliczane i zapisywane w specjalnym dzienniku transakcji.



Po zakończeniu wykonywania transakcji następuje jej zatwierdzenie, w wyniku czego zmiany są utrwalane
w bazie danych.

czynności:



zwolnienie założonych blokad



usunięcie punktów bezpieczeństwa



sprawdzenie odroczonych ograniczeń integralnościowych (kontrola po wykonaniu polecenia
modyfikującego dane)



trwały zapis zmian, wprowadzonych przez operacje w ramach transakcji (zmiany 1-nej transakcji widzi 2-
ga)

36. Techniki modelowania bazy danych, diagramy E/R i UML, narzędzia do modelowania.

Model bazy danych



Zbiór zasad opisujących strukturę danych w BD + dozwolone operacje



Struktura danych = zasady określające model (encje) + ich związki



Główne modele BD:

- Hierarchiczny (związki nadrzędny-podrzędny; drzewa)
- Relacyjny
- Sieciowy (grafowy)
- Obiektowy (obiekty i klasy obiektów)
- Sieci semantyczne

Diagramy E/R (ERD):



Diagram = graficzne przedstawienie związków między encjami



Przejrzystość, łatwość implementacji, niezależność od systemu



Wykorzystanie: walka z redundancją, sprawdzanie zależności, wizualizacji, projektowania



Brak standardowej notacji



Modelowanie relacyjnych baz danych, podejście zstępujące (encje i związki, potem szczegółowe
informacje)



Tworzy się encję (tabelę danych), w nich atrybuty (pola o różnych typach danych)



Łączymy encje relacjami (Krotność):

- 1 do 1
- 1 do wielu
- Wiele do wielu (tworzy się dodatkową encję żeby nie duplikować danych i by tabele zależały od siebie)



Oprócz krotności występuje też opcjonalność (czy encja musi być, czy może wystąpić wraz z inną itd.)

- Linia przerywana = opcjonalność związku, ciągła = konieczność

UML (Unified Modeling Language):



Ujednolicony język modelowania



Notacja w modelowaniu analizy/programowaniu obiektowej/wym



Typy diagramów:

Struktury

interakcji

zachowań



pakietów



obiektów



wdrożenia



struktur złożonych



komponentów



klas



czasowy



przeglądu interakcji



komunikacji



sekwencji



maszyny stanowej



przypadków użycia



czynności



UML a BD:
- Większość aplikacji = pojęcie obiektowe
- Brak obiektowych BD
- UML = próba pogodzenia modelu obiektowego z relacyjnym (przekształcanie diagramu klas do

relacyjnej BD)



Typy relacji między klasami:

asocjacja

agregacja

złożenie

uogólnienie



Zwykły, równorzędny
związek między encjami



Rodzaj asocjacji



Wyraża relację typu całość-
część



Separowana = może istnieć
bez klasy agregującej



Związek całość-część



Podobny do agregacji,
ale klasa agregowana nie
może istnieć bez klasy
agregującej



Związek hierarchiczny



Klasa nadrzędna
bardziej ogólna od klasy
podrzędnej



Specjalizacja =
odwrotna hierarchia



Przechodzenie z diagramu klas do schematu relacyjnego:
- Konieczność sprowadzenia do fizycznego modelu danych (PDM)

- Atrybuty klas automatycznie stają się kolumnami, identyfikatory -> kluczami głównymi (można

wyznaczać inne pola jako kluczowe, gdy identyfikatory nie istnieją)

- Metody klasy -> procedury



Diagramy klas = diagram ERD + szersze związki

- Szersze oznaczenia co do liczebności:

1-dokładnie 1

0..1 – zero lub 1



0..* - dowolnie wiele



1..* - co najmniej 1



* - wiele



6..8 – od 6 do 8



Narzędzia do modelowania BD/diagramów:

- MySQL Workbench
- MS Visio
- Visual Paradigm

37. Problemy współbieżności i wielodostępu w SZBD.

Anomalie współbieżnego dostępu:

anomalia

opis

Brudny odczyt

(ang. dirty read)



Groźna anomalia



Transakcja odczytuje dane zmienione przez inną, wycofaną transakcję

Utracona modyfikacja

(ang. lost update)



Groźna anomalia



Transakcja przetwarzana współbieżnie odczytuje dane, które zmieniła inna transakcja



2 transakcje modyfikują te same dane

Niepowtarzalny odczyt

(ang. non-repeatable

read)



Niegroźna anomalia



Transakcja wykonuje wielokrotnie tę samą operację odczytu danych (odczyt atrybutów, które mogą
zmienić inną transakcję), a my odczytujemy inne dane (1 komórka)



Niby odczyt 1-nej wartości, a tak naprawdę wielu

Fantomy

(ang. phantoms)



Niegroźna anomalia



Polecenie select na BD, za każdym razem wyświetla coraz więcej danych



inne pole rekordów (liczba zwracanych rekordów)



Nadpisanie danych (użytkownicy modyfikujący dane)

Poziomy izolacji transakcji:

Poziom iż. \ anomalie

Brudny odczyt

Niepowt. odczyt

fantomy

Odczyt niezat.danych

+

+

+

Odcz. zatw. danych

-

+

+

Powtarzalny odczyt

-

-

+

Uszeregowany

-

-

-

Gdzie: + (możliwa), - (niemożliwa)

38. Model ISO OSI. Model TCP/IP. Krótka charakterystyka warstw modelu.

Model ISO OSI



Ustandaryzowany model sieciowy



Warstwy wyższe (5,6,7) – współpraca z oprogramowaniem; interfejs do współpracy z warstwami niższymi



Warstwy niższe (pozostałe) – odnajdowanie drogi do celu, podział danych na pakiety PDU, weryfikacja
bezbłędności przesyłanych danych, ignorowanie sensu przesyłanych danych



Każda warstwa zrealizuje odwrotne zadania (w zależności od kierunku)

Korzyści:



Mniejsza złożoność



Ustandaryzowane interfejsy



Projektowanie modułowe



Współdziałanie technologii



Przyspieszony rozwój, uproszczenie procesu nauczania

Warstwy:

Nr

Warstwa

Charakterystyka

7

aplikacji



Połączenie procesów sieciowych z aplikacjami



Interfejs między aplikacjami, a siecią (komunikacja, usługi sieciowe np. poczta, przesyłanie pliku)



Specyfikacja interfejsu (do przesłania danych aplikacji przez sieć)



Aplikacja = proces uruchomiony na odległych hostach



Usługi interfejsu tej warstwy: gniazda



Warstwa klienta i serwera (komunikacja przez warstwy niższe)

6

prezentacji



Reprezentacja danych



Ruch w dół - przetwarzanie danych aplikacji do postaci kanonicznej (ten sam format)



Ruch w górę – tłumaczenie formatu otrzymywanych danych dla systemu docelowego



Kodowanie, konwersja danych, (de)kompresja, (de)szyfrowanie



Negocjuje składnię przesyłanych danych dla warstwy aplikacji

5

Sesji



Komunikacja między hostami



Synchronizacja danych różnych aplikacji



Synchronizacja warstw sesji nadawcy i odbiorcy



„wie, która aplikacja łączy się z którą” = właściwy kierunek przepływu danych (nadzorowanie połączenia)



Wznawia połączenie po przerwaniu



Ustanawia i zamyka sesje między aplikacjami (zarządzanie sesjami)

4

Transportowa



Połączenie typu end-to-end



Segmentuje dane i łączy je w strumień



Całościowe połączenie między stacją źródła i docelową (cała droga transmisji)



Dzieli dane na części, numeruje i przesyła do docelowych stacji



Wykorzystuje protokół: TCP (konieczność potwierdzenia odbioru; kontrola błędów transportu) i UDP (szybszy
ale mniej bezpieczny, bez potwierdzeń)



Kontrola integralności pakietów – odrzucanie błędnych pakietów

3

Sieciowa



Tylko ona zna fizyczną topologię sieci



Używa 4-ech procesów: adresowanie, (de/en)kapsulacja, routing



Trasowanie (drogi łączące komputery)



Decyduje ile informacji przesyłać 1 połączeniem a ile drugim



Ignoruje przesyłanie danych, gdy jest ich zbyt wiele



Nie zapewnia pewności transmisji – pomija niepoprawne pakiety danych



NPDU = paczka danych (sprawna łączność między odległymi punktami sieci)



Routery



Ruch w dół: enkapsulacja danych (pakiety zrozumiałe dla niższych warstw)



Pakiety: IPv4, IPv6, ICMP …

2

Łącza
danych
(liniowa,
kanałowa)



Nadzoruje jakość przekazywanych informacji (tylko dla warstwy niższej)



Możliwość zmiany parametrów pracy warstwy fizycznej (obniżanie błędów przekazu)



Ruch w dół: pakuje dane w ramki i wysyła je do warstwy 1 (inkapsulacja pakietów = ramki ze standardem)



Ramka danych: id odbiorcy, nadawcy, (opow. adresy MAC), informacja sterująca, CRC…



Rozpoznaje błędy niedotarcia pakietu i uszkodzeniem ramek -> naprawa



Dzieli się na

- LLC (logi cal link control) = sterowanie łączem danych, kontrola transmisji
- MAC (media access control) – sterowanie dostępem do nośnika (współpraca z warstwą fizyczną)



Urządzenia: most, przełącznik

1

fizyczna



Transmisja binarna



Składniki sieci do obsługi elektrycznego odbierania i wysyłania sygnałów



4 obszary funkcjonalne: mechaniczny, elektryczny, funkcjonalny i proceduralny (transmisja danych)



Brak weryfikacji integralności danych (tylko przesyłanie)



Przesyła i odbiera sygnały zaadresowane dla wszystkich protokołów jej stosu i aplikacji wykorzystujących ją

- Nadawanie danych (dane z ramek do postaci binarnych, metoda dostępu do nośnika, szeregowe

przesyłanie ramek danych)

- Odbiór – czekanie na transmisje hosta, odbiór strumieni, przesyłanie strumieni binarnych do łącza danych

(złożenie w ramki)

Model TCP/IP



Inny standard sieci internet



Ma mniej warstw niż OSI = prostszy



Standard komunikacji otwartej = dowolne urządzenia

Warstwy:

nr

warstwa

charakterystyka

4

Aplikacji



Protokoły wysoko-poziomowe



Reprezentacja danych, kodowanie, sterowanie konwersacją (aplikacje)



Opakowuje odpowiednio dane



Specyfikacja protokołów IP, TCP (internetowa, transportowa), a także przesyłania plików, poczty
elektronicznej, zdalnego logowania, FTP, NFS (rozproszony system plików), SMTP (przesyłanie poczty), Telnet
(zdalny dostęp do innego komputera), DNS …

3

Transportowej



Usługi przesyłania danych ze źródła do określonego hosta



Logiczne połączenie między komputerami w sieci



Podział/scalanie danych wyższych aplikacji w 1 strumień danych (połączenie logiczne)



Dzieli dane aplikacji, wysyła segmenty (TCP i UDP)



Kontrola przepływu, niezawodność, Transport typu end-to-end (między punktami końcowymi; tylko TCP)

2

Internetowej



Wybór najlepszej ścieżki dla pakietów w sieci i przełączanie pakietów



Protokoły: IP (bezpołączeniowe dostarczanie pakietów, format pakietu), ICMP (kontrola + informacja), ARP
(adres MAC dla IP), RARP (znajduje IP na podstawie MAC)

1

Dostępu
do sieci
(interfejs
sieciowy)



Łącze fizyczne przekazujące pakiet IP do medium



1+2 warstwa OSI



Działają tu sterowniki aplikacji, modemów i innych urządzeń



Działa tu wiele protokołów



Odwzorowuje adresy IP na adresy sprzętowe i inkapsuluje IP w ramki



Definiuje połączenie z fizycznym medium sieci w zależności od sprzętu/interfejsu sieciowego

Różnice:



Warstwa aplikacji TCP/IP = 5+6+7 OSI



Dostęp do sieci TCP/IP = 1 + 2 OSI



TCP/IP bardziej elastyczny od OSI



Brak stałej gwarancji dostarczania pakietów (w transportowej warstwie)



TCP/IP nie przypisuje sztywno funkcji do każdej warstwy (elastyczność)

39. Metody dostępu do medium. Protokół CSMA/CD.

Metody dostępu do medium



CSMA/CD (Ethernet)



Token Passing – przekazywanie znacznika, dostęp do medium = konieczność otrzymania tokena (ramki
sterującej); sieci Token Ring i FDDI



W modelu OSI – 2 warstwa (z MAC) = dostęp do nośnika

Problematyka dostępu do medium



Możliwość kolizji w sieci Ethernet (kilka urządzeń jednocześnie przesyła dane)

Mechanizmy dostępu do nośnika



Rywalizacja



Priorytet żądań



Na zasadzie pierścienia

CSMA/CD



Protokół wielodostępu CSMA z badaniem stanu kanału (łącza) i wykrywaniem kolizji



Wykorzystywany w sieciach LAN typu Ethernet



Węzły są nadajnikami prądu o stabilizowanym natężeniu





Jeśli kolizja – urządzenie wstrzymuje przesyłanie danych i informuje o kolizji (sygnał zagłuszania)



Urządzenie/węzeł posiada dane do przesłania -> nasłuchuje łącza (sprawdzanie czy linie są wolne)



Węzeł, który nie wysyła danych jedynie nasłuchuje, czy jakieś dane są przesyłane do niego



Poziom sygnału informującego o kolizji jest wyższy od normalnie generowanego przez węzeł (pewność że
każdy węzeł otrzymał informację o kolizji)



Retransmisja między węzłami, między którymi doszło do kolizji (sprawdzanie zajętości kanału po losowym
czasie)



Konieczność potwierdzania każdej ramki – samo CSMA

40. Adresowanie IP, podsieci i maski podsieci zmiennej długości.

Podstawowe informacje:



Adresowanie IP = przydział IP z puli adresów (podsieci)



Prefix „/” = sposób zapisu maski, np.

Przykładowa maska

Odpowiadający jej prefix

255.0.0.0

/8

255.255.0.0

/16

255.255.255.0

/24

- Prefix określa liczbę bitów z jedynkami (licząc od lewej strony)



Maska podsieci = identyfikacja części sieci i hosta IP (podział na podsieci = wydajność)



Adres IP = sieć + host (oddzielenie poprzez funkcję AND dla maski i IP; 1AND1 = 1 r 0)

Przykład:
255.255.240.0

Wartość tą zmieniamy na binarną

1111 1111. 1111 1111.1111 0000.0000 0000

Same 1 = część sieci
Same 0 = część hosta

Przykład:
Adres IP:

192.168.1.1

-> 1100 0000.1010 0100.0000 0001.0000 0001

Maska:

255.255.255.0

-> 1111 1111.1111 1111.1111 1111.0000 0000

Adres sieci :

192.168.1.0

<- 1100 0000.1010 0100.0000 0001.0000 0000

(funkcja AND IP i maski)

Adres rozgłoszeniowy:

192.168.1.255

<- 1100 0000.1010 0100.0000 0001.1111 1111

Broadcast
(część hosta z adresu sieci wypełniamy 1)



Adresowanie klasowe

- 5 klas adresów protokołu IPv4

klasa

Adres początkowy

Adres końcowy

A

0.0.0.0 /8

127.255.255.255 /8

B

128.0.0.0 /16

191.255.255.255 /16

C

192.0.0.0 /24

223.255.255.255 /24

D

224.0.0.0 /4

239.255.255.255 /4

E

240.0.0.0 /4

255.255.255.255 /4

- Każdej podsieci przydzielona pula adresów z 1 z klas

- Problem: zbyt duża pula adresów -> marnowanie adresów
- Braki w adresach -> rozwiązaniem adresowanie VLSM (bezklasowe – zmienna długość maski

podsieci)



Adresowanie bezklasowe

- Schemat adresowania IPv4
- Maski podsieci nie spełniają reguł z adresowania klasowego
- Duża elastyczność przy podziale zakresu adresów IP na odrębne sieci (p. 192.168.1.0 /8 jest

poprawne)

- VLSM (ang. variable length subnet mask)

 Maska podsieci o zmiennej długości -> oszczędność IP z puli
 Możliwość dobrania ilości IP do potrzeb

(np. 192.168.1.0/29 ma 6 hostów, bo: 32-29=3, 2

3

=8, 8-adres sieci i broadcast = 6)



Adresy specjalne:

127.0.0.0 – 127.255.255.255

<- pętle zwrotne

169.254.xxx.xxx

<- adresy domyślne



Subnetting (podsieciowanie)
- Podział zakresu adresów IP z 1 sieci na kilka podsieci
- Algorytm sprawdzania liczby hostów w ip: liczba hostów = 2

N

-2, N – bity hosta

- Ilość podsieci: 2

N

-2, N – bity sieci

- Przykład:

IP:

131.107.0.0

Maska: 255.255.0.0

Szukana maska dla 6 podsieci, liczba hostów do zaadresowania, przedziały

Rozwiązanie:
1) 6 = 2

3

-2 -> maska ma 3 bity z jedynką = 224

2) Rozpisuję maski binarnie:

255.255.0.0

<- 1111 1111.1111 1111.0000 0000.0000 0000

255.255.224.0

<- 1111 1111.1111 1111.1110 0000.0000 0000

3) Liczba hostów = 2

13

-2 = 8190

4) Liczmy przedział – szukamy najniższego bitu potrzebnego do uzyskania 224:

224 = 128 + 64 + 32

Zakres:
131.107.32.1

- 131.107.63.254

// bez broadcastu i adresu sieci

131.107.64.1

- 131.107.95.254

// dla klasy A trzeci oktet wynosi 255

131.107.96.1

- 131.107.127.254

// dla C w 4 oktecie startujemy od wartości + 1

131.107.128.1

- 131.107.159.254

131.107.160.1

- 131.107.191.254

131.107.192.1

- 131.107.223.254

5) Odpowiedź: maska: 255.255.224.0, można zaadresować 8190 hostów

41. Routing w sieciach komputerowych, metody routingu, porównanie.

Router (brama)



Urządzenie warstwy sieciowej



Określa optymalną ścieżkę przesyłania ruchu sieciowego, wykorzystując 1 lub kilka metryk



Przesyła pakiety z 1 sieci do 2-ej, wykorzystując informacje z warstwy sieci



Umożliwia komunikację między 2-ma różnymi sieciami

Routing = proces ustalania ścieżki i przesyłania ruchu sieciowego z 1 do 2-ej sieci

Rodzaje routingu:

dynamiczny

statyczny



Automatyczne dostosowanie do topologii sieci lub ruchu w
niej (protokół routingu konfiguruje tablice routing)



Metody routingu: wektor odległości, stanu łącza,



Działa dzięki zręcznemu wprowadzeniu wpisów do tablicy
routingu

Topologie dynamiczne:

topologia

opis

Wektora

odległości



Algorytm distance vector (Bellman-ford)

- każdy router wysyła całą/część swojej tablicy routingu tylko do swoich bezpośrednich sąsiadów (routing oparty na

sąsiadach; zgłasza nie tylko info o swoich sieciach, ale też tego, czego się dowiedział)

- trasy jako wektory (odległość (koszt) + kierunek)
- informowanie sąsiadów o najniższych kosztach
- protokoły te zużywają mniej systemowych zasobów routera
- powolna zbieżność = powolna reakcja na zmiany w sieci
- czas zbieżności = czas ustalenia się tabeli routingu
- te metryki routingu nie nadają się do dużych sieci
- generowanie dodatkowego ruchu w sieci (cykliczne rozgłaszanie pełnych tabel routingu – nawet gdy brak zmian)
- brak odporności na pętle między routerami
- brak weryfikacji poprawności danych otrzymanych przez sąsiadów -> router ma błędne info i przekazuje je dalej

(propagacja błędnych informacji)

- ograniczenie – maksymalna rozpiętość sieci (max liczba kolejnych routerów w ścieżce); jeśli ścieżka przekracza tą

wartość -> sieć jest nieosiągalna

- odszukanie dystansu (liczba skoków) i wektora (właściwy kierunek do celu)
- wymiana danych: komunikacja rozgłoszeniowa (broadcast), multiemisja (multicast)
- protokoły: RIP, IGRP

Stanu

łącza



algorytm link state (shortest path first)

- przesłanie informacji o routingu do wszystkich routerów -> tworzy się mapa sieci -> wytyczenie najkrótszej ścieżki

do wszystkich miejsc w sieci (algorytm Dijkstry; każdy router wyznacza dla siebie – jest korzeniem swojego drzewa)

- złożona baza danych z informacjami o topologii sieci
- każdy router wysyła pakiet z informacjami (o bezpośrednio podłączonych do niego sieciach i ich stanie) do

WSZYSTKICH swoich sąsiadów (każdy router pośredni zapisuje sobie to info, ale nie zmienia go)

- każdy router gromadzi info o topologii sieci, koszcie pojedynczych ścieżek i stanie połączeń
- pakiet = informacja o sieciach połączonych do routera; pełne info o routerach sieci i ich połączeniach
- osiągnięta zbieżność -> następne pakiety z aktualizacjami nie są takie duże (rozsyłane tylko zmiany)
- zbieżność szybciej osiągalna niż przy wektorze odległości
- szybsza reakcja na zmiany, brak cyklicznych ogłoszeń
- zmiana topologii sieci -> rozesłanie pakietów LSA -> routery zapisują zmiany w topologii -> wyznaczenie nowych

ścieżek routingu (niezawodność, mniej przepustowości na łączach sieciowych i kontrola)

- mniejsza podatność na pętle/błędy w routingu
- lepsze scalenie sieci
- wada: zużycie większej liczby zasobów routera; droższe; zużywają sporo pasma transmisji w początkowej fazie ich

działania

- protokoły: OSPF, IS-IS

Protokoły routingu:

Wektor odległości

Stanu łącza

Protokoły routingu

zewnętrznego

Klasowe

RIP, IGRP (tylko CISCO)

EGP

Bezklasowe

RIPv2, EIGRP (tylko
CISCO)

OSPFv2, IS-IS

BGPv4

42. Metody dostępu do sieci w technologii bezprzewodowej WiFi.

protokoły

opis

CSMA/CA
(ang. Cartier sense
multiple Access with
collision ayoidance)



Stacja skompletowała ramkę -> sprawdzanie stanu łącza (gdy wolne, to nadaje; jeśli zajęte, to czeka)



Zastosowanie: niektóre bezprzewodowe sieci LAN i sieci Packet Radio

BTMA
(ang.busy tone multiple
access )



Próba rozwiązania problemu ukrytych stacji (nie wszystkie stacje w sieci mają bezpośrednią łączność;
stacja ukryta – jest w zasięgu stacji odbierającej dane, ale poza zasięgiem stacji wysyłającej je)



Kanał transmisyjny rozbity na 2 podkanały:

- Podkanał komunikatów (przesyłane dane)
- Podkanał zajętości (każda stacja odbierająca informacje z podkanału komunikatów wysyła sygnał

zajętości – falę ciągłą)



Stacja z ramką do wysłania sprawdza stan podkanału zajętości (jeśli sygnał zajętości nieobecny – dane
wysłane; jeśli obecny – transmisja odkładana na później)



Wysoka efektywność protokołu – aż 70%

SRMA
(ang. slot reservation
multiple access)



Wykorzystuje mechanizm rezerwacji przedziałów czasowych



Konieczność wprowadzenia w sieci stacji sterującej



Podział kanału transmisyjnego:

- Podkanał komunikatów (przesłanie danych)
- Podkanał sterujący (przesłanie żądań i odpowiedzi)



Dla SRMA-RM stacja z danymi do wysłania przesyła żądanie do stacji sterującej

- Jeśli bezbłędnie -> dołączane do kolejki żądań (kolejka obsługiwana według dowolnego algorytmu)
- Gdy kanał komunikatów udostępniony – stacja sterująca przesyła stacji zgłaszającej kanałem

sterującym zezwolenie na nadawanie



Dla SRMA-RAM

- Kanał sterujący podzielony jest na 2 podkanały: żądań i odpowiedzi
- Stacja z danymi wysyła żądanie do stacji sterującej -> gdy brak błędu, stacja sterująca w kanale

odpowiedzi przekazuje informację z czasem transmisji danych dla stacji zgłaszającej

MACA i MACAW
(ang. multiple Access
with collision ayoidance)



Wymiana informacji sterujących przepływem danych (zamiast mechanizmu wykrywania fali nośnej)



Nadajnik wysyła ramkę RTS (gotowość do nadawania), odbiornik ramkę CTS (gotowość do odbioru)

- Mechanizm j.w. zapobiega kolizjom zakrytej i odkrytej stacji
- Istnieje ryzyko kolizji ramek sterujących



MACAW = dodatkowe ramki sterujące:

- DS. = poprzedza początek przesyłania danych
- ACK = potwierdzenie poprawy odbioru ramek danych
- RRTS = wysyłana gdy stacja nie może wcześniej odpowiedzieć na ramkę RTS z powodu wstrzymania

transmisji

BAPU
(ang. Basic Access
protocol solutions)



Sprawniejsze eliminowanie problemu zakrytej i odkrytej stacji niż w MACA



Podział

- Kanał danych (fizyczne)
- Kanał sterujący (większy zasięg transmisji)



Eliminacja interferencji stacji w kanale danych



Protokół używa 5 ramek sterujących:

- RTS – zgłoszenie gotowości do nadawania
- CTS – zgłoszenie gotowości do odbioru
- DS – poprzedza rozpoczęcie nadawania danych
- NCTS – zgłoszenie braku gotowości do odbioru (np. gdy stacja w zasięgu innej transmisji danych)
- ACK – potwierdzenie poprawnego odbioru ramek danych

Problemy sieci bezprzewodowych



Odkryta stacja - stacja w zasięgu nadawcy, ale poza zasięgiem stacji odbierającej – spadek przepustowości
w sieci bo zbędne wstrzymanie transmisji



Ukryta stacja - jest w zasięgu stacji odbierającej dane, ale poza zasięgiem stacji wysyłającej je



Interferencja – zakłócenia transmisji; 1-dna ze stacji poza zasięgiem nadajnika i odbiornika, ale zakłóca inne
stacje



Efekt przechwytywania – gdy do odbiornika docierają 2 sygnały o różnych mocach; silniejsza ramka
odczytana bezbłędnie – pozytywny efekt (poprawa wykorzystanie kanału transmisyjnego)

Typy dostępu do medium



Funkcje koordynacji dostępu

- DCF – typowy dostęp (bezprzewodowy dostęp połączenia sieciowego)
- PCF – specyficzny typ usług, wymagający braku rywalizacji o dostęp



Sprawdzanie zajętości kanału radiowego

- Gdy przejmowanie dostępu do kanału przez stację pełniącą funkcję nadawcy -> losowe opóźnienie

przy każdej ramce dla pozostałych stacji

- Czasami w DCF można stosować mechanizm RTS/CTS



Cechy funkcji PFC

- Konieczne stosowanie specjalnych stacji koordynujących
- Jedynie w sieciach strukturalnych
- Funkcja nadbudowana nad CDF
- Pierwszeństwo przed DCF (krótszy dostęp przed transmisją)

43. Podstawowe i złożone topologie sieci komputerowych.

Topologia = sposób organizacji koncentrator i okablowania

Topologia fizyczna = rzeczywisty układ przewodów i medium transmisyjnego; topologia logiczna = sposób
dostępu hosta do medium (rozgłaszanie i przekazywanie tokenu)

Topologie podstawowe:

topologia

opis

Magistrali

Wszystkie elementy sieci podłączone do 1 magistrali

Gwiazdy

Komputery podłączone do 1 punktu centralnego, koncentratora (koncentrator = fizyczna topologia gwiazdy, logicznie
– magistrala) lub przełącznika

Pierścienia

Poszczególne elementy połączone pomiędzy sobą odcinkami kabla (tworząc zamknięty pierścień)

podwójnego

pierścienia

poszczególne elementy połączone między sobą odcinkami tworząc 2 zamknięte pierścienie

Przełączana

(komutowana)

Wykorzystuje przełączniki (wieloporty);
Przełącznik uczy się adresów sterowania dostępem do nośnika
Między nadawcą ramki, a odbiorcą tworzone tymczasowe ścieżki przełączane (komutowane)

Siatki

oprócz koniecznych połączeń sieć zawiera połączenia nadmiarowe; sieci z wysoką bezawaryjnością

Dodatkowe:



Topologia liniowa – wszystkie elementy sieci (prócz granicznych) połączone są z dwoma sąsiadującymi



Gwiazdy rozszerzonej – posiada punkt centralny (jak w topologii gwiazdy) i punkty poboczne (1-na z
częstych topologii fizycznych Ethernet); rozszerzenie zasięgu

Topologie złożone:

Topologia

opis

Hierarchiczna
(drzewa)

Kombinacja topologii gwiazdy i magistrali, budowa podobna do drzewa binarnego; system podłączony do komputera
sterującego ruchem tej topologii

łańcuchy

Topologie złożone

-

rozszerzenia lub połączenia podstawowych topologii

-

topologie złożone = skalowalne,

-

w topologiach podstawowych skalowalność ograniczona

-

Łańcuchy

-

Hierarchie
-

Hierarchiczne pierścienie/ gwiazdy/ melanże

44. Charakterystyka systemów rozproszonych - zalety i wady.

System rozproszony



Zbiór niezależnych urządzeń technicznych połączonych w 1 spójną logicznie całość



Połączenie przez sieć komputerową (jednak możliwość użycia prostszych magistrali komunikacyjnych)



przykład przetwarzania współbieżnego, do realizacji systemów równoległych (problemy występujące w
systemach rozproszonych występują także w systemach równoległych, które z kolei występują w
przetwarzaniu współbieżnym)



Cel: bezpieczeństwo, niezawodność



Każdy zasób ma własny SO i zasoby lokalne



Programowanie warstwy pośredniej – tworzy się wirtualne oprogramowanie dla SO, służące usługi jako
całość



Autonomiczne działanie pojedynczego systemu, luźniejsze powiązanie współpracujących procesów niż w
przypadku obliczeń równoległych (zamiast synchronizacji czasowej mamy przyczynowo-skutkową)



Urządzenia posiadają oprogramowanie do współdzielenia zasobów systemowych



Cechy: przezroczystość (wrażenie 1-nczego i zintegrowanego systemu)

SYSTEM ROZPROSZONY = Co najmniej 1 KOMPUTERY W SIECI + OPROGRAMOWANIE TWORZĄCE
USŁUGI DLA WSZYSTKICH SYSTEMÓW

zalety

wady

+ Podział zasobów (dane, urządzenia sprzętowe)
+ Przyspieszenie obliczeń (dzielenie obciążenia)
+ Niezawodność (awaria 1 urządzenia nie uniemożliwia

działania systemu, co najwyżej może pogorszyć jego
wydajność)

+ Komunikacja (poczta elektroniczna)
+ Ekonomiczność (tańszy od systemu scentralizowanego)
+ Wewnętrzne rozproszenie (niektóre aplikacje z natury

rozproszone, wymagają rozproszonych komputerów)

+ Stopniowy wzrost (można stopniowo zwiększać moc

obliczeniową systemu); skalowalność – zdolność systemu do
adaptowania się do zapotrzebowań

+ Lepsze wykorzystanie sprzętu
+ Polepszenie jakości usług (usługi dostępne na serwerze)

- Złożoność oprogramowania i konieczność jego standaryzacji
- Sieć – możliwość awarii/przeciążenia
- Mniejsze bezpieczeństwo komputera podłączonego do sieci
- Współdzielenie i rozproszenie zasobów
- Niejednorodność (wydajność nie idzie w parze z

bezpieczeństwem)

- Otwartość (możliwość ataków)

45. Modele programowania równoległego.

Model programowania równoległego



Abstrakcja zasłaniająca architekturę sprzętu i pamięci



Nie są przypisane do żadnych konkretnych architektur – możliwość realizacji na dowolnym sprzęcie

Modele programowania równoległego:

model

cechy

Pamięć

współdzielona



Specjalnie utworzony segment wirtualnej przestrzeni adresowej, dostęp dla wielu procesów



Najszybsza komunikacja między procesami



1 z procesów tworzy segment pamięci współdzielonej, dowiązuje go -> odwzorowanie w bieżący obszar
procesu (opcjonalny zapis danych w segmencie)



Dostęp = miejsce wyznaczone przez adres dowiązania procesu (inny dla każdego procesu)



Koniec korzystania z segmentu pamięci -> możliwość odwiązania segmentu (usuwanie dowiązań)



Usunięcie segmentu pamięci współdzielonej przez proces-twórcę = gdy nie korzysta z niego żaden proces



(pod)zadania korzystają ze wspólnej przestrzeni adresowej



Odczyt/zapis w obrębie pamięci – asynchroniczny



Blokady i semafory – kontrola dostępu do pamięci



Brak potrzeby wymiany danych między zadaniami -> uproszczone programy (brak własności danych)



Utrudnione zarządzanie lokalnością danych



Zmniejszenie wydajności gry wiele procesorów potrzebuje tych samych danych = wymiana między PAO a
buforowaną cache



Implementacje:

- Natywne (bezpośrednie) kompilatory – przekład programów (obszar zmiennych w rzeczywistej lokalnej

pamięci)

- Brak powszechnych implementacji do tego modelu pamięci

Wątki



1 proces = wiele współbieżnych ścieżek do wykonania



Analogia: program zawierający szereg podprogramów



W przeciwieństwie do procesów wątki współdzielą przestrzeń adresową i inne struktur systemowych



Wymagają mnie zasobów, szybciej się tworzą



Łatwa komunikacja między wątkami (pamięć wspólna)



Związane z architekturą pamięci współdzielonej (wymóg odpowiednich funkcji SO)



Wykonanie programu:

- Załadowanie do pamięci
- Pozyskanie zasobów własnych i systemowych
- Sekwencyjne wykonanie prologu
- Utworzenie szeregu podzadań (wątków)
- Szeregowanie wątków (SO), wykonanie współbieżne
- Wątek ma dane lokalne i dostęp do pełnych zasobów programu (np. do obszaru pamięci)
- Komunikacja = wspólna pamięć -> konieczność synchronizacji dostępu
- Wątki tworzone i usuwane; program działa zaś do końca



Implementacje

- Biblioteka podprogramów programu równoległego
- Dyrektywy kompilatora w kodzie programu sekwencyjnego/równoległego
- Identyfikacja równoległości = programista



Standaryzacja

- POSIX Threads (PThreads)

o Oparta o bibliotekę funkcji
o Norma IEEE POSIX
o Tylko język C
o Konieczność kodowania równoległego
o Jawny opis równoległości
o Zależność efektu od umiejętności programisty

- OpenMP

o Oparty o dyrektywy kompilatora
o Języki Fortran/C++
o Wieloplatformowość, przenośność
o Możliwość użycia w kodzie sekwencyjnym
o prostota

Przekazywanie

komunikatów



zadania (podzadania) z własną lokalną pamięcią



zadania umieszczone w 1 fizycznej maszynie lub dowolnej ich liczbie



wymiana danych między zadaniami -> nadawanie i odbieranie komunikatów

- wymaga kooperacji zaangażowanych procesów (nadawanie + odbieranie)



implementacje

- biblioteka podprogramów kodu źródłowego
- programista = identyfikacja równoległości
- standard: MPI (standard przemysłowy)
- architektury o pamięci współdzielonej = nie korzysta z sieci (wydajność)

Dane

równoległe



operacje równoległe = działania na zbiorze danych



dane = struktura (p. tablica)



zadania (podzadania) = ta sama struktura danych



wykonanie tych samych operacji na swoich częściach struktury danych



systemy z pamięcią współdzieloną = wszystkie zadania sięgają do danych (pamięć globalna)



gdy pamięć rozproszona – podział na części struktury danych (jej kawałki umieszczone w lokalnej pamięci
odpowiednich zadań); kompilator przekształca program z wykorzystaniem API MPI (bez udziału programisty)



implementacje

- postać wywołań specjalnych podprogramów bibliotecznych dla danych równoległych
- postać dyrektyw odpowiedniego kompilatora



przykłady: Fortran, High performance Fortran, dyrektywy kompilatora

hybrydowy



połączenie różnych modeli programowania równoległego



pasuje do maszyn SMP z funkcjami sieciowymi



Przykłady: MPI + PThreads, MPI+openMP

Modele programowania wysokiego poziomu:

SPMD (ang. single program multiple data)

MPMD (ang. multiple program multiple data)



1 program dla wszystkich zadań



W 1 chwili = zadania wykonują te same lub różne instrukcje
wspólnego programu



Zadanie nie muszą wykonać całego programu



Model programowania wysokiego poziomu



Wiele różnych programów wykonywanych przez poszczególne
zadania



Zadania mogą przetwarzać różne dane

46. Miary efektywności obliczeń równoległych.

// ja bym to potraktował tylko jako dodatek, ważniejsze jest to co było u prowadzącego na wykładach:

Miara

efektywności

charakterystyka

Obserwacja



dla danej liczby procesorów przyspieszenie obliczeń równoległych jest większe dla zadań większych (ten sam
problem, ten sam algorytm, ten sam program, zmienia się tylko wielkość zadania)



przyspieszenie obliczeń równoległych większe dla zadań większych (dla danej liczby procesorów)



zmiana tylko wielkości zadania (problem, algorytm, program – te same)



dla zadań, dla których przy stałym p i rosnącym rozmiarze ilość obliczeń rośnie szybciej niż narzut obliczeń
równoległych

Miara

wielkości

zadania



praca W = liczba operacji przy realizacji zadania

Funkcja 2-óch

parametrów



przyspieszenie funkcją 2-óch parametrów (liczba procesorów p i wielkości zadania: S(p,W))



efektywność E(p,W)



analiza funkcji 2-óch zmiennych ->różne jej przekroje



Przyspieszenie skalowalne = przyspieszenie dla danej liczby procesorów p i zadaniu p-ktotnie większym od
zadania z pojedynczego procesora:

S

S

(p)=

=

Liniowe przyspieszenie skalowalne



Czas rozwiązania nie zmienia się przy rozwiązaniu zadania o rozmiarze p-krotnie większym na p razy więcej procesorach



Stała efektywność zrównoleglenia



Badanie słabej skalowalności = analiza przyspieszenia skalowalnego i skalowalnej efektywności (wydajność przy stałym rozmiarze
zadania na 1 procesorze)

- Czas rozwiązania zadania p-ktornie większego na większej liczbie procesorów będzie niezmieniony



Skalowalność równoległa - - zachowanie programu równoległego dla rosnącego zadania i liczby procesorów



Program skalowalny równolegle = efektywość obliczeń równoległych: E(W(p),p) ograniczona od dołu przez liczbę > 0

- Gdy W(p) funkcją liniową = liniowa skalowalność (wymagany rozmiar pamięci tych funkcji nie przekracza dostępnych

zasobów; wzrost liczby procesorów = liniowy wzrost pamięci)



Analiza równoległej skalowalności = funkcja izoefektywności (efektywność jest stała: E(Wizo(p),p)=const (>0)); obliczenia dla f
izoefektywności są skalowalne; liniowa skalowalność = liniowa funkcja izoefektywności; izoefektywność – gdy narzut obliczeń
równoległych



Stała efektywność = stosunek narzutu wykonania równoległego do czasu obliczeń sekwencyjnych = const przy stałym rozmiarze
zadania (narzut całkowity jest stały -> narzut na 1 procesor maleje odwrotnie proporcjonalnie do liczby procesorów p)



Wzrost liniowy procesorów i zadania powoduje liniowy wzrost całkowity narzutu na 1 procesor



Obliczenia liniowo skalowalne – 1 z warunków do spełnienia:

- stały czas rozwiązania zadania p-krotnie większego na p-razy większej liczbie procesorów
- stały narzut wykonania równoległego na 1 procesor (zadania rosnące liniowo wraz z liczbą procesorów)
- liniowa funkcja izoefektywności lub liniowe przyspieszenie skalowalności obliczeń



program dobrze skalowalne – niewielkie odstępstwa od warunków j.w. (duże odstępstwa = programy nieskalowane i źle skalowalne)



Skalowalność = kluczowe pojęcie dla równoległych obliczeń wysokiej wydajności



W praktyce nie istnieją programy dające się idealnie zrównoleglić (o liniowym przyspieszeniu), natomiast
istnieją programy dobrze skalowalne (o liniowym przyspieszeniu skalowanym)



Wydajność przetwarzania (różnie definiowana w różnych dziedzinach zastosowań) daje się często ustalić na
podstawie analizy skalowalności



W dziedzinie obliczeń wysokiej wydajności (HPC): wydajność = liczba_operacji /czas , co często daje się
przybliżyć jako: przyspieszenie*czas_wykonania_1_operacji

- - - - - - Z wykładów prowadzącego (chyba bardziej konkretne)

Cel obliczeń równoległych



Uzyskanie wysokiej wydajności obliczeń

Wydajność obliczeń równoległych

Szacowanie

wydajności na

podstawie

sprzętu

- Wydajny sprzęt = szybkie rozwiązania zadań
- Miara czasu rozwiązania zadania lub liczba zadań w jednostce czasu
- Zastosowanie: różne dziedziny (grafika – ramki na sek, BD – transakcje)
- Trudne zagadnienie, tylko dla określonych dziedzin
- Miary wydajności:

o MIPS (przetwarzanie procesora, jednak niewydajne bo zależy od urządzeń zewnętrznych; także różna

budowa procesorów -> inna liczba rozkazów dla programów)

o MFLOPS/ GFLOPS (szacowanie liczby rozkazów procesora na jednostkę czasu) -> algebra, rozwiązywania

układów liniowych; jednak problem, bo rezultaty praktyczne to nieraz 1% teoretycznego

Miary mierzone

bez sprzętu

- Miara przyspieszenia (obliczenia równoległe bez sprzętu); sprawdzamy wydajność programu przy zwiększaniu

liczby procesorów

- Podstawą – czas rozwiązania zadania
- Definicje przyspieszenia:

o Obliczenia równoległe (bezwzględne) = stosunek wykonania konkretnego zadania najlepszego programu

sekwencyjnego do czasu rozwiązania na p procesorach z użyciem algorytmu testowanego

S

(1)

(p) =

Intuicja podpowiada nam, że program na 4 procesorach powinien działać 4-rokrotnie szybciej (czyli, że
przyspieszenie = 4). W praktyce jednak nie zawsze algorytm sekwencyjny jest przystosowany do
zrównoleglenia. Czasami lepiej zastosować gorszy algorytm sekwencyjny, który jednak lepiej działa
równolegle. Algorytm dobrze skalowalny – stosujemy algorytm gorszy dla wykonania sekwencyjnego,
jednakże w przypadku wykonania równoległego jest bardziej wydajny

o Przyspieszenie względne = stosunek wykonania algorytmu na 1 procesorze do wykonania na p

procesorach

S(p) =

ó
ó

groźba – przyspieszenie powoduje, że mamy zawsze opłacalny wynik; ponadliniowość (superlinear speed-
up) – coś lepszego od ideału

- Analiza przyspieszenia = klasyczna analiza złożoności
- Prawo Amdahla = czas wykonania równoległego w programie jest mniejszy od sekwencyjnego
- Prawo Gustavsona = stały czas rozwiązania zadania (mimo dokładania procesorów)

Efektywność Zrównoleglenia: E(p) = S(p)/p

Skalowalność programu równoległego

Silne (liniowe) przyspieszenie

słabe



Przy analizie Andhala



Liniowe przyspieszenie przy zwiększaniu liczby procesorów
– rozwiązywane te same zadania



Nie może być części sekwencyjnej oraz komunikacji i
synchronizacji

Kłopotliwa (embarassing), nie może być rzeczywista



świetna skalowalność



jedyne co możemy uzyskać



wystarcza w większości wypadków



Dostajemy liniowe przyspieszenie jeśli rozmiar zadania rośnie
wraz z liczbą procesorów



Duże maszyny stosuje się do wykonywania coraz większych
zadań w sensownym czasie

47. Środowiska programowania równoległego.

środowisko

charakterystyka

OpenMP

(ang.Open Multi-

Processing)



Wieloplatformowe API (interfejs) programowania aplikacji



Model SPMD



Programowanie z pamięcią wspólną



Umożliwia tworzenie programów współbieżnych z pamięcią dzieloną



Wykorzystywany w językach: C,C++, Fortran …



Dostępny dla wielu architektur: Windows, Linux



Zbiór dyrektyw kompilatora (z argumentami tzw. klauzule) + biblioteki + specjalne zmienne środowiskowe
(dostępne są też funkcje)



Dyrektywa podziału pracy (najważniejsza, podział pracy w pętlach)



Dyrektywy i funkcje OpenMP nie gwarantują poprawności



Duża przenośność, skalowalność, elastyczność, prostota użycia (przezroczystość kodu – nie wygląda on tak
strasznie)



Można użyć do aplikacji na klastrach (pod kontrolą MPI - hybryda)



Możliwość użycia rozszerzeń dla systemów bez pamięci współdzielonej



2 obszary równoległe mogą mieć różną liczbę wątków, istnieje możliwość zagnieżdżania obszarów
równoległych (obszar w obszarze)



Możliwość użycia zamków/sekcji krytycznych/barier (walka z wyścigiem)

RPC

(ang. Remote

Procedure Call)



Nie przystosowany do programowania obiektowego



Używany w systemach Unix



Bazuje na gniazdach



Komunikacja – zdalne wywołanie procedur, namiastki (po stronie serwera i klienta; namiastka klienta
wysyła dane do namiastki serwera, które idą później do funkcji serwera i wracają drugą stroną)



Wspólny sposób reprezentacji podstawowych typów danych XDR (ang. external Data Representation)



Łatwiejsze zarządzanie stanem funkcji serwera niż obiektem w RMI



Ograniczenia:

- Zdalna procedura przyjmuje tylko 1 argument/1 wynik, który może być strukturą
- Zmiany w procedury w jej argumencie pozostają lokalne i nie są przekazywane do klienta
- Klient otrzymuje wynik jako dowolny typ XDR
- RPC używa port standardowy 111
- Wywołując funkcję w nazwie trzeba umieścić jej wersję

RMI

(ang. Remote

Method

Invocation)



Część Javy



Możliwość wywoływania metod obiektów istniejących w maszynie wirtualnej JAVY przez obiekty z innej
maszyny wirtualnej



Obiekty zdalne i lokalne = identyfikacja przez referencję



Przechowuje stany obiektów



Namiastka = przekazywanie całego obiektu na serwerze



Komunikacja między klientem, a serwerem poprzez zarządzanie referencjami (zdalne obiekty przesyła się
przez referencję)



Ograniczenia:

- Problemy rozproszonego bezpieczeństwa danych, synchronizacji, odświecania pamięci
- Możliwe wykonywanie metod zdalnego obiektu bez dostępu do jego pól
- Metody RMI zadeklarowane w interfejsie rozszerzającym interfejs Java.RMI.Remote

CORBA

(ang. Common

object request

broker

architecture)



Standard komunikacji aplikacji w środowisku rozproszonym (za pomocą wspólnego brokera ORB)



Usługi świadczone przez obiekty



Middleware = środowisko między aplikacją, a SO



Obiekty programów komunikują się zdalnie dzięki ORB



Object adapter = tłumaczenie programu na konkretny język



wywołanie klienta trafia najpierw do ORB, potem przekazywane jest do systemu i do adaptera. Adapter
sprawdza, z jakim językiem ma do czynienia i tłumaczy go (zmiana kodu na kod pisany w konkretnym
języku)



Opracowany przez Object Management Group



Interfejsy CORBY:

- Komunikacja modułów programowych z innymi poprzez brokery
- Brokery komunikują się ze sobą w sposób jednakowy
- Moduł poznaje charakterystykę interfejsu innego modułu
- Możliwość komunikacji modułów w różnych językach programowania
- Możliwość komunikacji modułów w różnych architekturach (język definicji interfejsów IDL)

MPI



Programowanie z modelem przesyłania komunikatów



synonim ogólnego programowania komputerów z pamięcią rozproszoną



przepość, elastyczność



Interfejs programowania definiujący powiązania z językami C, C++, Fortran



od początku wiele procesów



brak wspólnej przestrzeni adresowej



programy się kompiluje, powstają pliki binarne, które się uruchamia jednocześnie



różne schematy komunikacji (broadcast, scalther, gather itd.)

W Javie możemy tworzyć wątki dziedzicząc po klasie Thread, implementując interfejs Runnable
W Linuxie mamy możliwość użycia wątków systemowych PThreads

48. Prawo Amdahla.

Prawo Amdahla:



analiza przyspieszenia obliczeń zrównoleglonych



w programie występuje część, której nie da się zrównoleglić (rozgłaszanie, redukcja)



czas wykonania równoległego w programie jest mniejszy od sekwencyjnego, a przyspieszenie nie
przekroczy

, f =

, s- czas wykonania części sekwencyjnej

Prawo Amdahla jest wyidealizowane



brak analizy komunikacji i synchronizacji (im więcej procesów, tym więcej komunikacji i synchronizacji)



rzeczywiste programy działają gorzej niż prawo Amdahla

49. Obrazy rastrowe i wektorowe: budowa, właściwości, różnice.

Obrazy rastrowe

Obrazy wektorowe

Budowa



Budowa obrazu za pomocą pionowo-
poziomej siatki odpowiednio
kolorowanych pikseli na monitorze
komputera



Piksel = położenie + kolor („mozaika”)



Obraz opisany jest za pomocą figur geometrycznych (2D) lub
brył geometrycznych (3D)



Figury umiejscowione są w matematycznym układzie
współrzędnych

Właściwości



Kolor każdego piksela zdefiniowany
pojedynczo (brak kompresji)



Obrazek z głębią koloru RGB = 3 bajty
(czerwony, zielony, niebieski)



Obrazy czarno-białe wymagają tylko 1
bajtu na piksel (bitmapa)



Bitmapę charakteryzują 2 liczby: wysokość
i szerokość bitmapy (w pikselach)



Analiza zmiany koloru ciągłych zbiorów
pikseli (gdy dane o obrazie pobierane
kolejnymi rzędami



Edycja = modyfikacja poszczególnych
pikseli



Figury opisane w sposób matematyczny -> możliwość
wykonywania operacji (obrót, przesunięcie … )



Jakość obrazu zależy od dokładności opisu obrazu



Możliwość zmiany kolejności obiektów na osi głębokości



Możliwość konwersji do grafiki rastrowej



Generowana komputerowo



Podstawą: linia (prosty odcinek lub krzywa); linie ograniczają
obszary Lu tworzą obrysy; linie jako wektory = linie odniesienia
przy przekształceniach geometrycznych



Obszary zamykane liniami mogą mieć nadawanie atrybuty
koloru o określonym stopniu przezroczystości lub tworzyć maski



Mniejsza objętość plików

Różnice



Wielkość obrazka nie może zostać
zwiększona bez zmniejszenia jego ostrości



Bardziej użyteczna do zapisywania zdjęć i
rzeczywistych obrazów



Obrót o kąt niebędący wielokrotnością 90

o

obrazu może go zniekształcać (utrata
jakości)



Operacja na obrazie są kosztowne
obliczeniowo



Konwersja do grafiki wektorowej
nieopłacalna



Zależy od rozdzielczości



Zapamiętuje kolory i położenie pikseli



Nie trzeba nic dodatkowo instalować



Obraz ideowy, nie literalny



Pokazuje obraz z użyciem obiektów geometrycznych (krzywe,
wielokąty)



Skalowalna -> wielkość obrazka można skalować bez strat
jakości -> możliwość dopasowania do urządzenia



Obrazy z figur geometrycznych i prezentacji tekstu (tabele,
wzory …)



Maksymalna możliwa rozdzielczość



Możliwość modyfikacji poprzez zmianę parametrów obrazu



Mniejszy rozmiar (zastosowania niefotorealistyczne)



Opis przestrzeni 3D



Możliwość użycia ploterów zgodnie z metodą ich pracy



Zachowuje informacje o liniach, krzywych (kształty) obiektu



Możliwość szerokiej edycji poszczególnych elementów

Gdzie:

S – czas wykonania części sekwencyjnej

Czas wykonania równoległego na p procesorach:

Trówn. (p) = S +

Wzór na przyspieszenie obliczeń:

S

A

(p) =

=

=

Przyspieszenie tylko do 10

50. Grafika rastrowa - prymitywy graficzne 2D: kreślenie odcinków, okręgów, wypełnianie

obszarów.

Geometria obrazu – opis za pomocą „prymitywów”, jak:
- odcinki,
- trójkąty, prostokąty, wielokąty,
- łuki, okręgi, elipsy,
- koła i ich wycinki

Kreślenie odcinków

Kreślenie okręgów



Obliczanie współrzędnych pikseli o jak najmniejszej
odległości od wektora wyznaczającego jego przebieg



Idealny odcinek na siatce rastra + konwersja = zbiór
pikseli przybliżających wektor



Konwersja – algorytmy (zaokrąglenie przy wyborze
interesującego piksela):

- DDA (względem osi X lub Y) ; liczby

zmiennoprzecinkowe; mało efektywny

- Bresenhama (punk środkowy); liczby

stałoprzecinkowe

- Algorytm symetrii oktantowej (Podział okręgu na 8 symetrycznych
części)
- Algorytm z punktem środkowym (Obliczenia wykonywane w drugim
oktancie)
- W przypadku odcinka przyrost był wartością stałą, w przypadku okręgu
przyrosty są zmienne, gdyż zależą od wartości współrzędnych punktu P.
Punkt ten jest zatem punktem odniesienia

wypełnianie obszarów
Wypełnianie ograniczonego obszaru:
- barwą,
- gradientem,
- wzorem.

Problemy związane z wypełnianiem:
- wybór pikseli, które powinny zostać wypełnione,
- wybór metody wypełniania pikseli.

Wypełnianie wielokątów



Obraz analizowany wiersz po wierszu (linie przecinające wielokąt i wypełniane segmenty pikseli)



Wybór pikseli = reguła parzystości (przy przejściu przez kolejne krawędzi, bit raz parzysty, a raz nieparzysty;
rysowane tylko piksele o wartościach nieparzystych)



Problemyzwielokątami,któreposiadająwspólnekrawędzie–powielaniepunktówbrzegowych



Piksele znajdujące się wewnątrz dowolnego wielokąta powinny zostać wypełnione



Wypełnienie wielokąta przez spójność (punkt startowy – ziarno)



Sąsiedztwo piksela



Kontur figury na płaszczyźnie dyskretnej

„Drzazgi”



Negatywny efekt dyskretyzacji obrazu.



W wielokątach o krawędziach, między którymi jest niewielki kąt tworzą się „drzazgi”.



Segmenty pikseli zawartych we wnętrzu wielokąta mają niewielką lub zerową długość.

51. Algorytmy poprawy jakości obrazu rastrowego.

Metody poprawy jakości obrazu poprzez manewrowanie trzema głównymi elementami:



Jasność / zakresu koloru



Kontrast



Histogram

Algorytmy:

algorytm

opis

Liniowe odwzorowanie poziomów jasności



dodawanie/odejmowanie od obrazu stałej wartości; wynik: jasny/ciemny obraz



przy mnożeniu – poprawa jakości(kontrast), jednak możliwość utraty części
danych (przekroczenie wartości);



solaryzacja = zmiana poziomów jasności pikseli

Metoda nasycenia/modulo



przekroczymy zakres - wartości pikseli idą od początku



normalizacja jasności - kilka metod, np. podział obrazu wynikowego przez
największą wartość piksela z obrazów składowych; zmniejszenie szumu obrazu

Nieliniowe odwzorowanie poziomów
jasności



transformacja kwadratowa/sześcianowa



funkcja z potęgą



pierwiastkowanie = zwiększenie kontrastu w ciemnych partiach obrazu



logarytmowanie obrazu

Korekcja gamma = punktowa transformacja obrazu
monochromatycznego/poszczególnych kanałach barw obrazu kolorowego

Inne:



,,Rozciąganie” histogramu obrazu = zwiększenie kontrastowości obrazu



Inwersja poziomu jasności obrazu



Wyrównywanie histogramu obrazu



Obliczanie histogramu skumulowanego



Eliminacja zniekształceń - sumowanie obrazów



Redukcja zakłóceń obrazu przez uśrednianie sekwencji obrazów

52. Metody skalowania obrazów rastrowych.

Metoda

opis

Metoda

najbliższego

sąsiada



Wartość nowych pikseli wyliczana poprzez wybór wartości jednego z 4-ech najbliżej położonych pikseli



Piksel przyjmuje barwę piksela położonego najbliżej (miara euklidesowa) = powielanie/eliminację wybranych
pikseli (w zależności czy powiększamy, czy zmniejszamy obraz)



Brak nowych wartości wprowadzonych do obrazu



Brak interpolacji nie powoduje zmniejszenia ostrości krawędzi



Jeśli 2 piksele źródła równooddalone od nowego piksela -> wybór przebiega według dowolnej metody
(konsekwentność)



Dobra, gdy zwielokrotniamy rozdzielczość (zmiana długości i szerokości)



Na wartość nowego piksela ma wpływ tylko 1 z sąsiadów

Metoda

interpolacji

dwuliniowej



Poddawane są piksele występujące najczęściej w układzie 4-sąsiedztwa



Im bliżej analizowanego punktu jest piksel z jego sąsiedztwa, z tym większą wagą wpływa na wartość nowego
piksela



wszystkie piksele mają wpływ na wartość nowego piksela



powstają zupełnie nowe wartości pikseli (nieobecne w obrazie źródłowym)



kontury obiektu ulegają rozmyciu

Metoda

interpolacji

dwukubicznej



brane jest tu 16 sąsiadujących pikseli



wartość piksela liczona jest z wielomianu 3-ego stopnia



wada: znaczna złożoność obliczeniowa



w obrazie pojawiają się nowe wartości = rozmycie krawędzi (tak jakby rozmazany obraz był wyraźniejszy)

53. Modele barw stosowane w grafice komputerowej (RGB, CMY, HSV, LAB).

Model

Opis

RGB



Ukierunkowane na sprzęt (różna charakterystyka widmowa -> każde urządzenie ma zakres barw możliwych do
uzyskania)



Taka kostka; na osiach są barwy czerwona, niebieska i zielona



Powstał z właściwości odbiorczych ludzkiego oka (wrażenie dowolnej barwy = zmieszanie kolorów red, blue i Green w
ustalonych proporcjach)



Synteza addytywna = wartości najniższe – czerń, najwyższe - biel

CMYK



Ukierunkowane na sprzęt (drukarki)



Jedna z przestrzeni barw w pracy z grafiką komputerową



Jak RGB, tyle że na osiach są żółty, różowy i jasnoniebieski

HSV



Ukierunkowane na użytkownika (barwy = światło pochodzące z oświetlenia)



Wszystkie barwy wywodzą się ze światła białego (część widma wchłonięta, część odbita do oświetlanych przedmiotów)



Model opisu przestrzeni barw



Hue = barwa (dominująca długość fali)



Saturation = nasycenie (czystość pobudzenia)



Value (level) = jaskrawość



Model ten przypomina taki jakby stożek przecięty na części (poziomy)

LAB
(CIE

La*b*)



Niezależne od urządzenia



L = jasność, A,B = nieliniowo skompresowane koordynaty przestrzeni CIE XYZ



Najszersza zdefiniowana matematycznie przestrzeń barw (powstała w wyniku transformacji krzywoliniowego stożka
CIE)



Najważniejszy model grafiki komputerowej, wykorzystywany w obliczeniach barw przez systemy zarządzania barwami
CMS (ang. color management systems)

54. Cykl życia oprogramowania.

rola fazy strategicznej, etapy tworzenia oprogramowania

etap

opis

Wymagania



Analiza problemu, zrozumienie potrzeb użytkownika, dzielenie wejść/wyjść, prototypowanie



Tylko elementy istotne, precyzja, jasność, wykonalność



Warunki początkowe, przypadki użycia, uczestnicy, rozszerzenia

Specyfikowanie



Specyfikacja odbiorcy i ich potrzeb



Precyzowanie wymagań – formalizm (precyzja)



Języki specyfikacji: formalne i nieformalne



Oprogramowanie niebezpieczne

Projektowanie



Ogólne zasady projektowania = etap fazy analizy



Etapy projektowania = wysokiego poziomu i szczegółowe



Modele obiektowe i strukturalne



Sztuka tworzenia interfejsów



Notacja formalna

Kodowanie



Języki programowania i narzędzia wspomagające (analizatory, skrypty)



Projektowanie z użyciem pseudokodu, abstrakcyjne typy danych, hermetyzacja



Projektowanie obiektowe (obiekty rzeczywiste i programowe, wymagania obiektowe)

testowanie



Plan testów (cykl życia)



Implementacja, a testowanie



Testowanie funkcjonalne i oparte na błędach



Testy jednostek i systemu



Testy losowe, automatyczne, systematyczne i regresywne



Zarządzanie testowaniem

konwersacja



Dokumentacja systemu informatycznego



Zarządzanie projektem informatycznym

55. Model kaskadowy i spiralny, charakterystyka i porównanie.

Model kaskadowy – taki jak w 54 zadaniu

Dokumentacja

Faza strategiczna

analiza

synteza

Instalacja i utrzymanie



wymagania



specyfikowanie



początek
projektowania



projektowanie



kodowanie i
implementacja



początek testowania



testowanie



konserwacja
produktu

Model kaskadowy – wady:



narzuca twórcom oprogramowania ścisłą kontrolę kolejności realizowanych prac



wysoki koszt błędów popełnionych we wstępnych fazach (błędy wymagań i specyfikacji -> odkryte przy
testowaniu)



klient bierze udział tylko we wstępnej fazie projektu, jest mało zaangażowany -> obniżenie zainteresowania
produktem

Można rozbudować testowanie (żeby było w każdym etapie; model V)
Można rozbudować o model iteracyjny – jeśli któraś z faz zwróci niesatysfakcjonujący wynik, to cofamy się
wykonując kolejne iteracje)


Model spiralny



proces tworzenia ma postać spirali



najbardziej ogólny model cyklu życia oprogramowania



dobrze rozpoznaje zagrożenia i zapobiega/redukuje -> wysoka niezawodność każdego oprogramowania,
pewność dalszej realizacji



4 główne fazy cyklu życia oprogramowania wykonywane cyklicznie: analiza ryzyka, konstrukcja,
atestowanie i planowanie

planowanie

Analiza ryzyka

Konstrukcja (model

kaskadowy)

atestowanie



Wymagania początkowe



Planowanie projektu



Kolejne iteracje – wynik kontaktu z
klientem



Analiza ryzyka w oparciu o
wymagania



Przy kolejnych iteracjach:
analiza ryzyka w oparciu o
reakcje klienta



Tworzenie
oprogramowania
w oparciu o
najbardziej
odpowiedni
model wybrany
na podstawie
zagrożeń



Customer evaluation
(ocena klienta)

56. Metryki oprogramowania, przykłady i obszary zastosowań.

Metryka (miara) programowania



Miara pewnej własności oprogramowania/jego specyfikacji



Brak 1 definicji - wszystko to, co charakteryzuje oprogramowanie



Można wyróżnić różne metryki na różnych etapach życia oprogramowania

Cechy metryki:



Zarejestrowana historia (podobny projekt realizowaliśmy przez rok) nosi znamiona miary.



Powiązanie ilości kodu KDSI (thousand of delivered source code instruction), LOC (line of code) z
elementami potrzebnymi do napisania tego kodu:

Ludzie (ilość, czas),
Czas (długość i etapy harmonogramu)
Sprzęt (czyli zasób rzeczy konieczny do stworzenia oprogramowania)



Gdy brak własnych danych historycznych –modele estymacyjne = algorytmiczne (na podstawie wzoru)

Ocena rozwiązań:



Sukces = wybór realizacji przedsięwzięcia (faza strategiczna) -> wybiera się najlepsze



Trudności z wyborem rozwiązań: cele (kryteria oceny), niemożność precyzyjnej oceny rezultatów



Kryteria oceny: koszt, czas realizacji, niezawodność, możliwość ponownego wykorzystania systemu,
przenośność, wydajność

Wybór rozwiązania



Usunięcie rozwiązań zdominowanych (inne rozwiązanie nie gorsze w innych kryteriach i lepsze w co
najmniej 1 od wybranego)



Wagi dla poszczególnych kryteriów



Normalizacja wartości kryteriów



Suma iloczynów znormalizowanych wartości i wag = ocena rozwiązania



Niepewność = problem; szacowanie wartości optymistycznej i pesymistycznej (strategia działania);

- nie można w obiektywny sposób stwierdzić która strategia jest lepsza
- bardziej racjonalna ocena -> szacowanie prawdopodobieństw zdarzeń dla danych rozwiązań

Szacowanie kosztów oprogramowania



czynniki łatwe do oszacowania: koszt sprzętu/wyjazdów i szkoleń/zakupu narzędzi



czynniki trudne do oszacowania: nakład pracy



szacowanie kosztów oprogramowania = głównie nakłady pracy



metody:

metoda

charakterystyka

Przykład i zastosowanie

Modele algorytmiczne



wymaga opisu danego przedsięwzięcia za pomocą szeregu atrybutów
liczbowych i opisowych



odpowiedni algorytm = spodziewany nakład pracy



COCOMO

Ocena przez eksperta



Doświadczenie osoby



Nieraz duża precyzja

Ocena przez analogię



Wycena na podstawie wcześniej realizowanych przedsięwzięć



Sieci neuronowe



Systemy ekspertowe

Prawo Parkinsona



Przedsięwzięcie zawsze wiąże się z założonymi nakładami



Projekt zmieści się w założonych ramach

Wycena dla wygranej



Koszt oprogramowania szacowany na podstawie oceny możliwości
klienta i działań konkurentów



Obowiązuje tu prawo Parkinsona

Szacowanie
wstępujące



Realizacja przedsięwzięcia dzielona na mniejsze zadania -> koszt
łatwiej ocenić



Algorytmiczne modele szacowania kosztów oprogramowania

model

opis

Metoda punktów

fikcyjnych



Łatwiej oszacować rozmiar systemu niż nakład pracy



Model nie opierający się na liczbie instrukcji kodu



Szacowane czynniki:

- Dane odczytywane/pobierane przez system
- Interakcja z użytkownikiem
- Zewnętrzne interfejsy
- Pliki wykorzystywane przez system

COCOMO

(ang. COst

COnstruction MOdel)



Nakład pracy = możliwość oszacowania czasu realizacji przedsięwzięcia -> otrzymujemy przybliżoną
wielkość zespołu (korekcja za pomocą tzw. czynników modyfikujących – brane różne atrybuty
przedsięwzięcia, np. rozmiar bazy danych, wymagania niezawodności systemu itd)



Wymaga oszacowania liczby instrukcji systemu



Powszechnie wykorzystywany model



Opiera się na wielu rzeczywistych przedsięwzięciach



Nie do końca adekwatny w przypadku rzeczywistych przedsięwzięć (brak narzędzi CASE)



Pod uwagę bierze się czynniki i postać zależności w modelu



Przedsięwzięcie zalicza się do 1 z klas:

- Organiczne – mały zespół, podobne umiejętności każdego członka, dobrze znana dziedzina

problemu/narzędzia/metody

- Półdrewniane – różnica stopnia zaawansowania dla członków zespołu, niektóre

metody/dziedziny nie są znane

- Osadzone – realizacja systemów o złożonych wymaganiach, dziedzina/metoda/narzędzia

znane, brak doświadczenia członków zespołu

----- dodatek:
Metryki statyczne



Ocena kodu źródłowego



Analiza statystyczna



Przydatne dla programistów i osób zaangażowanych w rozwój programu



Bieżące śledzenie jakości kodu i zwrócenie uwagi na miejsca do uproszczenia/testowania

Metryki rozmiaru:

metryka

opis

Linie kodu



Nie odróżnia trudnych i łatwych części kodu



Premiuje rozwlekły styl pisania programów

Liczba tokenów



Token = podstawowa jednostka składni języka programowania



Tok enem mogą być operatory (słowa kluczowe - akcje) i operandy (stałe, zmienne itd.)



Wagi dla mniej i bardziej znaczących linii kodu

Inne metryki



Jednostki rozmiaru programu większe od linii kodu



Metryki dla większych aplikacji – liczba modułów/funkcji



Metody mierzenia programowania obiektowego (liczba klas i interfejsów)

57. Specyfikacja wymagań funkcjonalnych i niefunkcjonalnych, rola UML w procesie

specyfikowania wymagań.

Określanie wymagań



Celem – określenie wymagań klienta wobec systemu; potem bez użytkownika można tworzyć dalsze etapy



Zamiana celów klienta na określone wymagania realizacji tych celów



Dokumentacja projektowa – wskazanie, jak wejścia systemu powiązać z wyjściami



Konieczny dobry opis wymagań (szczegółowy, zrozumiały, bezsprzeczny)

funkcjonalne

niefunkcjonalne



Opisują funkcje systemu (mogą być wykonywane przy udziale systemów
zewnętrznych)



Język naturalny = sposób opisu wymagań

- Niejednoznaczność - różne interpretacje
- duża elastyczność – 1 treść na wiele sposobów, utrudnienie wykrycia wymagań



kompromis między metodą formalną, a językiem naturalnym – formularz opisu
wymagań (zapis podzielony na konkretne pola = uniknięcie szeregu błędów)



wymagany efekt funkcji, nie jej algorytm



może być bardzo duża



jedne funkcje systemu są podfunkcjami innych, bardziej ogólnych (zapis hierarchiczny
– technika zstępująca – od ogółu do szczegółu -> dekompozycja; jeśli zaczynamy od
szczegółowych funkcji to agregujemy je)



tylko zewnętrzne funkcje systemu



nie rozbijać funkcji systemu na te poziomy funkcji, które są czysto implementacyjne



niektóre funkcje składowe w ramach wielu nadrzędnych



Ograniczenia systemu



Wymagania produktu,
procesu, zewnętrzne



Wykorzystanie tabeli miar =
ilościowy opis pewnych cech
systemu

UML



notacja formalna



Graficzny język do obrazowania, specyfikowania, tworzenia i dokumentowania systemów informatycznych.



pozbawiona wad języka naturalnego, ale notacja ta niezrozumiała dla klienta; uporządkowanie wymagań

58. Model logiczny a model fizyczny systemu – rola w procesie tworzenia oprogramowania.

Model analityczny:



Pokazuje co system ma robić



Jest zorganizowany hierarchicznie, według poziomów abstrakcji



Unika terminologii implementacyjnej



Pozwala na wnioskowanie „od przyczyny do skutku” i odwrotnie

Model analityczny - wady



Wykracza poza zakres odpowiedzialności systemu

- Model posiada elementy nie będące częścią systemu, ale wyjaśniające jego działanie
- nie wiadomo, które elementy modelu realizowane przez oprogramowanie, a które w sposób

sprzętowy

- ograniczenie w środkach

Modelowanie



odpowiedź na wady modelu analitycznego



decyzja, jakie modele tworzyć



od identyfikacji problemu zależy rozwiązanie



różne poziomy szczegółowości modelu, odpowiadanie rzeczywistości



brak idealnych modeli (rozwiązaniem niewielka liczba niezależnych modeli)



model oprogramowania – uproszczony opis modelu analitycznego, z wszystkimi najważniejszymi cechami

- model logiczny i fizyczny

Model logiczny i fizyczny są modelami rozwiązania
Rolą tych modeli jest rozwiązanie problemu, zdefiniowanego na początku (fazy określenia wymagań)

Model logiczny systemu

Model fizyczny systemu



Model analityczny = model logiczny (podstawowy) systemu



Etap projektowania cyklu życia programowania (cel fazy analizy)



Odpowiada na pytanie – jak system ma działać?



Opisuje sposób realizacji przez system postawionych wymagań, ale bez szczegółów
implementacyjnych



Zbiór informacji określający zachowanie się systemu



Model pojęciowy (ze specyfikacji i analizy) dostosowywany do wymagań niefunkcjonalnych



Elementy:

- Lista funkcji systemu
- Określenie zewnętrznych obiektów systemu
- Określenie współzależności między funkcjami systemu



„inwentaryzacja stanu obecnego” (niezbędne porcje danych dla funkcji, połączenia
identycznych funkcji realizowanych na różne sposoby)



Podstawa prac analityczych i projektowania systemu informatycznego



Określa najlepszą strategię dla sposobu implementacji systemu



Unikanie niejednoznaczności



Określa się tu: encje, atrybuty, typy danych, ograniczenia + relacje



Model strukturalny (składowe pasywne – dane, aktywne - operacje) bądź obiektowy
(składowe = dane + operacje; obiekty, klasy …)



Opisany według notacji zgodnej z pewną konwencją



Implementacja konkretnego
modelu logicznego (faza
implementacji)



Cel fazy projektowania



Wynik: projekt
oprogramowania – opis
systemu implementacji



Techniczny projekt
oprogramowania i rozwiązań
sprzętowych



Model fizyczny = kod

59. UML w analizie i projektowaniu – omówienie podstawowych cech notacji.

Notacja graficzna



Diagramy graficzne = szybkie przekazywanie podstawowych informacji



nie pozwala na ukazanie wszystkich szczegółów.



Nadmierne nagromadzenie szczegółów = niska czytelność diagramu graficznego



Notacje graficzne uzupełniane są o dodatkowe informacje tzw. specyfikacje

UML (ang. unified modeling language)



Graficzny język do obrazowania, specyfikowania, tworzenia i dokumentowania systemów informatycznych



Notacja opisująca model o szczególnie ważnej roli



język do specyfikowania, wizualizowania, konstruowania i dokumentacji tzw. „artefactów” oraz czynności
biznesowych lub innych z obszaru działalności człowieka



obrazowania, specyfikowania, tworzenia i dokumentowania elementów powstałych podczas
procesu budowy systemu informatycznego



wspomaga specyfikowanie wszystkich ważnych decyzji analitycznych, projektowych i
implementacyjnych, które muszą być podejmowane w trakcie wytwarzania i wdrażania systemu
informatycznego

nazwa

opis

Artefakt



fizyczny element informacyjny wyprodukowany lub używany w procesie wytwarzania oprogramowania (fragmenty
modeli, bazy danych … )

Klasyfikator



element składowy modelu opisujący jego zachowanie/strukturę



posiada reprezentację geometryczną



przykłady: klasy, aktorzy, przypadki użycia, relacje

Obiekt



kawałek kodu



posiada:

- stan = definiowany przez atrybuty
- zachowanie = operacje i usługi świadczone przez obiekt na żądanie innych obiektów
- tożsamość = unikalna cecha obiektu (2 obiekty mogą być równe, ale nie identyczne)

Klasy



Klasa = opis zbioru obiektów o tych samych atrybutach, związkach i znaczeniu; pewien byt



Symbol: prostokąt



Abstrakcja tego, co można zrobić z każdym obiektem klasy



grupa obiektów o tych samych właściwościach, ograniczeniach i semantyce



deskryptor grupy obiektów o podobnej strukturze, zachowaniu i relacjach



własności

- atrybut = nazwana właściwość klasy; właściwość pewnego modelowanego bytu (określona dla wszystkich

jego wystąpień); klasa może mieć dowolną liczbę atrybutów

- operacja = implementacja pewnej usługi (jej wykonania można zażądać od każdego obiektu klasy)



relacje



Odpowiedzialność klas = zadania klas



Związek = współpraca klas

- Zależność – zmiany 1 elementu wpływają na inny, powiązany z 1
- Uogólnienie – związek między elementem ogólnym a specyficznym (nadklasa-podklasa)
- Dziedziczenie – potomek dziedziczy atrybuty i operacje przodka + jakieś własne; polimorfizm (operacje

potomka o takiej samej sygnaturze jak przodka jest ważniejsza)

- Powiązanie – związek wskazujący że elementy 1 systemu połączone z obiektami innego



Nie każda klasa musi mieć związek

Instancja

danej klasy



obiekt przypisywany do określonej klasy obiektów



asocjacje = zależność łącząca 2 lub więcej klas (instancje)



mnogość – ile instancji 1 klasy jest w relacji do 1 instancji 2-ej klasy



agregacja – rodzaj asocjacji; wskazuje na zawieranie się klas. nadklasa zawiera wszystkie instancje podklasy

generalizacja



związek między klasyfikatorami (klasy, nie instancje); nie definiuje się tam mnogości



wprowadza 6 typów diagramów: struktura stanu, przypadki użycia, wykres (rejestr) stanu, diagram
współpracy, wykres aktywności, wykres implementacji

UML – przypadki użycia



Obrazowanie zachowania systemu, podsystemu lub klasy



Zrozumiały dla użytkownika i programisty



Cele

- Modelowanie otoczenia systemu – wyznaczenie granicy wokół systemu; aktorzy korzystający z

systemu)

- Modelowanie wymagań stawianych systemowi (określenie co system ma robić)



Diagramy przypadków użycia (identyfikacja i uporządkowanie aktorów, )

Statyczny model klas = podejście klasyczne – obserwacja, że w wielu systemach są podobne klasy i obiekty ->
poszukiwanie podobnych klas (przedmioty namacalne, lokalizacje, zdarzenia…)

60. Diagramy stanu oraz diagramy sekwencji, porównanie obszarów stosowania.

Diagram stanów

Diagram sekwencji (interakcji)



Stany jakiegoś elementu, klasy z siecią
przejść między stanami



Nawiązuje do automatu skończonego



Maszyna stanów = stany + przejścia +
zdarzenia + czynności



Stan – pewna, stabilna sytuacja w jakiej
znajduje się dany element; określa
zachowanie się wybranego obiektu



Przejścia do innych stanów mogą
następować pod wpływem określonych
zdarzeń (np. Komunikatów otrzymanych od
innych elementów modelu)



Opis istotnych stanów pewnego procesu
(dla modelu pojęciowego) i przejścia
między stanami (wymuszane przez
wywoływanie usług projektu)



Określa reakcje obiektu na zdarzenia w
czasie jego życia



Dynamiczne aspekty systemu



Świat funkcjonalny + obiektowy



Ciąg interakcji między obiektami systemów



Pokazują następstwo czasowe w sekwencji komunikatów

- Linie życia –pionowe kolumny odnoszące się do obiektów z diagramów

obiektów

- Fragment włączony –sekwencje komunikatów realizowanych iteracyjnie
- Aktorzy również włączeni jako obiekty. Nazwa komunikatu nad strzałkami

obrazującymi ich wymianę. Komunikat powrotny –powrót sterowania



Odpowiada konkretnemu scenariuszowi przypadku użycia



Ważna kolejność komunikatów w czasie



W górnej jego części są obiekty uczestniczące w interakcji



Po lewej stronie – obiekt inicjujący interakcję



Po prawej stronie – obiekty coraz bardziej podrzędne



Komunikaty uporządkowane w czasie wzdłuż osi Y (wcześniejsze wyżej) ->
ułatwienie zrozumienia przepływu sterowania w czasie



Posiadają linie życia obiektów; uwzględnienie ośrodka sterowania



Współpraca obiektów – scentralizowana (kontroluje 1 obiekt) i zdecentralizowana



Modelowanie zachowania interfejsów, klas
i kooperacji



Projektowanie systemów interakcyjnych



Projektanci systemów czasu rzeczywistego



Wykorzystywane przez architektów (projektant) systemu oprogramowania

Te modele używa się do prezentacji systemu w działaniu, jednak brane są inne aspekty

61. Testowanie oprogramowania, omówić model V.

Testowanie oprogramowania



optymistycznie - celem sprawdzenie, czy oprogramowanie spełnia wymagania



pesymistycznie - Celem testowania oprogramowania jest znalezienie błędów



powinno być realizowane zgodnie z przyjętym planem testów



Dwa aspekty błędów:



awaria- oprogramowanie źle realizuje wymagania



usterka – błąd w kodzie programu powodujący awarię



Zasada IEEE: Celem testowania oprogramowania jest takie wyszukiwanie awarii, że gdy oprogramowanie
ulegnie awarii podczas testów, usterki odpowiedzialne za te awarie będą mogły być znalezione i
poprawione

Testowanie jednostek a testowanie systemu



Gdy dany moduł jest zakończony może być testowany na poziomie jednostki przez programistę (cykl test-
poprawianie).



Moduły są łączone w podsystemy i następnie w cały system który jest testowany na poziomie systemu



Testowanie jednostek jest efektem dekompozycji problemu i nie wykrywa błędów w interfejsach pomiędzy
nimi.



Samodokumentowanie się kodu procedur bez ich funkcjonalnej specyfikacji często prowadzi do błędów
(kod jest swoją własną definicją – to nie może być oceniany)



Testowanie jednostek systemu wymaga wprowadzenia tzw. namiastek będącymi pozornymi procedurami
uruchamiającymi testowaną jednostkę. Są to oczywiście warunki odmienne od występujących w
rzeczywistej pracy systemu. Najczęściej namiastki są interaktywnymi interfejsami pomiędzy testowaną
jednostką a testującym ją testerem (człowiekiem). Często stanowią również jednostki tzw. puste nie
robiące nic, a jedynie zwracające sterowanie do jednostki testowanej



Uprzęże testowe, służą automatyzacji testowania jednostek poprzez automatyczne programy testujące np.
typy zmiennych



Testowanie podsystemów - ukryte informacje w danych wewnętrznych prowadzi do losowego zachowania
systemu – wprowadzenie dodatkowych funkcji drukowania czytelnej dla testera wersji struktur
wewnętrznych (polepszanie testowalności kodu)



Testowanie kodu obiektowego – metody klasy obiektowej są podprogramami dostępu i również tutaj
powstaje problem badania danych ukrytych. Pomaga tutaj dziedziczenie – jeżeli metoda nadklasy
dziedziczona przez podklasy była testowana jednostkowo to nie ma potrzeby testowania jej w każdej
podklasie.



Testowanie ciągów wejść do podsystemów – generowanie stanów które powinny być obsłużone przez
system – eliminacja ślepych zaułków

Testowanie systemu



Testy systemowe - ich efekt będzie widoczny dla użytkowników. Inne działania testowe nie będą widoczne
dla użytkowników.



Testowanie integracyjne – przyrostowa metoda integracji systemu, dokładanie kolejnych podsystemów.
Testowanie z „góry” i z „dołu”.



Tak naprawdę dopiero w testowaniu systemowym widać spełnianie wymagań i realizację opracowanych
specyfikacji.



Inspekcja kodu a testowanie jednostki lub podsystemu mają doprowadzić do znalezienia usterki kodzie
jednostki

Model V



Kaskadowy model cyklu życia oprogramowania ma pewne wady (patrz: zadanie 55)



W obliczu wad j.w. poszerzono ten model o rozbudowanie testowania (testy dla każdej fazy; projektowanie
i weryfikacja nie następują zaraz po sobie, ale są wykonywane równolegle)



Stworzone wymagania są podstawą do rozpoczęcia definiowania weryfikacji



Wymagania podlegają analizie, część zespołu sprawdza czy dana idea realizowana



w procesie analizy muszą uczestniczyć testerzy



architekci tworzą specyfikację -> podział systemu na komponenty



lewe ramię = projektowanie



prawe ramię = weryfikacja



Testy końcowe to zazwyczaj tzw. testy akceptacyjne, odpowiadające na pytanie, czy dany produkt spełnia
wymagania klienta.

Zalety i wady systemu V:

zalety

wady

+ Precyzyjnie pokazuje zależności kolejnych etapów projektu
+ Każdy etap projektowania kończy się stworzeniem danych wejściowych dla następnej fazy i

korespondującej z nim fazy weryfikacji

+ Zachęca do jak najwcześniejszego rozpoczęcia procesu tworzenia planów testów, specyfikacji

testowej i samego testowania.

+ Dzięki analizie grafu możemy łatwo zidentyfikować obszary, gdzie stworzona dokumentacja



Mało szczegółowy



Mało wydajny

powinna być sprawdzona

+ Kooperacja między architektami, programistami, klientami …

Wygląd:

projektowanie

weryfikacja

Wymagania

Testy końcowe

Analiza

Testowanie systemu

Architektura projektu

Testowanie interfejsów

Architektura komponentu

Testowanie komponentów

Implementacja

62. Podstawowe pojęcia niezawodności systemów technicznych, niezawodność systemów

oprogramowania, miary niezawodności.

pojęcie

opis

zasoby



Wszystko, co ma wartość dla instytucji



Prawidłowe kierowanie zasobami = główny cel



Przykłady: zasoby fizyczne, dane, oprogramowanie, ludzie …

Zagrożenie



Potencjalna przyczyna niepożądanego incydentu, którego skutkiem może być szkoda dla systemu lub instytucji



Zagrożenie może wykorzystać podatność zasobów celem wyrządzenia szkody



Przykłady: atak (bez)pośredni na informację

Podatność



Słabość zasobu/grupy zasobów, która może być wykorzystana przez zagrożenie

Ryzyko



prawdopodobieństwo określające możliwości wykorzystania określonej podatności przez dane zagrożenie



cel zagrożenia: spowodowanie straty lub zniszczenia zasobu lub grupy zasobów = negatywne (bez)pośrednie
wpłynięcie na instytucję.

Ryzyko
szczątkowe



ryzyko, które pozostaje po wprowadzeniu zabezpieczeń



zabezpieczenia redukują ryzyko tylko częściowo



wszystko, co da się osiągnąć = ryzyko szczątkowe; im więcej chce się osiągnąć, tym większe koszta

Zarządzanie
ryzykiem



całkowity proces identyfikacji, kontrolowania i eliminacji lub minimalizowania prawdopodobieństwa zaistnienia
niepewnych zdarzeń, które mogą mieć wpływ na zasoby systemu informatycznego

Zabezpieczenie



praktyka, procedura lub mechanizm redukujący ryzyko



chronią przed zagrożeniem, wykrywają niepożądane incydenty

Analiza ryzyka



proces identyfikacji ryzyka, określania jego wielkości i identyfikowania obszarów wymagających zabezpieczeń.



identyfikuje ryzyko, które ma być kontrolowane lub zaakceptowane



analiza ryzyka = analiza wartości zasobów, zagrożeń i podatności



ryzyko określane jest przez potencjalne następstwa spowodowane naruszeniem poufności, integralności,
dostępności, rozliczalności, autentyczności i niezawodności

monitorowanie



Używanie zabezpieczeń powinno być monitorowane w celu zapewnienia ich prawidłowego działania,
upewnienia się, czy zmiany w środowisku nie wpłynęły na efektywność działania zabezpieczeń oraz czy
zapewniona jest rozliczalność

Efektywna ochrona = kombinacja różnych zabezpieczeń -> warstwy ochronne dla zasobów

63. Proces zarządzania bezpieczeństwem systemów informatycznych, polityka

bezpieczeństwa.

Zarządzanie bezpieczeństwem systemów informatycznych



Proces, którego celem jest osiągnięcie i utrzymanie odpowiedniego poziomu poufności, integralności,
dostępności, rozliczalności i niezawodności systemów informatycznych

Bezpieczeństwo systemu informatycznego (IT security):



wszystkie aspekty związane z definiowaniem, osiąganiem i utrzymywaniem poufności, integralności,
dostępności, rozliczalności, autentyczności oraz niezawodności



Polityka bezpieczeństwa instytucji w zakresie systemów informatycznych (IT security policy): zasady,
zarządzenia i procedury, które określają jak zasoby – włącznie z informacjami wrażliwymi - są zarządzane,
chronione i dystrybuowane w instytucji i jej systemach informatycznych

Cele, strategie i polityki bezpieczeństwa



Cele, strategie i polityki bezpieczeństwa instytucji powinny być opracowane hierarchicznie od poziomu
instytucji do poziomu eksploatacyjnego.



Powinny odzwierciedlać potrzeby instytucji i uwzględniać wszelkie występujące w instytucji ograniczenia.



Bezpieczeństwo wchodzi w skład odpowiedzialności na każdym poziomie kierowniczym instytucji i w każdej
fazie cyklu życia systemów.



Cele, strategie i polityki powinny być utrzymywane i aktualizowane w oparciu o wyniki cyklicznych
przeglądów bezpieczeństwa (na przykład analizy ryzyka, audytów bezpieczeństwa) oraz zmian w celach
działania instytucji.

Polityka bezpieczeństwa instytucji



Na politykę bezpieczeństwa instytucji składają się podstawowe zasady bezpieczeństwa i wytyczne dla całej
instytucji dot. bezpieczeństwa



Polityka bezpieczeństwa instytucji powinna odzwierciedlać polityki o szerszym zakresie w instytucji, w tym
te, które obejmują prawa jednostki, wymagania prawne i normy.

Polityka bezpieczeństwa systemów informatycznych



Polityka bezpieczeństwa systemów informatycznych powinna odzwierciedlać podstawowe zasady
bezpieczeństwa i zarządzenia wynikające z polityki bezpieczeństwa instytucji oraz ogólne zasady
korzystania z systemów informatycznych w instytucji.

Definicje podstawowe:

pojęcie

opis

Poufność



właściwość zapewniająca, że informacja nie jest udostępniania lub ujawniana nieautoryzowanym
osobom, podmiotom lub procesom.

Integralność systemu



właściwość polegająca na tym, że system realizuje swoją zamierzoną funkcję w nienaruszony sposób,
wolny od nieautoryzowanej manipulacji, celowej lub przypadkowej

Integralność danych



właściwość zapewniająca, że dane nie została zmienione lub zniszczone w sposób nieautoryzowany

Dostępność



właściwość bycia dostępnym i możliwym do wykorzystania na żądanie, w założonym czasie, przez
autoryzowany podmiot

rozliczalność



właściwość zapewniająca, że działania podmiotu mogą być przypisane w sposób jednoznaczny tylko temu
podmiotowi

autentyczność



właściwość zapewniająca, że tożsamość podmiotu lub zasobu jest taka, jak deklarowana.



Autentyczność dotyczy takich podmiotów jak: użytkownicy, procesy, systemy i informacja

niezawodność



właściwość oznaczająca spójne, zamierzone zachowanie i skutki

64. Kryptosystemy symetryczne oraz metody dystrybucji kluczy w systemach

symetrycznych.

Kryptosystem

symetryczny

opis

DES



Opracowany przez IBM, najbardziej popularny



Szyfrowanie 64-bitowe bloki danych



Długość bloku wejściowego = wyjściowego = 64



(de)szyfrowanie wyznacza 64-bitowy klucz



8 bitów = bity parzystości



Aktualnie uznawany za słaby

3DES



Potrójny DES (3-krotny szyfr algorytmem DES – 3 różne klucze)



Bezpieczniejszy



Chroni przed atakami przestrzeni kluczy

IDEA



Alternatywa dla DES, stworzona w Europie



Stosunkowo nowy algorytm

RC4



Algorytm szyfrowania strumieniowego



Opiera się o ciąg pseudolosowych permutacji generowanych z klucza



1 z częściej stosowanych algorytmów szyfrujących

RC5



Blokowy algorytm szyfrujący



Dane szyfrowane w 16, 32 lub 64-bitowych blokach



Długość klucza = parametr



Prosta budowa



Uważany za bezpieczny

RC6



Następca RC5



Blokowy algorytm szyfrujący



Prosta budowa wprost z RC5



Dane szyfrowane 128-bitowym kluczem

AES



Blokowy algorytm szyfrujący



Dane szyfrowane 128, 192 lub 256-bitowym kluczem



Wielkość bloku: 128



Standardowy algorytm szyfrowania symetrycznego

Serpent



Blokowy



Dane szyfrowane 256-bitowym kluczem

Twofish



Blokowy



Dane szyfrowane są 128-, 192- lub 256-bitowym kluczem w 128-bitowych blokach

Blowfish



Klucze o zmiennej długości (do 448 bitów)



bezpieczny

mars



Blokowy



Dane szyfrowane kluczem w 128-bitowych blokach



Długość klucza: 128 – 400 bitów

SAFER



Algorytm blokowy



Wersja z 64bitowym kluczem obejmująca 6 rund i z kluczem 128b o 12 rund

Szyfrowanie i odszyfrowywanie



Szyfrowanie polega na takim przekształceniu wiadomości (tekstu jawnego) by dla osoby trzeciej, różnej od
nadawcy i odbiorcy, stanowiła ona jedynie przypadkowy ciąg znaków, na podstawie którego nie jest
możliwe odtworzenie żadnej użytecznej informacji.



Otrzymany w wyniku szyfrowania ciąg znaków nosi nazwę tekstu zaszyfrowanego (lub inaczej szyfrogramu).



Procesem odwrotnym do szyfrowania, wykonywanym przez odbiorcę wiadomości jest odszyfrowywanie,
pozwalające na odtworzenie tekstu jawnego.

System kryptograficzny



zbiór wszystkich tekstów jawnych (wiadomości), które mogą być zaszyfrowane przy użyciu danego szyfru to
dziedzina przekształceń szyfrujących.



Nowoczesne szyfry zazwyczaj nie wprowadzają żadnych ograniczeń na postać wiadomości podlegającej
szyfrowaniu.



Wiadomość może stanowić dowolny – sensowny lub bezsensowny – ciąg znaków.



W rodzinie przekształceń odszyfrowujących istnieje zazwyczaj tylko jedno przekształcenie odwrotne do
wybranego przekształcenia szyfrującego.



Tylko użycie właściwego klucza po stronie odbiorczej zapewnia odtworzenie zaszyfrowanej wiadomości.

Klucze systemu kryptograficznego



Klucz kryptograficzny wyznacza odpowiednie przekształcenie szyfrujące i/lub odszyfrowujące.



Klucz szyfru jest parametrem, którego wartość decyduje o tym, które odwzorowanie ze zbioru
odwzorowań wyznaczonych przez ogólny algorytm szyfrowania, zostanie użyte do zaszyfrowania lub
odszyfrowania danej wiadomości.



Zbiór możliwych do wyboru kluczy powinien być na tyle liczny, by niemożliwe było (w praktyce)
odtworzenie będącego w użyciu klucza metodą sprawdzenia wszystkich możliwości

Systemy kryptograficzne dzielą się na dwie podstawowe grupy:



Systemy symetryczne (klasyczne) - w systemach tych, zwanych również systemami szyfrowania z kluczem
tajnym nadawca i odbiorca posługują się tym samym kluczem, zarówno do szyfrowania jak i do
deszyfrowania.



Systemy asymetryczne (publicznego klucza) - systemy te, zwane również systemami szyfrowania z kluczem
jawnym, posługują się dwoma oddzielnymi kluczami, przy czym jeden klucz służy do szyfrowania, a drugi
do deszyfrowania.



Para takich kluczy jest przypisana każdemu użytkownikowi sieci

Klasy systemów kryptograficznych

Szyfry blokowe

Szyfry strumieniowe



Jednoczesna transformacja ustalonej porcji (bloku) znaków wiadomości
wejściowej do postaci zaszyfrowanej



Długie wiadomości są wstępnie dzielone na fragmenty odpowiadające długości
podstawowego bloku



Jeśli ostatni fragment (lub krótka wiadomość) ma mniej znaków niż ustalona
długość bloku dla danego szyfru -> konieczność uzupełnienia lub dopełnienia
wiadomości przed szyfrowaniem (wielokrotność długości podstawowego bloku)



Jest kilka metod dopełniania wiadomości (wszystkie rozróżniają na jednoczesne
odróżnienie wiadomości od dopełnienia po stronie odbiorczej)



Jeśli wiadomość generowana współbieżnie z szyfrowaniem = urządzenie
szyfrujące musi czekać aż wygenerowana zostanie liczba znaków odpowiadająca
długości bloku (szyfrowanie i przesłanie zaszyfrowanego bloku)



Szyfrowanie każdego pojawiającego się
na wejściu urządzenia szyfrującego
znaku wiadomości (połączenie go w
pewien odwracalny sposób z
wygenerowanym wewnątrz urządzenia
znakiem klucza)



Kolejne znaki wiadomości łączone są z
kolejno generowanymi znakami klucza -
> szyfruje się „strumień” znaków
wiadomości przy pomocy „strumienia”
znaków danych

65. Kryptografia asymetrycznej w zagadnieniach bezpieczeństwa sieciowych systemów

komputerowych – przykłady zastosowań.

Teoria szyfrowania asymetrycznego – zadanie 64

nazwa

opis

Kryptosystem
RSA



Pierwszy, powszechny algorytm szyfrowania asymetrycznego



oparty jest na trudności obliczeniowej faktoryzacji dużych liczb półpierwszych.



zachowuje poufność i uwierzytelnienie danych (w zależności od szyfrowania kluczem prywatnym, czy
publicznym)



ciąg bitów podawanych na wejście przekształcenia szyfrującego jest traktowany jako duże (rzędu kilkuset cyfr
dziesiętnych) liczba całkowita M.



rolę klucza prywatnego pełni trójka dużych liczb całkowitych SK=(d, p,q)



rolę klucza publicznego pełni para liczb PK=(e ,n)



liczby p i q są dużymi liczbami pierwszymi



liczba n jest iloczynem liczb p i q, n=p⋅q



liczby e i d związane są zależnością: 1=(e⋅d)mod (( p –1)(q – 1))



przy czym musi d spełniać warunek: d< ( p– 1)(q –1)



przeznaczony do szyfrowania i odszyfrowywania n-bitowych loków danych



blok wejściowy i wyjściowy mają taką samą długość; obecnie przyjęte n = 1024 i jest wielokrotnością



Przekształcenie odwrotne wymaga znajomości liczby d (zawartej w kluczu prywatnym i wyznaczone jest przez
algorytm: M=(M ') d mod n.



generowanie kluczy



zaszyfrowanie i deszyfrowanie -> korzystamy z pierwotnych wzorów:

o Tekst zaszyfrowany=(tekst jawny )mod n
o Tekst niezaszyfrowany=(tekst zaszyfrowany)mod n



standard do podpisów cyfrowych

El Gammal



wariant systemu Diffiego – Hellmana (rozszerzenie)



1 algorytm szyfrujący i 1 uwierrzytelniający

Zaawansowane metody szyfrowania asymetrycznego



Algorytmy wykorzystujące dyskretne krzywe eliptyczne (ECC, Elliptic Curve Cryptosystems) opierają się na
innych zasadach matematycznych niż podzielniki czy dyskretny problem logarytmiczny



ECC są pod pewnymi względami lepsze niż RSA czy Diffie-Hellman - klucze są mniejsze, a tym samym
obliczenia przebiegają szybciej przy takim samym poziomie bezpieczeństwa .



Takie samo zabezpieczenie przy 1024-bitowym dla RSA można osiągnąć w ECC przy kluczu 160-bitowym.
Algorytmy wielomianowe oparte na trudnościach obliczeniowych tzw. pierścieni wielomianów ciał
skończonych.

66. Podpis elektroniczny a podpis cyfrowy, definicje, przykłady zastosowań.

elektroniczny

cyfrowy



Podpisanie dokumentu przez osobę fizyczną



Dane w postaci elektronicznej



Wraz z innymi danymi, do których został
dołączony/logicznie powiązany służy do identyfikacji osoby
składającej podpis elektroniczny



Równoważny pod względem skutków prawnych
dokumentowi podpisanego własnoręcznie (jeśli jest tzw.
Elektronicznym podpisem bezpiecznym)



Matematyczny sposób potwierdzenia autentyczności
cyfrowego dokumentu



Najpowszechniejszy – schemat podpisu dokumentów
cyfrowych w systemach kryptograficznych z kluczem
publicznym i 1-kierunkową funkcją skrótu (do wiadomości
dołącza się skrót dokumentu, zaszyfrowany prywatnym
kluczem nadawcy)

Zgodnie z ustawą bezpieczny podpis elektroniczny to podpis elektroniczny, który:



jest przyporządkowany wyłącznie do osoby składającej ten podpis



jest sporządzany za pomocą podlegających wyłącznej kontroli osoby składającej podpis elektroniczny
bezpiecznych urządzeń służących do składania podpisu elektronicznego i danych służących do składania
podpisu elektronicznego



jest powiązany z danymi, do których został dołączony, w taki sposób, że jakakolwiek późniejsza zmiana tych
danych jest rozpoznawalna.

Przykłady zastosowań:



deklaracje podatkowe



deklaracje ZUS



odwołania w postępowaniu administracyjnym

67. Zapory ogniowe – pojęcia podstawowe, obszary zastosowań.

Zapora sieciowa



Sposób zabezpieczania sieci i systemów przed intruzami



Odnosi się zarówno do dedykowanego sprzętu komputerowego i do specjalnego oprogramowania
blokującego dostęp do komputera



Ochrona sprzętowa + programowa sieci LAN przed dostępem z zewnątrz (i danych na zewnątrz)



Często komputer z odpowiednim oprogramowaniem – filtrowanie połączeń wchodzących i wychodzących =
odmowa żądań dostępu uznanych za niebezpieczne



Najczęstsze techniki obrony



Filtrowanie pakietów (akceptowanie pakietów)



Stosowanie algorytmów identyfikacji użytkownika



Zabezpieczanie programów obsługujących niektóre protokoły (FTP, TELNET)



Monitoruje ruch sieciowy i zapisuje zdarzeń do logu (możliwość zmian w konfiguracji)



Można zdefiniować strefę ograniczonego zaufania = podsieć izolującą od wewnętrznej sieci lokalne serwery
udostępniające usługi z zewnątrz

68. Systemy wykrywania zagrożeń (IDS) – koncepcja, zasady lokalizacji sondy.

IDS, IPS (ang. Intrusion Detection System, Intrusion Prevention System – systemy wykrywania i zapobiegania
włamaniom) – urządzenia sieciowe zwiększające bezpieczeństwo sieci komputerowych przez wykrywanie (IDS)
lub wykrywanie i blokowanie ataków (IPS) w czasie rzeczywistym

Typowe elementy systemu IDS/IPS to:



sonda (ang. sensor) – element analizujący ruch sieciowy i wykrywający ataki



baza danych – zbierająca informacje o atakach z grupy sensorów



analizator logów – umożliwiający wizualizację i analizę logów z grupy sensorów

Architektura



zależy od lokalizacji sondy i zakresu analizowanych zdarzeń



rodzaje:

Hostowe (ang. Host-based IDS)

sieciowe(ang. Network IDS)



działają jako aplikacja w jednym,
ochranianym systemie
operacyjnym analizując
zdarzenia pochodzące z logu
systemowego oraz z lokalnych
interfejsów sieciowych



analizują ruch sieciowy dla wszystkich systemów w segmencie sieci, do którego są
podłączone



potrafi rozpoznawać ataki skierowane przeciwko systemom, które nie mają zainstalowanych
HIDS



Równocześnie jednak ma ograniczone zdolności analizowania ruchu przesyłanego w
kanałach SSL lub zdarzeń zachodzących lokalnie w systemie (np. brak pamięci, ataki lokalne
z konsoli)

Sieciowe systemy IPS mogą działać w następujących topologiach sieciowych:

pasywna sonda

Inline



podłączona do portu monitorującego przełącznika analizuje
kopie wszystkich pakietów w danym segmencie sieci



Sonda w tej topologii ma ograniczone możliwości reagowania
na ataki



techniki blokowania ataków w topologii pasywnej



wysyłanie fałszywych pakietów TCP RST do obu stron
komunikacji i zerwanie połączenia (blokowany tylko TCP)



dynamiczna rekonfiguracja zapory, z którą sonda może
współpracować (możliwość spóźnienia reakcji)



umieszczona pomiędzy dwoma segmentami sieci, pozbawiona
adresów IP i działająca w trybie przezroczystego mostu
analizuje i bezpośrednio uczestniczy w przekazywaniu
wszystkich pakietów w sieci



sonda ma możliwość blokowania 100% pakietów rozpoznanych
jako niebezpieczne (fałszywe pakiety TCP RST nadal są
wysyłane dla uniknięcia retransmisji).



Działanie w tym trybie nakłada na oprogramowanie sondy
znacznie wyższe wymagania co do wydajności i stabilności

69. Wirtualne sieci prywatne (VPN) - koncepcja, przykłady zastosowań, stosowane

protokoły.

VPN



tunel, przez który płynie ruch w ramach sieci prywatnej pomiędzy klientami końcowymi za pośrednictwem
publicznej sieci (takiej jak Internet) w taki sposób, że węzły tej sieci są przezroczyste dla przesyłanych w ten
sposób pakietów



Można opcjonalnie kompresować lub szyfrować przesyłane dane w celu zapewnienia lepszej jakości lub
większego poziomu bezpieczeństwa



Określenie "Wirtualna" oznacza, że sieć ta istnieje jedynie jako struktura logiczna działająca w
rzeczywistości w ramach sieci publicznej, w odróżnieniu od sieci prywatnej, która powstaje na bazie
specjalnie dzierżawionych w tym celu łącz.



Pomimo takiego mechanizmu działania stacje końcowe mogą korzystać z VPN dokładnie tak jak gdyby
istniało pomiędzy nimi fizyczne łącze prywatne.



Rozwiązania oparte na VPN stosowane są np. w sieciach korporacyjnych firm, których zdalni użytkownicy
pracują ze swoich domów na niezabezpieczonych łączach.



Wirtualne Sieci Prywatne charakteryzują się dość dużą efektywnością, nawet na słabych łączach (dzięki
kompresji danych) oraz wysokim poziomem bezpieczeństwa (ze względu na szyfrowanie).



Rozwiązanie to sprawdza się w firmach, których pracownicy często podróżują lub korzystają z możliwości
telepracy

Protokoły

protokół

opis

IPSec



Najbardziej uniwersalny, ale mający też największe ograniczenia



Nadaje się do stworzenia wszystkich rodzajów VPNów



W wersji podstawowej nie radzi sobie z NATem i musi znać konfigurację zdalnej sieci.



zbiór protokołów stworzony w celu implementacji bezpiecznych połączeń pomiędzy komputerami



Protokół IP nie gwarantuje iż otrzymane datagramy:
– pochodzą od deklarowanego nadawcy
– zawierają dane, które były umieszczone w nim przez nadawcę
– ich zawartość nie został zmieniona

Tryb transportu

– Tryb transferu jest trybem domyślnym protokołu IPSec.
– Służy do ustanawiania komunikacji typu dwupunktowego (klient – serwer).
– Typowy tryb przy komunikacji software – urządzenie.
– W tym trybie szyfrowaniu podlega wyłącznie ładunek UP.
– IPSec zapewnia ochronę datagramów IP oraz protokołów warstw wyższych przy pomocy protokołów ESP i AH.

Tryb tunelowania

– W trybie tunelowania protokołu IPSec szyfrowane są nagłówek i ładunek IP (w trybie transportu szyfrowany jest
tylko ładunek IP).
– Tryb tunelowania zapewnia ochronę całego pakietu UP, traktując go jako ładunek AH lub ESP.
– W trybie tunelowania cały pakiet jest enkapsulowany za pomocą nagłówka AH lub ESP i uzupełniany dodatkowym
nagłówkiem IP.
– Adresy IP określone w zewnętrznym nagłówku IP są punktami końcowymi tunelu, a adresy IP określone w
enkapsulowanym nagłówku IP są ostatecznymi adresami-źródłowym i docelowym.
– Tryb tunelowania protokołu IPSec jest użyteczny do ochrony ruchu między....

L2TP



opcjonalnie wykorzystuje IPSec do zapewnienia poufności (szyfrowania).



Zazwyczaj Client-to-Site, prosta konfiguracja i autoryzacja na podstawie loginu i hasła



Wyraźny podział na serwer (router) i klienta (zdalny komputer). Serwer musi mieć publiczny (routowalny) adres IP, klient
może być za NATem, pod warunkiem, że router dostępowy w jego sieci obsługuje (i ma aktywną) funkcję L2TP Pass-
Through.



Ten sam problem co z IPSec - protokół ESP.

PPTP



Najmniej konfliktowy



Najniższy poziom bezpieczeństwa



GRE – protokół do transmisji danych



Autoryzacja na podstawie loginu i hasła



Autoryzacja przez MS-CHAP, opcjonalne szyfrowanie przez MPPE. Reszta zasad jak w L2TP

70. Wyjaśnij określenie "exploitation-exploration trade-off" w kontekście próby definicji

sztucznej inteligencji.



Trudność definicji sztucznej inteligencji



Wskazuje się na wspólne cechy będące mianownikami SI



Inteligentny system wykorzystuje wiedzę na temat problemu (exploitation) = wykorzystanie tego co już
wiemy w celu rozwiązania



System musi dążyć do poznania nowego (exploration)



Dobrze skonstruowany system, powinien odpowiednio wyważyć ile zasobów poświęcić na exploitation i
exploration zarazem

71. Na czym polega uczenie sieci neuronowej algorytmem typu backpropagation.

Jest to uczenie z nadzorem lub inaczej – z nauczycielem.
Pierwszą czynnością w procesie uczenia jest przygotowanie dwóch ciągów danych: uczącego i weryfikującego.
Ciąg uczący jest to zbiór takich danych, które w miarę dokładnie charakteryzują dany problem. Jednorazowa

porcja danych nazywana jest wektorem uczącym. W jego skład wchodzi wektor wejściowy, czyli te dane
wejściowe, które podawane są na wejścia sieci i wektor wyjściowy czyli takie dane oczekiwane, jakie sieć
powinna wygenerować na swoich wyjściach. Po przetworzeniu wektora wejściowego, nauczyciel porównuje
wartości otrzymane z wartościami oczekiwanymi i informuje sieć czy odpowiedź jest poprawna, a jeżeli nie, to
jaki powstał błąd odpowiedzi. Błąd ten jest następnie propagowany do sieci ale w odwrotnej niż wektor
wejściowy kolejności (od warstwy wyjściowej do wejściowej) i na jego podstawie następuje taka korekcja wag
w każdym neuronie, aby ponowne przetworzenie tego samego wektora wejściowego spowodowało
zmniejszenie błędu odpowiedzi. Procedurę taką powtarza się do momentu wygenerowania przez sieć błędu
mniejszego niż założony. Wtedy na wejście sieci podaje się kolejny wektor wejściowy i powtarza te czynności.
Po przetworzeniu całego ciągu uczącego (proces ten nazywany jest epoką) oblicza się błąd dla epoki i cały cykl
powtarzany jest do momentu, aż błąd ten spadnie poniżej dopuszczalnego.

Uczenie sieci można przeprowadzić dwoma metodami:



on-line - polega na modyfikacji wag po wczytaniu każdej danej wejściowej



off-line - polega na modyfikacji wag po wczytaniu wszystkich danych wejściowych

72. Omów podstawowe metody bezstratnej i stratnej kompresji danych.

Kompresja stratna

Kompresja bezstratna



X

in

X

out



Wyższy poziom upakowania



metoda zmniejszania liczby
bitów potrzebnych do wyrażenia
danej informacji, które nie dają
gwarancji, że odtworzona
informacja będzie identyczna z
oryginałem



Dla niektórych danych algorytm
kompresji stratnej może
odtworzyć informację w sposób
identyczny.



Używa niedoskonałości ludzkich
zmysłów



Algorytmy kompresji stratnej ->
modele psychoakustyczne i
psychowizualne -> odrzucenie
najmniej istotnych danych o
dźwięku, obrazie



pozostawiają dane o wyższej
wartości dla rozpoznawania tej
informacji (akustycznej,
wizualnej) przez zmysły



stopień kompresji = ilość
odrzucanych danych



brak algorytmów kompresji
stratnej dla dowolnego typu
danych (np. pliki)



zastosowania: obrazy, dźwięki,
mowa, sekwencje video



dane wizualne – osobna
kompresja dźwięku i obrazu



X

in

=X

out



Stosowana tam, gdzie nie można dopuścić do różnicy między danymi a ich
rekonstrukcji



Typowe zastosowanie – tekst, rekordy bazy danych a także obrazy, które podlegają
dalszej obróbce (zdjęcia rentgenowskie, zdjęcia satelitarne itp.)



ogólna nazwa metod kompresji informacji do postaci zawierającej zmniejszoną
liczbę bitów, pod warunkiem że metoda ta gwarantuje możliwość odtworzenia
informacji z postaci skompresowanej do identycznej postaci pierwotnej.



dobrze kompresują "typowe" dane (ze znaczną nadmiarowością informacji
(redundancji))



Pewne rodzaje danych są bardzo trudne lub niemożliwe do skompresowania:

- strumienie liczb losowych (niemożliwe do skompresowania)
- strumienie liczb pseudolosowych (trudne do skompresowania, choć

teoretycznie łatwe)

- dane skompresowane za pomocą tego samego lub innego algorytmu (w

praktyce trudne)



Najczęściej używane metody kompresji bezstratnej: na słownikowe i statystyczne,
choć wiele metod lokuje się pośrodku:

- metody słownikowe - poszukiwanie dokładnych wystąpień danego ciągu

znaków, np. zastępują 'the ' krótszą ilością bitów niż jest potrzebna na
zakodowanie 4 niezwiązanych znaków. Jednak znajomość symbolu 'the '
nie pociąga za sobą usprawnień w kompresowaniu 'they' czy 'then'.

- metody statystyczne - mniejsza ilości bitów dla częściej występujących

symboli, w przypadku praktycznie wszystkich oprócz najprostszych metod,
prawdopodobieństwa zależą od kontekstu. A więc np. dla 'h'
występującego po 't' używają mniejszej ilości bitów niż dla innych znaków
w tym kontekście.

Popularne metody



kodowanie Shannona, Shannona-Fano, Huffmana, arytmetyczne



LZ77, LZ78 i pochodne (LZSS, LZP, LZW, LZMW, LZAP)



RLE



PPM



transformata Burrowsa-Wheelera, Move To Front



kodowanie transformacyjne



maskowanie (przesłanianie



Metody kodowania długości serii (zastępowanie serii jednakowych znaków jednym
opisem)

brzmienia dźwięków)



kodowanie różnicowe
(nadmiarowość przestrzenna)



- unikatowej wartości (ciąg znaków dzielony na podciągi i potem od nowa

kodowany )

- unikatowych bitów (łączy wartość podciągu z licznikiem powtórzeń w 1 daną)
- dwóch serii (dane dzielone na serie danych powtarzających się/swobodnych)



Metoda Huffmana – metoda probabilistyczna, rozkład prawdopodobieństwa ->
tworzy się niezrównoważone drzewo binarne



Metoda arytmetyczna – rozkład występowania elementów z kodowanego zbioru
(dystrybuanta, tam sumowanie prawdopodobieństw)



Metody słownikowe – wykorzystują istnienie powtarzających się sekwencji symboli

- LZ77 – słownik wewnętrzny (zapisuje na wyjściu gdzie i jak długa sekwencja)
- LZW– słownik zewnętrzny (dynamiczna tablica kodowa, po starcie procesu na

wejściu symbole otrzymują kody)

metoda

opis

LZ77



kompresja bezstratna



Prosta metoda adaptacyjna, nie wymaga wcześniejszej wiedzy o charakterze źródła



Kodowanie czasochłonne (dużo porównań); dekodowanie proste i szybkie



Nieduże wymagania dotyczące pamięci



Asymptotycznie – wyniki najlepsze jakie można uzyskać przy pełnej częstości pojawiania się znaków i korelacji
między nimi



Można zastosować różne modyfikacje algorytmu (zwiększenie efektywności)

LZSS



Kompresja bezstratna



Odmiana LZ77



Redundancja – albo nie trzeba pointera (bo jest zerowy), albo kodu znaku (może być przekazany w następnym
wejściu)

Pkzip,

Zip, gzip,

ARJ,

LHarc



Kompresja bezstratna



poprawa efektywności kodowania – kodowanie trójek (lub dwójek liczb) kodowaniem o zmiennej długości

LZ78



Szybsze kodowanie niż LZ77 (znacznie mniej porównań stringów)



Łatwe dekodowanie (choć wolniejsze niż dla LZ77 – konieczność odbudowy słownika)



Wzorce są stale dodawane do słownika (1 wzorzec na jeden proces kodowania) i nie zapominane –
niebezpieczeństwo przepełnienia pamięci



Jest punktem wyjścia dla algorytmów pochodnych – najbardziej znany algorytm LZW.

LZW



Kompresja bezstratna



Zastosowanie: format GIF, kompresja danych wysyłanych przez modem

Kompresja stratna:

obraz

video

dźwięk



JPEG, podstawa algorytmu
MPEG, oparty na DCT i dający
relatywnie słabe rezultaty;
wykorzystuje ograniczenia
ludzkiego wzroku -> lepsza
kompresja, możliwe
odwzorowanie kolor 24-
bitowego; opis zdjęć i
naturalnych obrazów;
użytkownik określa stopień
kompresji



JPEG2000, oparty na falkach,
dający znacznie lepsze wyniki



DivX/XviD, przy odpowiednich
warunkach może skompresować
zawartość płyty DVD na zwykłą CD, bez
widocznych różnic.



MPEG, jedną z jego odmian stosuje się
przy filmach na DVD, bardzo wysoka
jakość, połączona z większymi
objętościowo plikami (100MB DivX =
ok. 350MB MPEG).



Real Video, niską jakość obrazu
rekompensuje mała objętość dzięki
czemu wykorzystywany jest przy
transmisjach na żywo.



MP3, najpopularniejsze kodowanie
stratne audio, oparte na MDCT,
stosuje model psychoakustyczny
Instytutu Fraunhoffera i firmy
Thomson.



Ogg Vorbis, oparte na MDCT



Real Audio, podobnie jak Real Video,
rekompensuje straty jakości małą
objętością, jest stosowany głównie do
transmisji na żywo.

Kompresja bezstratna

obraz

video

dźwięk



GIF – prezentacja 8-bitowego koloru,
umożliwia wyświetlanie przeplotem;
GIF89a – zapis animacji



TIFF – mechanizm wymiany danych
rastrowych w sposób niezależny od
platformy, zapis wielu typów obrazów;
kompresja lub bez kompresji
(bestratna)



PNG – wszystkie typy grafiki rastrowej,
lepsza od kompresji GIF, 2-wymiarowy
przeplot, brak możliwości animacji

73.

Wymień standardowe metody kompresji sygnałów multimedialnych: obrazów
nieruchomych, dźwięku, video. Omów dokładniej jedną z nich.

Kompresja obrazków
JPEG
Najbardziej powszechnym algorytmem kompresji obrazów jest JPEG. Wiele rozwiązań użytych w JPEG jest
używanych także w innych algorytmach, więc warto je tutaj omówić. Kolejne kroki algorytmu JPEG to:



zamiana przestrzeni kolorów z RGB na kanał jasności i dwa kanały koloru. Ludzie znacznie dokładniej
postrzegają drobne różnice jasności od drobnych różnic barwy, a więc użyteczne jest tutaj użycie różnych
parametrów kompresji. Krok nie jest obowiązkowy.



obniżenie rozdzielczości kanałów koloru, zwykle odrzuca się co drugą wartość wzdłuż osi poziomej i każdą
na pionowej, choć możliwe są też inne ustawienia. Tak radykalne cięcie danych nieznacznie wpływa na
jakość, ponieważ rozdzielczość postrzegania kolorów przez ludzkie oko jest słaba. Krok nie jest
obowiązkowy.



podzielenie każdego kanału obrazka na bloki 8x8. W przypadku kanałów kolorów, jest to 8x8 aktualnych
danych, a więc zwykle 16x8.



transformata kosinusowa każdego z bloków. Zamiast wartości pikseli mamy teraz średnią wartość
wewnątrz bloku oraz częstotliwości zmian wewnątrz bloku, obie wyrażone przez liczby
zmiennoprzecinkowe. Transformata DCT jest odwracalna, więc na razie nie tracimy żadnych danych.



Zastąpienie średnich wartości bloków przez różnice wobec wartości poprzedniej. Poprawia to w pewnym
stopniu współczynnik kompresji.



Kwantyzacja, czyli zastąpienie danych zmiennoprzecinkowych przez liczby całkowite. To właśnie tutaj
występują straty danych. Zależnie od parametrów kompresora, odrzuca się mniej lub więcej danych.
Zasadniczo większa dokładność jest stosowana do danych dotyczących niskich częstotliwości niż wysokich
kodowanych algorytmem Huffmana.

Użyta transformata powoduje efekty blokowe w przypadku mocno skompresowanych obrazków.


Kompresja dźwięku

Dwa najpopularniejsze publicznie dostępne algorytmy - MP3 i Vorbis, używają podobnych technik. Warto tu
omówić algorytm Vorbis, ponieważ używa on bardziej efektywnych rozwiązań.



Strumień jest dzielony na okna. Okna występują w dwóch rozmiarach - duże (zwykle 2048 próbek) i małe
(zwykle 256 próbek). Małe służą do przedstawienia szybko zmieniającego się dźwięku oraz nagłego wzrostu
intensywności dźwięku w danej częstotliwości. Nie używa się ich w przypadku spadków intensywności,
ponieważ ludzkie ucho jest na nie znacznie mniej czułe. Okna nie są po prostu grupą kolejnych wartości
natężenia dźwięku. Okna częściowo się nakrywają i jedna wartość należy w tych obszarach częściowo do

kilku okien. Dla obszarów zachodzenia na siebie okien, dana wartość należy do lewego okna w stopniu
sin(pi/2 × sin2(pi/2 × t)), gdzie t=0 dla początku obszaru i t=1 dla jego końca.



Na każdym oknie jest przeprowadzana zmodyfikowana transformata kosinusowa. Zamiast poszczególnych
wartości mamy teraz w bloku widmo parametrów MDCT czyli (pomijając szczegóły) częstotliwości.



Dane z MDCT są upraszczane zależnie od parametrów kompresji zgodnie z modelem psychoakustycznym.



Dane o energii przypadającej na daną częstotliwość są skalowane, co umożliwia równie dobrą kompresje
głośnych jak i cichych dźwięków.



Dane są kwantyfikowane i kompresowane bezstratnie.