Opracowanie Skrócone BJ

mod by B-art-eq

PYTANIA NA EGZAMIN DYPLOMOWY, STUDIA I STOPNIA INŻYNIERSKIE, KIERUNEK

INFORMATYKA, SPECJALNOŚĆ INŻYNIERIA SYSTEMÓW INFORMATYCZNYCH oraz

INFORMATYKA OGÓLNA

(obowiązuje na egzaminie inżynierskim od lutego 2011)

Spis treści

Algorytm. Własności algorytmu. Prezentacja algorytmu. ........................................................................ 5

Złożoność algorytmów. ........................................................................................................................................ 5

Problemy sortowania. Przykłady algorytmów sortowania i ich złożoność. ....................................... 6

Drzewa przeszukiwań binarnych. Sposób wykonywania na nich podstawowych operacji

(dodawanie, wyszukiwanie, usuwanie)........................................................................................................... 7

Algorytmy przeszukiwania grafu. ..................................................................................................................... 8

Abstrakcyjne struktury danych: listy, kolejki, stosy. Ich implementacja komputerowa. ................ 9

Zasada działania i sposoby implementacji tablic haszowanych. ......................................................... 10

Idea algorytmu zachłannego. Przykład. ....................................................................................................... 11

Idea Dijkstry algorytmu znajdowania najkrótszej ścieżki. ...................................................................... 12

10.

Pozycyjne systemy liczbowe (binarny, dziesiętny, szesnastkowy). Prezentacja liczb

w komputerze. ...................................................................................................................................................... 12

11.

Budowa komputera ............................................................................................................................................. 13

12.

Struktura procesora. ............................................................................................................................................ 14

13.

Cykl rozkazowy procesora ................................................................................................................................. 14

14.

Metody odwzorowania pamięci głównej w pamięci podręcznej. ....................................................... 15

15.

Przetwarzanie potokowe. .................................................................................................................................. 16

16.

Porównanie różnych architektur sieci komputerowych ......................................................................... 16

17.

Funkcje warstwy łącza danych modelu OSI. ............................................................................................... 18

18.

Funkcje warstwy sieci modelu OSI. ................................................................................................................ 18

19.

Dynamiczne przydzielanie adresów............................................................................................................... 19

20.

Protokoły połączeniowe i bezpołączeniowe. ............................................................................................. 19

21.

Tryby FTP. ................................................................................................................................................................ 20

22.

Podstawowe pojęcia baz danych. Baza Danych. Funkcje bazy danych. Właściwości bazy

danych. Modele baz danych. ........................................................................................................................... 21

23.

System zarządzania bazami danych. Funkcje systemu. Przykłady SZDB. ......................................... 22

24.

Model relacyjny baz danych. Relacje, klucze główne i obce, integralność referencyjna. ........... 22

25.

Modelowanie baz danych. Diagram związków encji. ............................................................................. 24

26.

Język baz danych SQL. Podjęzyki DDL, DML, DCL. ................................................................................. 25

27.

Instrukcja SELECT. ................................................................................................................................................. 26

28.

Instrukcje DDL i DCL. ........................................................................................................................................... 27

29.

Indeksy w bazach danych, podział indeksów , B+-drzewo. .................................................................. 27

30.

Normalizacja., cel normalizacji, postać normalna Boyce'a-Codda. .................................................... 28

31.

Transakcje, własności transakcji. ..................................................................................................................... 29

mod by B-art-eq

32.

Diody półprzewodnikowe. Tranzystory. ....................................................................................................... 30

33.

Układy scalone. ..................................................................................................................................................... 31

34.

Układy impulsowe. ............................................................................................................................................... 31

35.

Układy cyfrowe. ..................................................................................................................................................... 32

36.

Pamięci półprzewodnikowe, magnetyczne, optyczne. ........................................................................... 33

37.

Przetworniki analogowo-cyfrowe i cyfrowo-analogowe........................................................................ 34

38.

Metody pomiarów wielkości elektrycznych. ............................................................................................... 34

39.

Metody pomiarów wielkości nieelektrycznych. ......................................................................................... 35

40.

Generatory kwarcowe – czas i częstotliwość w komputerze ................................................................ 36

41.

Grafy. Grafy eulerowskie i hamiltonowskie. ............................................................................................... 36

42.

Kolorowanie grafów, definicja liczby chromatycznej grafu i indeksu chromatycznego. ............ 37

43.

Ciąg Fibonacciego. Definicja rekurencyjna i wzór ogólny. .................................................................... 38

44.

Grafy planarne. ...................................................................................................................................................... 39

45.

Drzewa spinające grafu. Minimalne drzewa spinające. .......................................................................... 40

46.

Typy zmiennych. Podział. Przykłady w wybranym języku programowania. .................................... 40

47.

Rodzaje pętli. Uwarunkowanie zastosowań. Problem równoważności pętli w wybranym

języku programowania. ..................................................................................................................................... 41

48.

Zmienne typu adresowego (wskaźniki). Implementacja w wybranym języku programowania.43

49.

Funkcje (z wzmianką o procedurach). Przekazywanie parametrów przez wartość i referencję

lub adres. ................................................................................................................................................................ 43

50.

Cechy programowania strukturalnego. Kluczowe różnice między programowaniem

strukturalnym a obiektowym. ......................................................................................................................... 44

51.

Zalety języków programowania obiektowo orientowanych. Składniki klasy. Konstruktory i

destruktory. Podać przykłady. ......................................................................................................................... 44

52.

Zastosowanie składników statycznych w klasie. Statyczne funkcje składowe. Podać przykłady.46

53.

Dziedziczenie. Dostęp do składników klasy. Kolejność wywołania konstruktorów. Przypisanie

i inicjalizacja obiektów w warunkach dziedziczenia. ............................................................................... 47

54.

Polimorfizm. Deklarowanie funkcji wirtualnych. Mechanizm wywołania. Podać przykłady. ..... 48

55.

Definiowanie szablonu klasy. Korzystanie z szablonu............................................................................. 50

56.

Cykl pracy procesora przy wykonaniu programu. .................................................................................... 50

57.

Procesy, zarządzanie procesami. .................................................................................................................... 51

58.

Metody przydziału pamięci operacyjnej procesowi. Organizacja pamięci wirtualnej. ................ 52

59.

Funkcje systemowe – podstawowe kategorie, przykłady. ..................................................................... 53

60.

Szeregowanie procesów. Wybrane algorytmy szeregowania. ............................................................. 54

61.

Synchronizacja procesów współbieżnych. Semafory. ............................................................................. 55

62.

Cykle projektowania i życia oprogramowania. .......................................................................................... 56

63.

Klasyfikacja narzędzi wspierających wytwarzanie oprogramowania. ............................................... 56

64.

Metody oraz strategie testowania oprogramowania. ............................................................................ 58

65.

Instalacja i konserwacja oprogramowania. ................................................................................................. 59

66.

Zagadnienia etyczne i prawne związane z procesem wytwarzania i użytkowania

oprogramowania. ................................................................................................................................................ 59

mod by B-art-eq

67.

Etapy cyklu życia systemu informatycznego i ich charakterystyka ................................................... 60

68.

Modele organizacyjne wytwarzania systemów informatycznych i ich charakterystyka – zalety i

wady. ........................................................................................................................................................................ 62

69.

Istota i znaczenie fazy strategicznej w realizacji przedsięwzięć informatycznych. ...................... 63

70.

Metody identyfikacji wymagań na systemy informatyczne i ich charakterystyka. ..................... 63

71.

Znaczenie modelowania obiektowego funkcjonowania informatyzowanej organizacji

w ustalaniu wymagań na system informatyczny. ..................................................................................... 65

72.

Pożądana zawartość dokumentu „Wymagania na system informatyczny”. ................................... 65

73.

Podstawowe rezultaty fazy modelowania systemu. ................................................................................ 66

74.

Podstawowe zadania realizowane w procesie budowy obiektowego modelu systemu

informatycznego. ................................................................................................................................................. 66

75.

Rodzaje modyfikacji wprowadzanych w fazie pielęgnacji systemu informatycznego. ............... 67

76.

Działania na zbiorach. ......................................................................................................................................... 67

77.

Rachunek zdań. ..................................................................................................................................................... 69

78.

Działania na macierzach. ................................................................................................................................... 70

79.

Układy równań liniowych – twierdzenie Kroneckera-Capelliego, wzory Cramera. ....................... 71

80.

Pojęcie relacji i funkcji. ....................................................................................................................................... 73

81.

Własności relacji: relacje porządkujące; relacje równoważności. ........................................................ 73

82.

Własności funkcji: miejsca zerowe, ciągłość, pochodna. ....................................................................... 74

83.

Zmienna losowa i jej charakterystyki liczbowe. ......................................................................................... 74

84.

Cel i rodzaje programowania deklaratywnego. ......................................................................................... 75

85.

Definicje unifikatora (podstawienia uzgadniającego), najogólniejszego unifikatora, algorytm

unifikacji i twierdzenie o unifikacji. ............................................................................................................... 76

86.

Programy Horna, SLD-rezolucja, odpowiedzi poprawne, odpowiedzi obliczone, poprawność i

zupełność SLD-rezolucji. ................................................................................................................................... 77

87.

Zasada rezolucji liniowej w programowaniu w logice. ........................................................................... 78

88.

Budowa programu w Prologu: klauzule (fakty, reguły), definicje predykatów. Sposób realizacji

programu................................................................................................................................................................ 79

89.

Co to są systemy (zestawy) funkcjonalnie pełne? Podać przykładowe. ........................................... 80

90.

Podaj rodzaje układów sekwencyjnych oraz różnice w procedurach ich projektowania. .......... 80

91.

Jakie znasz elementy pamięciowe stosowane układach sekwencyjnych? ....................................... 82

92.

Co oznacza termin mikroprogramowanie? Do czego służy? ............................................................... 82

93.

Podaj znane zapisy liczbowe i zakres ich stosowania. ............................................................................ 83

94.

Co to są mikrokontrolery? ................................................................................................................................. 83

95.

Jakie parametry są charakterystyczne dla pamięci dynamicznych? ................................................... 84

96.

Podaj tryby adresowania dla rozkazów mikrokontrolera i odpowiadający im czas trwania

cyklu instrukcyjnego wraz z omówieniem kolejnych cykli maszynowych. ...................................... 85

97.

Jakie znasz rodzaje transmisji szeregowej i na czym one polegają? ................................................. 85

98.

Porównaj pod względem szybkości znane rozwiązania operacji mnożenia w systemach

wbudowanych. ...................................................................................................................................................... 86

99.

Model obliczeniowy perceptronu – możliwości i ograniczenia. .......................................................... 86

mod by B-art-eq

100. Metody uczenia sieci neuronowych. ............................................................................................................. 88
101. Mechanizm działania algorytmu genetycznego. ...................................................................................... 88
102. Definicja entropii informacji i wybrane zastosowanie tego pojęcia. ................................................. 89
103. Metody generacji reguł systemu decyzyjnego, minimalne, pokrywające, wyczerpujące........... 89

104. Podaj znaczenie oraz omów wzajemne związki między terminami: przestrzeń urządzenia,

przestrzeń operacyjna urządzenia, powierzchnia obrazowania, macierz adresowalna,
jednostka rastru, krok kreślaka. ...................................................................................................................... 90

105. Zdefiniuj okno i widok oraz oknowanie i obcinanie; podaj co to są współrzędne

znormalizowane i do czego one służą. ........................................................................................................ 90

106. Podaj ideę algorytmu Cohena-Sutherlanda obcinania odcinka do prostokątnego okna i jego

trzy pierwsze kroki; podaj w jakich współrzędnych działa ten algorytm i dlaczego? ................. 90

107. Sformułuj zadanie i ogólne warunki trójkątowania wielokąta, warunki trójkątowania

naturalnego oraz podaj ideę trójkątowania wielokąta monotonicznego. ...................................... 92

108. Zdefiniuj przekształcenie 3-punktowe. Do czego ono służy?. ............................................................. 93
109. Podaj wzajemne położenie układów współrzędnych: danych i obserwatora. ............................... 94
110. Wymień we właściwej kolejności operacje, jakie należy wykonać, aby obrócić punkt P o kąt

dookoła prostej zadanej przez dwa punkty

. ..................................................................... 94

111. Opisać 3 podstawowe obszary uzależnień komputerowych. ............................................................... 94
112. Wymienić przynajmniej 3 polskie ustawy dotyczące środowiska informatycznego. ................... 95
113. Jaka jest zasadnicza różnica między ochroną własności intelektualnej i ochroną patentową?95
114. Opisać na czym polega szpiegostwo komputerowe. .............................................................................. 95

mod by B-art-eq

Algorytm. Własności algorytmu. Prezentacja algorytmu.

Algorytm — jednoznacznie sformułowany sposób postępowania, który w skończonej liczbie
kroków umożliwia rozwiązanie zadania określonej klasy. Zakodowany w
wybranym języku programowania zamienia się w program
komputerowy.
Każdy algorytm:

• Posiada dane wejściowe pochodzące z dobrze zdefiniowanego

zbioru

• Produkuje pewien wynik

• Każdy krok algorytmu musi być jednoznacznie określony

• Jest skończony

• Powinien być efektywny tzn. wykonywać swoją pracę w jak

najkrótszym czasie i wykorzystując jak najmniejszą ilość pamięci

• Powinien dawać poprawne wyniki

Złożoność algorytmów.

Złożoność algorytmu rozumiemy jako ilość niezbędnych zasobów do wykonania algorytmu.
Złożoność dzielimy na czasową oraz pamięciową.

W przypadku złożoności czasowej, z reguły wyróżnimy pewną operację dominującą, a czas
będziemy traktować jako liczbę wykonanych operacji dominujących. W ten sposób nasza analiza
będzie zależna jedynie od algorytmu, a nie od implementacji i sprzętu. W przypadku algorytmów
tekstowych operacją dominującą jest porównanie dwóch symboli a w przypadku sortowania,
operacją dominującą jest przeważnie porównanie dwóch elementów.

Złożoność algorytmu może być rozumiana w sensie złożoności najgorszego przypadku lub
złożoności średniej. Złożoność najgorszego przypadku nazywamy złożonością pesymistyczną - jest
to maksymalna złożoność dla danych tego samego rozmiaru .

Rozważmy przykład. Przypuśćmy, że chcemy znaleźć pierwszą jedynkę z n - elementowej tablicy
zerojedynkowej i nasz algorytm przegląda tablicę od strony lewej sprawdzając kolejne elementy.
Niech operacją dominującą będzie sprawdzenie jednego elementu. Jeśli nie ma jedynki, to
wykonamy n - sprawdzeń. Jest to maksymalna liczba, zatem złożoność pesymistyczna wynosi

. Jeśli każdy ciąg binarny jest dany z tym samym prawdopodobieństwem, to łatwo

policzyć, że złożoność średnia jest ograniczona przez stałą.

liniowa,

kwadratowa, gdy

jest wielomianem to złożoność wielomianowa.

Podobnie jak złożoność czasowa jest miarą czasu działania algorytmu, tak złożoność pamięciowa
jest miarą ilości wykorzystanej pamięci. Jako tę ilość najczęściej przyjmuje się użytą pamięć
maszyny abstrakcyjnej. Możliwe jest również obliczanie rozmiaru potrzebnej pamięci fizycznej
wyrażonej w bitach lub bajtach.

mod by B-art-eq

Problemy sortowania. Przykłady algorytmów sortowania i ich złożoność.

Sortowanie – polega na uporządkowaniu zbioru danych względem pewnych cech
charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie
względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Problem sortowania można zdefiniować następująco:

•

Danymi wejściowymi jest ciąg n liczb.

•

Wynikiem jest taka ich permutacja (czyli zmiana kolejności), że tworzą one ciąg rosnący
(niemalejący).

Zadaniem algorytmu sortowania jest takie przestawienie elementów danego ciągu, aby były one
uporządkowane rosnąco (niemalejąco).

Złożoność algorytmów sortowania jest określana jako liczba wykonywanych porównań i zamian
elementów, wyrażona w zależności od liczby porządkowanych elementów. Złożoność najlepszych
algorytmów sortowania jest proporcjonalna do nlog

n, gdzie n jest liczbą porządkowanych

elementów.

Przykładowe algorytmy sortowania

•

sortowanie bąbelkowe (ang. bubblesort)

O(n

)

•

sortowanie przez wstawianie (ang. insertion sort)

O(n

)

•

sortowanie przez scalanie (ang. merge sort)

O(nlogn), wymaga O(n) dod. pamięci

•

sortowanie przez zliczanie (ang. count sort)

O(n + k), wymaga O(n + k) d. pamięci

•

sortowanie kubełkowe (ang. bucket sort)

O(n), wymaga O(k) dod. pamięci

•

sortowanie biblioteczne (ang. library sort)

O(nlogn), pesymistyczny O(n

)

Sortowanie bąbelkowe

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona
porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie
dokonano żadnej zmiany.

Złożoność obliczeniowa

Algorytm wykonuje n przejść
a każdym przejściu wykonuje
n-1 porównań.

Przez co jego teoretyczna złożoność czasowa
wynosi O(n

). Mało tego, każda permutacja powoduje,

że algorytm jest wykonywany w czasie pesymistycznym.

mod by B-art-eq

Drzewa przeszukiwań binarnych. Sposób wykonywania na nich

podstawowych operacji (dodawanie, wyszukiwanie, usuwanie).

Drzewo przeszukiwań binarnych (BST- binary search tree)
struktura danych będąca drzewem binarnym. Oprócz pola
wartości drzewo przeszukiwań binarnych posiada jeszcze dwa
pola: L i P, wskazujące odpowiednio na lewy i prawy następnik.
Drzewo przeszukiwań binarnych ma szczególną własność:

•

jeżeli element drzewa znajduje się w lewej gałęzi to jest
mniejszy od swego poprzednika

•

jeżeli element drzewa znajduje się w prawej gałęzi to jest
większy od swego poprzednika

•

wierzchołki znajdujące się bezpośrednio pod danym
węzłem nazywamy synami (lub dziećmi).

•

wierzchołki, które nie mają potomków nazywane są liśćmi.

Przeszukiwanie drzewa:

Wszerz:

Przechodzenie wszerz polega na odwiedzaniu kolejno

każdego węzła od najwyższego (najniższego) poziomu i
przechodzeniu kolejno po tych poziomach od góry w dół (od
dołu do góry) i od lewej do prawej lub od prawej do lewej.

Kolejność: F B G A D I C E H

W głąb:

•

Preorder:

korzeń, lewe poddrzewo, prawe poddrzewo. F B A D C E G I H

•

Inorder:

lewe poddrzewo, korzeń, prawe poddrzewo. A B C D E F G H I

•

Postorder:

lewe poddrzewo, prawe poddrzewo, korzeń. A C E D B H I G F

Dodawanie elementów:
Jeśli drzewo BST jest puste (korzeń=null) należy wstawić element, w przeciwnym wypadku
porównujemy wartość elementu z następnikami każdego węzła (zaczynając od korzenia). Jeżeli
wartość elementu jest niewiększa od wartości porównywanego wierzchołka to przechodzimy do
lewego następnika, w przeciwnym razie przechodzimy do prawego następnika. Następnie
wstawiamy element jako odpowiedni następnik (prawy, jeśli element jest większy od węzła, lewy
jeśli niewiększy).
Usuwanie elementów:
Jeżeli usuwany element nie ma następników to można zwolnić przydzieloną mu pamięć. Jeśli
element do usunięcia ma jeden następnik należy go połączyć (następnik) z poprzednikiem
usuwanego elementu. Jeśli element ma dwa następniki można go usunąć na dwa sposoby:

•

połączyć poprzednik elementu z wierzchołkiem o najmniejszej wartości z prawego
poddrzewa usuwanego

•

połączyć poprzednik elementu z wierzchołkiem o największej wartości z lewego poddrzewa

mod by B-art-eq

Algorytmy przeszukiwania grafu.

Przeszukiwanie grafu lub inaczej przechodzenie grafu to
czynność

polegająca

odwiedzeniu

w usystematyzowany sposób wszystkich wierzchołków
grafu w celu zebrania potrzebnych informacji.
Powszechnie stosuje się dwie podstawowe metody
przeszukiwania grafów:

przeszukiwanie wszerz (BFS) - (ang. Breadth-first search, w skrócie BFS) – Algorytm zaczyna od
korzenia i odwiedza wszystkie połączone z nim węzły. Następnie odwiedza węzły połączone z tymi
węzłami i tak dalej, aż do odnalezienia celu.
przeszukiwanie w głąb (DFS) - (ang. Depth-first search, w skrócie DFS) – Przeszukiwanie zaczyna
się od korzenia i porusza się w dół do samego końca gałęzi, po czym wraca się o jeden poziom i
próbuje kolejne gałęzie itd.

Przeszukiwanie w głąb (DFS):

Zaczynamy od wierzchołka 1, odwiedzamy go i
wrzucamy na stos wszystkie jego następniki, w
kolejności od tego z największym indeksem:
Odwiedzone: 1; Stos: 3, 2;
Bierzemy wierzchołek ze stosu, odwiedzamy go i
znów wrzucamy wszystkie jego nieodwiedzone
jeszcze następniki na stos:
Odwiedzone: 1, 2; Stos: 3, 5, 4;
Bierzemy wierzchołek ze stosu, odwiedzamy go,
jedynym następnikiem 4 jest 1, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy
nic na stos:
Odwiedzone: 1, 2, 4; Stos: 3, 5;
Bierzemy wierzchołek ze stosu, odwiedzamy go,
jedynym następnikiem 5 jest 4, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy
nic na stos:
Odwiedzone: 1, 2, 4, 5; Stos: 3;
Bierzemy wierzchołek ze stosu, odwiedzamy go,
jedynym następnikiem 3 jest 6, ten wierzchołek
jeszcze nie jest odwiedzony więc wrzucamy go na
stos:
Odwiedzone: 1, 2, 4, 5, 3; Stos: 6;
Bierzemy wierzchołek ze stosu, odwiedzamy go,
wierzchołek 6 nie ma następników, więc nie ma
czego wrzucić na stos:
Odwiedzone: 1, 2, 4, 5, 3, 6; Stos: ;
Stos

jest

pusty

zatem

zakończyliśmy

przeszukiwanie grafu w głąb.

Przeszukiwanie wszerz (BFS):

Zaczynamy od wierzchołka 1, odwiedzamy go i
wrzucamy do kolejki wszystkie jego następniki, w
kolejności od tego z najmniejszym indeksem:
Odwiedzone: 1; Kolejka: 2, 3;
Bierzemy wierzchołek z kolejki, odwiedzamy go i
znów wrzucamy wszystkie jego nieodwiedzone
jeszcze następniki do kolejki:
Odwiedzone: 1, 2; Kolejka: 3, 4, 5;
Bierzemy wierzchołek z kolejki, odwiedzamy go,
jedynym następnikiem 3 jest 6 więc wrzucamy go
do kolejki:
Odwiedzone: 1, 2, 3; Kolejka: 4, 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go,
jedynym następnikiem 4 jest 1, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy
go do kolejki:
Odwiedzone: 1, 2, 3, 4; Kolejka: 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go,
jedynym następnikiem 5 jest 4, ale ten
wierzchołek już odwiedzaliśmy więc nie wrzucamy
go do kolejki:
Odwiedzone: 1, 2, 3, 4, 5; Kolejka: 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go,
wierzchołek 6 nie ma następników, więc nie ma
czego wrzucić do kolejki:
Odwiedzone: 1, 2, 3, 4, 5, 6; Kolejka: ;
Kolejka

jest

pusta

zatem

zakończyliśmy

przeszukiwanie grafu w szerz.

mod by B-art-eq

Abstrakcyjne struktury danych: listy, kolejki, stosy. Ich implementacja

komputerowa.

Stos

Liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są

pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu).

Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy

egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze.
Elementy stosu poniżej wierzchołka stosu można wyłącznie obejrzeć, aby je ściągnąć, trzeba
najpierw po kolei ściągnąć to, co jest nad nimi.

Implementacja Strukturami danych służącymi do reprezentacji stosu mogą być tablice (gdy

znamy maksymalny rozmiar stosu), tablice dynamiczne lub listy. Złożoność obliczeniowa operacji
na stosie zależy od konkretnej implementacji, ale w większości przypadków jest to czas stały O(1).

Listy

To rodzaj kontenera – dynamiczna struktura danych – składająca się z podstruktur

wskazujących na następniki i/lub poprzedniki.

Typowa lista jest łączona jednostronnie - komórki zawierają tylko odnośnik do kolejnej

komórki. Innym przypadkiem jest lista dwustronna, gdzie komórki zawierają także odnośnik do
poprzednika.

Implementacja listy

Tablicowa
Jak wskazuje nazwa, lista zaimplementowana
w ten sposób opiera się na tablicy obiektów
(lub rekordów) danego typu.

Wskaźnikowa
W tej implementacji każdy obiekt na liście
musi (co nie było konieczne w wersji
tablicowej) zawierać dodatkowy element:
wskaźnik do innego obiektu tego typu.
Wynika to z faktu, że to wskaźniki są
podstawą nawigacji w tym typie listy, a
dostęp do jej elementów jest możliwy
wyłącznie przez wskaźnik.

Kolejki

Liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku

kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy
na wejściu, pierwszy na wyjściu).

Implementacja tablicowa - Jak wskazuje nazwa, kolejka zaimplementowana w ten sposób

opiera się na tablicy obiektów (lub rekordów) danego typu.

http://tnij.org/stosy_kolejki

mod by B-art-eq

Zasada działania i sposoby implementacji tablic haszowanych.

Idea
Tablica mieszająca lub tablica z haszowaniem (ang. hash table) to jeden ze sposobów realizacji
tablicy asocjacyjnej, tj. struktury danych służącej do przechowywania informacji, w taki sposób aby
możliwy był do nich szybki dostęp. Stosuje się je w sytuacjach, w których kolejność kluczy nie ma
znaczenia, natomiast istotna jest jak największa efektywność przeszukiwania.
Zasada działania
Tablice mieszające opierają się na zwykłych tablicach indeksowanych liczbami - dostęp do danych
jest bardzo szybki, nie zależy od rozmiaru tablicy ani położenia elementu. W tablicy mieszającej
stosuje się funkcję mieszającą (funkcję skrótu, funkcję haszującą), która dla danego klucza
wyznacza indeks w tablicy.
Implementacje
Każda implementacja tablicy mieszającej musi zmierzyć się z dwoma problemami: wyborem funkcji
skrótu i rozwiązaniem problemu kolizji.

1. Funkcja skrótu:

Dzielenie:

h(x) = x mod m

zbiór kluczy składa się z liczb naturalnych, a m jest rozmiarem tablicy haszującej. Jeśli elementami
uniwersum są słowa, to możemy również użyć funkcji mieszającej zdefiniowanej przez dzielenie,
ponieważ słowa są reprezentowane przez ciągi bitów.
Zakładając, że tablica haszująca ma 10 elementów, 149 powinno się znaleźć na pozycji dziewiątej,
bo 149 mod 10 = 9.

Wycinanie:

W tej metodzie do obliczenia adresu wykorzystuje się tylko część klucza. Może to być np. fragment
środkowy, albo ostatnie cztery pozycje, albo konkretnie wskazane pozycje. Na ogół pomijamy te
fragmenty klucza, które nie rozróżniają dostatecznie dobrze elementów.
Na przykład, gdybyśmy chcieli zapamiętać numery telefonów stacjonarnych, to nie ma sensu brać
pod uwagę prefiksu 89, gdyż jest on identyczny dla wszystkich przypadków.

2. Problem kolizji:
W sytuacji gdy wartość funkcji mieszającej obliczonej dla klucza elementu wstawianego do tablicy
pokrywa się z wartością funkcji obliczoną dla klucza jakiegoś elementu już znajdującego się w tej
tablicy, mówimy o kolizji. Istnieje kilka sposobów rozwiązywania tego problemu. Najprostszym
sposobem jest zastąpienie elementu znajdującego się w tablicy przez nowy element lub
ewentualnie rezygnacja z wstawiania nowego elementu. Na ogół jednak wymagane jest, aby oba
elementy znalazły się w tablicy, co pociąga za sobą konieczność zastosowania innej metody.

Metoda

łańcuchowa

Polega na przechowywaniu elementów nie bezpośrednio w tablicy, lecz na liście związanej z danym
indeksem. Wstawiane elementy dołącza się do jednego z końców listy. Średnia złożoność
wyszukiwania jest złożonością liniowego wyszukiwania elementu na liście i zależy od współczynnika
wypełnienia listy, czyli stosunku liczby elementów do wielkości tablicy. Ponieważ złożoność
pesymistyczna wyszukiwania wynosi O(n), czasami zamiast list stosuje się drzewa. Zaletą metody
łańcuchowej jest szybkość i prostota usuwania elementów z listy.

mod by B-art-eq

Adresowanie otwarte

W podejściu tym nowy element wstawia się w innym miejscu niż wynikałoby to z wartości funkcji
mieszającej. Nowa lokalizacja określana jest przez dodanie do wartości funkcji mieszającej wartości
tzw. funkcji przyrostu p(i), gdzie i oznacza numer próby (to znaczy ile razy wstawienie się nie
powiodło ze względu na kolizję). Ze względu na rodzaj funkcji przyrostu wyróżnia się różne metody
adresowania otwartego:

•

szukanie liniowe, dla funkcji przyrostu postaci p(i)=i

•

szukanie kwadratowe, dla p(i)=i

•

mieszanie podwójne, dla p(i)=i *h' (K), gdzie h' jest dodatkową fun. mieszającą od klucza K.

W przypadku szukania liniowego może pojawić się problem grupowania, to znaczy koncentracji
miejsc zajętych w pewnych zakresach indeksów przy małej zajętości innych obszarów tablicy.
Problem ten jest w znacznym stopniu zredukowany w przypadku szukania kwadratowego, chociaż
w tej metodzie występuje analogiczny problem grupowania wtórnego, natomiast praktycznie
wyeliminowany dla mieszania podwójnego.

Innym kłopotem jest skomplikowanie procesu usuwania elementu, w sytuacji gdy w tablicy
znajdują się inne, o tej samej wartości funkcji mieszającej. Wymusza to rozróżnianie trzech stanów
elementów tablicy: zajęta, wolna, wolna po usunięciu.

Idea algorytmu zachłannego. Przykład.

