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