Algorytm zachłanny w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj.
najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm
zachłanny nie patrzy czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje
decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym,
kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji.

Istnieje wiele problemów, dla których udowodnić można, że rozwiązanie zachłanne jest zawsze
optymalne - między innymi znajdowanie minimalnego drzewa rozpinającego, czy znajdowanie
najkrótszej ścieżki między dwoma punktami w grafie. W przypadku innych problemów zachłanność
może opłacać się jedynie w szczególnych przypadkach.

Przykład – Algorytm Kruskala - wyznacza minimalne drzewo rozpinające
dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy,
znajduje drzewo zawierające wszystkie wierzchołki grafu, których waga jest
najmniej możliwa.

Algorytm wydawania reszty w większości przypadków jest nierozwiązywalny
w sposób zachłanny. Przykładowo, dane są dwa rodzaje monet: 2 zł i 5 zł.
Należy obliczyć ile, i jakich monet należy wydać, by reszta wynosiła 6 zł.

mod by B-art-eq

Idea Dijkstry algorytmu znajdowania najkrótszej ścieżki.

Algorytm Dijkstry, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o
nieujemnych wagach krawędzi. Jest często używany w trasowaniu.
Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła
do wszystkich pozostałych wierzchołków. Łatwo zmodyfikować go tak, aby szukał wyłącznie ścieżki
do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do
wierzchołka docelowego.

http://tnij.org/dijkstra_gif

10.

Pozycyjne systemy liczbowe (binarny, dziesiętny, szesnastkowy).

Prezentacja liczb w komputerze.

Posiadają symbole (cyfry) tylko dla kilku najmniejszych liczb naturalnych: 0, 1, 2, ..., g-1, gdzie g to
tzw. podstawa systemu. Cyfry te są umieszczane na ściśle określonych pozycjach i są mnożone
przez odpowiednią potęgę g.

DEC - System dziesiętny

Dziesiętny system liczbowy, to pozycyjny system liczbowy, w którym podstawą pozycji są kolejne
potęgi liczby 10. Do zapisu liczb potrzebne jest więc w nim 10 cyfr: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Jak w każdym pozycyjnym systemie liczbowym, liczby zapisuje się tu jako ciąg cyfr, z których każda
jest mnożnikiem kolejnej potęgi liczby stanowiącej podstawę systemu. Część całkowitą i ułamkową
oddziela separator dziesiętny.

Np zapis "5045,7" wynika z:

Pozycyjny, dziesiętny system liczbowy jest obecnie na świecie podstawowym systemem
stosowanym niemal we wszystkich krajach.

BIN - System binarny (dwójkowy)

Dwójkowy system liczbowy (inaczej binarny) to pozycyjny system liczbowy, w którym podstawą jest
liczba 2. Do zapisu liczb potrzebne są więc tylko dwie cyfry: 0 i 1.

Powszechnie używany w elektronice cyfrowej, gdzie minimalizacja liczby stanów (do dwóch)
pozwala na prostą implementację sprzętową odpowiadającą zazwyczaj stanom wyłączony i
włączony oraz zminimalizowanie przekłamań danych. Co za tym idzie, przyjął się też w informatyce.

Np. liczba zapisana w dziesiętnym systemie liczbowym jako 10, w systemie dwójkowym przybiera
postać 1010, gdyż:

mod by B-art-eq

HEX - System heksadecymalny (szesnastkowy)

Szesnastkowy system liczbowy (czasem nazywany heksadecymalnym, skrót hex) – pozycyjny
system liczbowy, w którym podstawą jest liczba 16. Do zapisu liczb w tym systemie potrzebne jest
szesnaście cyfr.

W najpowszechniejszym standardzie poza cyframi dziesiętnymi od 0 do 9 używa się pierwszych
sześciu liter alfabetu łacińskiego: A, B, C, D, E, F (dużych lub małych). Cyfry 0-9 mają te same
wartości co w systemie dziesiętnym, natomiast litery odpowiadają następującym wartościom: A =
10, B = 11, C = 12, D = 13, E = 14 oraz F = 15.

Jak w każdym pozycyjnym systemie liczbowym, liczby zapisuje się tu jako ciągi znaków, z których
każdy jest mnożnikiem kolejnej potęgi liczby stanowiącej podstawę systemu. Np. liczba zapisana w
dziesiętnym systemie liczbowym jako 1000, w systemie szesnastkowym przybiera postać 3E8, gdyż:

System szesnastkowy sprawdza się szczególnie przy zapisie dużych liczb takich jak adresy pamięci,
zakresy parametrów itp.

11.

Budowa komputera

Komputer to urządzenie elektroniczne służące do przetwarzania wszelkich informacji, które da się
zapisać w formie ciągu cyfr albo sygnału ciągłego. Obecnie większość komputerów cechuje
możliwość ich programowania, czyli wprowadzenia do pamięci komputera listy instrukcji, które
mogą być wykonane w innym czasie.
Budowa takiej maszyny opiera się na architekturze stworzonej w 1945 przez Johna von
Neumanna. Dzieliła ona komputer na trzy podstawowe części:

• procesor (w ramach którego wydzielona bywa część sterująca oraz część arytmetyczno-

logiczna)

• pamięć komputera (zawierająca dane i sam program)

• urządzenia wejścia/wyjścia

Model komputera wykorzystującego architekturę von Neumanna jest często nazywany
przykładową maszyną cyfrową (PMC).
Większość współczesnych komputerów składa się z trzech podstawowych elementów:

• procesora – podzielonego na część arytmetyczno-logiczną czyli układu, który faktycznie

wykonuje wszystkie konieczne obliczenia oraz część sterującą

• pamięci RAM – (od ang. Random Access Memory) czyli układy scalone, które przechowują

program i dane (umożliwia to m.in. samo modyfikację programu) oraz bieżące wyniki
obliczeń procesora i stale, na bieżąco wymienia dane z procesorem

• urządzeń wejścia/wyjścia – które służą do komunikacji komputera z otoczeniem.

Procesor (ang. processor), także CPU (ang. Central Processing Unit) – urządzenie cyfrowe
sekwencyjne, które pobiera dane z pamięci, interpretuje je i wykonuje jako rozkazy. Wykonuje on
ciąg prostych operacji (rozkazów) wybranych ze zbioru operacji podstawowych określonych
zazwyczaj przez producenta procesora jako lista rozkazów procesora.
Płyta główna (ang. motherboard, mainboard) – najważniejsza płyta drukowana urządzenia
elektronicznego, na której montuje się najważniejsze elementy urządzenia, umożliwiająca
komunikację wszystkim pozostałym komponentom i modułom.
Karta graficzna – karta rozszerzeń komputera odpowiedzialna za renderowanie grafiki i jej
konwersję na sygnał zrozumiały dla wyświetlacza.

mod by B-art-eq

12.

Struktura procesora.

W funkcjonalnej strukturze procesora, niezależnie czy jest to CPU, czy GPU można wyróżnić
takie elementy, jak:

• bardzo szybką pamięć podręczną (cache)

• zespół rejestrów do przechowywania danych i wyników, rejestry mogą być ogólnego

przeznaczenia lub mają specjalne przeznaczenie,

• jednostkę arytmetyczną do wykonywania operacji obliczeniowych na danych,

• układ sterujący przebiegiem wykonywania programu,

• inne układy, w które producent wyposaża procesor w celu usprawnienia jego pracy.

Jednym z parametrów procesora jest rozmiar elementów budujących jego strukturę. Im są one
mniejsze, tym niższe jest zużycie energii, napięcie pracy oraz wyższa możliwa do osiągnięcia
częstotliwość pracy.

Przykładowe rozkazy procesora:

• kopiowanie danych: z pamięci do rejestru, z rejestru do pamięci, z pamięci do pamięci;

• działania

arytmetyczne (dodawanie, odejmowanie, porównywani, dwóch liczb,

dodawanie i odejmowanie jedności, zmiana znaku liczby

• działania na bitach (iloczyn/suma logiczna, suma modulo XOR, negacja NOT,

przesunięcie

• skoki

13.

Cykl rozkazowy procesora

Cykl rozkazowy procesora to pewien schemat powtarzających się czynności, realizujących
wykonywanie instrukcji programu. Na cykl rozkazowy składają się dwie fazy:

• faza pobrania,

• faza wykonania.

W fazie pobrania procesor pobiera kod rozkazu z komórki pamięci. Adres pod którym znajduje
się rozkaz przechowywany jest w liczniku rozkazów. Wartość tego licznika wysyłana jest na
magistralę adresową a licznik rozkazów zostaje zwiększony tak, aby wskazywał na następny rozkaz
przeznaczony do wykonania.
Po fazie pobrania następuje faza wykonania, w której procesor dekoduje rozkaz i określa jego typ.
Układ sterowania generuje odpowiednie sygnały sterujące, realizujące dany rozkaz.
Jeżeli rozkaz wymaga pobrania argumentów, to przed jego wykonaniem są one pobierane z
pamięci i umieszczane w odpowiednich rejestrach.
We współczesnych procesorach oba te cykle wykonywane są jednocześnie.
W czasie wykonywania rozkazu pobierany jest już następny.

mod by B-art-eq

14.

Metody odwzorowania pamięci głównej w pamięci podręcznej.

Odwzorowanie bezpośrednie - najprostsza metoda, polega na odwzorowywaniu każdego bloku
pamięci głównej na tylko jeden możliwy wiersz pamięci podręcznej.
Odwzorowywanie jest wyrażane jako:

i = j modulo m

gdzie
i - numer wiersza pamięci podręcznej
j - numer bloku pamięci głównej
m - liczba wierszy w pamięci podręcznej

Metoda odwzorowywania bezpośredniego jest prosta i tania przy wdrażaniu. Jej główną wadą jest
to, że dla danego bloku istnieje stała lokalizacja w pamięci podręcznej. W rezultacie, jeśli program
będzie się często odwoływał do słów z dwóch różnych bloków przypisanych do tego samego
wiersza, to bloki te będą ciągle przenoszone do pamięci podręcznej, co obniży ogólną szybkość.

Odwzorowywanie skojarzeniowe eliminuje wady odwzorowywania bezpośredniego, gdyż
umożliwia ładowanie każdego bloku pamięci głównej do dowolnego wiersza pamięci podręcznej.
W tym przypadku sterujące układy logiczne pamięci podręcznej interpretują adres pamięci po
prostu jako znacznik i pole słowa. Pole znacznika jednoznacznie określa blok pamięci głównej. W
celu stwierdzenia, czy blok znajduje się w pamięci podręcznej, sterujące układy logiczne pamięci
podręcznej muszą jednocześnie zbadać zgodność znacznika każdego wiersza. W przypadku
odwzorowywania skojarzeniowego blok do zastąpienia jest wybierany elastycznie, kiedy nowy blok
jest wczytywany do pamięci podręcznej. Opracowano algorytmy zastępowania służące do
maksymalizacji współczynnika trafień. Główną wadą odwzorowywania skojarzeniowego są złożone
układy wymagane do równoległego badania znaczników wszystkich wierszy pamięci podręcznej.

Odwzorowywanie sekcyjno-skojarzeniowe stanowi kompromis łączący zalety odwzorowywania
bezpośredniego i skojarzeniowego; jest ono pozbawione wad charakteryzujących te metody. W
tym przypadku pamięć podręczna jest dzielona na v sekcji, z których każda składa się z k wierszy.
W przypadku odwzorowywania sekcyjno-skojarzeniowego blok Bj może być odwzorowywany na
dowolny wiersz sekcji i. W tym przypadku sterujące układy logiczne pamięci podręcznej
interpretują adres pamięci jako trzy pola: znacznik, sekcja i słowo. Za pomocą d bitów sekcji
precyzuje się jedną z v = 2d sekcji, a s bitów znacznika w połączeniu z polem sekcji określa jeden z
2s bloków pamięci głównej.

mod by B-art-eq

15.

Przetwarzanie potokowe.

Przetwarzanie potokowe

—

(Używanie w celu zwiększenia
wydajności)

sposób

pracy

procesora

polegający

wykonywaniu kolejnych instrukcji,
przy czym rozpoczęcie następnej
nie

wymaga

zakończenia

poprzedniej. Uzyskuje się dzięki
temu pełniejsze wykorzystanie
mocy obliczeniowej procesora.
cykl przetwarzania dzieli się na
odrębne bloki przetwarzania, z
których każdy oprócz pierwszego i
ostatniego jest połączony z
następnym. Dane po przejściu przez jeden blok trafiają do następnego, aż osiągną ostatni blok.
Dzięki temu, że przetwarzanie odbywa się w rozdzielnych blokach system może przetwarzać
jednocześnie tyle danych ile zdefiniowano bloków.
Wadą takiego rozwiązania jest dłuższy czas oczekiwania na zakończenie pierwszej operacji po
chwili przestoju, gdyż dla potoku o długości n etapów minimalny czas oczekiwania wynosi n cykli
zegarowych. Jedynym sposobem ograniczenia tego problemu jest zwiększanie częstotliwości
taktowania układu oraz likwidowanie przerw w przetwarzaniu.

16.

Porównanie różnych architektur sieci komputerowych

Architektura sieci – określa sposoby realizacji przekazu informacji pomiędzy urządzeniami końcowymi.
Przeważnie organizowana warstwowo tworząc warstwową architekturę sieci.

Ważniejsze architektury warstwowe:
ISO-OSI (ISO - Open Systems Interconection)
TCP/IP (Transmission Control Protocol/Internet Protocol)
SNA (Systems Network Architecture) firmy IBM
DNA (Digital Network Architecture) firmy DEC

Model OSI - jest powszechnie uznawanym modelem architektury komunikacyjnej sieci opisującym
środowisko komunikacyjne, w którym dwa systemy mogą wymieniać informacje między sobą pod
warunkiem, że w obu przypadkach zaimplementowano te same protokoły komunikacyjne.
Warstwy modelu ISO/OSI:
1 APLIKACJI - zajmuje się specyfikacją interfejsu, który wykorzystują aplikacje do przesyłania
danych do sieci;
2 PREZENTACJI - zapewnia tłumaczenie danych, definiowanie ich formatu oraz odpowiednią
składnię;
3 SESJI - zadaniem jest zarządzanie przebiegiem komunikacji, podczas połączenia miedzy dwoma
komputerami;
4 TRANSPORTOWA - segmentuje dane oraz składa je w tzw. strumień, zapewnia całościowe
połączenie między stacjami;

mod by B-art-eq

5 SIECIOWA - podstawowe zadania to przesyłanie danych pomiędzy węzłami sieci wraz z
wyznaczaniem trasy przesyłu, łączenie bloków informacji w ramki na czas ich przesyłania a
następnie stosowny ich podział;
6 ŁĄCZA DANYCH - odpowiada za obsługę ramek, czyli stałej długości pakietów danych, do jej
zadań należy wykrywanie wszelkich błędów, które wystąpiły w warstwie fizycznej, oraz ich
usuwanie;
7 FIZYCZNA - odpowiedzialna za przesyłanie sygnałów w elektryczny, elektromagnetyczny,
mechaniczny, optyczny czy też inny sposób, wykorzystując do tego fizyczne medium
komunikacyjne (przewody miedziane, światłowody)

Model TCP/IP - teoretyczny model warstwowej struktury protokołów komunikacyjnych.
Podstawowym założeniem modelu TCP/IP jest podział całego zagadnienia komunikacji
sieciowej na szereg współpracujących ze sobą warstw (ang. layers). Każda z nich może
być tworzona przez programistów zupełnie niezależnie, jeżeli narzucimy pewne
protokoły według których wymieniają się one informacjami. Założenia modelu TCP/IP są
pod względem organizacji warstw zbliżone do modelu OSI. Jednak ilość warstw jest
mniejsza i bardziej odzwierciedla prawdziwą strukturę Internetu.
Model TCP/IP składa się z czterech warstw:
1 APLIKACJI - najwyższy poziom, w którym pracują użyteczne dla człowieka aplikacje takie jak, np.
serwer WWW czy przeglądarka internetowa. Obejmuje ona zestaw gotowych protokołów, które
aplikacje wykorzystują do przesyłania różnego typu informacji w sieci.
2 TRANSPORTOWA - zapewnia pewność przesyłania danych oraz kieruje właściwe informacje do
odpowiednich aplikacji.
3 INTERNETU - przetwarzane są datagramy posiadające adresy IP. Ustalana jest odpowiednia
droga do docelowego komputera w sieci.
4 DOSTĘPU DO SIECI - zajmuje się przekazywaniem danych przez fizyczne połączenia między
urządzeniami sieciowymi. Najczęściej są to karty sieciowe lub modemy. Dodatkowo warstwa ta jest
czasami wyposażona w protokoły do dynamicznego określania adresów IP.

Model OSI

Model TCP/IP

został wymyślony przed wynalezieniem
odpowiadających mu protokołów. Taka kolejność
oznacza, że model nie był ukierunkowany na
konkretny zbiór protokołów i stał się przez to
bardziej ogólny.

Model jest opisem istniejących już
protokołów. Jedyny problem jest taki że nie
pasuje do żadnego innego stosu
protokołów.

7 warstw

4 warstwy

Funkcjonalność warstw jest zbliżona. Np. w obu modelach warstwy od dołu aż do transportowej
włącznie mają zapewnić dwupunktową, niezależną od sieci usługę transportową procesów, które
chcą się komunikować.

Warstwy powyżej transportowej w obu modelach są zorientowanymi na aplikację użytkownikami
usługi transportowej.

mod by B-art-eq

17.

Funkcje warstwy łącza danych modelu OSI.

Druga warstwa modelu OSI. Jest ona odpowiedzialna za końcową zgodność przesyłanych danych.
W zakresie zadań związanych z przesyłaniem, warstwa łącza danych jest odpowiedzialna za
upakowywanie instrukcji, danych itp. w tzw. ramki. Ramka jest strukturą rodzimą, czyli właściwą dla
warstwy łącza danych, która zawiera ilość informacji wystarczającą do pomyślnego przesłania
danych przez sieć lokalną do ich miejsca docelowego.
Pomyślna transmisja danych zachodzi wtedy, gdy dane osiągają miejsce docelowe w postaci
niezmienionej w stosunku do postaci, w której zostały wysłane. Ramka musi więc również zawierać
mechanizm umożliwiający weryfikowanie integralności jej zawartości podczas transmisji.
Wysoka jakość transmisji wymaga spełnienia następujących dwóch warunków:
• Węzeł początkowy musi odebrać od węzła końcowego potwierdzenie otrzymania każdej ramki w
postaci niezmienionej.
• Węzeł docelowy przed wysłaniem potwierdzenia otrzymania ramki musi zweryfikować
integralność jej zawartości.
Warstwa łącza danych jest również odpowiedzialna za ponowne składanie otrzymanych z warstwy
fizycznej strumieni binarnych i umieszczanie ich w ramkach. Ze względu na fakt przesyłania
zarówno struktury, jak i zawartości ramki, warstwa łącza danych nie tworzy ramek od nowa.
Buforuje raczej przychodzące bity dopóki nie uzbiera w ten sposób całej ramki.

18.

Funkcje warstwy sieci modelu OSI.

Warstwa sieci modelu OSI odpowiada za określenie trasy pomiędzy nadawcą a odbiorcą.
Zadaniem tej warstwy jest kierowanie przepływem pakietów w sieci. Zapewnia ona, że pakiety
przesyłane między komputerami nie łączącymi się bezpośrednio, będą przekazywane z komputera
na komputer, aż osiągną adresata. Proces znajdowania drogi w sieci nazywa się trasowaniem lub
rutowaniem. Nie wymaga się aby pakiety pomiędzy ustalonymi punktami poruszały się za każdym
razem po tej samej drodze. Warstwa ta nie posiada żadnych mechanizmów wykrywania oraz
korygowania błędów. W pewnych sytuacjach dopuszcza się gubienie pakietów przez tę warstwę.
Gubienie pakietów jest jedynym wyjściem gdy router - węzeł dokonujący trasowania lub pewien
segment sieci są przeciążone i nie mogą przyjmować nowych pakietów.

Nagłówek

Pole treści

Stopka

mod by B-art-eq

19.

Dynamiczne przydzielanie adresów.

Protokół DHCP opisuje trzy techniki przydzielania adresów IP:

•

przydzielanie ręczne oparte na tablicy adresów MAC oraz odpowiednich dla nich adresów
IP. Jest ona tworzona przez administratora serwera DHCP. W takiej sytuacji prawo do pracy
w sieci mają tylko komputery zarejestrowane wcześniej przez obsługę systemu.

•

przydzielanie automatyczne, gdzie wolne adresy IP z zakresu ustalonego przez
administratora są przydzielane kolejnym zgłaszającym się po nie klientom.

•

przydzielanie dynamiczne, pozwalające na ponowne użycie adresów IP. Administrator sieci
nadaje zakres adresów IP do rozdzielenia. Wszyscy klienci mają tak skonfigurowane
interfejsy sieciowe, że po starcie systemu automatycznie pobierają swoje adresy. Każdy
adres przydzielany jest na pewien czas (lease). W czasie trwania okresu lease klient DHCP
nie występuje do serwera DHCP podczas startu systemu o nowy adres, a jedynie żąda
potwierdzenia istniejącego stanu lease. Protokół DHCP minimalizuje również możliwe źródła
błędów. Na życzenie podaje, oprócz adresu IP, również inne parametry, jak choćby
standardowa brama, czy adresy serwerów nazw. Taka konfiguracja powoduje, że zwykły
użytkownik ma ułatwioną pracę z siecią.

20.

Protokoły połączeniowe i bezpołączeniowe.

Protokół połączeniowy to protokół komunikacyjny, w którym przed rozpoczęciem wymiany
komunikatów strony muszą nawiązać połączenie, w którego ramach może zostać wynegocjowany
sam protokół. Po zakończeniu łączności połączenie musi ulec likwidacji. W wyniku budowy
połączenia zostaje utworzona pojedyncza ścieżka
między stacją nadawczą a stacją odbiorczą. W fazie
przesyłania dane są transmitowane przez utworzoną
ścieżkę w sposób sekwencyjny. Dane docierają do
stacji odbiorczej w kolejności ich wysyłania przez
stację nadawczą. W fazie likwidacji połączenia
utworzone połączenie ulega przerwaniu. Dalsza
transmisja między stacjami nadawczą i odbiorczą
musi być ponownie poprzedzona fazą budowy
połączenia.
Protokół bezpołączeniowy - typ protokołu sieciowego, umożliwia przesyłanie bez ustanawiania
połączenia z odbiorcą. Nie buduje się jedynej ścieżki między stacją nadawczą i odbiorczą, pakiety
do stacji odbiorczej mogą docierać w innej kolejności niż są wysyłane przez stację nadawczą, ze
względu na to, że mogą być przesyłane różnymi trasami. W usłudze bezpołączeniowej dane
przepływają przez trwałe połączenia między węzłami sieci, a każdy pakiet jest obsługiwany
indywidualnie i niezależnie od innych pakietów danego komunikatu. Jest to możliwe pod
warunkiem, że każdy pakiet jest kompletnie zaadresowany, to znaczy, że każdy z nich ma swój
adres stacji nadawczej i stacji odbiorczej.

mod by B-art-eq

21.

Tryby FTP.

FTP (ang. File Transfer Protocol – Protokół Transferu Plików) – protokół typu klient-serwer,
który umożliwia przesyłanie plików z serwera i na serwer poprzez sieć TCP/IP.
FTP jest protokołem 8-bitowym, dlatego nie wymaga specjalnego kodowania danych na postać 7-
bitową, tak jak ma to miejsce w przypadku poczty elektronicznej.
Do komunikacji wykorzystywane są dwa połączenia TCP. Jedno z nich jest połączeniem kontrolnym
za pomocą którego przesyłane są np. polecenia do serwera, drugie natomiast służy do transmisji
danych m.in. plików. FTP działa w dwóch trybach: aktywnym i pasywnym, w zależności od tego,
w jakim jest trybie, używa innych portów do komunikacji.
N > 1024
Jeżeli FTP pracuje w trybie aktywnym korzysta z portów:

• 21 dla poleceń

• 20 do przesyłu danych.

Połączenie nawiązywane jest wówczas przez serwer.
Jeżeli FTP pracuje w trybie pasywnym wykorzystuje port:

• 21 do poleceń

• port o numerze > N do transmisji danych,

gdzie obydwa połączenia zestawiane są przez klienta.

Tryb aktywny FTP:
polecenia : klient > N -> serwer 21
dane : klient > N+1 <- serwer 20

Tryb pasywny FTP:

polecenia : klient > N -> serwer 21
dane : klient > N+1 -> serwer > N

Aktywny tryb FTP jest wygodny dla administratora serwera FTP, jednak kłopotliwy dla klienta.
Serwer FTP stara się nawiązać połączenie z nieuprzywilejowanym portem klienta, co
najprawdopodobniej zostanie udaremnione przez firewall po stronie klienta.
Tryb pasywny jest wygodny dla klienta, lecz kłopotliwy dla administratora serwera FTP. Oba
połączenia nawiązuje klient, ale jedno z nich dotyczy nieuprzywilejowanego portu, i
najprawdopodobniej będzie zablokowane przez firewall po stronie serwera.

mod by B-art-eq

22.

Podstawowe pojęcia baz danych. Baza Danych. Funkcje bazy danych.

Właściwości bazy danych. Modele baz danych.

Baza danych – zbiór informacji opisujący wybrany fragment rzeczywistości.

Najogólniej rzecz biorąc „baza danych” to zbiór informacji wraz z możliwością łatwego

dostępu oraz zmiany tych informacji.

Właściwości baz danych:

◦ współdzielenie danych – wielu użytkowników tej samej bazy,

◦ integracja danych – baza nie powinna mieć powtarzających się, bądź zbędnych danych,

◦ integralność danych – dokładne odzwierciedlenie obszaru analizy,

◦ trwałość danych – dane przechowywane przez pewien czas,

◦ bezpieczeństwo danych – dostęp do bazy lub jej części przez upoważnionych

użytkowników,

◦ abstrakcja danych – dane opisują tylko istotne aspekty obiektów świata rzeczywistego,

◦ niezależność danych – dane niezależnie od aplikacji wykorzystujących te dane.

Funkcje bazy danych:

• aktualizujące – dokonują zmian na danych,

• zapytań – wydobywają dane z bazy danych.

Model baz danych - to zbiór zasad (specyfikacji), opisujących strukturę danych w bazie
danych. Określane są również dozwolone operacje.

Model hierarchiczny:

W modelu hierarchicznym dane są przechowywane na zasadzie rekordów nadrzędnych-
podrzędnych, tzn. rekordy przypominają strukturę drzewa. Każdy rekord (z wyjątkiem
głównego) jest związany z dokładnie jednym rekordem nadrzędnym.

Model relacyjny:

Dane w takim modelu przechowywane są w tabelach, z których każda ma stałą liczbę
kolumn i dowolną liczbę wierszy. Każda tabela (relacja) ma zdefiniowany klucz danych (key) -
wyróżniony atrybut lub kilka takich atrybutów, którego wartość jednoznacznie identyfikuje
dany wiersz.

Model obiektowy:

Dane w tym modelu przechowywane są jako instancje/obiekty zdefiniowanych klas. Każda
klasa może mieć zdefiniowany unikalny zbiór atrybutów, a również super klasę (przodka) po
którym dziedziczy atrybuty. Obiekty jednej klasy posiadają ten sam zbiór atrybutów a różnić
się mogą tylko ich wartościami.

Model sieciowy:

Model danych operujący pojęciami typów rekordów i typów kolekcji (opisów związków

“jeden do wielu” między dwoma typami rekordów). Związki asocjacyjne pomiędzy danymi są
reprezentowane poprzez powiązania wskaźnikowe. Struktura danych tworzy więc graf, czyli
sieć.

mod by B-art-eq

23.

System zarządzania bazami danych. Funkcje systemu. Przykłady SZDB.

System zarządzania bazą danych, SZBD (ang. Database Management System, DBMS) –
oprogramowanie bądź system informatyczny służący do zarządzania bazą danych. System
zarządzania bazą danych może być również serwerem bazy danych (SBD) lub też może
udostępniać bazę danych lokalnie – na określonym komputerze.

Funkcje SZBD:

• optymalizacja zapytań – takie przekształcenie zapytań kierowanych do bazy, aby

oczekiwanie na odpowiedź było możliwie najkrótsze

• zapewnienie integralności danych – uniemożliwienie przejścia bazy do stanu, który nie

istnieje w modelowanej rzeczywistości

• zarządzanie współbieżnym dostępem wielu użytkowników, tak aby ich działania nie

kolidowały ze sobą

• odporność na awarie – możliwość odtworzenia poprawnego stanu bazy po wystąpieniu

awarii

• ochrona danych – uniemożliwienie dostępu do danych bez autoryzacji

Przykłady SZBD:

• MySQL: silniki MyISAM, InnoDB

• Access: silnik Microsoft Jet

• Kexi (konkurent Access): silnik SQLite

24.

Model relacyjny baz danych. Relacje, klucze główne i obce, integralność

referencyjna.

Model relacyjny – model organizacji danych bazujący na matematycznej teorii mnogości, w
szczególności na pojęciu relacji. Reprezentacją relacji jest dwuwymiarowa tabela złożona z kolumn
(atrybutów) i wierszy (krotek). W modelu relacyjnym przyjmuje się następujące założenia o tabeli:

•

Liczba kolumn (atrybutów) jest z góry ustalona

•

Z każdą kolumną (atrybutem) jest związana jej nazwa oraz dziedzina, określająca zbiór

wartości, jakie mogą występować w danej kolumnie

•

Na przecięciu wiersza i kolumny znajduje się pojedyncza (atomowa) wartość należąca do

dziedziny kolumny

•

Wiersz (krotka) reprezentuje jeden rekord informacji

•

W modelu relacyjnym kolejność wierszy (krotek) może się zmieniać

mod by B-art-eq

Relacje - związki między tabelami pozwalają zapobiec występowaniu powtarzających się
(nadmiarowych) danych. Wyróżnia się trzy typy związków między tabelami:

• Jeden – do – wielu (1 - ∞)

W przypadku tego typu relacji, wierszowi (krotce) w tabeli A może odpowiadać wiele
zgodnych wierszy (krotek) w tabeli B, ale wierszowi w tabeli B może odpowiadać tylko jeden
zgodny wiersz w tabeli A

• Wiele – do – wielu (∞ - ∞)

W przypadku relacji wiele-do-wielu, wierszowi (krotce) w tabeli A może odpowiadać wiele
zgodnych wierszy (krotek) w tabeli B i na odwrót. Relacje taką tworzy się definiując trzecią
tabelę, zwaną tabelą skrzyżowań, której klucz podstawowy zawiera zarówno klucz obcy z
tabeli A, jak i z tabeli B.

• Jeden – do – jednego (1 - 1)

W przypadku relacji jeden-do-jednego wierszowi (krotce) w tabeli A może odpowiadać nie
więcej niż jeden zgodny wiersz (krotka) w tabeli B i na odwrót. Relacja jeden-do-jednego
jest tworzona, jeśli obie powiązane kolumny są kluczami podstawowymi lub mają
ograniczenia UNIQUE.

Klucz główny - dla każdej tabeli w modelu relacyjnym musi być określony, jednoznaczny
identyfikator, nazywany kluczem głównym (podstawowym). Klucz główny składa się z jednej lub ze
zbioru kolumn (atrybutów), w których wartości w jednoznaczny sposób identyfikują cały wiersz
(krotkę). Oznacza to, że wartości znajdujące się w kolumnie będącej kluczem głównym nie mogą
się powtarzać i muszą być unikatowe.

Klucz obcy - jest to zbiór złożony z jednej kolumny lub więcej kolumn, w których wartości
występują, jako wartości ustalonego klucza głównego lub jednoznacznego w tej samej lub innej
tabeli i są interpretowane, jako wskaźniki do wierszy w tej drugiej tabeli.
Zasada integralności referencyjnej w relacyjnej bazie danych wymaga, aby wartości klucza obcego
tabeli podrzędnej były puste (null) lub odpowiadały wartościom klucza podstawowego tabeli
nadrzędnej.

Integralność referencyjna – zasada integralności referencyjnej mówi, że klucz obcy nie może
odnosić się do nieistniejących rekordów.
Z reguły wynika, że:

•

Do tablicy nie można dodać wiersza, którego wartość klucza obcego nie ma odpowiednika

w tablicy odniesień

•

Zmiana wartości klucza głównego w tablicy (lub usunięcie całego rekordu) nie może

prowadzić do „osierocenia” wierszy w innej tablicy (która poprzez klucz obcy wskazuje na
modyfikowany klucz główny)

mod by B-art-eq

25.

Modelowanie baz danych. Diagram związków encji.

Model bazy danych to zbiór zasad (specyfikacji), opisujących strukturę danych w bazie danych.
Określane są również dozwolone operacje. Definiuje się strukturę danych poprzez specyfikację
reprezentacji dozwolonych w modelu obiektów (encji) oraz ich związków.
Hierarchiczny model danych
W modelu hierarchicznym dane są przechowywane na zasadzie rekordów nadrzędnych-
podrzędnych, tzn. rekordy przypominają strukturę drzewa. Każdy rekord (z wyjątkiem głównego)
jest związany z dokładnie 1 rekordem nadrzędnym. Przykładem takiego modelu może być
struktura katalogów na dysku twardym komputera.
Relacyjny model danych (RDBMS)
Dane w takim modelu przechowywane są w tabelach, z których każda ma stałą liczbę kolumn i
dowolną liczbę wierszy. Każda tabela (relacja) ma zdefiniowany klucz danych (key) - wyróżniony
atrybut lub kilka takich atrybutów, którego wartość jednoznacznie identyfikuje dany wiersz.

ODL (ang. Object Definition Language) – język specyfikacji obiektu, przeznaczony do definiowania
schematu, struktury bazy danych oraz interfejsów do obiektów. Uniwersalny język wysokiego
poziomu umożliwiający integrację różnych systemów.

Specyfikując schemat klasy obiektów w języku ODL, opisujemy trzy rodzaje właściwości obiektów:
Atrybuty - przyjmują wartości typów pierwotnych takich jak całkowity lub tekstowy, albo typów
złożonych powstających z pierwotnych;
Związki - referencje do obiektów pewnej klasy, albo kolekcje (zbiory) takich referencji;
Metody - funkcje operujące na obiektach danej klasy.

Diagram Związków Encji
Modele danych można opracowywać na różnych poziomach szczegółowości wykorzystując
technikę diagram związków encji.

Komponent Opis
Encja

Rzecz mająca znaczenie, rzeczywista lub wymyślona, o której informacje należy
znać lub przechowywać.

Atrybut

Element informacji służący do klasyfikowania, identyfikowania, kwalifikowania,
określania ilości lub wyrażania stanu encji.

Związek

Znaczący sposób, w jaki mogą być ze sobą powiązane dwie rzeczy tego samego
typu lub różnych typów.

Przykład

L I E

* N

a z w

* A

d r e s

o e _ m

a i l

F A

T U

t r y b u t y

n c j a

Z w

i ą z e k

Uwaga: encje opisuje się za pomocą rzeczowników lub wyrażeń rzeczownikowych w liczbie
pojedynczej.

mod by B-art-eq

26.

Język baz danych SQL. Podjęzyki DDL, DML, DCL.

SQL (ang. Structured Query Language) – strukturalny język zapytań używany do tworzenia,
modyfikowania baz danych oraz do umieszczania i pobierania danych z baz danych.

Język SQL jest językiem deklaratywnym. Decyzję o sposobie przechowywania i pobrania danych
pozostawia się systemowi zarządzania bazą danych (DBMS).

Z technicznego punktu widzenia, SQL jest podjęzykiem danych. Oznacza to, że jest on
wykorzystywany wyłącznie do komunikacji z bazą danych. Nie posiada on cech pozwalających na
tworzenie kompletnych programów. Jego wykorzystanie może być trojakie i z tego względu
wyróżnia się trzy formy SQL-a:

1. SQL interakcyjny (autonomiczny) wykorzystywany jest przez użytkowników w celu
bezpośredniego pobierania lub wprowadzania informacji do bazy. Przykładem może być zapytanie
prowadzące do uzyskania zestawienia aktywności kont w miesiącu. Wynik jest wówczas
przekazywany na ekran, z ewentualną opcją przekierowania go do pliku lub drukarki.

2. Statyczny kod SQL (Static SQL) nie ulega zmianom i pisany jest wraz z całą aplikacją, podczas
której pracy jest wykorzystywany. Nie ulega zmianom w sensie zachowania niezmiennej treści
instrukcji, które jednak zawierać mogą odwołania do zmiennych lub parametrów przekazujących
wartości z lub do aplikacji. Statyczny SQL występuje w dwóch odmianach.

a. Embedded SQL (Osadzony SQL) oznacza włączenie kodu SQL do kodu źródłowego
innego języka. Większość aplikacji pisana jest w takich językach jak C++ czy Java, jedynie
odwołania do bazy danych realizowane są w SQL. W tej odmianie statycznego SQL-a do
przenoszenia wartości wykorzystywane są zmienne.

b. Język modułów. W tym podejściu moduły SQL łączone są z modułami kodu w innym
języku. Moduły kodu SQL przenoszą wartości do i z parametrów, podobnie jak to się dzieje
przy wywoływaniu podprogramów w większości języków proceduralnych. Jest to pierwotne
podejście, zaproponowane w standardzie SQL. Embedded SQL został do oficjalnej
specyfikacji włączony nieco później.

3. Dynamiczny kod SQL (Dynamic SQL) generowany jest w trakcie pracy aplikacji. Wykorzystuje
się go w miejsce podejścia statycznego, jeżeli w chwili pisania aplikacji nie jest możliwe określenie
treści potrzebnych zapytań – powstaje ona w oparciu o decyzje użytkownika. Tę formę SQL
generują przede wszystkim takie narzędzia jak graficzne języki zapytań. Utworzenie
odpowiedniego zapytania jest tu odpowiedzią na działania użytkownika.

Zapytania można zaliczyć do jednego z trzech głównych podzbiorów:

* SQL DML (ang. Data Manipulation Language – „język manipulacji danymi”),

* SQL DDL (ang. Data Definition Language – „język definicji danych”),

* SQL DCL (ang. Data Control Language – „język kontroli nad danymi”).

mod by B-art-eq

DML

DML (Data Manipulation Language) służy do wykonywania operacji na danych – do ich
umieszczania w bazie, kasowania, przeglądania, zmiany. Najważniejsze polecenia z tego zbioru to:

* SELECT – pobranie danych z bazy,

* INSERT – umieszczenie danych w bazie,

* UPDATE – zmiana danych,

* DELETE – usunięcie danych z bazy.

Dane tekstowe muszą być zawsze ujęte w znaki pojedynczego cudzysłowu (').

DDL

Dzięki DDL (Data Definition Language) można operować na strukturach, w których dane są
przechowywane – czyli np. dodawać, zmieniać i kasować tabele lub bazy. Najważniejsze polecenia
tej grupy to:

* CREATE (np. CREATE TABLE, CREATE DATABASE, ...) – utworzenie struktury (bazy, tabeli,
indeksu itp.),

* DROP (np. DROP TABLE, DROP DATABASE, ...) – usunięcie struktury,

* ALTER (np. ALTER TABLE ADD COLUMN ...) – zmiana struktury (dodanie kolumny do tabeli,
zmiana typu danych w kolumnie tabeli).

DCL

DCL (Data Control Language) ma zastosowanie do nadawania uprawnień do obiektów
bazodanowych. Najważniejsze polecenia w tej grupie to:

* GRANT (np. GRANT ALL PRIVILEGES ON EMPLOYEE TO PIOTR WITH GRANT OPTION) –
przyznanie wszystkich praw do tabeli EMPLOYEE użytkownikowi PIOTR z opcją pozwalającą mu
nadawać prawa do tej tabeli.

* REVOKE – odebranie użytkownikowi wszystkich praw do tabeli, które zostały przyznane
poleceniem GRANT.

* DENY.

27.

Instrukcja SELECT.

Polecenie SELECT nazywa się także „zapytaniem”. Polecenie to pobiera krotki z relacyjnej bazy
danych i zwraca w postaci zbioru odczytanych krotek (zbiór taki może być też pusty), opcjonalnie
może je przetworzyć przed zwróceniem. Mówiąc prościej polecenie SELECT służy do odczytywania
danych z bazy danych i dokonywaniu na nich prostych obliczeń i przekształceń.
Najprostszą wersją polecenia SELECT, jest postaci:
Dodatkowo polecenie może zawierać dodatkowe pola, bardziej rozbudowana wersja:
SELECT [DISTINCT] {atrybut1, atrybut2, ....}
FROM {nazwa relacji}
[WHERE {waruek}] [ORDER BY {{wyrażenie5 [ASC|DESC], alias1 [ASC|DESC]}] [LIMIT {limit}];

mod by B-art-eq

28.

Instrukcje DDL i DCL.

DDL (Data Definition Language- Język definiowania danych) definiuje struktury danych, na których
operują instrukcje DML.
Najważniejsze polecenia tej grupy to:
CREATE (np. CREATE TABLE, CREATE DATABASE, ...) – utworzenie struktury (bazy, tabeli, indeksu
itp.),
DROP (np. DROP TABLE, DROP DATABASE, ...) – usunięcie struktury,
ALTER (np. ALTER TABLE ADD COLUMN ...) – zmiana struktury (dodanie kolumny do tabeli, zmiana
typu danych w kolumnie tabeli).

DCL (Data Control Language - Język kontrolowania danych) ma zastosowanie do nadawania
uprawnień do obiektów bazodanowych.
Najważniejsze polecenia w tej grupie to:
GRANT– (GRANT {ALL | lista_uprawnień} TO użytkownik})-przyznaje użytkownikowi uprawnienia
REVOKE – (REVOKE {ALL | lista_uprawnień} TO użytkownik})-zabiera uprawnienia, które zostały
wcześniej przyznane
DENY- (DENY {ALL | lista_uprawnień} TO użytkownik})-Bezpośrednio zabiera uprawnienia

29.

Indeksy w bazach danych, podział indeksów , B+-drzewo.

Indeks jest mechanizmem poprawienia szybkości dostępu do danych bez zmiany struktury ich
przechowywania. Indeks zazwyczaj jest założony na jednym polu rekordu danych.
Natomiast rekord indeksu ma strukturę: <wartość pola, adres w pliku danych> i jest zapisywany do
pliku indeksu w kolejności zgodnej z wartością pola indeksowanego. Plik indeksu jest zazwyczaj
znacznie mniejszy niż plik z danymi.
Indeksy dzielimy na:

• indeks główny – założony na atrybucie porządkującym unikalnym,

• grupujący – założony na atrybucie porządkującym nieunikalnym,

• pomocniczy – założony na atrybucie nieporządkującym.

• Indeks gęsty - posiada rekord indeksu dla każdego rekordu indeksowanego pliku danych

• Indeks rzadki - posiada rekordy tylko dla wybranych rekordów indeksowanego pliku

danych (wskazuje na blok rekordów, a nie poszczególne rekordy)

W miarę wzrostu rozmiarów indeksu wydłuża się czas wyszukiwania po tym indeksie, dlatego wiele
systemów zarządzania bazą danych stosuje pewną formę indeksu wielopoziomowego:

• statyczne wielopoziomowe indeksy – modyfikowanie zawartości pliku z danymi

powoduje, że struktura indeksu staje się nieefektywna

• dynamiczne wielopoziomowe indeksy – B

-Drzewo

B+-drzewo jest zrównoważoną strukturą drzewiastą, w której wierzchołki
wewnętrzne służą do wspomagania wyszukiwania, natomiast wierzchołki liści zawierają
rekordy indeksu ze wskaźnikami do rekordów w plikach danych. Zrównoważenie
struktury oznacza, że odległość (liczba poziomów) od korzenia do dowolnego liścia jest
zawsze taka sama.
W celu zapewnienia odpowiedniej efektywności realizacji zapytań przedziałowych
wierzchołki liści stanowią listę dwukierunkową.
CREATE INDEX <nazwa indeksu> ON <nazwa tabeli> (<nazwa kolumny>)

mod by B-art-eq

30.

Normalizacja., cel normalizacji, postać normalna Boyce'a-Codda.

Normalizacja bazy danych jest to proces mający na celu eliminację powtarzających się danych
w relacyjnej bazie danych. Główna idea polega na trzymaniu danych w jednym miejscu, a w razie
potrzeby linkowania do danych. Taki sposób tworzenia bazy danych zwiększa bezpieczeństwo
danych i zmniejsza ryzyko powstania niespójności (w szczególności problemów anomalii).

Pierwsza postać normalna (1NF)

Relacja jest w pierwszej postaci normalnej, jeśli:

opisuje jeden obiekt,

wartości atrybutów są elementarne

(atomowe, niepodzielne) - każda kolumna jest
wartością skalarną (atomową), a nie macierzą
lub listą czy też czymkolwiek, co posiada własną
strukturę,

nie zawiera kolekcji (powtarzających się grup informacji),

posiada klucz główny,

kolejność wierszy może być dowolna (znaczenie danych nie zależy od

kolejności wierszy).

Właściwości które muszą zaistnieć w 1 formie :

Jest zdefiniowany klucz relacji.

Wszystkie atrybuty nie kluczowe są w zależności funkcyjnej od klucza.

Druga postać normalna (2NF)

Relacja jest w drugiej postaci normalnej wtedy i tylko wtedy gdy jest w I postaci normalnej i każda kolumna
zależy funkcyjnie od całego klucza głównego (a nie np. od części klucza).

Trzecia postać normalna (3NF)

Mamy z nią do czynienia wtedy i tylko wtedy, gdy
tabela jest w 2NF oraz gdy wszystkie pola nie będące
polami klucza głównego są od niego zależne
bezpośrednio.

Wartości w kolumnie "Stawka za godzinę" są zależne
jedynie od pola "Stanowisko", a tylko pośrednio od
klucza głównego. Prowadzi to do powtarzania się
wartość "20 zł".

Sprowadzenie do III postaci normalnej
będzie polegać na przeniesieniu stawek do
osobnej tabeli, a w tabeli pracowników
pozostawienie jedynie nazwy stanowiska.

Postać normalna Boyce'a-Codda

Mówimy, że schemat relacji R ze zbiorem zależności F jest w postaci normalnej

Boyce'a-Codda, jeśli zawsze, gdy w R zachodzi zależność

i atrybut A nie jest zawarty w X, to X jest nadkluczem

do R; oznacza to, że X jest kluczem lub że zawiera klucz. Mówiąc inaczej, jedynymi zależnościami nietrywialnymi są te
zależności , w których klucz wyznacza funkcyjnie jeden lub więcej atrybutów.

mod by B-art-eq

31.

Transakcje, własności transakcji.

Transakcja jest sekwencją logicznie powiązanych operacji na bazie danych, która przeprowadza
bazę danych z jednego stanu spójnego w inny stan spójny. Typy operacji na bazie danych
obejmują: odczyt i zapis danych oraz zakończenie połączone z akceptacja (zatwierdzeniem) lub
wycofaniem transakcji.

Własności ACID
Atomicity - atomowość - zbiór operacji wchodzących w skład transakcji jest niepodzielny, to
znaczy albo zostaną wykonane wszystkie operacje transakcji albo żadna.
Consistency - spójność - transakcja przeprowadza bazę danych z jednego stanu spójnego do
innego stanu spójnego. W trakcie wykonywania transakcji baza danych może być przejściowo
niespójna. Transakcja nie może naruszać ograniczeń integralnosciowych.
Isolation - izolacja - transakcje są od siebie logicznie odseparowane. Transakcje oddziałują na
siebie poprzez dane. Mimo współbieżnego wykonywania, transakcje widza stan bazy danych tak,
jak gdyby były wykonywane w sposób sekwencyjny.
Durability - trwałość - wyniki zatwierdzonych transakcji nie mogą zostać utracone w wyniku
wystąpienia awarii systemu. Zatwierdzone dane w bazie danych, w przypadku awarii, musza być
odtwarzalne.

Podział transakcji ze względu na

porządek operacji:

• sekwencyjne,

• współbieżne;

zależność operacji:

• zależne od danych,

• niezależne od danych;

typ operacji:

• odczytu,

• aktualizujące dane.

mod by B-art-eq

32.

Diody półprzewodnikowe. Tranzystory.

Diodą półprzewodnikową nazywamy element wykonany z półprzewodnika (np. krzem, german),
zawierającego jedno złącze – najczęściej p-n z dwiema końcówkami wyprowadzeń.
Oznaczenia: A – anoda K – katoda n – warstwa ujemna(elektrony) p – warstwa dodatnia

Dioda przepuszcza prąd w jednym kierunku (od anody do katody),
natomiast w kierunku przeciwnym - w minimalnym stopniu
Diody stosowane są w układach analogowych i cyfrowych.
Diody półprzewodnikowe stosuje się w układach prostowania prądu
zmiennego, w układach modulacji i detekcji, przełączania, generacji i
wzmacniania sygnałów elektrycznych.

Każda dioda ma pewną częstotliwość graniczną, po przekroczeniu której nie zachowuje się jak
dioda, lecz jak kondensator
Klasyfikację diod można przeprowadzić ze względu na:

• materiał (krzemowe, germanowe z arsenku galu);

• konstrukcję (ostrzowe i warstwowe; stopowe i dyfuzyjne: mesa, planarne i epiplarne);

• strukturę fizyczną złącza (p-n, m-s, heterozłącza);

• zastosowanie

(prostownicze, uniwersalne, impulsowe, stabilitrony - Zenera,

pojemnościowe - warikapy i waraktory, tunelowe, mikrofalowe: detekcyjne i mieszające);

• przebiegające zjawiska (Zenera, Gunna, lawinowe, tunelowe)

Tranzystor - trójelektrodowy półprzewodnikowy element elektroniczny, posiadający zdolność
wzmacniania sygnału elektrycznego
Wyróżnia się dwie główne grupy tranzystorów:

Tranzystory bipolarne, w których prąd wyjściowy jest funkcją prądu wejściowego
(sterowanie prądowe).
Tranzystory unipolarne (tranzystory polowe), w których prąd wyjściowy jest funkcją
napięcia (sterowanie napięciowe)

Tranzystor posiada trzy końcówki przyłączone do warstw
półprzewodnika, nazywane:
emiter (ozn. E), baza (ozn. B), kolektor (ozn. C)

Znaczenie
Wynalezienie tranzystora uważa się za przełom w elektronice, zastąpił on bowiem duże, zawodne i
energochłonne lampy elektronowe, dając początek coraz większej miniaturyzacji przyrządów i
urządzeń elektronicznych.
Zastosowanie
Tranzystory ze względu na swoje właściwości wzmacniające znajdują bardzo szerokie zastosowanie.
Są wykorzystywane do budowy wzmacniaczy różnego rodzaju. Są kluczowym elementem w
konstrukcji wielu układów elektronicznych, takich jak źródła prądowe, lustra prądowe, stabilizatory,
przerzutniki, generatory i wiele innych.
Z tranzystorów buduje się także bramki logiczne realizujące podstawowe funkcje boolowskie,
Tranzystory są także podstawowym budulcem wielu rodzajów pamięci półprzewodnikowych (RAM,
ROM itp.

mod by B-art-eq

33.

Układy scalone.

Układ scalony jest zminiaturyzowanym układem elektronicznym, który może zawierać w sobie

miliony elementów elektronicznych. Płytki krzemowe bo na nich najczęściej budowane są układy
scalone stanowią podłoże półprzewodnikowe dla elementów elektronicznych jak diody,
kondensatory, tranzystory lub rezystory.

Po zamontowaniu wszystkich elementów płytka zostaje umieszczona w hermetycznie

zamkniętej obudowie z tworzywa sztucznego, szkła bądź metalu. Ze względu na sposób wykonania
układy scalone dzieli się na główne grupy:

•

monolityczne, w których wszystkie elementy, zarówno elementy czynne jak i bierne,
wykonane są w monokrystalicznej strukturze półprzewodnika. Większość stosowanych
obecnie układów scalonych jest wykonana właśnie w tej technologii.

•

hybrydowe – na płytki wykonane z izolatora nanoszone są warstwy przewodnika oraz
materiału rezystywnego, które następnie są wytrawiane, tworząc układ połączeń
elektrycznych oraz rezystory. Do tak utworzonych połączeń dołącza się indywidualne,
miniaturowe elementy elektroniczne (w tym układy monolityczne).

Często używanym wskaźnikiem technicznego zaawansowania procesu oraz gęstości

upakowania elementów układów scalonych jest minimalna długość kanału tranzystora wyrażona w
mikrometrach lub nanometrach. W najnowszych technologiach, w których między innymi
produkowane są procesory firm Intel i AMD, minimalna długość bramki wynosi 22nm.

34.

Układy impulsowe.

Układ sterowania lub regulacji, w którym sygnały wejściowe (sterujące), a często również sygnały
wyjściowe (wielkości sterowane) mogą zmieniać swoje wartości tylko w pewnych chwilach czasu —
uzależnionych od różnych czynników (np. gdy sygnał wejściowy przekracza pewną wartość).

Sam termin układ dyskretny w odróżnieniu od układu ciągłego oznacza, że wartości uwzględniane
w procesie mają postać ciągu impulsów, co odpowiada reprezentacji funkcji tylko w określonych i z
zasady równych odstępach czasu.

Układy dyskretne opisywane są za pomocą równań różnicowych. Transmitancja operatorowa
układów dyskretnych opiera się o przekształcenie Z. Transmitancją impulsową układu dyskretnego
nazywa się stosunek transformaty Z odpowiedzi układu do transformaty Z sygnału wejściowego,
przy zerowych warunkach początkowych:

mod by B-art-eq

35.

Układy cyfrowe.

Układy cyfrowe to rodzaj układów elektronicznych, w których sygnały napięciowe przyjmują tylko
określoną liczbę poziomów, którym przypisywane są wartości liczbowe. Najczęściej (choć nie
zawsze) liczba poziomów napięć jest równa dwa, a poziomom przypisywane są cyfry 0 i 1, wówczas
układy cyfrowe realizują operacje zgodnie z algebrą Boole'a i z tego powodu nazywane są też
układami logicznymi. Obecnie układy cyfrowe budowane są w oparciu o bramki logiczne
realizujące elementarne operacje znane z algebry Boola: iloczyn logiczny (AND, NAND), sumę
logiczną (OR, NOR), negację NOT, różnicę symetryczną (XOR) itp. Ze względu na stopień
skomplikowania współczesnych układów wykonuje się je w postaci układów scalonych.

Zalety układów cyfrowych:

•

Możliwość bezstratnego kodowania i przesyłania informacji – jest to coś, czego w układach
analogowych operujących na nieskończonej liczbie poziomów napięć nie sposób
zrealizować.

•

Zapis i przechowywanie informacji cyfrowej jest prostsze.

•

Mniejsza wrażliwość na zakłócenia elektryczne.

•

Możliwość tworzenia układów programowalnych, których działanie określa program
komputerowy

Wady układów cyfrowych:

•

Są skomplikowane zarówno na poziomie elektrycznym, jak i logicznym i obecnie ich
projektowanie wspomagają komputery (patrz: język opisu sprzętu).

•

Chociaż są bardziej odporne na zakłócenia, to wykrywanie przekłamań stanów logicznych,
np. pojawienie się liczby 0 zamiast spodziewanej 1, wymaga dodatkowych zabezpieczeń
(patrz: kod korekcyjny) i też nie zawsze jest możliwe wykrycie błędu. Jeszcze większy
problem stanowi ewentualne odtworzenie oryginalnej informacji.

Klasyfikacja układów cyfrowych

Ze względu na sposób przetwarzania informacji rozróżnia się dwie główne klasy układów
logicznych:

•

układy kombinacyjne – układy „bez pamięci”, w których sygnały wyjściowe są zawsze takie
same dla określonych sygnałów wejściowych;

•

układy sekwencyjne – układy „z pamięcią”, w których stan wyjść zależy nie tylko od
aktualnego stanu wejść, ale również od stanów poprzednich.

Ze względu na technologie w jakiej wykonano bramki logiczne:

•

bipolarne, (niewielki prąd płynący pomiędzy dwiema jego elektrodami (nazywanymi bazą i
emiterem) steruje większym prądem płynącym między innymi elektrodami (kolektorem i
emiterem)).

•

unipolarne, (sterowanie prądem odbywa się za pomocą pola elektrycznego).

mod by B-art-eq

Ograniczenia techniczne

Ze względu na różne czynniki, takie jak wahania napięcia zasilającego,
zakłócenia zewnętrzne, rozrzut parametrów itp. sygnały przetwarzane
w układach cyfrowych nie mają ściśle określonych wartości, stąd też
liczby przypisuje się nie wartościom napięć, ale przedziałom napięć.

W układach logicznych, gdzie są zdefiniowane tylko dwie wartości
liczbowe, rozróżnia się dwa przedziały napięć: wysoki (ozn. H, z ang.
high) i niski (ozn. L, z ang. low); pomiędzy nimi jest przerwa, dla której
nie określa się wartości liczbowej – jeśli napięcie przyjmie wartość z
tego przedziału, to stan logiczny układu jest nieokreślony.

Jeśli do napięć wysokich zostanie przyporządkowana logiczna jedynka, a do niskich logiczne zero,
wówczas mówi się, że układ pracuje w logice dodatniej (inaczej zwaną pozytywną), w przeciwnym
razie mamy do czynienia z logiką ujemną (inaczej zwaną negatywną).

36.

Pamięci półprzewodnikowe, magnetyczne, optyczne.

W zależności od konstrukcji i zastosowania można je podzielić na pamięci o dostępie swobodnym
– np. pamięć RAM, ROM czy dysk twardy lub sekwencyjnym – np. taśma magnetyczna. Inną
metodą jest podział na pamięci ulotne – przechowujące informację tylko kiedy są zasilane oraz
nieulotne, przechowujące dane również po wyłączeniu zasilania.

W zależności od technologii w której są wykonane mogą to być:

•

pamięci półprzewodnikowe (np. RAM, EEPROM);

•

magnetyczne (dysk twardy, taśma magnetyczna), optyczne (dysk CDROM, taśma filmowa)

Rodzaj pamięci

Cechy

Pamięci
półprzewodnikowe

•

Bardzo szybkie – czas dostępu rzędu ns (nanosekund)

•

Bardzo duży transfer danych – rzędu GB/s (Gigabajtów na sekundę)

•

Duża cena za jednostkę pojemności

•

Możliwość bezpośredniego sprzężenia z mikroprocesorami

•

Zapis, odczyt, zachowywanie danych:

Utrata informacji po odłączeniu zasilania (RAM)

Tylko do odczytu (ROM)

Trwały odczyt i zapis (EEPROM, Flash)

Pamięci dyskowe
(magnetyczne,
optyczne)

•

Wolne – duży czas dostępu rzędu ms (milisekund)

•

Średni transfer danych – rzędu dziesiątek MB/s (megabajtów na sekundę)

•

Niewielka cena za jednostkę pojemności

•

Wymagają specjalnych układów (interfejsowych – pośredniczących)

•

Podtrzymują dane bez zasilania

•

Możliwość realizacji jako pamięci wymiennych – nośnik jest oddzielony od
czytnika

mod by B-art-eq

37.

Przetworniki analogowo-cyfrowe i cyfrowo-analogowe.

Przetwornik C/A przetwarzający sygnał cyfrowy na sygnał analogowy w postaci prądu
elektrycznego lub napięcia o wartości proporcjonalnej do tej liczby. Innymi słowy jest to układ
przetwarzający dyskretny sygnał cyfrowy na równoważny mu sygnał analogowy. Taki przetwornik
ma n wejść i jedno wyjście. Przetworniki C/A pracują w oparciu jedną z trzech metod przetwarzania:
równoległą, wagową, zliczania.

Przetwornik A/C to układ służący do zamiany sygnału analogowego (ciągłego) na reprezentację
cyfrową (sygnał cyfrowy). Dzięki temu możliwe jest przetwarzanie ich w urządzeniach
elektronicznych opartych o architekturę zero-jedynkową oraz gromadzenie na dostosowanych do
tej architektury nośnikach danych. Proces ten polega na uproszczeniu sygnału analogowego do
postaci skwantowanej (dyskretnej), czyli zastąpieniu wartości zmieniających się płynnie do wartości
zmieniających się skokowo w odpowiedniej skali (dokładności) odwzorowania. Przetwarzanie A/C
tworzą 3 etapy: próbkowanie, kwantyzacja (dyskretyzacja) i kodowanie.

38.

Metody pomiarów wielkości elektrycznych.

Do wykonania pomiarów elektrycznych niezbędne są odpowiednie przyrządy pomiarowe:

woltomierz – miernik napięcia,

amperomierz – miernik natężenia prądu elektrycznego,

omomierz – miernik oporu ( rezystancji ),

watomierz – miernik mocy.

Pomiar napięcia
Miernik napięcia (woltomierz) podłączamy w
obwodzie do:

•

źródła prądu (ogniwo, bateria) – miernik
pokazuje napięcie źródła (

ŹR

)

•

odbiornika prądu (obciążenia) – miernik
pokazuje spadek napięcia w obwodzie na
odbiorniku (

ODB

)

Gdy obwód jest zamknięty i pominiemy wpływ
oporu elektrycznego, to woltomierz

pokaże

wartość napięcia źródła taką samą, jak
woltomierz

(rys. a). Gdy obwód jest otwarty,

to woltomierz

pokaże wartość napięcia źródła,

a woltomierz

wskazywać będzie „0” (rys. b).

Pomiary natężenia prądu elektrycznego

Miernik natężenia prądu elektrycznego (amperomierz)

podłączamy w obwodzie szeregowo. Aby instrument
pomiarowy (A) pokazał wartość natężenia prądu (I) obwód musi
być zamknięty, a źródło prądu i odbiorniki w obwodzie muszą
być sprawne.

mod by B-art-eq

Pomiar oporu
Miernik oporu (omomierz) podłączamy bezpośrednio do
końcówek elektrycznych odbiornika (

OBC

Jeśli dokonujemy pomiaru oporu odbiornika będącego w
obwodzie elektrycznym, to pamiętamy, by sprawdzić opór tylko w
otwartym obwodzie. Nie wolno mierzyć oporu odbiornika
elektrycznego znajdującego się pod napięciem.

Pomiar mocy
Miernik mocy (watomierz) posiada dwa wewnętrzne obwody pomiarowe:

• napięciowy – podłączany równolegle do odbiornika (

OBC

) w obwodzie,

• prądowy – podłączany szeregowo w układzie elektrycznym.

39.

Metody pomiarów wielkości nieelektrycznych.

Ze względu na wymaganą dokładność i czułość, wielkości nieelektryczne mierzy się dziś
metodami elektrycznymi. Obecnie tylko te metody umożliwiają wykonywanie pomiarów wielkości
szybko zmieniających się w czasie, prowadzenie tych pomiarów zdalnie i automatycznie.
Obecnie metodami elektrycznymi mierzy się następujące wielkości:

•

geometryczne (długość, kąt, gładkość powierzchni)

•

kinetyczne (prędkość, przyspieszenie)

•

dynamiczne (siłę, ciężar, naprężenie, ciśnienie)

•

akustyczne (natężenie dźwięku)

•

optyczne (natężenie oświetlenia, strumień świetlny)

•

cieplne (temperaturę, ilość ciepła)

•

fizykochemiczne materii (kwasowość, lepkość, wilgotność)

W pomiarach tych wielkości nieelektryczne muszą być zamienione na wielkości elektryczne. Do
tego służą przetworniki pomiarowe. Wielkości elektryczne pojawiające się na wyjściu
przetwornika są następnie mierzone metodami elektrycznymi, przy czym przyrządy pomiarowe
mogą być wyskalowane w jednostkach mierzonych wielkości nieelektrycznych.

Przetworniki:

•

parametryczne - zmiana wielkości nieelekt. powoduje zmianę parametru elektrycznego

przetwornika - rezystancji, indukcyjności

•

generacyjne - zmiana wielkości nieelekt. powoduje powstanie siły elektromotorycznej stałej

lub zmiennej w czasie).

mod by B-art-eq

40.

Generatory kwarcowe – czas i częstotliwość w komputerze

Generatory kwarcowe - generatory drgań elektrycznych małej mocy, ale wielkiej częstości,
charakteryzujące się niezwykle dużą stabilnością drgań. Wykorzystano w nich własności
piezoelektryczne kryształu kwarcu. Umożliwiają wytwarzanie sygnału o częstotliwościach od 10 kHz
do 200 MHz. Taki typ generatora jest stosowany w układach taktujących, układach impulsowych,
we wzorcach częstotliwości, a także w zegarach kwarcowych. Służy, jako wzorzec częstości i
wzorzec czasu.
Czas i częstotliwość w komputerze:
Częstotliwość przerwań zegarowych zależna jest od sposobu zaprogramowania licznika.
Tak, więc im wyższa częstotliwość przerwań zegarowych tym większa dokładność pomiaru czasu w
systemie. Jednak częstotliwość taka, nie może być też zbyt wysoka, gdyż obsługa przerwania
zegarowego absorbuje określony ułamek mocy procesora.
Częstotliwość przerwań zegarowych jest kompromisem pomiędzy dokładnością pomiaru czasu, a
narzutem na obsługę przerwań zegarowych.
W większości stosowanych obecnie systemów częstotliwość przerwań leży pomiędzy 10Hz, a
1000Hz.

41.

Grafy. Grafy eulerowskie i hamiltonowskie.

Graf to zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda

krawędź kończy się i zaczyna w którymś z wierzchołków.

Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie jest grafem

skierowanym. Krawędź może posiadać także wagę, to znaczy przypisaną liczbę, która określa na
przykład odległość między wierzchołkami. W grafie skierowanym wagi mogą być zależne od
kierunku przechodzenia przez krawędź.

Graf hamiltonowski to graf zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek

dokładnie jeden raz zwaną ścieżką Hamiltona. W szczególności grafem hamiltonowskim jest
graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona. W niektórych źródłach graf
zawierający tylko ścieżkę Hamiltona nazywany jest grafem półhamiltonowskim.

Graf eulerowski, graf Eulera – graf eulerowski odznacza się tym, że da się w nim skonstruować

cykl Eulera, czyli drogę, która przechodzi przez każdą jego krawędź dokładnie raz i wraca do
punktu wyjściowego. Liczba krawędzi stykających się z danym wierzchołkiem nazywana jest jego
stopniem. Jeżeli wszystkie wierzchołki grafu nieskierowanego mają stopień parzysty, to znaczy,
że da się skonstruować zamkniętą ścieżkę Eulera nazywaną cyklem Eulera. Jeżeli najwyżej dwa
wierzchołki mają nieparzysty stopień, to możliwe jest zbudowanie tylko takiej ścieżki Eulera,
która nie jest zamknięta. Graf zawierający cykl Eulera jest nazywany grafem eulerowskim, a graf
posiadający jedynie ścieżkę Eulera nazywany jest półeulerowskim.

Graf skierowany - ruch może odbywać się tylko w kierunkach wyznaczonych przez krawędzie.

Poruszanie się "pod prąd" jest zabronione. Każdy wierzchołek posiada pewną liczbę krawędzi
wejściowych nazywaną stopniem wchodzącym. Analogicznie ilość krawędzi wychodzących to
stopień wychodzący. Graf skierowany posiada drogę Eulera, gdy wszystkie wierzchołki z
wyjątkiem dwóch mają takie same stopnie wychodzące i wchodzące, w jednym z tych dwóch
wierzchołków stopień wychodzący jest o 1 większy niż wchodzący a w drugim odwrotnie. Inaczej
skierowany graf eulerowski definiowany jest jako graf silnie spójny, w którym dla każdego
wierzchołka grafu liczba krawędzi wchodzących jest równa ilości krawędzi wychodzących.

mod by B-art-eq

42.

Kolorowanie grafów, definicja liczby chromatycznej grafu i indeksu

chromatycznego.

Kolorowanie grafu polega na przyporządkowaniu koloru każdemu węzłowi w grafie przy
wykorzystaniu jak najmniejszej liczby kolorów (liczby chromatycznej). Jednakże przy założeniu, że
dwa różne ale przyległe do siebie węzły nie będą miały tego samego koloru. Takie kolorowanie
stosuje się często na mapach do oznaczenia terenów lub do określenia jak składować chemikalia
bo jak wiadomo niektóre substancje po zetknięciu się ze sobą mogą spowodować eksplozje.

Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu
(najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle
określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem
wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie
wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest
poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego
koloru.

Podstawowe definicje

•

Klasyczne (wierzchołkowe) kolorowanie grafu - przyporządkowywanie wierzchołkom grafu

liczb naturalnych w taki sposób, aby końce żadnej krawędzi nie miały przypisanej tej samej
liczby. Ze względów historycznych oraz dla lepszego zobrazowania problemu mówi się o
kolorowaniu, przy czym różnym kolorom odpowiadają różne liczby.

•

Pokolorowaniem wierzchołków grafu nazywamy jedno konkretne przyporządkowanie

kolorów wierzchołkom. Pokolorowanie jest legalne (dozwolone), gdy końcom żadnej krawędzi
nie przyporządkowano tego samego koloru.

•

Optymalnym pokolorowaniem danego grafu nazywamy legalne pokolorowanie zawierające

najmniejszą możliwą liczbę kolorów.

Liczba chromatyczna - w teorii grafów jest to liczba kolorów (liczb) niezbędna do optymalnego
klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba k taka, że
możliwe jest legalne pokolorowanie wierzchołków grafu k kolorami. Oznacza się ją symbolem χ(G).

Algorytmy kolorowania grafów

Algorytm LF (largest first)

Kolorowanie grafu za pomocą algorytmu LF można opisać następująco:

•

Uporządkuj wierzchołki grafu malejąco według ich stopni (liczby krawędzi z nich wychodzących).

•

Koloruj wierzchołki zachłannie, zgodnie z ustaloną wcześniej kolejnością (zaczynając od

wierzchołka o największym stopniu).

Algorytm LF jest algorytmem statycznym, gdyż raz ustalona kolejność wierzchołków nie zmienia się
w trakcie jego działania. Najmniejszym dość trudnym grafem jest ścieżka P6.

mod by B-art-eq

Algorytm SL (smallest last)

Algorytm SL wygląda następująco:
•

Znajdź wierzchołek o minimalnym stopniu i usuń go z grafu.

•

Powtarzaj krok pierwszy tak długo, aż graf będzie pusty (zapamiętaj kolejność usuwanych

wierzchołków).

•

Koloruj wierzchołki zachłannie, zgodnie z ustaloną wcześniej kolejnością (zaczynając od

wierzchołków usuniętych później).

Algorytm SL jest statyczny, jego złożoność wynosi O(n + m), gdzie n - liczba wierzchołków, m –
liczba krawędzi.
Algorytm SLF (saturated largest first)
Kolorowanie grafu przy pomocy algorytmu SLF polega na wykonaniu poniższych czynności:
Dopóki istnieją nie pokolorowane wierzchołki wykonuj operacje:

•

znajdź wierzchołek o maksymalnym stopniu spośród wierzchołków o maksymalnym stopniu

nasycenia pokoloruj

•

znaleziony wierzchołek zachłannie

Stopniem nasycenia wierzchołka nazwiemy tu liczbę różnych kolorów sąsiednich z tym
wierzchołkiem. Złożoność algorytmu SLF wynosi O(mlogn).

Indeks chromatyczny grafu określa minimalną liczbę kolorów wystarczającą do prawidłowego
pokolorowania krawędzi grafu. Indeks chromatyczny grafu jest równy liczbie chromatycznej jego
grafu krawędziowego.

Znalezienie indeksu chromatycznego jest problemem NP-trudnym, mimo że można bardzo
dokładnie oszacować jego wartość. V. G.

43.

Ciąg Fibonacciego. Definicja rekurencyjna i wzór ogólny.

Ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący:
Kolejne elementy tego ciągu to liczby stanowiące sumę
dwóch poprzednich elementów z wyjątkiem dwóch
pierwszych.

Kolejne liczby tego ciągu to: 0, 1, 1, 2, 3, 5, 8, 13, 21…
fib(n) {
if(n<2) return n;
return fib(n-1) + fib(n-2);
}
Jedną wartość fib(n) będziemy liczyć więcej niż jeden raz. Zdecydowanie więcej niż jeden raz.

Ponieważ drugi człon tego wyrażenia szybko zbiega do zera

mod by B-art-eq

44.

Grafy planarne.

Graf planarny – graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie
grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności
nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi
zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim.

Kryterium Kuratowskiego
Dwa minimalne grafy, które nie są planarne,
to K

i K

3,3

. Twierdzenie Kuratowskiego

mówi, że graf skończony jest planarny
wtedy i tylko wtedy, gdy nie zawiera
podgrafu homeomorficznego z grafem K

ani z grafem K

3,3

Wzór Eulera
Dowolny rysunek płaski grafu planarnego wyznacza spójne obszary płaszczyzny zwane ścianami.
Dokładnie jeden z tych obszarów, zwany ścianą zewnętrzną, jest nieograniczony.

Zgodnie z wzorem Eulera, jeżeli G jest grafem spójnym i planarnym,
to | V | + | S| − | E | = 2,
gdzie
V - zbiór wierzchołków,
E - zbiór krawędzi,
S - zbiór ścian dowolnego rysunku płaskiego grafu G.

Wnioski ze wzoru Eulera:
Jeżeli G jest planarny, to

Jeżeli G jest planarny, to wierzchołek o najmniejszym stopniu jest stopnia co najwyżej 5.

Zgodnie z twierdzeniem o czterech barwach, graf planarny daje się zawsze pokolorować przy
użyciu co najwyżej czterech kolorów.

mod by B-art-eq

45.

Drzewa spinające grafu. Minimalne drzewa spinające.

Drzewem rozpinającym (ang. Spanning Tree) grafu G nazywamy drzewo, które zawiera wszystkie
wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu. Konstrukcja
drzewa rozpinającego polega na usuwaniu z grafu tych krawędzi które należą do cykli.
Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree ) jest to drzewo rozpinające
danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo
rozpinające o mniejszej sumie wag krawędzi.
Istnieją deterministyczne algorytmy o złożoności liniowo-logarytmicznej znajdujące dla zadanego
grafu minimalne drzewo rozpinające. Są to:

Algorytm Prima (nazywany też algorytmem Dijkstry-Prima)

•

utwórz drzewo zawierające jeden wierzchołek, dowolnie wybrany z grafu,

•

powtarzaj, dopóki drzewo nie obejmuje wszystkich wierzchołków grafu:

•

wśród krawędzi, których jeden wierzchołek należy do drzewa, a drugi nie, wybierz krawędź o

najmniejszej wadze; jeśli takich gałęzi jest wiele, wybierz dowolną z nich,

•

dodaj tę krawędź wraz z drugim wierzchołkiem do drzewa.

Algorytm Kruskala

•

Utwórz las L z wierzchołków oryginalnego grafu – każdy wierzchołek jest na początku

osobnym drzewem.

•

Utwórz zbiór S zawierający wszystkie krawędzie oryginalnego grafu.

•

Dopóki S nie jest pusty:

•

Wybierz i usuń z S krawędź o minimalnej wadze.

•

Jeśli krawędź ta łączyła dwa różne drzewa, to dodaj ją do lasu L, tak aby połączyła dwa

odpowiadające drzewa w jedno.

•

W przeciwnym wypadku odrzuć ją.

Po zakończeniu algorytmu L jest minimalnym drzewem rozpinającym.

46.

Typy zmiennych. Podział. Przykłady w wybranym języku programowania.

Typ liczbowy

Zmienne typu liczbowego dzielimy przede wszystkim na liczby całkowite (są to liczby bez części
dziesiętnych) i zmiennoprzecinkowe nazywane również rzeczywistymi (te liczby mają już części
dziesiętne). W zależności jaki typ wybierzemy mamy w każdym do wyboru kilka typów różniących się ilością
zajmowanych bajtów w pamięci i przedziałem wartości. Jedynie typ decimal może występować jako typ
całkowity (dokładny) lub zmiennoprzecinkowy.

int i = 10;
long l = 13456;
byte b = 100;
float f = 3.14;
double d = 45.349134;

mod by B-art-eq

Typ znakowy

Zmienne typu znakowego służą do przechowywania pojedynczego znaku, umieszcza się go w parze
pojedynczych cudzysłowów. Jeśli chcemy by zapisać więcej znaków trzeba zadeklarować tablicę typu char.

string B = "B";

// zmienna typu string przechowująca literę B.

char literaB = Char.Parse("B");

// zamiana typu string na char.

Typ łańcuchowy (string)

Typ string jest typem obiektowym, reprezentującym jednowymiarowy zbiór znaków.

string s = "Imię";
string s1 = "234";
string s2 = "Mam na imię Adam i mam 21 lat.";

Tablice
Tablica to ciąg zmiennych jednego typu. Ciąg taki posiada jedną nazwę a do jego poszczególnych
elementów odnosimy się przez numer (indeks).

typ nazwa_tablicy[rozmiar];
int tablica[20];

Typ wskaźnikowy
Wskaźnik zawiera adres zmiennej. Deklaracja zmiennych typu wskaźnikowego zawiera
operator * po nazwą typu, na który ma wskazywać. Kiedy chcemy uzyskać adres zmiennej,
poprzedzamy ją operatorem &. Kiedy chcemy się odwołać do elementu wskazywanego przez
wskaźnik, piszemy przed nazwą wskaźnika *.

47.

Rodzaje pętli. Uwarunkowanie zastosowań. Problem równoważności pętli

w wybranym języku programowania.

Pętla, z definicji, to element języka programowania pozwalający na wielokrotne, kontrolowane
wykonywanie danego fragmentu kodu.
Zasadniczo, w języku C/C++ zdefiniowane są trzy rodzaje pętli:

• Pętla warunkowa do…while

• Pętla warunkowa while…

• Pętla krokowa for…

mod by B-art-eq

Zaczynając od pętli warunkowych, pętla do… i pętla while… są sobie równoważne pod względem
konstrukcyjnym. Różnica tkwi w miejscu sprawdzania warunku. W przypadku pętli do… najpierw
wykonywany jest ciąg operacji objęty pętlą, a potem sprawdzany jest warunek. Jeśli warunek nie
zostanie spełniony, następuje zakończenie wykonywania pętli, i przejście do instrukcji
następujących po bloku pętli. Zatem warunek, jest warunkiem wyjścia z pętli. Pętlę do... można
interpretować jako „Wykonuj instrukcje dopóki jest spełniony warunek”.
do
{
instrukcje
} while ( warunek )

Analogicznie do powyższego, działa pętla while…. Tutaj warunek jest sprawdzany przed
wykonaniem pętli. Jeśli warunek jest spełniony zostaną wykonane instrukcje zawarte w bloku pętli.
Zatem tutaj, warunek jest warunkiem wejścia do pętli. Pętlę while… można interpretować jako
„Dopóki warunek jest spełniony wykonuj instrukcje”
while ( warunek )
{
instrukcje
}

Pętla do… zostanie wykonana co najmniej raz (zanim warunek zostanie sprawdzony), natomiast
pętla while… może nie wykonać się ani razu (warunek jest sprawdzany zanim wykonane zostaną
jakiekolwiek instrukcje z pętli). W wyniku tej różnicy, w przypadku przekształcania pętli do… na
pętlę while… konieczne może okazać się dopisanie instrukcji poprzedzających samą pętlę.
Odrębnym rodzajem jest pętla krokowa for…. Odrębnym, ponieważ pętla jest wykonywana zadaną
ilość razy kontrolowaną przez licznik, tworzony specjalnie na potrzeby tej pętli. W pierwszym
wierszu pętli określa się wartość początkową licznika, wartość końcową licznika i kierunek zmiany
licznika: inkrementację lub dekrementację.
for ( [ początek ] ; [ warunek ] ; [ cykl ] )
{
instrukcje
}

Równoważność między pętlą krokową for… i pętlami warunkowymi while… i do… jest tylko
częściowa. Pętlę for… zawsze można zaimplementować za pomocą pętli while… lub do…,
przenosząc bezpośrednio warunek kończący lub zanegowany warunek początkowy i dodając do
instrukcji wewnątrz pętli, instrukcję inkrementującą lub dekrementującą licznik. Implementacja w
drugim kierunku jednak nie zawsze jest możliwa.

mod by B-art-eq

48.

Zmienne typu adresowego (wskaźniki). Implementacja w wybranym języku

programowania.

Zmienne typu adresowego, zamiast faktycznej wartości danego typu, przechowują adres fizycznej
pamięci, przechowujący właściwą zmienną z wartością. Wykorzystywane są najczęściej, jeśli funkcja
ma operować na głównej zmiennej, a nie standardowo na jej kopii utworzonej na potrzeby funkcji.
W przypadku deklarowania wskaźnika dla tablicy, pod tą zmienną znajduje się adres pierwszej
komórki tej tabeli. Aby dostać się do kolejnych komórek tabeli należy inkrementować odpowiednio
zmienną wskaźnika.

49.

Funkcje (z wzmianką o procedurach). Przekazywanie parametrów przez

wartość i referencję lub adres.

Funkcja jest to fragment kodu, który może być wywołany wielokrotnie w różnych miejscach
programu. Każda funkcja powinna zwracać wynik wykonanego kodu. Procedura nie zwraca
wartości.
typ nazwa_funkcji (parametry){

// instrukcje

}
typ – jest to typ zwracanej wartości przez daną funkcję. Np. int, double, void (oznacza, że funkcja
nie zwraca wartości)
parametry – podajemy typ parametru i jego nazwę np. (int zmienna, double zmiennaB)
void f1(int c, int d){
c++;
d++;
}
void f2(int &x, int &y){
x++;
y++;
}
int main(){
int a, b;
cout << "Podaj a: ";

cin >> a;
cout << "\nPodaj b: ";
cin >> b;
cout << "\nWprowadzone liczby: a= "
<< a << ", b= " << b;
f1(a, b);
cout << "\nPo wykonaniu funkcji f1: a= "
<< a << ", b= " << b;
f2(a, b);
cout << "\nPo wykonaniu funkcji f2: a= "
<< a << ", b= " << b;

Przekazywanie parametrów przez wartość (funkcja f1) – pracujemy na kopiach zmiennych a i b,
czyli nie zostaną one zmienione w głównym programie.
Przekazywanie parametrów przez referencję (funkcja f2) – do funkcji przekazujemy adresy
zmiennych a i b, czyli pracujemy na wartościach przechowywanych w ich adresach.

Implementacja wskaźnika dla zmiennej typu int.

int* wsk;

Implementacja wskaźnika dla bloku dowolnego typu pamięci

void* wsk;

wskaźnik 3-elementowej tablicy liczb całkowitych,

int (*ptab)[3];

wskaźnik do 3-elementowej tablicy wskaźników,

int *(*ptab)[3];

Tablica 4 wskaźników liczb całkowitych

int *tab[4]; lub int
(*tab[4]);

stały wskaźnik typu całkowitego

int *const pc

wskaźnik stałej typu całkowitego

int const *pxc

mod by B-art-eq

50.

Cechy programowania strukturalnego. Kluczowe różnice między

programowaniem strukturalnym a obiektowym.

Zasady programowania strukturalnego
W projektowaniu programu można zastosować dwie metody:

•

analityczną, czyli podejście "z góry na dół" (ang. top-down)

•

syntetyczną, czyli podejście "z dołu do góry" (ang. bottom-up)

Metoda analityczna polega na podziale zadania na mniejsze podzadania, które z kolei można
podzielić na jeszcze mniej złożone zadania, itd. aż kolejne podzadania staną się tak proste, że
ich realizacja będzie oczywista.
Metoda syntetyczna polega na dokładnie odwrotnym postępowaniu niż w metodzie
analitycznej. Najpierw zajmujemy się realizacją podzadań elementarnych i w następnych krokach
budujemy zadania bardziej złożone składające się z zadań elementarnych aż dojdziemy do
realizacji całego programu.
Do kluczowych różnic między programowaniem strukturalnym a obiektowym zaliczamy:

• program pisany strukturalnie – zawiera „bloki”, gdzie program pisany obiektowo zawiera

obiekty czyli byty

• dane i procedury w programowaniu strukturalnym nie są ze sobą bezpośrednio powiązane

• programy strukturalne nie posiadają takich cech jak: abstrakcja, hermetyzacja, polimorfizm,

dziedziczenie – charakterystyczne dla programowania obiektowego

• programowanie obiektowe może być oparte na wzorach projektowych – gdzie strukturalne

ma sztywną metodę pisania

•

51.

Zalety języków programowania obiektowo orientowanych. Składniki

klasy. Konstruktory i destruktory. Podać przykłady.

Zalety programowania obiektowego
a) łatwość przekładania poszczególnych wymogów na poszczególne moduły systemu;
b) kolejną zaletą jest możliwość wielokrotnego zastosowania poszczególnych modułów systemu;
c) każdy moduł odpowiedzialny jest za konkretne zadanie, nie występuje dublowanie
funkcjonalności co pozwala szybko i skutecznie poprawiać powstałe błędy.

Klasa jest to grupa danych i funkcji, które na tych danych operują. Tworząc klasę tworzymy nowy
typ danych, którego składnikami są inne typy danych.

Składnik klasy to element należący do danej klasy. Składnikami klasy mogą być: pola,
konstruktory, destruktory, metody, właściwości, indeksatory, delegacje, operatory jak również
zagnieżdżone: klasy, struktury listy wyliczeniowe czy interfejsy.

mod by B-art-eq

Definiując klasę możemy ograniczyć dostęp do niektórych składników klasy. Są trzy rodzaje
dostępu do składników:

a) public - oznacza, że składniki deklarowane po tej etykiecie są dostępne z każdego miejsca
programu,
b) private - oznacza, że składniki deklarowane po tej etykiecie dostępne są tylko dla funkcji
składowych tej klasy; funkcje globalne (zwykłe) nie mają dostępu do tych składników, a więc z
funkcji main również nie ma dostępu do tych danych,
c) protected - tak jak w przypadku private z tą tylko różnicą, że dostęp do takich składników
mają jeszcze klasy wywodzące się z tej klasy (będzie to wytłumaczone przy dziedziczeniu)

Definicja klasy przechowującej dane osobowe:

class osoba
{

public:

char imie[20];

char nazwisko[30];

int wiek;

osoba(char imie, char nazwisko, int wiek)

{

this->imie=imie;

this->nazwisko=nazwisko;

this->wiek=wiek;

};

// konstruktor z parametrami

osoba(const osoba &osoba1)

{

imie=imie.osoba1;

nazwisko=nazwisko.osoba1;

wiek=wiek.osoba1

};

// konstruktor kopiujący

virtual ~osoba();

// destruktor wirtualny, bezparametrowy

};
osoba osoba1(Jan, Kowalski,30); // wywołanie konstruktora
osoba osoba2(osoba1); // wywołanie konstruktora kopiującego
osoba1.osoba::~osoba(); // wywołanie destruktora

Konstruktor jest to funkcja w klasie, wywoływana w trakcie tworzenia każdego obiektu danej
klasy. Funkcja może stać się konstruktorem gdy spełni poniższe warunki

•

Ma identyczną nazwę jak nazwa klasy

•

Nie zwraca żadnej wartości (nawet void)

•

Jest ustawiona w przestrzeni publicznej klasy (sekcja public:)

Należy dodać że każda klasa ma swój konstruktor. Nawet jeżeli nie zadeklarujemy go jawnie
zrobi to za nas kompilator (stworzy wtedy konstruktor bezparametrowy).

Destruktor jest natomiast funkcją, którą wykonuje się w celu zwolnienia pamięci; następuje
niszczenie obiektu danej klasy.

mod by B-art-eq

52.

Zastosowanie składników statycznych w klasie. Statyczne funkcje

składowe. Podać przykłady.

Czasami zachodzi potrzeba dodania elementu, który jest związany z klasą, ale nie z konkretną
instancją tej klasy. Możemy wtedy stworzyć element statyczny. Element statyczny jest właśnie
elementem, który jest powiązany z klasą, a nie z obiektem tej klasy, czyli np. statyczna metoda
nie może się odwołać do niestatycznej zmiennej lub funkcji.

Elementy statyczne poprzedza się podczas definicji słówkiem static. Statyczne mogą być
zarówno funkcje, jak i pola należące do klasy.

class Klasa
{
protected:
static int iloscInstancji; // pole statyczne
public:
Klasa()
{
iloscInstancji++;
}
virtual ~Klasa()
{
iloscInstancji--;
}
static int IloscInstancji()
{
return iloscInstancji;
}
};

int Klasa::iloscInstancji=0;

Do obiektów statycznych z wewnątrz klasy możemy się odwołać tak samo jak do innych pól. Pole
IloscInstancji jest polem statycznym - powstanie tylko jedna instancja tego pola.

W powyższym przykładzie ponadto istnieje metoda statyczna. Z takiej metody nie można się
odwołać do niestatycznych elementów klasy. Zarówno do klasy statycznej jak do statycznego
pola możemy się odwołać nawet jeżeli nie został stworzony żaden obiekt klasy Klasa.

Odwołanie się do metody statycznej IloscInstancji z programu wymaga następująco:

int i=Klasa::IloscInstancji();

Gdyby zaś pole iloscInstancji było publiczne, a nie chronione, to moglibyśmy się do niego
odwołać poprzez:

int i=Klasa::iloscInstancji;

Ponieważ jednak w powyższym przykładzie pole iloscInstancji jest chronione możemy się do
niego odwołać jedynie z klasy Klasa bądź z klas które po niej dziedziczą.

mod by B-art-eq

Statyczne funkcje składowe

Funkcje składowe klasy mogą być zadeklarowane jako statyczne. Takie funkcje można wywołać
nawet wtedy, gdy nie istnieje jeszcze żaden obiekt klasy. Do jej nazwy z zewnątrz klasy
odwołujemy się poprzez nazwę klasy za pomocą operatora zasięgu, czyli „czterokropka” ('

'),

albo za pomocą operatora wyboru składowej (kropka) - nie ma wtedy znaczenia, jakiego obiektu
tej klasy użyjemy. Ponieważ funkcja statyczna nie jest wywoływana na rzecz obiektu, ale jak
funkcja globalna, nie można w niej odwoływać się do this ani do żadnych składowych
niestatycznych - te bowiem istnieją tylko wewnątrz konkretnych obiektów i w każdym z nich
mogą być różne. Można natomiast w funkcjach statycznych klasy odwoływać się do składowych
statycznych tej klasy: innych funkcji statycznych i zmiennych klasowych (określanych przez
statyczne pola klasy).

53.

Dziedziczenie. Dostęp do składników klasy. Kolejność wywołania

konstruktorów. Przypisanie i inicjalizacja obiektów w warunkach
dziedziczenia.

Dziedziczenie to w programowaniu obiektowym operacja polegająca na stworzeniu nowej klasy
na bazie klasy już istniejącej. Stosowana najczęściej przy tworzeniu potomnych klas
specjalizowanych, lub przy tworzeniu klas użytkowych z klasy abstrakcyjnej. Dziedziczenie jest
właściwie tym, co oddziela zwykłe programowanie przy użyciu abstrakcyjnych typów danych od
właściwego programowania obiektowego.

Dostęp do składników klasy głównej jest zależny od tego w jakich sekcjach są one zdefiniowane.
Do składników z sekcji private danej klasy mają dostęp jedynie metody i przyjaciele tej klasy. Aby
więc klasa dziedzicząca mogła naprawdę dziedziczyć z klasy głównej, wszystkie typy danych w
klasie głównej muszy być typu public lub protected. Oczywiście w klasie głównej mogą istnieć
typy danych w sekcji private, ale nie mogą być kluczowe dla wykonania operacji dziedziczenia,
czyli nie mogą powodować upośledzenia klasy potomnej.

W języku C++ dziedziczenie odbywa się za pomocą następującego zapisu:
class KlasaPotomna : public KlasaGlowna
{ public:
KlasaPotomna(float x, int y, int z) : KlasaGlowna(x, y, z) { }
};
Pierwszy wiersz jest właściwym dziedziczeniem, zapisem jak nazywa się klasa potomna i z jakiej
klasy dziedziczy. Niezbędne jest aby znalazło się tu słowo kluczowe public. W przeciwnym
przypadku odziedziczony np. konstruktor będzie dostępny w klasie, jednak nie, już poza nią, czyli
nie będzie widoczny w sekcji main(), a co za tym idzie, nie będzie możliwe utworzenie żadnego
obiektu nowej klasy. Koniecznej jest też stworzenie konstruktora klasy potomnej, nawet jeśli
będzie identyczny z konstruktorem klasy głównej i odpowiedni zapis po „dwukropku”
oznaczający z jakiej funkcji (konstruktora) będzie dziedziczyć. Sam konstruktor jest pusty, więc
będzie dziedziczyć wszystkie właściwości z konstruktora klasy głównej. Nie jest natomiast
konieczne ponowne definiowanie destruktora, jeśli nie będzie się różnił od destruktora w klasie
głównej. Podobnie jest z innymi funkcjami klasy głównej. Są dziedziczone bez uprzedniego
definiowania.

mod by B-art-eq

Bardzo ważną rzeczą, na którą trzeba zwrócić uwagę jest to, że klasa, która powstaje poprzez
dziedziczenie, nie musi być identyczna jak klasa główna. Może ona zawierać więcej, bądź mniej
zmiennych. Konstruktor i destruktor może zawierać dodatkowe instrukcje. Można dodać do klasy
dodatkowe funkcje i zmienne.

W przypadku, gdy konstruktor klasy potomnej będzie zawierał dodatkowe instrukcje względem
konstruktora klasy głównej, będzie można zauważyć, że konstruktory wywoływane są w pewnej
kolejności. Mianowicie najpierw wykonuje się konstruktor klasy z której się dziedziczy, a
następnie instrukcje konstruktora klasy dziedziczącej.
Przy wywoływaniu funkcji z klasy potomnej lub głównej, gdy funkcje publiczne w obu
przypadkach mają taką samą nazwę, należy poprzedzać je zapisem przynależności do przestrzeni
odpowiedniej klasy:
KlasaPotomna.funkcja1(); KlasaGlowna.funkcja1();

54.

Polimorfizm. Deklarowanie funkcji wirtualnych. Mechanizm wywołania.

Podać przykłady.

Polimorfizm - mechanizmy pozwalające programiście używać wartości, zmiennych i
podprogramów na kilka różnych sposobów. Inaczej mówiąc jest to możliwość wyabstrahowania
wyrażeń od konkretnych typów.
Podczas pisania programu wygodnie jest traktować nawet różne dane w jednolity sposób.
Niezależnie czy należy wydrukować liczbę czy napis, czytelniej (zazwyczaj) jest gdy operacja taka
nazywa się po prostu drukuj, a nie drukuj_liczbę i drukuj_napis. Jednak napis musi być drukowany
inaczej niż liczba, dlatego będą istniały dwie implementacje polecenia drukuj ale nazwanie ich
wspólną nazwą tworzy wygodny abstrakcyjny interfejs niezależny od typu drukowanej wartości.

Funkcje wirtualne to specjalne funkcje składowe, które przydają się szczególnie, gdy używamy
obiektów posługując się wskaźnikami lub referencjami do nich.
Dla zwykłych funkcji z identycznymi nazwami to, czy zostanie wywołana funkcja z klasy
podstawowej, czy pochodnej, zależy od typu wskaźnika, a nie tego, na co faktycznie on wskazuje.
Dysponując funkcjami wirtualnymi będziemy mogli użyć prawdziwego polimorfizmu - używać
metod klasy pochodnej wszędzie tam, gdzie spodziewana jest klasa podstawowa. W ten sposób
będziemy mogli korzystać z metod klasy pochodnej korzystając ze wskaźnika, którego typ
odnosi się do klasy podstawowej.

class

Baza

{

public

void

pisz()

{

std::cout

"Tu funkcja pisz z klasy Baza"

std::endl;

}

};

class

Baza2 :

public

Baza

{

public:

void

pisz()

{

std::cout

"Tu funkcja pisz z klasy Baza2"

std::endl

;

}

};

mod by B-art-eq

Jeżeli teraz w funkcji main stworzymy wskaźnik do obiektu typu Baza, to możemy ten wskaźnik
ustawiać na dowolne obiekty tego typu. Można też ustawić go na obiekt typu pochodnego, czyli
Baza2:

Po skompilowaniu na ekranie zobaczymy dwa wypisy: "Tu funkcja pisz z klasy Baza". Stało

się tak dlatego, że wskaźnik jest do typu Baza. Gdy ustawiliśmy wskaźnik na obiekt typu
pochodnego (wolno nam), a następnie wywołaliśmy funkcję składową, to kompilator "na ślepo"
sięgnął po funkcję pisz z klasy bazowej (bo wskaźnik wskazuje na klasę bazową).

Można jednak określić żeby kompilator nie sięgał po funkcję z klasy bazowej, ale sam się

zorientował na co wskaźnik pokazuje. Do tego służy przydomek virtual, a funkcja składowa nim
oznaczona nazywa się wirtualną. Różnica polega tylko na dodaniu słowa kluczowego virtual, co
wygląda tak:

Gdy funkcja jest oznaczona jako wirtualna, kompilator nie przypisuje na stałe wywołania

funkcji z tej klasy, na którą pokazuje wskaźnik, już podczas kompilacji. Pozostawia decyzję co do
wyboru właściwej wersji funkcji aż do momentu wykonania programu - jest to tzw. późne
wiązanie. Wtedy program skorzysta z krótkiej informacji zapisanej w obiekcie a określającej klasę,
do jakiej należy dany obiekt. Dopiero po odczytaniu informacji o klasie danego obiektu
wybierana jest właściwa metoda.

Wirtualność nie gra roli gdy nie używamy wskaźników; kompilator generuje wtedy taki sam

kod, jakby wszystkie funkcje były niewirtualne. Przy wskaźnikach musi orientować się czytając
informację o klasie obiektu, na który wskazuje wskaźnik.

int

main()

{
Baza* wsk;
Baza objB;
Baza2 objB2;

wsk = &objB;
wsk -> pisz();

wsk = &objB2;

// Teraz ustawiamy wskaźnik wsk na obiekt typu pochodnego

wsk -> pisz();

return

;

}

class

Baza

{

public:

virtual void

pisz()

{

std::cout

"Tu funkcja pisz z klasy baza"

std::endl

;

}

};

class

Baza2 :

public

Baza

{

public:

virtual void

pisz()

{

std::cout

"Tu funkcja pisz z klasy Baza2"

std::endl;

}

};

mod by B-art-eq

55.

Definiowanie szablonu klasy. Korzystanie z szablonu.

Szablonów klas używamy, jeśli planujemy używać podobnych/identycznych struktur dla różnych
typów danych. Np: stos, kolejka, lista dla wartości całkowitych, rzeczywistych lub znaków.

Definiowanie szablonu klasy:
template <class T>
class Stack
{
public:
Stack();
void push(T i);
T pop();
private:
int top;
T st[100];
};
template <class T>
Stack<T>::Stack()
{
top = -1;
}

Korzystanie z szablonu:
Stack<int> ii;
Stack<string> ss;
ii.push(25);
ss.push("Hello");
cout<<ii.pop();
cout<<ss.pop();

Specjalizowanie szablonu:
Jeśli dla konkretnego typu danych
potrzebna

nam

inna

implementacja,

możemy użyć specjalizacji szablonu:

template <>
class Stack <string>
{
public:
[...]
string pop_uppercase ()
{
string str;
str = st[top--];
for (int i=0; i<str.length(); i++)
{
str[i] = toupper(str[i]);
}
return str;
}
private:
int top;
string st[100];
};

56.

Cykl pracy procesora przy wykonaniu programu.

Typowy cykl rozkazowy w systemie o architekturze von Neumanna zaczyna się od pobrania
rozkazu z pamięci i przesłania go do rejestru rozkazów (ang. instruetion register). Rozkaz jest
następnie dekodowany i realizowany (może spowodować pobranie argumentów z pamięci i
umieszczenie ich w innym rejestrze wewnętrznym). Po wykonaniu rozkazu na argumentach jego
wynik można z powrotem
przechować

pamięci.

Zauważmy, że jednostka pamięci
„widzi" tylko strumień adresów
pamięci. Nie jest jej znany
sposób, wjaki one powstały
(licznik rozkazów, indeksowanie,
modyfikacje pośrednie, adresy
literalne itp.) ani czemu służą.

mod by B-art-eq

57.

Procesy, zarządzanie procesami.

Proces jest to po prostu egzemplarz wykonywanego programu. Należy odróżnić jednak proces
od wątku. Każdy proces posiada własną przestrzeń adresową, natomiast wątki posiadają wspólną
sekcję danych.
Każdemu procesowi przydzielone zostają zasoby, takie jak:

•

procesor

•

pamięć

•

dostęp do urządzeń wejścia-wyjścia

•

pliki

Każdy proces posiada tzw. "rodzica". W ten sposób tworzy się swego rodzaju drzewo procesów.
Proces może (ale nie musi) mieć swoje procesy potomne. Za zarządzanie procesami odpowiada
jądro systemu operacyjnego. Wykonanie musi przebiegać sekwencyjnie.
Może przyjmować kilka stanów:

• działający,

• czekający na udostępnienie przez system operacyjny zasobów,

• przeznaczony do zniszczenia,

• właśnie tworzony itd. -proces zombie

W skład procesu wchodzi:

• kod programu

• licznik rozkazów

• stos

• sekcja danych

Zarządzanie procesami

• System operacyjny odpowiada za następujące działania dotyczące zarządzania procesami:

tworzenie i usuwanie

• planowanie porządku wykonywania

• mechanizmy synchronizacji, komunikacji

• usuwanie zakleszczeń

Stany procesu:

• proces jest aktywny jeśli znajduje się w stadium wykonywania

• proces jest zablokowany jeśli oczekuje przydzielenia zasobu innego niż procesor

• proces jest gotowy jeśli znajduje się w stanie gotowości (mógłby natychmiast wykorzystać

procesor gdyby mu został przydzielony)

• proces jest uśpiony jeśli nie jest jeszcze śledzony przez system operacyjny

• proces jest zakończony jeśli zakończył swoje działanie

mod by B-art-eq

58.

Metody przydziału pamięci operacyjnej procesowi. Organizacja pamięci

wirtualnej.

Pamięć możemy traktować jak dużą tablicę słów (maszynowych). W zależności od architektury,
słowo maszynowe składa się z określonej liczby (będącej potęgą 2-ki) bitów, np. 32, 64 czy 128.
Pozycję słowa w tablicy, jaką jest pamięć, nazywamy adresem. Adres jest liczbą binarną złożoną z
określonej liczby bitów. Zwykle liczba tych bitów jest również potęgą 2-ki, często taką samą jak w
słowie maszynowym, choć nie zawsze.

Metody przydziału pamięci

Gdy system operacyjny przydziela procesowi obszar pamięci, to zwykle może go przydzielić z
jednego z wielu obszarów wolnej pamięci. Oczywiście obszar wolnej pamięci, z którego
przydzielamy pamięć musi być wystarczająco duży. Istnieje kilka strategii wybierania, z którego
obszaru przydzielić pamięć.

First-Fit - Jest to najprostsza możliwa strategia. Wybierany jest pierwszy (pod względem
adresów) wolny obszar, który jest wystarczająco duży.

Best-Fit - Wybieramy najmniejszy wolny obszar, który jest wystarczająco duży. Pomysł, który się
kryje za tą strategią jest następujący: Wolny obszar jest zwykle większy niż przydzielany obszar,
więc po przydzieleniu część wolnego obszaru pozostaje wolna. W przypadku strategii best-fit,
taka "końcówka" jest możliwie najmniejsza. Jeśli w przyszłości nie wykorzystamy jej, to straty z
powodu fragmentacji zewnętrznej będą możliwie małe.

Worst-fit - Przydzielamy pamięć zawsze z największego wolnego obszaru (oczywiście, o ile jest
on wystarczająco duży). W przypadku tej strategii, część obszaru, która pozostaje wolna jest
możliwie jak największa. Jest więc szansa, że będzie można ją jeszcze wykorzystać bez
konieczności kompaktyfikacji.

Segmentacja

Pamięć wykorzystywana przez proces, z logicznego punktu widzenia, nie stanowi jednego
spójnego obszaru. Zwykle składa się z kilku segmentów. Typowe segmenty to: kod programu,
zmienne globalne, stos i sterta. System operacyjny może więc przydzielać procesom pamięć nie
w postaci jednego spójnego bloku, ale kilku takich bloków, segmentów. Co więcej, proces może
w trakcie działania prosić o przydzielenie lub zwolnienie segmentów.

Stronicowanie

Stronicowanie to rozwiązanie, w którym proces widzi spójny obszar pamięci logicznej, ale nie
tworzy ona spójnego obszaru w pamięci fizycznej. Zarówno pamięć logiczna, jak i pamięć
fizyczna jest podzielona na kawałki równej wielkości. W odniesieniu do pamięci logicznej
mówimy o stronach, a w odniesieniu do pamięci fizycznej mówimy o ramkach. Wielkość stron i
ramek jest potęgą dwójki z przedziału od 512B do 16MB. Typowa wielkość to 4kB. Strony i ramki
są podstawowymi jednostkami przydziału pamięci. W rezultacie, wielkość przydzielonego
procesowi obszaru jest wielokrotnością wielkości ramek i stron. Strony pamięci logicznej mogą
być umieszczone w dowolnych ramkach pamięci fizycznej.

mod by B-art-eq

Pamięć wirtualna

jest techniką programową a także sprzętową gospodarowania pamięcią

operacyjną RAM pozwalającą na przydzielanie pamięci dla wielu procesów, zwalnianie jej i
powtórne przydzielanie, w ilości większej niż rzeczywista ilość pamięci fizycznej zainstalowanej w
komputerze poprzez przeniesienie danych z ostatnio nie używanej pamięci do pamięci masowej
(np. twardego dysku), w sytuacji gdy procesor odwołuje się do danych z pamięci przeniesionej
na dysk przesuwa się te dane do pamięci w wolne miejsce, a gdy brak wolnej pamięci zwalnia się
ją przez wyżej opisane przerzucenie jej na dysk.

Najczęściej spotykane są dwa sposoby przechowywania danych zrzuconych z pamięci fizycznej
na dysk. Pierwszy, stosowany w systemach rodziny Windows polega na zapisie pamięci w pliku
znajdującym się na ustalonej partycji komputera. Drugi, stoso-wany w systemach z rodziny UNIX
to utworzenie osobnej partycji wymiany (partycji swap) przeznaczonej wyłącznie na pamięć
wirtualną. Zapewnia to szybszy dostęp do danych niż pierwsze rozwiązanie (głównie ze względu
na ominięcie obsługi systemu plików).

59.

Funkcje systemowe – podstawowe kategorie, przykłady.

Wywołanie systemowe (ang. system call) stanowi interfejs między wykonywanym programem a
(posiadającym zwykle wyższe uprawnienia) jądrem systemu operacyjnego. Funkcje systemowe
wywoływane są przez specjalny, wspierany przez dany procesor mechanizm, na przykład z
użyciem wyznaczonego przerwania lub instrukcji skoku dalekiego.
Mechanizm ten pozwala na realizację zależnych od platformy sprzętowej zadań, do
których proces użytkownika może nie mieć bezpośredniego dostępu.
Funkcje udostępniane przez system operacyjny możemy pogrupować w następujący sposób
KATEGORIE:

• operacje na procesach Ta grupa funkcji obejmuje m.in.: tworzenie nowych procesów,

uruchamianie programów, zakończenie się procesu, przerwanie działania innego procesu,
pobranie informacji o procesie, zawieszenie i wznowienie procesu, oczekiwanie na
określone zdarzenie, przydzielanie i zwalnianie pamięci,

• operacje na plikach Ta grupa funkcji obejmuje takie operacje, jak: utworzenie pliku,

usunięcie pliku, otwarcie pliku, odczyt z pliku, zapis do pliku, pobranie lub zmiana
atrybutów pliku.

• operacje na urządzeniach Zamówienie i zwolnienie urządzenia, odczyt z i zapis do

urządzenia, pobranie lub zmiana atrybutów urządzenia, (logiczne) przyłączenie lub
odłączenie urządzenia.

• informacje systemowe Funkcje te obejmują pobieranie i/lub ustawianie najrozmaitszych

informacji systemowych, w tym: czasu i daty, wersji systemu operacyjnego, atrybutów
użytkowników itp.

• komunikacja Ta grupa funkcji obejmuje przekazywanie informacji między procesami.

Spotykane są dwa schematy komunikacji: przekazywanie komunikatów i pamięć
współdzielona. Przekazywanie komunikatów polega na tym, że jeden proces może wysłać
(za pośrednictwem systemu operacyjnego) pakiet informacji, który może być odebrany
przez drugi proces. Mechanizm pamięci współdzielonej polega na tym, że dwa procesy
uzyskują dostęp do wspólnego obszaru pamięci. Cokolwiek jeden z procesów zapisze w
tym obszarze, będzie widoczne dla drugiego procesu.

mod by B-art-eq

60.

Szeregowanie procesów. Wybrane algorytmy szeregowania.

Algorytm szeregowania (ang. scheduler, planista) - część jądra wielozadaniowego systemu
operacyjnego, odpowiedzialna za przydzielanie dostępu do procesora dla poszczególnych
procesów. Planista musi także uwzględniać priorytety procesów i ich gotowość do wykonania
oraz przeciwdziałać zagłodzeniu procesu poprzez przedłużający się brak dostępu do zasobów
oraz tzw. inwersji priorytetów.

Rozróżniamy dwa typy planistów: krótkoterminowi i długoterminowi. Planista krótkoterminowy
odpowiada za wybór procesów spośród gotowych do wykonania. Musi być on bardzo szybki, w
przeciwieństwie do planisty długoterminowego, który wybiera procesy z pamięci masowej i
ładuje do pamięci operacyjnej.

Najpopularniejsze rodzaje algorytmów szeregowania
FIFO - algorytm powszechnie stosowany, jeden z prostszych w realizacji, dający dobre efekty w
systemach ogólnego przeznaczenia; zadanie wykonuje się aż nie zostanie wywłaszczone przez
siebie lub inne zadanie o wyższym priorytecie

Planowanie priorytetowe - wybierany jest proces o najwyższym priorytecie. W tej metodzie
występuje problem nieskończonego blokowania (procesu o niskim priorytecie przez procesy o
wysokim priotytecie). Stosuje się tu postarzanie procesów, polegające na powolnym
podnoszeniu priorytetu procesów zbyt długo oczekujących.

Planowanie rotacyjne ('round-robin) - Planista przydziela każdemu z procesów kwant czasu i
jeżeli nie zdąży się wykonać to ląduje na końcu kolejki FCFS.
W systemach operacyjnych czasu rzeczywistego (stosowanych m. in. w automatyce)
najważniejszym zadaniem algorytmu szeregowania jest zapewnienie, by wykonanie danego
procesu zakończyło się przed upływem zdefiniowanych dla niego ograniczeń czasowych.
Opracowano w tym celu deterministyczne algorytmy szeregowania, takie jak RMS, EDF i inne.

Algorytm wywłaszczający - Algorytm, który może przerwać wykonanie procesu i przenieść go z
powrotem do kolejki.

Algorytm niewywłaszczający - Algorytm, w którym procesy przełączają się dobrowolnie. Proces
aktywny (wykonujący się) jest przenoszony do kolejki procesów oczekujących tylko wtedy, gdy
sam przerwie (wstrzyma, zawiesi) swe działanie; dopóki tego nie uczyni (lub nie zakończy
działania), żaden inny proces nie otrzyma dostępu do procesora.

http://pl.wikipedia.org/wiki/Algorytm_szeregowania

mod by B-art-eq

61.

Synchronizacja procesów współbieżnych. Semafory.

Procesy współbieżne to takie procesy, które są wykonywane jednocześnie w systemie
operacyjnym. Można je podzielić na dwie kategorie: niezależne oraz współpracujące. Procesy
współpracujące mogą wpływać na inne procesy lub podlegać ich oddziaływaniom. Mogą
również dzielić wspólne dane, do których trzeba zagwarantować zsynchronizowany dostęp, aby
zapewnić ich spójność, tzn. nie można dopuścić do sytuacji, w której wykonywane na nich zmiany
zaburzają się wzajemnie.

Każdy proces ma sekcję krytyczną, to znaczy segment kodu, w którym może zmieniać
współdzielone dane. Cechą tego rozwiązania jest to, że w danej chwili tylko jeden proces może
wykonywać swoją sekcję krytyczną. Proces musi poprosić o wejście do sekcji krytycznej – ten
fragment kodu nazywa się sekcją wejściową. Może również wystąpić sekcja wyjściowa. Problem
sekcji krytycznej musi spełniać trzy warunki:

wzajemne wykluczanie,

postęp,

ograniczone czekanie.

Sekcję krytyczną łatwo zastosować w systemie jednoprocesorowym, dużo trudniej w
wieloprocesorowym. W takich systemach potrzebne są specjalne, niepodzielne rozkazy
realizowane sprzętowo.

Jednym z narzędzi do synchronizacji jest semafor. Semafor to zmienna całkowita, która
przyjmuje pewną początkową wartość (zazwyczaj 1) i na której można wykonać tylko dwie
operacje: wait i signal. Są to operacje niepodzielne. Jeśli jeden proces zmienia wartość semafora,
to żaden inny proces nie może jednocześnie tego robić.

Każdy proces przed wejściem do sekcji krytycznej wywołuje funkcję wait, która sprawdza wartość
semafora:

w klasycznej definicji semafora: Jeżeli wartość jest większa od zera, to proces wchodzi do

sekcji krytycznej, zmniejsza wartość semafora o jeden i modyfikuje dane. Gdy wartość
semafora jest równa bądź mniejsza niż 0 proces wykonuje pętlę w sekcji wejściowej, tak
długo aż nie dostanie pozwolenia na wejście do swojej sekcji krytycznej (dopóki inny
proces nie zwiększy wartości semafora) – jest to tak zwane aktywne czekanie,

w definicji semafora z kolejką procesów: proces najpierw zmniejsza wartość semafora a

następnie sprawdza czy jest ona większa bądź równa 0. Jeżeli tak, to proces wchodzi do
sekcji krytycznej. W przeciwnym razie proces blokuje się, tzn. dodaje do kolejki związanej
z semaforem i przechodzi w stan czekania. Moduł z wartości semafora jest liczbą
czekających procesów.

Proces, który zakończy wykonywanie sekcji krytycznej wywołuje funkcję signal, która dla
klasycznego semafora zwiększa jego wartość o jeden. W przypadku rozwiązania semafora z
kolejką procesów czekających, funkcja signal zwiększa wartość semafora o jeden i wznawia jeden
z procesów czekających w kolejce.

Istnieje też druga konstrukcja semafora: semafor binarny. Różni się on od wcześniejszego,
zwanego semaforem zliczającym, tym, że przyjmuje tylko dwie wartości: 0 lub 1.

mod by B-art-eq

62.

Cykle projektowania i życia oprogramowania.

• strategiczna (ang. strategy) wykonywana przed formalnym podjęciem decyzji o realizacji

przedsięwzięcia. W tej fazie podejmowane są decyzje strategiczne odnośnie podejmowania
przedsięwzięcia projektowego: zakresu, kosztów, czasu realizacji itp.

• analizy (ang. analysis), w której budowany jest logiczny model systemu,

• dokumentacji, w której wytwarzana jest dokumentacja użytkownika. Opracowywanie

dokumentacji przebiega równolegle z produkcją oprogramowania. Faza ta praktycznie
rozpoczyna się już w trakcie określania wymagań. Sugeruje się nawet, że podręcznik
użytkownika dla przyszłego systemu jest dobrym dokumentem opisującym wymagania.
Ostatnie uaktualnienia w dokumentacji dokonywane są w fazie instalacji.

• określania wymagań, w której określane są cele oraz szczegółowe wymagania wobec

tworzonego systemu,

• projektowania (ang. design), w której powstaje szczegółowy projekt systemu spełniającego

ustalone wcześniej wymagania,

• implementacji/kodowania (ang. implementation/coding) oraz testowania modułów, w której

projekt zostaje zaimplementowany w konkretnym środowisku programistycznym oraz
wykonywane są testy poszczególnych modułów,

• testowania, w której następuje integracja poszczególnych modułów połączona z testowaniem

poszczególnych podsystemów oraz całego SI,

• instalacji, w której następuje przekazanie systemu użytkownikowi,

• konserwacji, w której oprogramowanie jest wykorzystywane przez użytkownika (ów), a

producent dokonuje konserwacji SI (a przede wszystkim oprogramowania) – wykonuje
modyfikacje polegające na usuwaniu błędów, zmianach i rozszerzaniu funkcji systemu;

• likwidacja, w której wykonuje się czynności związane z zakończeniem użytkowania SI

63.

Klasyfikacja narzędzi wspierających wytwarzanie oprogramowania.

Zintegrowane środowisko programistyczne (ang. Integrated Development Environment, IDE)

jest to aplikacja lub zespół aplikacji (środowisko) służących do tworzenia, modyfikowania,
testowania i konserwacji oprogramowania.

Przykłady:

• pakiet Microsoft Visual Studio (popularny na systemach rodziny Windows)

• Eclipse i NetBeans (domyślnie stworzone dla Javy; posiadają możliwość rozszerzenia, w celu

obsługi innych języków)

• Zend Studio (rozwiązanie dedykowane dla jezyka PHP)

• Dev-C++

CASE (Computer-Aided Software Engineering,) - oprogramowanie używane do

komputerowego wspomagania projektowania oprogramowania.

Narzędzia CASE automatyzują metody projektowania, dokumentacji oraz tworzenia struktury
kodu programu w wybranym języku programowania, najczęściej w programowaniu obiektowym.
Typowymi narzędziami CASE są:

• narzędzia do modelowania w języku UML i podobnych

• narzędzia do zarządzania konfiguracją zawierające system kontroli wersji

• narzędzia do re factoringu

mod by B-art-eq

Systemy kontroli wersji (ang. version/revision control system) służą do śledzenia zmian

głównie w kodzie źródłowym oraz pomocy programistom w łączeniu i modyfikacji zmian
dokonanych przez wiele osób w różnych momentach.
a)

Wolnodostępne systemy kontroli wersji:

• Scentralizowane: RCS, CVS, Subversion

• Rozproszone: Bazaar, Codeville, svk

Zamknięte (własnościowe) systemy kontroli wersji:

• StarTeam firmy Borland

• Visual SourceSafe firmy Microsoft

• Visual Studio Team Foundation Server firmy Microsoft

Kompilatory(ang. compiler) - programy służący do automatycznego tłumaczenia kodu

napisanego w jednym języku (języku źródłowym) na równoważny kod w innym języku (języku
wynikowym)

Przykłady:

• Microsoft Visual Studio

• GNU Compiler for Java

• MIDletPascal

Narzędzia wspomagające kompilację

• Ccache

• Distcc

• Scratchbox

Narzędzia wspomagające budowę aplikacji

• Autotools

• Autoconf

• Autoheader

• Automake

Narzędzia do analizy programów (Debuggery)

programy komputerowy służący do dynamicznej analizy innych programów, w celu odnalezienia
i identyfikacji zawartych w nich błędów, zwanych z angielskiego bugami (robakami).
Debugger jest standardowym wyposażeniem większości współczesnych środowisk
programistycznych
Przykładowe Debuggery:

• GNU Debugger

• SoftICE

mod by B-art-eq

64.

Metody oraz strategie testowania oprogramowania.

Testowanie oprogramowania – proces związany z wytwarzaniem oprogramowania. Jest on
jednym z procesów kontroli jakości oprogramowania. Testowanie ma dwa główne cele:

• weryfikację oprogramowania

• walidację oprogramowania.

Wyróżniamy testy:
1. Statyczne: proces pozwalający na wyszukanie błędów od fazy zbierania wymagań
biznesowych poprzez konstruowanie kodu, aż po dostarczenie produktu, jednak bez
uruchamiania aplikacji.
Testy statyczne przeprowadzane są przy użyciu:

• Przegląd jest procesem lub spotkaniem podczas którego produkt/system jest

przedstawiany członkom zespołu projektowego, użytkownikom oraz innym
zainteresowanym stronom w celu uzyskania komentarzy lub aprobaty dla danego
rozwiązania.

Przeglądy mogą dotyczyć:
- wymagań
- specyfikacji
- kodu
- strategii testów
- planu testów
- warunków koniecznych do przeprowadzenia testów
- przypadków testowych
- instrukcji użytkownika

• Analiza statyczna jest to analiza struktury kodu źródłowego lub kodu skompilowanego bez

jego uruchomienia. Analiza statyczna może odbywać się na etapie budowania aplikacji,
ponieważ jej wyniki są dostępne już podczas kompilacji kodu źródłowego.

2. Dynamiczne:

• Testy funkcjonalne (testy czarnej skrzynki lub black box testing). Tester nie ma dostępu do

kodu testowanej aplikacji. Testy wykonywane są przez osobę, która nie tworzyła aplikacji
w opaciu o dokumentację oraz założenia funkcjonalne. Pozwala to na wykrycie błędów
związanych z np. brakiem implementacji funkcjonalności opisanych przez wymagania,
jednak nie pozwala precyzyjnie określić miejsca w którym dany błąd występuje. W zakres
testów metodą czarnej skrzynki wchodzi badanie wartości brzegowych oraz definiowanie
klas równoważności.

• Testy strukturalne (structural tests lub white-box tests).Przykładem testów strukturalnych

są testy jednostkowe (unit tests), które polegają na stworzeniu kodu sprawdzającego
poprawność działania właściwego kodu aplikacji.
Do zdefiniowania zasad przejścia przez ścieżki aplikacji, używane są kryteria pokrycia pętli
i warunków.

mod by B-art-eq

65.

Instalacja i konserwacja oprogramowania.

Przez instalację (wdrożenie) systemu informatycznego rozumiemy przekazanie systemu

użytkownikowi, po czym następuje etap funkcjonowania SI i jego konserwacji (usuwania błędów,
modyfikacji).

Proces wdrożenia zależy od tego, czy wytwarzane oprogramowanie jest seryjnym

(komercyjnym) − sprzedawanym w wielu egzemplarzy, czy też jest stworzono na konkretne
zamówienie (jest dedykowanym SI). W tym ostatnim wypadku na etapie wdrożenia dokonuje się:

Szkolenie przyszłych administratorów systemu oraz jego użytkowników.

Instalacja sprzętu i oprogramowania.

Wprowadzanie rzeczywistych danych do baz danych.

Uruchomienie systemu i nadzorowanie, wspólnie z przedstawicielami klienta, za przebiegiem

jego pracy.

Usuwanie znalezionych błędów w programach i dokumentacji.

Przekazanie systemu użytkownikowi.

Konserwacja oprogramowania polega na wykonaniu ewentualnych modyfikacji

oprogramowania. Tymi modyfikacjami mogą być:

Dostosowanie oprogramowania do zmian zachodzących w środowisku pracy klienta (zmian

pewnych funkcji systemu).

Dostosowanie oprogramowania do zmian sprzętu, urządzeń technicznych.

Poprawianie jakości oprogramowania.

Usuwanie odnalezionych błędów.

66.

Zagadnienia etyczne i prawne związane z procesem wytwarzania i

użytkowania oprogramowania.

Przykłady nieetycznych zachowań w obszarze IT obejmują:

• przejmowanie cudzych pomysłów i projektów,

• kradzież informacji, przedkładanie plagiatów,

• złośliwe usuwanie dokumentów,

• handel danymi,

• zarzucanie niechcianą informacją,

• zamieszczanie informacji obraźliwych,

• celowe przeciążanie serwerów

Podobnie marnotrawstwo publicznych funduszy podczas budowy dużych systemów
informatycznych o zasięgu krajowym występuje niemal w każdym kraju. Do często spotykanych
błędów w kontraktach publicznych na oprogramowanie zalicza się:

•

Deklarowane wirtualne koszty, tj. takie, które pozwolą wygrać przetarg,

•

Nierealny termin dostawy,

•

Nieprawidłowy harmonogram etapów,

•

Świadomie niekompletne wymagania,

•

Brak doświadczenia dostawcy w danej dziedzinie zastosowań,

•

Długi okres wyczekiwania na poprawę zgłaszanych defektów,

•

Brak alternatywnych procedur na wypadek niepowodzenia przedsięwzięcia
programowego,

•

Niewystarczająca troska o walidację danych.

mod by B-art-eq

67.

Etapy cyklu życia systemu informatycznego i ich charakterystyka

Poszczególne etapy realizowane są sekwencyjnie, w podanej poniżej kolejności, co upraszcza
znacznie zarządzanie przedsięwzięciami realizowanymi z wykorzystaniem tej metodyki.

Określenie założeń i celów systemu
Etap ten jest konieczny przed rozpoczęciem pracy analityków i projektantów systemu.
Najczęściej jest on realizowany przez Komitet Sterujący, w którym zasiadają przedstawiciele
najwyższego szczebla kierownictwa przedsiębiorstwa. W deklaracji założeń i celów należy
przedstawić problem, który powinien zostać rozwiązany oraz obszar działania, którego on
dotyczy.
Efektem końcowym tego etapu jest deklaracja założeń i celów projektu

Zebranie informacji i studium możliwości
Efektem tego etapu jest ocena technicznych możliwości rozwiązania problemów i realizacji
założeń projektu. Wykonanie zadań związanych z tym etapem wymaga zebrania informacji
charakteryzujących obecnie wykorzystywany system pracy, niezbędne jest zebranie i zbadanie
dokumentacji organizacyjnej, obserwacja, wywiady z pracownikami. Mogą tutaj zostać
zaprezentowane różne warianty rozwiązań w ogólnym zarysie wraz z szacunkiem kosztów,
efektów i możliwości realizacji. Celem tego etapu jest dostarczenie danych niezbędnych do
podjęcia decyzji o kontynuowaniu prac nad projektem.
Efektem realizacji tego etapu jest dokument: studium możliwości

Analiza systemu
Faza ta obejmuje dekompozycję funkcji systemu, a następnie stworzenie modelu logicznego
przepływu danych i procesów niezbędnych do realizacji opisanych funkcji. Efektem tej fazy jest
model logiczny systemu uzupełniony o specyfikację algorytmów przetwarzania, słowniki danych i
modele danych. Do akceptacji modelu niezbędna jest zgoda zarządu i użytkowników, że model
jest pełnym i logicznym odzwierciedleniem problematycznego obszaru funkcjonowania.
Produktem końcowym tego etapu jest model logiczny systemu

Projektowanie ogólne
Po analizie systemu, projektanci mogą przystąpić do konstrukcji logicznej struktury systemu.
Następuje wybór procesów, które będą wspomagane informatycznie i tych, które pozostaną, z
różnych względów, realizowane w sposób tradycyjny. Następuje wybór optymalnej platformy
sprzętowej, struktury bazy danych, itp. Efektem tej fazy są różne warianty projektowanego
systemu, wraz z ich oceną dotyczącą kosztu, wpływu na organizacje i prognozowanych efektów
wdrożenia.
Po zakończeniu tego etapu pozostaje schematyczny projekt systemu, tzw. model ogólny.

mod by B-art-eq

Projektowanie szczegółowe
Po akceptacji modelowego rozwiązania niezbędne jest stworzenie wymagań dotyczących
koniecznych zakupów sprzętu i oprogramowania. Następujące pytania wymagają odpowiedzi:

•

jakie programy należy napisać (kupić) aby zostały spełnione wymagania funkcjonalne
postawione w modelu ogólnym systemu,

•

jaki sprzęt należy kupić aby powyższe oprogramowanie działało sprawnie i efektywnie
(szczegółowa specyfikacja dotycząca serwerów, pamięci dyskowej, urządzeń sieciowych i
komunikacyjnych, itp.),

•

jaka powinna być struktura bazy danych oraz systemu plików,

•

jaki powinien być harmonogram wdrożenia, szkolenia użytkowników, instalacji
oprogramowania, itp.

Efektem projektowania szczegółowego jest specyfikacja logiczna i fizyczna składników systemu

Wdrożenie
W czasie wdrożenia, zaprojektowany system jest fizycznie tworzony. Programy są pisane przez
programistów i instalowane na zakupionym sprzęcie. Przeprowadzane są testy działania systemu
i współpracy różnych programów. Tworzona jest struktura bazy danych, następuje przeniesienie
danych historycznych ze starych systemów do nowego systemu.
Zakończeniem tego etapu jest działający system wraz z dokumentacją i procedurami użytkowymi

Przejście na nowy system
Jest to etap, w którym przedsiębiorstwo zaczyna wykorzystywać nowy system w działalności
operacyjnej. Może on trwać krótko w przypadku gdy po uruchomieniu systemu, stare systemy
przestają działać. Mogą też zostać wykorzystane alternatywne sposoby: np. równoległe
wykorzystywanie dwóch systemów, wdrażanie nowego sytemu „po kawałku”, itp. Każde z tych
rozwiązań ma swoje wady i zalety i zależy od specyfiki przedsiębiorstwa i stopnia
skomplikowania systemu.
Efektem jest system zainstalowany i użytkowany w praktyce

Eksploatacja oraz ocena działania systemu
W tym momencie firma posiada już uruchomiony i wykorzystywany w codziennej pracy system.
Powinien on realizować cele i zadania do których został zaprojektowany. Jednakże aby mógł on
poprawnie działać niezbędna jest jego prawidłowa obsługa i utrzymanie (np. usuwanie awarii
sprzętu, poprawianie i korygowanie błędów oprogramowania, zabezpieczenie danych, szkolenie
nowych użytkowników, itp.).
Po określonym czasie powinien zostać przeprowadzony audyt oceniający porównujący założenia
i cele stawiane systemowi na początku z efektami, które zostały osiągnięte po wdrożeniu.
Okresowo w trakcie eksploatacji powinien być sporządzany raport oceniający

mod by B-art-eq

68.

Modele organizacyjne wytwarzania systemów informatycznych i ich

charakterystyka – zalety i wady.

Modele wytwarzania SI stosowane gdy mamy pełną wiedzę o pożądanych jego właściwościach:
- model kaskadowy (wodospadowy),
- realizacja przyrostowa,
- model spiralny,

Modele wytwarzania SI stosowane gdy wiedza o pożądanych jego właściwościach jest
ograniczona:
- prototypowanie,
- programowanie odkrywcze.

Model

Fazy

Zalety

Wady

MODEL KASKADOWY-
polega na wykonywaniu
podstawowych czynności
jako odrębnych faz
projektowych, w porządku
jeden po drugim. Każda
czynność to kolejny
schodek (kaskada)

- określenia wymagań,
- analizy,
- projektowania,
- implementacji/kodowania
- testowania i integracji,
- konseracji

- prostota,
- ułatwia planowanie i
monitorowanie postępów

- może być stosowany gdy
jest możliwość
precyzyjnego określenia
wymagań;
- narzuca twórcom SI ścisłą
kolejność wykonywania
prac
- długa przerwa w
kontaktach z klientem.
- wysoki koszt następstw
błędów popełnianych we
wstępnych fazach.

MODEL SPIRALNY
proces tworzenia ma
postać spirali, której każda
pętla reprezentuje jedną
fazę procesu.

- planowania,
- analizy ryzyka,
- konstrukcji,
- atestowania- rozpoczęcie
nowego cyklu możliwe po
akceptacji
dotychczasowych prac
przez klienta

- regularne kontakty z
klientem,
- minimalizacja ryzyka
porażki,
- realizacja przyrostowa,
- z punktu widzenia
klienta- pełna kontrola
postępów prac

- koszty realizacji większe
niż w modelu kaskadowym,
- pokusa odkładania
realizacji szczegółów na
później

PROTOTYPOWANIE –
MODEL PRZYROSTOWY
sposób na uniknięcie zbyt
wysokich kosztów błędów
popełnionych w fazie
określania wymagań.

- ogólne określenie
wymagań,
- budowa prototypu,
- weryfikacja działającego
prototypu przez klienta,
- uszczegółowienie
wymagań
- realizacja pełnego
systemu według modelu
kaskadowego

- szybkie stworzenie
działającej wersji systemu
- korekta/weryfikacja
specyfikacji w oparciu o
prototyp
- możność prowadzenia
szkoleń w trakcje
konstrukcji

- koszty budowy prototypu,
- kłopoty percepcyjne
klienta (prototyp działa-
dlaczego system tak długo
powstaje?)

mod by B-art-eq

69.

Istota i znaczenie fazy strategicznej w realizacji przedsięwzięć

informatycznych.

Znaczenie fazy strategicznej

• Uniknięcie nieporozumień, nieścisłości dzięki precyzyjnie zdefiniowanym celom projektu - z

punktu widzenia klienta.

• Oszacowanie rozmiaru systemu

• Oszacowanie pracochłonności

• Oszacowanie harmonogramu

Faza strategiczna :
Ocenia się:
Czy rozpoznane potrzeby klientów mogą być spełnione przy obecnych technologiach sprzętu
i/lub oprogramowania.
Czynności fazy strategicznej:

• Wywiady z klientem / przedstawicielami

• Określenie celów projektu z punktu widzenia klienta

• Określenie zakresu oraz kontekstu przedsięwzięcia

• Zgrubna analiza i projekt systemu

• Możliwe rozwiązania – propozycja

• Oszacowanie kosztów

• Analiza i ocena rozwiązań

• Prezentacja wyników fazy strategicznej klientowi oraz korekcja wyników na podstawie uwag

• Określenie wstępnego harmonogramu i struktury zespołu

Określenie standardów, zgodnie z którymi realizowane będzie przedsięwzięcie

70.

Metody identyfikacji wymagań na systemy informatyczne i ich

charakterystyka.

Metodyki

• Postulują przebieg procesu projektowania

• Wyznaczają zadania i kolejność ich wykonywania - co, kiedy i dlaczego powinno być

wykonane

• Wskazują zastosowanie odpowiednich technik

Strukturalne

• Dane i procesy modelowane osobno

• Wykorzystują w zasadzie tylko proste typy danych

• Dobrze dostosowane do modelu relacyjnego danych

• Podstawowe techniki

◦ diagramy związków encji (ERD)

◦ hierarchie funkcji (FHD)

◦ diagramy przepływu danych (DFD)

◦ inne – np.modele macierzowe

W analizie strukturalnej podstawowymi strukturami pojęciowymi modelowania są funkcje
(procesy) i dane.

mod by B-art-eq

Kolejność czynności w analizie strukturalnej

• Określenie wymagań użytkownika oraz charakterystyk funkcji – najczęściej wywiad

• Stworzenie modelu funkcjonalnego – diagram hierarchii funkcji - FHD

• Określenie zapotrzebowania informacyjnego – danych do realizacji funkcji - ERD

• Stworzenie modelu przepływu danych - DFD

Obiektowe

Dane i procesy są modelowane łącznie!!!

• Wykorzystują złożone typy danych

• Dostosowane do obiektowego modelu danych

• W przypadku realizacji opartej na relacyjnej b.d. wynikowy obiektowy model danych musi

być odpowiednio przekształcony

• Podstawowe techniki

• diagramy klas UML

• przypadki użycia i modele dynamiczne UML

W analizie obiektowej podstawową strukturą modelowania jest: obiekt (klasa)
System jest przedstawiony jaki kolekcja obiektów o określonych cechach (atrybutach) i
realizujących zadania z wykorzystaniem metod (funkcji). Dynamiczna strona systemu jest
opisana poprzez model interakcji pomiędzy obiektami, które zachodzą po przesłaniu przez
obiekt komunikatu i są zobrazowane na tak zwanych diagramach interakcji.

Każdy obiekt jest scharakteryzowany poprzez:

• tożsamość – daje się jednoznacznie wyróżnić;

• stan;

• zachowanie.

Podstawowe cechy:

• Dziedziczenie (klasy nadrzędne i podrzędne)

• Hermetyzacja (metody związane z klasą)

Kolejność czynności w analizie obiektowej

Określenie wymagań użytkownika – inżynieria wymagań

Identyfikacja klas obiektów

Określenie i zdefiniowanie atrybutów obiektów

Identyfikacja związków związków zachodzących pomiędzy klasami obiektów oraz relacji –

generalizacja i specjalizacja

Identyfikacja i zdefiniowanie metod obiektów

Zdefiniowanie części dynamicznej systemu – interakcji między obiektami

mod by B-art-eq

71.

Znaczenie modelowania obiektowego funkcjonowania informatyzowanej

organizacji w ustalaniu wymagań na system informatyczny.

Obiektowe modelowanie funkcjonowania organizacji określane jest mianem modelowania
biznesowego. Służy do opisu wszystkiego, co składa się na daną organizację (dokumentacji,
procedur i procesów biznesowych). Dzięki modelom biznesowym można odpowiedzieć na 6
kluczowych pytań dla każdej organizacji biznesowej: co, jak, dlaczego, kto, gdzie i kiedy.
W procesie wytwarzania oprogramowania jest pierwszym etapem z jakim spotykają się twórcy
oprogramowania, gdyż model biznesowy to opis rzeczywistej firmy lub instytucji.
Modelowanie biznesowe pozwoli zrozumieć czym zajmuje się dane przedsiębiorstwo, czemu
akurat tym i czemu akurat w taki sposób. Ponadto można stwierdzić za co odpowiedzialne są
konkretne osoby w analizowanej firmie, jaka jest ich rola, czy też zakres współpracy z innymi
pracownikami.
Zasadniczym celem budowy modelu biznesowego jest utworzenie takiego obrazu organizacji,
który będąc opisem rzeczywistości stanie się podstawą szkieletu aplikacji (opisem tego szkieletu).
Stworzenie prawidłowego modelu funkcjonowania organizacji pozwala na zidentyfikowanie
obszarów, których informatyzacja może usprawnić jej działanie. Model pomaga w wskazywaniu
potrzeb organizacji, a zatem staje się bardzo użyteczny w późniejszych etapach projektowania
(np. podczas tworzenia diagramu przypadków użycia, jeśli używamy języka UML).
Modelowanie biznesowe jest sposobem odwzorowywania i dokumentowania procesów
biznesowych.
Zrozumienie istoty procesów biznesowych jest podstawą specyfikacji wymagań oraz analizy i
projektowania systemów informatycznych. Wiele metodyk przypisuje temu zagadnieniu wysoki
priorytet. Modelowanie biznesowe to pierwszy etap iteracyjno-przyrostowego cyklu życia
systemu w metodyce Rational Unified Process.

72.

Pożądana zawartość dokumentu „Wymagania na system informatyczny”.

Dokument taki powinien zawierać następujące elementy:

Wprowadzenie – cele, zakres i kontekst systemu

Opis wymagań funkcjonalnych - Wymagania funkcjonalne - opisują funkcje (czynności,

operacje) wykonywane przez system. Mogą być opisywane za pomocą: Języka
naturalnego, Języka naturalnego strukturalnego, Tablic i Formularzy, Diagramów
blokowych, Diagramów kontekstowych i DPU

Opis wymagań niefunkcjonalnych - Wymagania niefunkcjonalne – opisują ograniczenia,

przy których system ma realizować swoje funkcje;

Opis ewolucji systemu – rozwój systemu

Model logiczny systemu, opracowany przy użyciu np. języka UML - Model logiczny to

zbiór informacji określający zachowanie się systemu. elementy: lista funkcji systemu,
określenie obiektów zew. systemu, określenie współzależności między funkcjami systemu

Słownik terminów niejednoznacznych na udziałowców przedsięwzięcia

projektowego - Słownik zawiera terminy, które mogą być niejednoznacznie
interpretowane przez uczestników przedsięwzięcia informatycznego- co może być
przyczyną nieporozumień podczas jego realizacji;

Dokument „Wymagania na system informatyczny” stanowi podstawę do realizacji dalszych prac
projektowych nad systemem, w tym do opracowania testów akceptacyjnych systemu.

mod by B-art-eq

73.

Podstawowe rezultaty fazy modelowania systemu.

diagram klas

diagram przypadków użycia SI

diagramy sekwencji komunikatów

diagramy stanów

diagramy czynności

raport zawierający definicje i opisy klas, atrybutów, związków, metod, itd.

słownik danych, zawierający specyfikację modelu

poprawiony dokument opisujący wymagania

harmonogram fazy projektowania

74.

Podstawowe zadania realizowane w procesie budowy obiektowego

modelu systemu informatycznego.

Na bazie obiektów powstają obiektowe modele, czyli kopie rzeczywistych systemów.
Modelowanie obiektowe polega zatem na:

- znajdowaniu obiektów w otoczeniu
- opisywaniu struktury i dynamiki działania obiektów,
- klasyfikacji obiektów,
- opisywaniu struktury powiązań klas obiektów oraz
- opisywaniu dynamiki współpracy obiektów podczas funkcjonowania systemu

Możemy też powiedzieć, że modelowanie obiektowe polega na rysowaniu diagramów
opisujących strukturę i dynamikę systemu składającego się z obiektów.

Proces tworzenia modelu obiektowego:

- Identyfikacja klas i obiektów
- Identyfikacja związków pomiędzy klasami
- Identyfikacja i definiowanie pól (atrybutów)
- Identyfikacja i definiowanie metod i komunikatów

Czynności te są wykonywane iteracyjnie. Kolejność ich wykonywania nie jest ustalona i zależy
zarówno od stylu pracy, jak i od konkretnego problemu. Inny schemat realizacji procesu budowy
modelu obiektowego polega na rozpoznaniu funkcji, które system ma wykonywać. Dopiero w
późniejszej fazie następuje identyfikacja klas, związków, atrybutów i metod. Rozpoznaniu funkcji
systemu służą modele funkcjonalne (diagramy przepływu danych) oraz model przypadków
użycia.
Na etapie projektowania należy ustalić z jakich elementów składa się modelowany system lub
modelowana dziedzina i w jaki sposób elementy te są ze sobą powiązane. Strukturę możemy
prezentować na dwóch poziomach: na poziomie obiektów i na poziomie klas.
Drugim zasadniczym elementem modelowania jest ukazanie dynamiki modelowanego systemu.
O ile w modelu struktury pokazujemy aspekty statyczne, to model dynamiki pokazuje system w
działaniu. Model dynamiki jest o tyle istotny, że podczas konstrukcji oprogramowania staramy
się zrealizować właśnie dynamiczną funkcjonalność systemu odpowiadającą wymaganiom
zamawiających. Od dobrej specyfikacji, a potem realizacji dynamiki systemu zależy zatem jego
jakość rozumiana jako spełnienie rzeczywistych potrzeb zamawiającego.

mod by B-art-eq

75.

Rodzaje modyfikacji wprowadzanych w fazie pielęgnacji systemu

informatycznego.

Faza pielęgnacji rozpoczyna się po fazie testowania, kiedy klient rozpoczyna użytkowanie
systemu. Jest to najczęściej najdłuższa faza cyklu życia oprogramowania, gdyż obejmuje okres
eksploatacji oprogramowania jak i jego utrzymania.

Pielęgnacja oprogramowania polega na wprowadzeniu modyfikacji właściwości użytkowych.
Istnieją trzy rodzaje takich modyfikacji:

• Modyfikacje poprawiające – polegają na usuwaniu z oprogramowania błędów powstałych

bądź wykrytych w poprzednich fazach

• Modyfikacje ulepszające – polegają na poprawie jakości oprogramowania,

• Modyfikacje dostosowujące – polegają na dostosowaniu oprogramowania do zmian

zachodzących w wymaganiach użytkownika lub w środowisku komputerowym

76.

Działania na zbiorach.

Suma zbiorów

Sumą zbiorów A i B nazywamy zbiór tych
elementów, które należą do zbioru A lub do
zbioru B, matematycznie zapisujemy ją
tak:

Iloczyn zbiorów
Iloczynem zbioru A i B nazywamy zbiór
tych elementów, które należą jednocześnie
do zbioru A i do zbioru B, formalnie
zapisujemy

ją

tak:

Iloczyn zbiorów nazywany jest także częścią
wspólną zbiorów lub przekrojem zbiorów.

Różnica zbiorów
Różnicą zbiorów A i B nazywamy zbiór tych
elementów, które należą do zbioru A, a
które nie należą do zbioru B, możemy ją
zapisać
tak:

Różnica zbiorów A i B zapisywana jest
też A − B.

mod by B-art-eq

Dopełnienie zbioru

Dopełnieniem zbioru A z przestrzeni U
nazywamy

zbiór

tych

elementów

przestrzeni U, które nie należą do zbioru A.
Dopełnienie zbioru A oznaczamy jako A' lub
A

. Dopełnienie możemy zapisać tak:

Z definicji dopełniania wynika także, że jest
to po prostu różnica przestrzeni U i zbioru

. Zbiór U zwany jest zbiorem

uniwersum. Czasami zamiast U używa się
innego oznaczenia przestrzeni np. X.

Dla dowolnych zbiorów A, B, C zachodzą prawa:

– I prawo De Morgana

– II prawo De Morgana

– przemienność dodawania zbiorów

– przemienność mnożenia zbiorów

– łączność dodawania zbiorów

– łączność mnożenia zbiorów

– rozdzielność dodawania zbiorów względem

mnożenia

– rozdzielność mnożenia zbiorów względem

dodawania

mod by B-art-eq

77.

Rachunek zdań.

Rachunek zdań to dział logiki matematycznej badający związki między zdaniami (zmiennymi
zdaniowymi) lub funkcjami zdaniowymi utworzonymi za pomocą spójników zdaniowych ze zdań
lub funkcji zdaniowych prostszych.

W klasycznym rachunku zdań przyjmuje się założenie, że każdemu zdaniu można przypisać jedną
z dwu wartości logicznych - prawdę albo fałsz, które umownie przyjęto oznaczać 1 i 0. Klasyczny
rachunek zdań jest więc dwuwartościowym rachunkiem zdań.

Wartość logiczną zdań określa funkcja prawdy, związana z każdym spójnikiem zdaniowym.
Wartość ta zależy wyłącznie od prawdziwości lub fałszywości zdań składowych. Szczególną rolę
w rachunku zdań odgrywają takie zdania złożone, dla których wartość logiczna jest równa 1,
niezależnie od tego, jakie wartości logiczne mają zdania proste, z których się składają. Takie
zdania nazywa się prawami rachunku zdań lub tautologiami.

Alfabet Klasycznego Rachunku Zdań składa się z trzech rodzajów znaków: zmiennych
zdaniowych, stałych logicznych (funktorów) i znaków pomocniczych.

Zmienne zdaniowe: p, q, r, s, itd.
Funktory: koniunkcja, alternatywa, równoważność, implikacja, itd.
Znaki pomocnicze: nawiasy: (, ), [, ], {, }.

Tabela prawdy dla pierwszego prawa de Morgana

Ważniejsze prawa rachunku zdań:

a.

prawo przemienności koniunkcji

prawo przemienności alternatywy

prawo łączności koniunkcji

prawo łączności alternatywy

prawo

rozdzielności

koniunkcji

względem alternatywy

prawo rozdzielności alternatywy

względem koniunkcji

pierwsze prawo De Morgana

(prawo zaprzeczenia koniunkcji)

drugie prawo De Morgana

(prawo zaprzeczenia alternatywy)

mod by B-art-eq

78.

Działania na macierzach.

Dodawanie i mnożenie przez skalar
Mnożenie macierzy przez stałą (skalar, element pierścienia) oraz dodawanie macierzy definiuje
się następująco:

) + (b

) = (a

+ b

Słownie: mnożenie macierzy przez skalar polega na wymnożeniu przez niego wszystkich jej
elementów, a dodawanie macierzy na dodaniu odpowiadających sobie elementów. Analogicznie
definiuje się różnicę macierzy.
Zbiór

z dodawaniem jest grupą przemienną: łączność i przemienność działań w pierścieniu

przenosi się na działania na macierzach, elementem neutralnym jest macierz zerowa Θ o
wszystkich

elementach

równych

, elementem

przeciwnym do

macierzy A jest

macierz

którą

nazywa

się macierzą

przeciwną do A.

Oczywiście

jest A − B = A + ( − B) o ile macierze te są zgodnego typu.

Mnożenie przez skalar spełnia warunki:

zatem zbiór

z dodawaniem i mnożeniem przez skalary jest modułem nad pierścieniem R.

Przykład mnożenia przez skalar

Mnożenie
Działanie mnożenia macierzy można określić na wiele sposobów, jednak niżej określone,
nazywane mnożeniem Cauchy'ego, ma wiele zastosowań w algebrze liniowej, w której macierze
służą do zapisu przekształceń liniowych – odpowiada ono ich składaniu. Macierze można
również mnożyć używając iloczynu Kroneckera.

Iloczyn

macierzy

(nazywanej w tym kontekście lewym

czynnikiem) i macierzy

(prawy czynnik) jest macierzą

taką,

że

Przykład dodawania macierzy

mod by B-art-eq

79.

Układy równań liniowych – twierdzenie Kroneckera-Capelliego, wzory

Cramera.

Układy równań liniowych

Równaniem liniowym o n niewiadomych

nazywamy równanie postaci

Układem dwóch równań liniowych o dwóch niewiadomych nazwiemy wyrażenie postaci

Układ równań liniowych o niewiadomych ma postać

Wzory Cramera
Najpierw wyznaczmy tzw wyznacznik główny

Następnie utwórzmy wyznaczników

Dla w. w. wyznaczników zachodzą 3 przypadki

nie każdy

układ jest sprzeczny

Układ jest nieoznaczony

nieskończenie wiele rozwiązań

mod by B-art-eq

Równania liniowe jednorodne
Równaniem liniowym jednorodnym nazwiemy równanie postaci

Układ równań liniowych jednorodnych o niewiadomych ma postać

Jeżeli

powyższego układu równań jest różne od 0 (

), układ ma tylko jedno

rozwiązanie, zerowe.
Z kolei, jeśli

układ ma nieskończenie wiele rozwiązań, łącznie z rozwiązaniem zerowym.

Twierdzenie Kroneckera-Capelli'ego
Dla układu równań liniowych (jednorodnych albo niejednorodnych) o niewiadomych
(

)

utwórzmy macierz W ze współczynników

Przez

oznaczamy rząd macierzy

- największy stopień ( różny od ) minora z tej macierzy.

(Jeśli wszystkie elementy macierzy wynoszą to

Dopisując do macierzy

kolumnę wyrazów wolnych, otrzymujemy macierz uzupełnioną .

Twierdzenie Kroneckera-Caleppi'ego mówi: wkw rozwiązalności układu równań liniowych jest
równość rzędu macierzy

współczynników układu i rzędu macierzy uzupełnionej

Gdy:
1.

układ ma dokładnie jedno rozwiązanie

układ ma nieskończenie wiele rozwiązań zależnych od

parametrów

mod by B-art-eq

80.

Pojęcie relacji i funkcji.

RELACJA

FUNKCJA

Definicja

Relacją dwuczłonową R nazywa się dowolny
podzbiór iloczynu kartezjańskiego A × B
dowolnych zbiorów A i B. R ⊂ A × B

Własności relacji:
• zwrotna (Z), jeśli ∀x ∈ A : xRx
• przeciwzwrotna (PZ), jeśli ∀x ∈ A : ∼ xRx
• symetryczna (S), jeśli ∀x ∈ A, y ∈ A : xRy ⇒
yRx
• antysymetryczna (AS), jeśli ∀x ∈ A, y ∈ A :
xRy ∧ yRx ⇒ x = y
• przechodnia (P), jeśli ∀x, y, z ∈ A : xRy ∧
yRz ⇒ xR

Przyporządkowanie każdemu elementowi
zbioru X dokładnie jednego elementu ze
zbioru Y. Funkcja jest relacją
dwuczłonową.

Funkcje można określić za pomocą:
- grafu
- wykresu
- wzoru
- zbioru
- tabelki
- opisu słownego

Pojęcia
związane

R jest relacją równoważności, gdy
1) R jest zwrotne,
2) R jest symetryczne,
3) R jest przechodnie,
R jest relacją częściowego porządku, gdy
1) R jest zwrotne,
2) R jest słabo antysymetryczne,
3) R jest przechodnie,
R jest relacją liniowego porządku, gdy
1)R jest relacją częściowego porządku,

2)R jest relacją spójną

Dziedzina funkcji - zbiór X
Zbiór wartości funkcji - zbiór Y
Miejsce zerowe funkcji - argument x dla
którego funkcja przyjmuje wartość 0, na
wykresie jest to punkt przecięcia z osią X
Monotoniczność funkcji - określa czy
funkcja jest rosnąca czy malejąca.
Funkcja jest rosnąca gdy wraz ze
wzrostem argumentów rosną wartości
funkcji
Funkcja jest malejąca gdy wraz ze
wzrostem argumentów maleją
wartości funkcji

81.

Własności relacji: relacje porządkujące; relacje równoważności.

Relacją w A

x … x A

(iloczyn kartezjański) nazywamy dowolny zbiór R A

x … x A

Nazywamy ją relacją n-argumentową. Relacje dwuargumentowe to R A x B.
xRy ↔ (x,y) R
Np.

Relacja równoważności
R X

jest relacją

• Zwrotną

• Symetryczną

• Przechodnią

Np.
xRy ↔ x=y na zbiorze R
xRy ↔ |x|=|y| na zbiorze R

Relacje porządkujące:
Częściowo porządkująca

R X

jest relacją

• Zwrotną

• Słabosymetryczną

• Przechodnią

Porządkująca i dodatkowo spójna

Relacja porządkująca, która jest
spójna

Przykłady xRy ↔ x≤y

mod by B-art-eq

82.

Własności funkcji: miejsca zerowe, ciągłość, pochodna.

Ciągłość
Niech funkcja f będzie określona w pewnym otoczeniu U punktu x

Funkcję f nazywamy ciągłą w punkcie x

, jeżeli istnieje jej granica w tym punkcie i

Funkcja f jest ciągła w przedziale otwartym (a, b), jeżeli jest ciągła w każdym punkcie x

∈(a,b)

Funkcja f jest ciągła w przedziale domkniętym <a, b>, jeżeli spełnia następujące warunki

• Jest ciągła w (a,b)

•

(funkcja prawostronnie ciągła w punkcie a),

•

(funkcja lewostronnie ciągła w punkcie b).

Miejsce zerowe (pierwiastek) funkcji to argument, dla którego dana funkcja przyjmuje wartość 0.
Niech

będzie przedziałem otwartym i funkcja

Jeśli dla pewnego

istnieje skończona granica ilorazu różnicowego

to mówimy, że jest różniczkowalna w punkcie

. Z kolei punkt

nazywamy punktem

różniczkowalności funkcji .

Wartość powyższej granicy nazywamy pochodną funkcji w punkcie

i oznaczamy symbolem

83.

Zmienna losowa i jej charakterystyki liczbowe.

Pojęcie zmiennej losowej: Intuicyjne można powiedzieć, że zmienna losowa (związana z
pewnym doświadczeniem), to taka zmienna, która w wyniku doświadczenia przyjmuje wartość
liczbową zależną od przypadku (nie dając ą się ustalić przez przeprowadzeniem doświadczenia).

Definicja: Do określenia zmiennej losowej potrzebna jest przestrzeń probabilistyczna. Załóżmy
więc, że dana jest dowolna przestrzeń probabilistyczna (E, Z, P), a więc zmienna losową
nazywamy dowolna funkcję X, określoną na przestrzeni zdarzeń elementarnych E, o własnościach
ze zbioru liczb rzeczywistych i mierzalną względem ciała zdarzeń Z.
Zmienna losowa X dana jest zbiorem:

Zmienne losowe oznaczamy dużymi literami np.: S, T, X, Y, Z, ich własności zaś odpowiednimi
małymi literami: s, t, x, y, z, często ze wskaźnikami.
Jeżeli zbiór wartości, jakie przyjmuje funkcja X, jest zbiorem policzalnym, wtedy zmienną losową
nazywamy zmienną losową dyskretną lub skokową.
Natomiast jeśli funkcja X przyjmuje wartości z pewnego przedziału liczbowego, nazywamy ją
zmienną losową ciągłą.

mod by B-art-eq

Charakterystyki liczbowe zmiennej losowej

Wartość oczekiwana. Obliczenie wartości oczekiwanej zmiennej losowej bezpośrednio za
pomocą funkcji prawdopodobieństwa lub gęstości prawdopodobieństwa zmiennej losowej X
przedstawia następujący wzór :

1. Zmienna losowa dyskretna – Niech X będzie zmienną losową typu dyskretnego. Wartością
oczekiwaną nazywa się sumę iloczynów wartości tej zmiennej losowej oraz prawdopodobieństw
z jakimi są one przyjmowane.

2. Zmienna losowa ciągła - Jeżeli X jest zmienną losową typu ciągłego zdefiniowaną na
przestrzeni probabilistycznej (Ω, P, F), to wartość oczekiwaną zmiennej losowej definiuje się jako
całkę.

( )













∫

∑

∞

−

XdP

Wariancja zmiennej losowej. jest średnią arytmetyczną kwadratów odchyleń (różnic)
poszczególnych wartości cechy od wartości oczekiwanej.

Odchylenie standardowe zmiennej losowej. Odchylenie standardowe zmiennej losowej X jest
to pierwiastek z jej wariancji i opisany jest wzorem:

84.

Cel i rodzaje programowania deklaratywnego.

Programowanie deklaratywne dzieli się na programowanie funkcyjne i programowanie w logice.
Programowanie deklaratywne - polega na określeniu oczekiwanych własności
rozwiązania które ma być uzyskane bez podawania szczegółowego algorytmu jego uzyskania.

Program deklaratywny = sformułowanie problemu w pewnym języku formalnym

Programowanie

funkcyjne

Program jest funkcja wyznaczająca wynik działania programu

Cechy programu funkcyjnego:

• nie ma zmiennych (stanu programu) - tylko argumenty funkcji

• nie ma trwałych efektów ubocznych wykonania funkcji

• nie ma instrukcji iteracyjnych

• instrukcjom iteracyjnym odpowiada rekurencja,

• do rozwiązania bardziej złożonych problemów definiuje sie liczne funkcje pomocnicze

Przykładowe języki: LISP, Haskell, można ten styl stosować w większości języków strukturalnych

mod by B-art-eq

Programowanie

w logice:

Problem definiuje się w taki sposób aby rozwiązanie mogło być znalezione poprzez wyznaczenie
elementów z pewnego zbioru, dla których zachodzi określona własność wyrażona za pomocą
formuł (predykatów) logicznych
Cechy programu funkcyjnego:

• Program to sformułowanie własności rozwiązania w języku formalnym pozwalającym na

definiowanie predykatów.

• Wykonanie programu polega na znalezieniu takich danych, dla których można "udowodnić"

spełnienie wymaganej własności .

• Zadaniem kompilatora i interpretera programu logicznego jest znalezienie ciągu operacji

prowadzących do rozwiązania problemu (udowodnienia własności

Przykład:
ojciec(jan, jerzy).
ojciec(jerzy, janusz).
ojciec(jerzy, józef).
dziadek(X, Z) :- ojciec(X, Y), ojciec(Y, Z).
?- dziadek(X, janusz).
Przykładowe jezyki: Prolog, SQL

85.

Definicje unifikatora (podstawienia uzgadniającego), najogólniejszego

unifikatora, algorytm unifikacji i twierdzenie o unifikacji.

Podstawienie uzgadniające (ang. unifier) dwóch termów jest to takie podstawienie, które czyni
te termy identycznymi.
Najbardziej ogólne podstawienie uzgadniające (ang. most general unifier, mgu) dwóch
termów to takie podstawienie uzgadniające, w którym wspólna instancja jest w najbardziej
ogólnej postaci.
Algorytm:
Wejście: dwa termy T

i T

do uzgodnienia. Wyjście: θ = mgu( T

i T

) lub niepowodzenie.

θ ← ε.
niepowodzenie ← NIE.
Umieść T

na stosie.

while ( ~(stos pusty) ^ niepowodzenie = NIE ) do:

zdejmij X=Y ze stosu.
if ( X jest zmienną nie występującą w Y):

zamień Y na X na stosie i w θ dodaj X=Y

else if (Y jest zmienną nie występującą w X):

zamień X na Y na stosie i w θ dodaj Y=X

else if( X i Y są identycznymi stałymi bądź zmiennymi):

continue

else if ( X= f



... , X



∧Y= f



... ,Y



dla pewnego funktora f gdzie n >0):

dodaj na stos “ X

”,...,” T

”

else:

niepowodzenie ← TAK.

if (niepowodzenie = TAK):

return niepowodzenie.

Else: return θ.

mod by B-art-eq

86.

Programy Horna, SLD-rezolucja, odpowiedzi poprawne, odpowiedzi

obliczone, poprawność i zupełność SLD-rezolucji.

Formuła atomowa jest najmniejszym wyrażeniem, czyli składa się wyłącznie z jednego predykatu oraz
jego argumentów
Przykład:

P(x), P(x, y), Q(x, y, z)

REGUŁA REZOLUCJI
Def. (literał, literał pozytywny, literał negatywny)
Literałem nazywa się formułę atomową lub formułę atomową z negacją. Formuła atomowa
jest literałem pozytywnym, a formuła atomowa z negacją jest literałem negatywnym. Dowolne literały
postaci A oraz ∼Α stanowią parę literałów komplementarnych.

Def. (rezolucja źródłowa)
Rezolucja źródłowa jest to strategia wnioskowania za pomocą reguły rezolucji, w której każdą,
kolejną parę przesłanek tworzą:

• resolwenta uzyskana w kroku poprzednim,

• dowolny aksjomat.

Def. (klauzula)
Klauzulą nazywa się dowolną formułę, przyjmującą jedną z wymienionych postaci:
1.



∀



...



∀



∨

…

∨

dla n



1 ,



∀



...



∀



3. Formuła pusta (tzw. klauzula pusta, oznaczana symbolem )przy za



łożeniu, że L1, …, Ln dla n > 1 są

dowolnymi literałami, nie zawierającymi żadnych zmiennych oprócz x1, …, xm dla m ≥ 1. Przyjmuje się, że
kwantyfikatory w zapisie klauzuli mogą być pominięte.

Klauzula Horna

Klauzula Horna jest to dowolna klauzula, zawierająca co najwyżej jeden literał pozytywny.

Def. (implikacyjna postać klauzuli Horna)
Dowolną klauzulę Horna H ∨ ∼ L1 ∨…∨ ∼ Lm, gdzie H oraz L1, …, Ln są formułami
atomowymi, można zapisać w postaci H ← L1 ∧…∧ Lm lub równoważnie



∀



...



∀



H ←

∃



...

∃



∧

…

∧



gdzie

, …,

to wszystkie zmienne występujące w formule H a

, …,

są

wszystkimi zmiennymi, które występują wyłącznie w formule

∧…∧

Def. (SLD-rezolucja)

Rezolucja źródłowa w zbiorze klauzul Horna z określoną strategią wyboru literału aktywnego nosi
nazwę SLD-rezolucji [1] (ang. Linear resolution with Selection function for Definite clauses).
Lub:
Rezulucja liniowa dla programu definitywnego z regułą selekcji.

Def. Reguła selekcji
Regułą selekcji nazywamy funkcję R, która każdej skończonej derywacji liniowej



, δ



1 ≤ n≤ p

tak,

że Gp = , przyporz



ądkowuje liczbę naturalną n taką, że

1 ≤ m ≤ k

, gdzie k jest długością G

mod by B-art-eq

Def. Odpowiedź poprawna
Podstawienia δ (delta), nazywamy odpowiedzią poprawną dla

{G} gdzie G :



− G

… B

jeżeli formuła



∧

...

∧



δ wynika logicznie w LPR z programu P, co zapisujemy

LPR



and...

∧



δ . Przyjmujemy dodatkowo, że δ jest zawarta w V



∧

...

∧



Odpowiedź poprawna jest pojęciem deklaratywnym, związanym ze znaczeniem programu.

Def. Odpowiedź obliczona
Niech



, δ



1≤ n≤ p

będzie liniową refutacją dla P

{G} . Odpowiedzią obliczona dla

{G} wyznaczoną przez tę refutację nazywamy podstawienie δ

...

ograniczone do zmiennych

występujących w G tzn.



1...



| V(G).

Odpowiedź obliczona jest pojęciem proceduralnym związanym z wykonaniem programu.

O poprawności rezolucji liniowej
Każda odpowiedź obliczona dla P

{G} jest odpowiedzią poprawną dla P

{G} tzn. jeżeli

δ =



...



jest odpowiedzią obliczoną dla P

{G}, gdzie G :



− B

… , B

to P

LPR



and...

∧



δ .

O zupełności rezolucji liniowej
Dla każdej odpowiedzi Θ dla P

{G}, istnieje odpowiedź obliczona δ dla P

{G} oraz podstawienie

γ(gamma) tak, że Θ = ( δ γ)|V(G).
Inaczej:
Odpowiedzi poprawne pokrywają się ze wszystkimi możliwymi konkretyzacjami odpowiedzi obliczonych.

87.

Zasada rezolucji liniowej w programowaniu w logice.

1. Rezolucja liniowa:
Jeżeli formuły {A1, A2, … An} nie są sprzeczne, to formuła B jest ich konkluzją (tzn. wynika
inferencyjnie z formuł A1, A2,… An) wtedy i tylko wtedy, gdy formuły { A1, A2,…An, B} są
sprzeczne.
Jeżeli naszym zadaniem jest udowodnienie faktu, że formuła B wynika ze zbioru formuł
{A1, A2,… An} (przy założeniu, że formuły te nie są sprzeczne) to należy do tego zbioru dodać
zanegowaną formułę B. Jeżeli z nowopowstałego zbioru uda nam się wyprowadzić klauzulę
pustą, będzie to oznaczać, że ten zbiór jest sprzeczny. Co za tym idzie formuła B jest
niespełniona, a zatem formuła B jest spełniona (wynika ze zbioru formuł {A1, A2,… An}).
Jeśli przesłankami rezolucji będą dwie pojedyncze klauzule to powstała na ich podstawie
rezolwenta będzie klauzulą pustą. Klauzula pusta jest bez względy na interpretację zawsze
fałszywa. W systemach ekspertowych opartych na zasadzie rezolucji, pusta klauzula jest bardzo
ważna. Uzyskanie takiej klauzuli oznacza niespełnialność rozpatrywanego zbioru klauzul.

2. Przykład:
KOBIETA(Ewa)
MEZCZYZNA(Adam)
~MEZCZYZNA(x)\/~KOBIETA(y)\/~LUBI_WINO(y)\/KOCHA(x,y)
~KOBIETA(x)\/LUBI_WINO(x)

Naszym zadaniem jest, na podstawie powyższych formuł udowodnić prawdziwość formuły
KOCHA(Adam, Ewa).

mod by B-art-eq

Pierwszym krokiem jest zanegowanie tej formuły, a następnie dodanie jej w takiej formie do
zbioru formuł (przy założeniu, że zbiór ten jest niesprzeczny), z których będziemy prowadzić
wywód. Po tym kroku zbiór formuł wygląda następująco:
(1) KOBIETA(Ewa)
(2) MEZCZYZNA(Adam)
(3) ~MEZCZYZNA(x)\/~KOBIETA(y)\/~LUBI_WINO(y)\/KOCHA(x,y)
(4) ~KOBIETA(x)\/LUBI_WINO(x)
(5) ~ KOCHA(Adam, Ewa)
Teraz można już prowadzić wywód. Naszym celem jest uzyskanie klauzuli pustej.
(6) ~KOBIETA(y)\/~LUBI_WINO(y)\/KOCHA(Adam,y) -otrzymane z formuł 2 i 3, przy
zastosowaniu reguły nr 2.
(7) LUBI_WINO(Ewa) -otrzymane z formuł 2 i 3, przy zastosowaniu reguły nr 2.
(8) ~KOBIETA(Ewa)\/KOCHA(Adam,Ewa) - otrzymane z formuł 6 i 7, przy zastosowaniu reguły nr
2. (9) KOCHA(Adam,Ewa) -otrzymane z formuł 1 i 8, przy zastosowaniu reguły Modus ponens.
(10) [] -otrzymane z formuł 5 i 9, przy zastosowaniu reguły nr 4.

Jak widać udało nam się uzyskać klauzulę pustą. Świadczy to o tym, iż formuła KOCHA(Adam,
Ewa) jest niespełniona, zatem formuła KOCHA(Adam, Ewa) jest spełniona, co należało dowieść.

88.

Budowa programu w Prologu: klauzule (fakty, reguły), definicje

predykatów. Sposób realizacji programu.

PROGRAM zbiór procedur; kolejność procedur w programie nie jest istotna.
PROCEDURA ciąg klauzul definiujących jeden predykat kolejność klauzul w procedurze jest
istotna
KLAUZULA fakt lub reguła.
FAKT Bezwarunkowo prawdziwe stwierdzenie o istnieniu pewnych powiazań (relacji) miedzy
obiektami. Budowa: symbol_relacji (obiekt1, ..., obiektn)
Przykłady student(marcin). Marcin jest studentem.
lubi(ewa, marek). Ewa lubi Marka
REGUŁA: Warunkowe stwierdzenie istnienia pewnych powiazań (relacji) miedzy obiektami.

symbol_relacji (obiekt1, ..., obiektn) :- symbol_relacji_1 (obiekt1, ..., obiektn1),
symbol_relacji_2 (obiekt1, ..., obiektn2)…
Przykład: powierzchnia (X, Y) :- dlugosc (X, D), szerokosc (X, S), Y is D*S.

Powierzchnia Y prostokata X jest równa iloczynowi długosci D i szerokosci S tego prostokata.
Rozpoczęcie działania programu polega na wywołaniu dowolnej procedury, które jest nazywane
w Prologu zadawaniem pytań lub podawaniem celu.
Celem działania programu jest uzyskanie odpowiedzi na Pytanie o prawdziwość podanych
faktów lub polecenie znalezienia nazw obiektów będących w podanej relacji z innymi.
Postać ?- symbol_relacji_1 (obiekt1, ..., obiektn1),
symbol_relacji_2 (obiekt1, ..., obiektn2).

Przykład
?- lubi (marta, jan). - Czy Marta lubi Jana?
lubi(marta, X). – Kogo lubi Marta?
lubi(X, marta) –Kto lubi Martę?

mod by B-art-eq

89.

Co to są systemy (zestawy) funkcjonalnie pełne? Podać przykładowe.

Zbiór funkcji boolowskich nazywa się systemem funkcjonalnie pełnym (bazą), jeśli dowolna
funkcja boolowska może być przedstawiona za pomocą stałych 0 i 1 oraz funkcji należących do
tego zbioru i argumentów funkcji.

Funkcje sumy, iloczynu i negacji tworzą tzw. podstawowy system funkcjonalnie pełny. Nie jest to
jednak system minimalny. Systemy funkcjonalnie pełne tworzą również:

•

iloczyn i negacja (suma może zostać wyeliminowana dzięki prawu De Morgana)

•

suma i negacja (analogicznie jak wyżej)

•

funkcja Sheffer'a (NAND) (jak wyżej oraz ponieważ

)

•

funkcja Pierce'a (NOR) (

)

90.

Podaj rodzaje układów sekwencyjnych oraz różnice w procedurach ich

projektowania.

Układ sekwencyjny

Układ sekwencyjny jest jednym z
rodzajów

układów

cyfrowych.

Charakteryzuje się tym, że stan wyjść y
zależy od stanu wejść x oraz od
poprzedniego stanu, zwanego stanem
wewnętrznym, pamiętanego w zespole
rejestrów (pamięci).

Jeżeli stan wewnętrzny nie ulega
zmianie pod wpływem podania różnych
sygnałów X, to taki stan nazywa się stabilnym.

Rozróżnia się dwa rodzaje układów sekwencyjnych:

1. asynchroniczne

2. synchroniczne

Układ sekwencyjny może być opisany za pomocą dwóch funkcji:

1. Y = f(X,A) − wyjście zależy od stanu wewnętrznego i wejść

2. Y = f(A) − wyjście zależy wyłącznie od stanu wewnętrznego

gdzie A to stan wewnętrzny, X i Y są zgodne z ilustracją. Pierwsza funkcja dotyczy tzw. automatu
Mealy'ego, druga automatu Moore'a - oba automaty są sobie równoważne.

Zachowanie układu sekwencyjnego może być opisane następująco:

* słownie;

* przebieg czasowy - pokazujący zależności czasowe pomiędzy X i Y;

* grafy przejść (ich wygląd zależy od rozpatrywanego automatu);

* tablice przejść i wyjść.

mod by B-art-eq

Układy asynchroniczne

W układach asynchronicznych zmiana sygnałów wejściowych X natychmiast powoduje zmianę
wyjść Y. W związku z tym układy te są szybkie, ale jednocześnie podatne na zjawisko hazardu i
wyścigu. Zjawisko wyścigu występuje, gdy co najmniej dwa sygnały wejściowe zmieniają swój
stan w jednej chwili czasu (np. 11b -> 00b). Jednak, ze względu na niezerowe czasy przełączania
bramek i przerzutników, zmiana jednego z sygnałów może nastąpić [trochę] wcześniej niż innych,
powodując trudne do wykrycia błędy. Dlatego też w analizie układów asynchronicznych uznaje
się, że jednoczesna zmiana kilku sygnałów jest niemożliwa.

Układy synchroniczne

W układach synchronicznych zmiana stanu wewnętrznego następuje wyłącznie w określonych
chwilach, które wyznacza sygnał zegarowy (ang. clock). Każdy układ synchroniczny posiada
wejście zegarowe oznaczane zwyczajowo symbolami C, CLK lub CLOCK. Charakterystyczne dla
układów synchronicznych, jest to, iż nawet gdy stan wejść się nie zmienia, to stan wewnętrzny -
w kolejnych taktach zegara - może ulec zmianie.

Ponieważ w przypadku układu synchronicznego zrealizowanego jako automat Moore'a wyjście
układu jest funkcją stanu wewnętrznego, może ono zmieniać się tylko w chwili nadejścia taktu,
co daje gwarancję, że odpowiedni stan wyjść utrzyma się przez cały takt. W przypadku automatu
Mealy'ego zmiana wyjścia układu może nastąpić także w momencie zmiany wejścia.

Jeśli układ reaguje na określony stan (logiczny) zegara, to mówi się że układ jest statyczny
(wyzwalany poziomem), jeśli zaś układ reaguje na zmianę sygnału zegarowego jest dynamiczny
(wyzwalany zboczem). Układ dynamiczny może być wyzwalany zboczem (ang. edge) opadającym
lub narastającym, albo impulsem.

Jeśli układ synchroniczny nie ma wejść, a jedynie charakteryzuje go stan wewnętrzny, to taki
układ nazywany jest autonomicznym (dobrym przykładem takich układów są liczniki stosowane
w popularnych zegarkach elektronicznych).

Synchroniczny:
Proces projektowania automatu rozpoczyna się
zwykle od analizy jego opisu słownego. Z opisu
tego powinna wynikać liczba sygnałów
wejściowych, wyjściowych oraz liczba stanów, a
także możliwość określenia funkcji przejść i
funkcji wyjść. Narzędziem pomocniczym do
analizy opisu może być graf automatu. Na jego
podstawie niekiedy łatwiej jest wyznaczyć
tablicę przejść i wyjść. Po wyznaczeniu tych
tablic, proces projektowania może być
sformalizowany. Algorytm postępowania jest
następujący:

Minimalizacja liczby stanów automatu.

Zakodowanie tablicy przejść i wyjść.

Wybór typu przerzutników.

Znalezienie funkcji wzbudzeń

przerzutników.

Znalezienie funkcji wyjść.

Asynchroniczny:
Proces

projektowania

automatów

asynchronicznych składa się z 4 etapów:

Wyznaczanie tablic przejść i wyjść.

Minimalizacja tablicy przejść.

Kodowanie tablicy przejść.

Wyznaczenie funkcji realizujących

tablice przejść i wyjść.

Proces

projektowania

automatów

asynchronicznych rozpoczyna się, tak jak w
przypadku automatów synchronicznych, od
opisu słownego. Metodą przejścia od opisu
słownego do opisu formalnego (tablica przejść i
wyjść lub graf) jest tzw. wykres czasowy.
Ponieważ zmiany stanów automatu i zmiany
sygnałów wyjściowych następują w momencie
zmiany sygnałów wejściowych, wygodnie
przedstawić te zmiany w funkcji czasu.

mod by B-art-eq

91.

Jakie znasz elementy pamięciowe stosowane układach sekwencyjnych?

Układ sekwencyjny jest jednym z rodzajów układów cyfrowych, który charakteryzuje się tym, że
stan wyjść y zależy od stanu wejść x oraz od poprzedniego stanu, pamiętanego w zespole
rejestrów, czyli układów służących do przechowywania i odtwarzania informacji w postaci bitów.
Ze względu na sposób wprowadzania i wyprowadzania informacji dzielimy rejestry na :

Szeregowe - umożliwiające szeregowe wprowadzenie i wyprowadzenie danych (tzn. bit po
bicie), są to tak zwane rejestry SISO (Serial In Serial Out)

Równoległe - umożliwiające równoległe wprowadzenie i wyprowadzenie informacji
jednocześnie do wszystkich pozycji rejestru, PIPO (Parallel In Parallel Out)

Szeregowo-równoległe - umożliwiające szeregowe wprowadzenie i równoległe wyprowadzenie
informacji, SIPO (Serial In Parallel Out)

Równoległo–szeregowe - umożliwiające równolegle wprowadzenie i szeregowe wyprowadzenie
informacji, PISO (Parallel In Serial Out)

Rejestry budowane są poprzez połączenie ze sobą przerzutników, które służą jako podstawowe
elementy pamiętające. Wśród monolitycznych wyróżnia się przerzutniki:

Przerzutnik typu RS,

Przerzutnik typu D,

Przerzutnik typu T,

Przerzutnik typu JK,

92.

Co oznacza termin mikroprogramowanie? Do czego służy?

Układ mikroprogramowany to jedno z możliwych rozwiązań stosowanych w technice cyfrowej
dla projektów o dużej złożoności. Projekt dekomponowany jest na dwie części: układ operacyjny
(wykonawczy) i układ sterujący. Układ sterujący można zaprojektować jako układ
mikroprogramowany. Bity sterujące, wraz z innymi odpowiednimi bitami służącymi do napisania
mikroprogramu, umieszcza się w pamięci ROM.

mod by B-art-eq

93.

Podaj znane zapisy liczbowe i zakres ich stosowania.

Zapisy można podzielić na stałopozycyjne (liczby całkowite) i zmiennopozycyjne (liczby
rzeczywiste). Stałopozycyjne to: ZNAK-MODUŁ, U1 i U2. Najpowszechniejszy jest U2 ze względu
na najprostsze algorytmy operacji arytmetycznych. Zmiennopozycyjny zapis polega na
reprezentowaniu liczby za pomocą trzech grup bitów: jednobitowej grupy znaku, np. 63-bitowej
mantysy i np. 16-bitowego wykładnika.

Zapis U2 jest najczęściej stosowanym zapisem liczb całkowitych. Jest on podobny do NKB, z tą
różnicą, że najbardziej znaczący bit ma wagę ujemną. Typ int jest we współczesnych
komputerach implementowany jako zapis U2.
Zapis U1 jest podobny do U2, ale wartość bezwzględna najbardziej znaczącego bitu jest tu o
jeden mniejsza.
Zapis znak-moduł wydaje się być najbardziej intuicyjnym – jeden bit jest interpretowany jako
znak liczby, pozostałe bity – jako wartość bezwzględna w kodzie NKB. W kodzie ZM występują
dwie reprezentacje zera, np. dla ośmiobitowych słów: 100000000 i 000000000.

Do zapisywania liczb ułamkowych i mieszanych można użyć zapisu stałopozycyjnego. W zapisie
tym liczba jest reprezentowana przez słowo binarne, w którym pewne, z góry określone liczby
bitów reprezentują część całkowitą i część ułamkową liczby. Odpowiada to interpretacji zapisu
całkowitoliczbowego, pomnożonej przez wartość będącą ujemną potęgą liczby 2.

Do zapisu liczb bez znaku używa się jako bazowej postaci NKB, a do zapisu liczb ze znakiem –
U2.

94.

Co to są mikrokontrolery?

Mikrokontroler

system mikroprocesorowy

zrealizowany w postaci pojedynczego

układu

scalonego, zawierającego jednostkę centralną (CPU), pamięć

RAM

oraz na ogół pamięć

programu i rozbudowane układy wejścia-wyjścia. Określenie

mikrokontroler

pochodzi od

głównego obszaru zastosowań, jakim jest sterowanie urządzeniami elektronicznymi.

Mikrokontroler stanowi użyteczny i całkowicie autonomiczny

system mikroprocesorowy, nie

wymagający

użycia

dodatkowych

elementów,

których

wymagałby

pracy

tradycyjny

mikroprocesor. Skądinąd, mikrokontrolery przystosowane są do bezpośredniej

współpracy z rozmaitymi urządzeniami zewnętrznymi, w tym również takimi, do których obsługi
tradycyjny

mikroprocesor

wymagałby

użycia

dodatkowych

układów

peryferyjnych.

Mikrokontrolery wykorzystuje się powszechnie w sprzęcie AGD, układach kontrolno-
pomiarowych, w przemysłowych układach automatyki, w telekomunikacji itp.

mod by B-art-eq

95.

Jakie parametry są charakterystyczne dla pamięci dynamicznych?

Podstawowymi parametrami opisującymi każdy typ pamięci są:

• Szybkość

• Pojemność

• Pobór mocy

• Koszt

Dla pamięci dynamicznej charakterystycznymi parametrami są:

• wymagany czas odświeżania (8-64 ms)

• wymaganą liczbę cykli odświeżania (pierwiastek z liczby bitów).

Pojemność każdej pamięci, to ilość informacji którą dana pamięć jest w stanie przechować.
Mierzy się ją zazwyczaj w bitach, bajtach i słowach. Wyrażana jest w kilobitach - kb, megabitach -
Mb, gigabitach - GB, oraz analogicznie w kilobajtach - kB, megabajtach MB i w gigabajtach GB.
Szybkość jest parametrem określającym jak często procesor, lub inne urządzenie wykorzystujące
pamięć mogą z niej korzystać. Szybkość pamięci jest określana kilkoma precyzyjnymi
parametrami:
Czasem dostępu - access time. Jest to czas upływający od momentu w którym wysyłane jest
żądanie dostępu do pamięci do czasu w którym informacja zwrotna ukaże się na jej wyjściu.
Czasem cyklu - cycle time. Jest to czas najkrótszy, który upływa między dwoma kolejnymi
żądaniami dostępu do pamięci.
Szybkością transmisji - transfer speed. Szybkość transmisji mierzymy liczbą bitów, bądź bajtów,
którą jesteśmy w stanie przesłać pomiędzy urządzeniem, a pamięcią. Ten parametr jest bardzo
ważny w pamięciach, adresowanych ilością bitów większą od słowa, na przykład pamięci na
dyskach magnetycznych. Ze względu na konieczność odczytu i zapisu bloku słów, mniej istotny
staje się czas dostępu, natomiast ważniejszy jest czas w którym porcja danych może zostać
przesłana. Szybkość transmisji mierzymy w bajtach lub bitach na sekundę.
Również pobór mocy stanowi bardzo ważny parametr, który staje się problemem przy
budowaniu urządzeń zasilanych bateryjnie, jak komputery kieszonkowe, laptopy.
Oprócz parametrów typowych jak np. pojemność, czas cyklu (dostępu), pobór mocy, koszt itp.
pamięć dynamiczna posiada charakterystyczne dla niej parametry, tj. wymagany czas
odświeżania (8-64 ms) i wymaganą liczbę cykli odświeżania (pierwiastek z liczby bitów).

mod by B-art-eq

96.

Podaj tryby adresowania dla rozkazów mikrokontrolera i odpowiadający

im czas trwania cyklu instrukcyjnego wraz z omówieniem kolejnych cykli
maszynowych.

Trybem adresowania nazywa się sposób określenia miejsca przechowywania argumentów
rozkazu.
Rozróżniamy następujące tryby adresowania:

• adresowanie natychmiastowe, w którym argument rozkazu zawarty jest w kodzie rozkazu.

Cykl: fetch, odczytu;

• adresowanie bezpośrednie, w którym kod rozkazu zawiera adres komórki pamięci

przechowującej argument rozkazu. Cykl: fetch, 4xodczyt;

• adresowanie rejestrowe, w którym w kodzie rozkazu określony jest rejestr zawierający

argument rozkazu. Cykl: fetch;

• adresowanie pośrednie (rejestrowe pośrednie), w którym kod rozkazu zawiera określenie

rejestru, bądź rejestrów zawierających adres komórki pamięci z argumentem rozkazu.Cykl:
fetch i odczytu;

Cykl instrukcyjny (rozkazowy) – czas potrzebny na odczytanie kodu rozkazu z pamięci, na
pobranie argumentów, na wykonanie rozkazu i przesłanie wyniku operacji.

Rodzaje cykli:

• Pobranie kodu operacyjnego (fetch)

• Odczyt z pamięci (memory read)

• Zapis do pamięci (memory write)

• Odczyt z urządzenia wejściowego (IOread)

• Zapis do urządzenia wyjściowego (IOwrite)

• Cykl przyjęcia przerwania (interrupt)

• Cykl zatrzymania (HALT)

97.

Jakie znasz rodzaje transmisji szeregowej i na czym one polegają?

Asynchroniczna: Transmisja ta pozwala na transmisję 1 bajtu z parametrami. Zegary w
nadajniku i odbiorniku ustawione są na tą samą częstotliwość. Transmisja rozpoczyna się od
przesłania bitu startu, następnie przesyłany jest znak i transmisję kończy bit stopu. Następnie
procedura jest powtarzana.
Synchroniczna: W transmisji synchronicznej specjalna preambuła dokonuje zsynchronizowania
nadawcy i odbiorcy. Preambuła ta to ciąg znaków zerojedynkowych o ściśle określonym czasie
trwania i ilości. Po synchronizacji następuje przesłanie danych. Preambuła synchronizująca jest
powtarzana tylko wtedy, gdy następuje rozsynchronizowanie – co może się objawiać wzrostem
błędów w transmisji. Transmisję kończą bajty CRC
(suma kontrolna wykorzystywana do wykrycia
uszkodzenia ciągu binarnego).
Kod Manchester – jest to sposób fazowej
modulacji sygnału cyfrowego. Logicznemu zeru
odpowiada zmiana stanu z niskiego na wysoki, dla
jedynki z wysokiego na niski.

mod by B-art-eq

98.

Porównaj pod względem szybkości znane rozwiązania operacji mnożenia

w systemach wbudowanych.

Mnożenie w układzie kombinacyjnym (układ iteracyjny gdzie wynik pojawia się po czasie
opóźnienia wnoszonym przez bramki) jest najszybsze.
Mnożenie w układzie sekwencyjnym (tyle kroków ile jest bitów, a każdy krok to dodawanie
warunkowe i przesunięcie) jest wolniejsze.
W układach synchronicznych zmiana stanu wewnętrznego następuje wyłącznie w określonych
chwilach, które wyznacza sygnał zegarowy (ang. clock)
Mnożenie programowe (bez żadnego sprzętu) jest najwolniejsze.

99.

Model obliczeniowy perceptronu – możliwości i ograniczenia.

Gdzie:
n – liczba wejść w neuronie,
u1, u2, ..., un – sygnały wejściowe,
w0, w1, ..., wn – wagi synaptyczne,
un+1 – wartość wyjściowa neuronu,
u0 – wartość progowa,
f – funkcja aktywacji,

s – wartość sumy ważonej.

∑

Perceptron - sieć neuronowa najprostszego typu.

Perceptron (wg. Rosnblatta) spełnia warunki:

1. sieć jednokierunkowa;
2. posiada przynajmniej dwie warstwy (Wejściowa i Wyjściowa), oraz może posiadać dowolną

ilość warstw ukrytych;

3. neurony danej warstwy nie są ze sobą połączone;
4. używa tylko funkcji aktywacji unipolarnej lub bipolarnej.

funkcja unipolarna:

( )







≥

funkcja biplarna:

( )







≤

−

funkcja sigmoidalna(nie stosowana dla perceptronu Rosenblatta):

( )

−

mod by B-art-eq

Działanie perceptronu polega na klasyfikowaniu danych pojawiających się na wejściu i ustawianiu
stosownie do tego wartości wyjścia. Przed używaniem perceptron należy wytrenować podając
mu przykładowe dane na wejście i
modyfikując w odpowiedni sposób wagi
wejść i połączeń między warstwami
neuronów, tak aby wartość na wyjściu
przybierała pożądane wartości.

Perceptrony mogą klasyfikować dane na
zbiory, które są liniowo separowalne.
Własność ta uniemożliwia na przykład
wytrenowanie złożonego z jednego
neuronu perceptronu, który wykonywałby logiczną operację XOR na wartościach wejść.

X1 X2

XOR

Sposobem na ominięcie tych ograniczeń jest budowa bardziej złożonej struktury sieci, tzn.
połączenie wielu perceptronów (już dwa wystarczają, by zrealizować XOR).
Zalety sieci neuronowych:
-sieci neuronowe same się uczą, twórca co najwyżej musi pokierować procesem uczenia sieci;
-w przypadku uszkodzenia nadal działają (oczywiście do pewnego stopnia);
-zdolność uogólniania zdobytej wiedzy(jeśli sieć nauczy się, rozpoznawać kolory: czerwony i
żółty, to rozpozna również różowy i bladożółty, czyli kolory podobne do znanych.);

warstwa
wejściowa

warstwa
wyjściowa

mod by B-art-eq

100.

Metody uczenia sieci neuronowych.

Pod pojęciem uczenia sieci rozumiemy wymuszenie na niej określonej reakcji na zadane sygnały
wejściowe. Uczenie jest konieczne tam, gdzie brak jest informacji doświadczalnych o powiązaniu
wejścia z wyjściem lub jest ona niekompletna, co uniemożliwia szczegółowe zaprojektowanie
sieci. Uczenie może być realizowane krok po kroku lub poprzez pojedynczy zapis.

Uczenie z nadzorem

Stosuje się tylko wówczas, gdy istnieje możliwość zweryfikowania
poprawności odpowiedzi udzielanych przez sieć; oznacza to, że dla
każdego wektora wejściowego musi być znana dokładna postać
wektora wyjściowego (pożądana odpowiedź).
Schemat postępowania:
- podaj na wejście sieci wektor wejściowy
- wyznacz błąd popełniany przez sieć
- wykorzystaj wyznaczony błąd do korekty wag sieci
Uczenie bez nadzoru

Stosuje się wówczas gdy nie znamy oczekiwanych odpowiedzi na
zadany wzorzec.
Warunki samo uczenia:
- Sygnały wejściowe muszą się dać jakoś sklasyfikować (muszą być
podobne do pewnych wzorców)
-Neuronów musi być wyraźnie więcej, niż wzorców. Znaczy to, że sieć
musi być dostatecznie mądra, by zaabsorbować pewną dawkę wiedzy.
- Różnorodne początkowe preferencje poszczególnych neuronów. Jeśli sieć ma się nauczyć
rozpoznawania różnych obiektów, musi mieć takie neurony, które mają różne upodobania

101.

Mechanizm działania algorytmu genetycznego.

Algorytm genetyczny - rodzaj algorytmu przeszukującego przestrzeń alternatywnych rozwiązań
problemu w celu wyszukania rozwiązań najlepszych.
Sposób działania algorytmów genetycznych nieprzypadkowo przypomina zjawisko ewolucji
biologicznej. Obecnie zalicza się go do grupy algorytmów ewolucyjnych.

Najczęściej działanie algorytmu przebiega następująco:

Losowana jest pewna populacja początkowa.

Populacja poddawana jest ocenie (selekcja). Najlepiej przystosowane osobniki biorą

udział w procesie reprodukcji.

Genotypy wybranych osobników poddawane są operatorom ewolucyjnym:

• są ze sobą kojarzone poprzez złączanie genotypów rodziców (krzyżowanie),

• przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian.

Rodzi się drugie (kolejne) pokolenie i algorytm powraca do kroku drugiego, jeżeli nie

znaleziono dostatecznie dobrego rozwiązania. W przeciwnym wypadku uzyskujemy wynik.

Działanie algorytmu genetycznego obejmuje kilka zagadnień potrzebnych do ustalenia:

ustalenie genomu jako reprezentanta wyniku

ustalenie funkcji przystosowania/dopasowania

ustalenie operatorów przeszukiwania

mod by B-art-eq

102.

Definicja entropii informacji i wybrane zastosowanie tego pojęcia.

Entropia

– w ramach teorii informacji

jest definiowana jako średnia

ilość informacji

, przypadająca

na pojedynczą wiadomość ze źródła informacji. Innymi słowy jest to średnia ważona ilości
informacji

niesionej

przez

pojedynczą

wiadomość,

gdzie

wagami

są prawdopodobieństwa nadania poszczególnych wiadomości.
Wzór na entropię:

gdzie

p(i)

– prawdopodobieństwo zajścia zdarzenia

– liczba wszystkich zdarzeń danej przestrzeni.

Przykładem zastosowania może być wykorzystanie entropii informacji do oceny sieci
monitoringu jakości wód podziemnych. Podstawą tej oceny jest wartość marginalnej entropii
informacyjnej, obliczona w każdym punkcie pomiarowym. Na podstawie wartości tego kryterium
można zaproponować warianty zmniejszenia liczby punktów pomiarowych w sieci monitoringu.

103.

Metody generacji reguł systemu decyzyjnego, minimalne, pokrywające,

wyczerpujące.

Reguły systemu decyzyjnego są jednym z narzędzi reprezentacji wiedzy. Opisują one związki
między atrybutami warunkowymi (zwykle wieloma), a atrybutem decyzyjnym. Systemy decyzyjne
oparte na regułach zawierają zwykle wiele (np. tysiące) reguł, z których każda może być oparta
na innym zestawie atrybutów warunkowych.
Metody minimalne - metody tworzenia systemu decyzyjnego poprzez wygenerowanie
minimalnej ilości reguł ze zbioru treningowego. Przykład: LEM2 (Learn from examples by
modules 2).
Dla danej klasy decyzyjnej (klasy, kategorii, decyzji, etykiety, atrybutu decyzyjnego, konceptu)
wyszukujemy najczęściej pojawiający sie deskryptor i sprawdzamy czy jest niesprzeczny. Jeśli jest
sprzeczny skupiamy uwagę na tych obiektach, do których pasuje i wyszukujemy kolejny
najczęstszy deskryptor, który dodajemy do reguły. Dodawanie kończymy, gdy nasza reguła jest
niesprzeczna. Obiekty do których ta reguła pasuje wyrzucamy z rozwiązań. Generowanie reguł
kończymy gdy usuniemy z konceptu wszystkie obiekty.
Metody pokrywające - idea: nauczyć sie reguły, po czym usunąć obiekt, który ta reguła
pokrywa - powtarzać aż do wyczerpania zbioru obiektów. Przykład: Pokrywanie sekwencyjne
(Sequential Covering). Przeglądamy wszystkie deskryptory systemu decyzyjnego w poszukiwaniu
reguł niesprzecznych. Po napotkaniu reguły niesprzecznej wyrzucamy z rozwiązań deskryptor
tworzący regułę (zaznaczamy deskryptor okręgiem). W przypadku reguł wyższego rzędu po
znalezieniu reguły niesprzecznej wyrzucamy z rozwiązań koniunkcję deskryptorów warunkowych
tej reguły. Warunkiem STOP jest pusty zbiór kandydatów na regułę danego rzędu.
Metody wyczerpujące - wykorzystują brute force, mało efektywne dla systemów z dużą ilością
atrybutów i dużymi zbiorami treningowymi. Przykład: EXHAUSTIVE: z najmniejszą ilością
deskryptorów. Polega na przeszukiwaniu wszystkich deskryptorów warunkowych obiektów
treningowych począwszy od kombinacji długości 1 w celu znalezienia kombinacji , która jest
niesprzeczna w systemie decyzyjnym i która nie zawiera w sobie reguł niższego rzędu. Procedura
wyszukiwania kończy się, gdy dany rząd reguł nie przekazuje żadnej nowej reguły do zbioru
wszystkich reguł.

mod by B-art-eq

104.

Podaj znaczenie oraz omów wzajemne związki między terminami:

przestrzeń urządzenia, przestrzeń operacyjna urządzenia, powierzchnia
obrazowania, macierz adresowalna, jednostka rastru, krok kreślaka.

Przestrzeń urządzenia (obrazującego) - to obszar zdefiniowany przez układ współrzędnych,
ograniczony pojemnością rejestrów pozycji x i y w urządzeniu graficznym
Przestrzeń operacyjna - to obszar przestrzeni urządzenia którego zawartość została
odwzorowana na powierzchni obrazowania
Powierzchnia obrazowania - nośnik, na którym mogą pojawiać się obrazy i rysunki, np. ekran
lampy kineskopowej lub papier w ploterze.
Macierz adresowalna - to macierz utworzona z punktów adresowalnych określająca wielkość
obrazu który można przesłać do generatora obrazu wielkość przyrostu - to odległość między
dwoma punktami adresowalnymi na powierzchni obrazowania
Jednostka rastru - jednostką rastru jest piksel

105.

Zdefiniuj okno i widok oraz oknowanie i obcinanie; podaj co to są

współrzędne znormalizowane i do czego one służą.

Okno – ograniczony obszar w obrębie przestrzeni obrazowania, który
może być rozszerzony do całej przestrzeni obrazowania. Okno jest
Prostokątnym obszarem w przestrzeni danych.

Widok – ograniczony obszar w obrębie przestrzeni
operacyjnej urządzenia, który prezentuje zawartość okna.
Widok może być rozszerzony do całej przestrzeni
operacyjnej. Obszar (prostokątny) na urządzeniu graficznym

Okienkowanie

–

wyizolowanie

dowolnej

części

wyświetlonego obrazu .

Obcinanie – wyznaczanie elementów wewnątrz okna.

Współrzędne znormalizowane – Często przejście od współrzędnych rzeczywistych do
współrzędnych danego urządzenia graficznego jest wykonywane dwustopniowo. Najpierw
przechodzi do współrzędnych znormalizowanych, to znaczy do kwadratu [0,1]x[0,1],a stad do
współrzędnych urządzenia.

106.

Podaj ideę algorytmu Cohena-Sutherlanda obcinania odcinka do

prostokątnego okna i jego trzy pierwsze kroki; podaj w jakich
współrzędnych działa ten algorytm i dlaczego?

Algorytm Cohena-Sutherlanda jest analitycznym algorytmem obcinania dwuwymiarowych
odcinków przez prostokąt obcinający, którego boki są równoległe do osi układu współrzędnych.

Algorytm Cohena-Sutherlanda polega na przypisaniu każdemu końcowi odcinka czterobitowego
kodu określającego położenie tego punktu względem prostokątnego okna. Dokładniej, bity są
numerowane od prawego:

mod by B-art-eq

Kod(P) = b

– gdy P leży na lewo od okna

- gdy P leży na prawo od okna

- gdy P leży poniżej okna

- gdy P powyżej okna

a w przeciwnym razie odpowiednie bity kodu mają wartość 0.

Wielkości te łatwo się wyznacza, gdyż b

jest bitem znaku x – x

min

, b

i b

odpowiednio x

max

– x i y

– y

min

, a b

jest bitem znaku y

max

– y. Punkt P=(x,y) leży wewnątrz okna, jeśli spełnione są

nierówności:

min

=< x =< x

max

, y

min

=< y =< y

max,

a wtedy kod(P) = 0000.

Odcinek P1P2 leży całkowicie wewnątrz okna, gdy kod(P1) = kod(P2) = 0000.
Odcinek leży na zewnątrz okna, jeżeli kod(P1) AND kod(P2) =/= 0000.

Algorytm przebiega następująco:

1. Wybierany jest koniec odcinka leżący poza prostokątem, a więc mający niezerowy kod; jeśli

kody obu końców są niezerowe to można wybrać dowolny z nich.

2. Wyznaczany jest punkt przecięcia odcinka z jedną z prostych. Wybór prostych determinuje

kod wybranego końca. Np. jeśli ustawiony jest bit nr 2, to znaczy, że należy znaleźć przecięcie
z prostą y = ymin.

3. Następnie odcinek jest przycinany do tego punktu - koniec wybrany w punkcie pierwszym jest

zastępowany przez punkt przecięcia.

4. Kody końców odcinka są testowane tak jak opisano wyżej. Algorytm powtarza się dopóki

jeden z dwóch testów nie będzie prawdziwy, tzn. aż odcinka nie będzie można w całości
zaakceptować, albo odrzucić.

Liczba iteracji potrzebnych do obcięcia odcinka może wynosić od 0 do 4.

mod by B-art-eq

107.

Sformułuj zadanie i ogólne warunki trójkątowania wielokąta, warunki

trójkątowania naturalnego oraz podaj ideę trójkątowania wielokąta
monotonicznego.

Trójkątowanie wielokątów jest zwane inaczej triangulacją, jest to podział wielokąta na trójkąty.
Ułatwia to rozwiązywanie problemów takich jak wypełnianie obszarów, określanie zasłaniania,
oświetlania obiektów trójwymiarowych czy wyznaczania linii ich przecięcia. Ważne jest by liczba
składowych trójkątów była jak najmniejsza i by nie trzeba było definiować nowych danych.
Zadanie triangulacji definiuje się jako:
„podział wielokąta zwykłego na sumę nie nakładających się na siebie trójkątów. Których
wierzchołki mogłyby być tylko wierzchołki danego wielokąta.”

Algorytm dzielenia wielokąta monotonicznego na trójkąty.

• Dane są współrzędne wierzchołków.

• Sortujemy wierzchołki według malejących wartości y. Otrzymany ciąg oznaczamy Q1,

Q2,...,Qn.

• Na stos układamy dwa pierwsze wierzchołki: Q1, Q2.

• dla j=3,...,n

• niech R1,R2,...,Ri (na początku i=2) będzie aktualną zawartością stosu.

• jeśli Qj sąsiaduje z R1, ale nie z Ri, to

• prowadzimy przekątne QjR2, QjR3, ...,QjRi

• zamieniamy zawartość stosu na Ri, Qj,

• w przeciwnym razie, jeśli Qj sąsiaduje z Ri, ale nie z R1, to

• (*) jeśli i=1 lub wewnętrzny kąt wielokąta W w Ri jest >= 180

to dodajemy Qj

na wierzchołek stosu,

• w przeciwnym razie prowadzimy przekątną QjRi-1, zdejmujemy Ri ze stosu,

podstawiamy i=i-1 i wracamy do (*),

• w przeciwnym razie (Qj sąsiaduje z R1 i Ri) prowadzimy przekątne QjR2, QjR3, ...,QjRi-1.

Koszt algorytmu jest rzędu n (pętla wykonuje się n razy).

mod by B-art-eq

108.

Zdefiniuj przekształcenie 3-punktowe. Do czego ono służy?.

Przekształcenie trzypunktowe

Jest ono wykorzystywane przy budowie scen trójwymiarowych. Dane są trzy nie współliniowe
punkty: P1, P2, P3 i Q1, Q2, Q3. Szukamy takiej izometrii (przekształcenia), które będzie spełniało
następujące warunki:

• Odwzorowuje punkt P1 w Q1,

• Kierunek P=P2-P1 w kierunek Q=Q2-Q1,

• Transformuje płaszczyznę wyznaczoną przez : P1, P2, P3 w płaszczyznę wyznaczoną

przez Q1, Q2, Q3

Aby wyznaczyć taką transformację wprowadzimy dwa wersory ortogonalne:

u1=(P2-P1)/|P2-P1|

u2=(P2-P1)x(P3-P1)/|(P2-P1)x(P3-P1)|

a trzeci wyznaczymy jako u3=u1xu2.

gdzie x oznacza iloczyn wektorowy i jest on zdefiniowany następująco:

w1xw2 jest iloczynem wektorowym gdy spełnia własności:

• w1xw2 jest prostopadły do w1 i do w2,

• wektory w1, w2, w są dodatnio zorientowane, tzn. det(w1,w2,w)>0

• |w|=|w1||w2|sin(w1,w2)

Podobnie konstruujemy wektory w1, w2 i w3 dla punktów Q1,Q2,Q3, czyli

w1=(Q2-Q1)/|Q2-Q1|

w2=(Q2-Q1)x(Q3-Q1)/|(Q2-Q1)x(Q3-Q1)|

a trzeci wyznaczymy jako w3=w1xw2.

Równanie:

























jest równaniem na macierz obrotu R, która przekształca wektory u1, u2, u3 w wektory w1, w2,
w3. Macierz U=[u1,u2,u3]

jest ortogonalna, tzn. UU

=I=>U

-1

, podobne właściwości ma

macierz W. Macierz R jest więc postaci: R=U

Ponieważ potrzebne jest jeszcze przesunięcie, to otrzymujemy je z warunku, że obrazem punktu
P1 ma być punkt Q1. Zatem przesunięcie o wektor T musi być postaci: T=Q1-P1R.

mod by B-art-eq

109.

Podaj wzajemne położenie układów współrzędnych: danych i obserwatora.

Układ współrzędnych obserwatora nie jest określony jednoznacznie. Przyjmuje się, że jego
początek O’ pokrywa się z początkiem O układu danych. Najprostszym sposobem przejścia z
układu danych do układu obserwatora jest przejście przez rzutnię Ω osi z=0.
Przekształcenie układu danych do układu obserwatora polega na wykonaniu takich obrotów wokół
osi układu, by wektor n=[xn , yn , zn] stał się antyrównoległy do osi z nowego układu.

Objaśnienie
W rzutowaniu perspektywicznym (nie zachowuje proporcji, wszystkie promienie rzutujące
przecinają się w ognisku rzutowania) obserwator znajduje się w środku rzutowania E o
współrzędnych (xE , yE , zE) układu danych Oxyz. Płaszczyzna Ω jest prostopadła do OE.
W rzutowaniu równoległym(równoległość prostych, proporcje dł. odcinków równoległych i związki
miarowe figury płaskiej) płaszczyznę Ω zadaje się za pomocą jej wersora(wektora jednostkowego)
normalnego n; w rzucie równoległym ortogonalnym rzutnia Ω jest prostopadła do kierunku
rzutowania k.

110.

Wymień we właściwej kolejności operacje, jakie należy wykonać, aby

obrócić punkt P o kąt

dookoła prostej zadanej przez dwa punkty

Obrót wokół takiej prostej można otrzymać jako złożenie odpowiednich translacji i obrotów
wokół osi układu współrzędnych.
1) Wykonujemy translacje P1 P2 o wektor –P1=[-x1,-x2,-x3].Punkt P1 będzie przesunięty do

początku układu współrzędnych. Nich β oznacza kąt, jaki prosta P1’P2’ tworzy z
płaszczyzną xz, a kąt miedzy jej rzutem P1’P2” na tę płaszczyznę i osią x niech będzie
równy α .

2) Obracamy najpierw o kąt –α wokół osi y, a następnie o kat β wokół osi z przekształcając

prostą P1’P2’ na oś x. Wybór osi układu współrzędnych na która przekształcamy oś P1P2
jest dowolny.

3) Wykonujemy obrót o kat φ wokół osi x.
4) Dokonujemy przekształceń odwrotnych do wstępnych transformacji (2) i (1) w

odpowiedniej kolejności: obrót o kat β, obrót o kat α i przesuniecie o wektor +P1

111.

Opisać 3 podstawowe obszary uzależnień komputerowych.

Środkami uzależniającymi są:

gry komputerowe,

Internet,

programowanie.

Pojawiły się pierwsze próby opisu "choroby komputerowej". Pozbawieni dostępu do komputera
przeżywają stany identyczne z zespołem abstynenckim, są pobudzeni, cierpią na zaburzenia snu,
popadają w stany depresyjne, fantazjują na temat Internetu. Uzależnienia komputerowe można
podzielić na pierwotne i wtórne. W pierwszym przypadku mamy do czynienia z potrzebą przeżycia
emocji, uzyskania efektu pobudzenia, sprawdzenia swoich umiejętności. W drugim przypadku
komputer jest traktowany jako forma ucieczki od rzeczywistości. Ponadto należy pamiętać, że ten
rodzaj uzależnienia ma negatywne konsekwencje dla zdrowia.

mod by B-art-eq

Uzależnienie od komputera u dziecka można stwierdzić, gdy:

• udaje, że się uczy, kiedy tymczasem godzinami siedzi przed ekranem monitora,

• w czasie gry lub przeglądania stron WWW wpada w stan przypominający trans,

• próby ograniczenia czasu spędzanego przy komputerze napotykają na silny opór, nawet

agresję,

• niechętnie spotyka się z kolegami, brak mu przyjaciół, woli komputer niż ruch na świeżym

powietrzu,

• nie potrafi odpoczywać, nie wzrusza się.

112.

Wymienić przynajmniej 3 polskie ustawy dotyczące środowiska

informatycznego.

Dla środowiska informatycznego najważniejszymi regulacjami prawnymi, które weszły w życie
w minionych kilku latach, są ustawy:

•

łączności z 1990 roku (z późniejszymi nowelizacjami),

•

prawie autorskim i prawach pokrewnych z 1994 roku,

•

zamówieniach publicznych z 1994 roku,

•

ochronie danych osobowych z 1997 roku.

113.

Jaka jest zasadnicza różnica między ochroną własności intelektualnej i

ochroną patentową?

Podstawową różnicą prawa patentowego jako systemu ochrony partykularnej jest wyłączenie
możliwości uzyskania patentu przez różne podmioty na wynalazki, które są do siebie podobne.
Czyli mając coś opatentowane nie możesz stworzyć czegoś podobnego posiadającego podobne
algorytmy, funkcje itp a w prawie autorskim chronisz tylko program a nie algorytm itd.

Jak cos jest chronione patentem to jest chronione jako patent i własność intelektualna, a jak cos
jest chronione jako własność intelektualna, to niekoniecznie jest chronione patentem.
Prawo autorskie chroni tylko formę (kod źródłowy i wynikowy). Nie chroni jednak odkryć, idei,
procedur, metod, zasad działania, koncepcji matematycznych.

114.

Opisać na czym polega szpiegostwo komputerowe.

Szpiegostwo definiuje się jako działanie przestępne dokonywane na szkodę określonego państwa,
polegające na wykonywaniu odpowiednich czynności na rzecz obcego wywiadu, a w szczególności
na zbieraniu, przekazywaniu informacji organom obcego wywiadu lub na gromadzeniu i
przechowywaniu informacji w celu przekazania obcemu wywiadowi.

Artykuł 130 – paragrafy 1 do 4 określają szpiegostwo komputerowe jako:

• Działanie w obcym wywiadzie przeciwko Rzeczypospolitej Polskiej

• Działanie w obcym wywiadzie lub biorąc w nim udział, udziela informacji, które mogą

wyrządzić szkodę Rzeczypospolitej Polskiej,

• Kto, w celu udzielenia obcemu wywiadowi wiadomości określonych w § 2, gromadzi je lub

przechowuje, włącza się do sieci komputerowej w celu ich uzyskania albo zgłasza gotowość
działania na rzecz obcego wywiadu przeciwko Rzeczypospolitej Polskiej,

• Kierowanie lub tworzenie organizacji obcego wywiadu