ZagadnieniaSHORT, Studia, Egzamin inżynierski
[ Pobierz całość w formacie PDF ]

Notacja O (omikron)
– ograniczenie funkcji f(n) z
góry. Służy do szacowania czasu działania w przypadku
pesymistycznym

Notacja theta
– ograniczenie funkcji f(n) z góry i z
dołu. Asymptotyczne przybliżenie dokładne.

Notacja omega
– ograniczenie funkcji f(n) z dołu.
Służy do szacowania czasu działania w przypadku
najlepszym.
1. AISD
1.1. Schemat blokowy algorytmu. Elementy
notacji, reguły stosowania
Schemat blokowy
– forma przedstawienia algorytmu, czyli
skończonego uporządkowanego zbioru jasno zdefiniowanych
czynności koniecznych do wykonania pewnego zadania w
skończonej liczbie kroków
Problemy NP-zupełne
(nie da się ich rozwiązać w czasie
wielomianowym a zwykle 2^N)

Problem komiwojażera
– np. znalezienie najkrótszej
trasy pomiędzy kilkoma miastami

Problem plecakowy
– jak wybrać przedmioty, tak aby
ich sumaryczna wartość była jak największa i nie
przekroczyła pojemności plecaka
Elementy notacji:

Blok graniczny (owal),

Blok we/wy (równoległobok),

Blok obliczeniowy (prostokąt)

Blok decyzyjny (romb)
1.4. Algorytmy sortowania oraz
charakterystyka ich złożoności
obliczeniowej.
Reguły stosowania:

Każda operacja umieszczona w bloku

Schemat ma jedną skrzynkę
Start
i przynajmniej
jedną
Stop

Skrzynki są ze sobą połączone

Ze skrzynki wychodzi jedno połączenie.
Wyjątki
: ze
Stop
nie wychodzi żadne, z
bloku decyzyjnego
wychodzą dwa.
Algorytmy ze złożonością O(n
2
) i sortowaniem w miejscu
Sortowanie bąbelkowe (Bubble sort)
Zasada działania
– cykliczne porównywanie par sąsiadujących
elementów i zamiana ich kolejności w przypadku niespełnienia
kryterium porządkowego zbioru. Operację tę wykonujemy
dotąd, aż cały zbiór zostanie posortowany.
1.2. Struktury listowe. Przykłady
zastosowań w praktyce
Sortowanie w miejscu
- wymaga stałej liczby dodatkowych
struktur danych, która nie zależy od liczby elementów
sortowanego zbioru danych. Dodatkowa złożoność pamięciowa
jest zatem klasy O(1). Sortowanie odbywa się wewnątrz zbioru.
Lista jednokierunkowa

Każdy element oprócz wartości, posiada wskaźnik do
następnego elementu.

Trzeba posiadać wskaźnik do pierwszego elementu

Ostatni element wskaźnik ustawiony na adres pusty

Brak dostępu swobodnego - przeszukiwanie po
każdym elemencie – złożoność O(n)

Proste wstawianie i usuwanie elementów
Sortowanie przez wybór (Select sort)
Zasada działania
Szukamy w zbiorze elementu najmniejszego i wymieniamy go z
elementem na pierwszej pozycji.
W ten sposób element najmniejszy znajdzie się na swojej
docelowej pozycji.
W identyczny sposób postępujemy z resztą elementów.
Lista dwukierunkowa

Każdy element oprócz wartości, posiada wskaźnik do
poprzedniego i następnego elementu.

Trzeba posiadać wskaźnik do pierwszego i ostatniego
elementu.

Brak dostępu swobodnego – przeszukiwanie po
każdym elemencie z dowolnej strony

Proste wstawianie i usuwanie elementów
Sortowanie przez wstawianie (insertion sort)
Działa jak układanie kart pobieranych z talii.
Każdą pobraną kartę porównujemy z kartami, które już
trzymamy w ręce i szukamy dla niej miejsca przed pierwszą
kartą starszą (młodszą w przypadku porządku malejącego). Gdy
znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy
na przygotowane w ten sposób miejsce
Zastosowanie w praktyce

Proste bazy danych (np. nieograniczona rozmiarem
baza adresów)

Ze zbioru N k-literowych słów utworzyć listy
wyrazów zaczynających się na daną literę
Algorytmy ze złożonością O(nlogn) używające metody dziel i
zwyciężaj
1.3. Złożoność obliczeniowa. Miary
złożoności, problemy NP-zupełne.
Sortowanie przez scalanie (Merge sort)
Dzielenie

Rekurencyjnie dzielimy zbiór na dwie przyległe
połówki

Wynik scalenia ma być umieszczony z powrotem w
tym samym zbiorze.
Złożoność obliczeniowa
Ilość zasobów komputera jakiej potrzebuje dany algorytm.
Złożoność czasowa lub pamięciowa. Złożoność jest
proporcjonalna do jakiejś funkcji.
Scalanie
Miary złożoności
1

Przygotuj pusty zbiór tymczasowy

Dopóki żaden ze scalanych zbiorów nie jest pusty,
porównuj ze sobą pierwsze elementy każdego z nich
i w zbiorze tymczasowym umieszczaj mniejszy z
elementów usuwając go jednocześnie ze scalanego
zbioru.

W zbiorze tymczasowym umieść zawartość tego
scalanego zbioru, który zawiera jeszcze elementy.

Zawartość zbioru tymczasowego przepisz do zbioru
wynikowego i zakończ algorytm.
Podstawowe typy:
Minimalne drzewo rozpinające
(dla grafu) – podzbiór
krawędzi grafów, który łączy wszystkie wierzchołki, gdzie suma
wszystkich wag krawędzi jest najmniejsza
Drzewo poszukiwań binarnych
– drzewo binarne (liczba
synów wierzchołka nie większa niż dwa). W drzewie takim
szybko się wyszukuje, a co za tym idzie wstawia i usuwa
elementy.
Metody przeszukiwania:

Wzdłużna - preorder: korzeń, lewe poddrzewo, prawe
poddrzewo.

Poprzeczna - inorder: lewe poddrzewo, korzeń, prawe
poddrzewo.

Wsteczne - postorder: lewe poddrzewo, prawe
poddrzewo, korzeń.
Sortowanie szybkie (Quick sort)

Sortowany zbiór dzielimy na dwie części (piwotem –
zwykle średnim elementem zbioru) w taki sposób,
aby wszystkie elementy leżące w pierwszej części
(zwanej lewą partycją) były mniejsze lub równe od
wszystkich elementów drugiej części zbioru (zwanej
prawą partycją).

Każdą z partycji sortujemy rekurencyjnie tym samym
algorytmem.

Otrzymujemy posortowany zbiór
Przykłady zastosowań
Przechodząc drzewo BST metodą inorder uzyskuje się ciąg
wartości posortowanych rosnąco.
UWAGA
: w przypadku pesymistycznym (źle dobrany piwot i
niekorzystne ułożenie danych wejściowych) algorytm
degraduje się do O(n
2
).
1.6. Funkcje skrótu oraz przykłady
zastosowań w informatyce.
1.5.Struktury drzewiaste, charakterystyka
podstawowych typów drzew oraz przykłady
ich zastosowań.
Funkcja skrótu
to funkcja, która przyporządkowuje każdej
liczbie wartość określaną jako hasz. Jeżeli dwie liczby są różne,
to ich hashe, z wysokim prawdopodobieństwem, też powinny
być różne.
Struktury drzewiaste
zawierają:

Korzeń (element bez poprzedników)

Każdy inny element ma dokładnie jednego
poprzednika

Dla wszystkich elementów oprócz liści (el. ostatnich)
istnieje co najmniej jeden element następny
Zastosowania

buduje się za ich pomocą efektywne struktury danych
(tablica haszująca),

używa się ich do weryfikacji poprawności przesyłu
danych,

stosuje się je w kryptografii.
2
2. JITP
Nie można wymyślać swoich operatorów
Nie można zmieniać priorytetów operatorów
Nie można zmienić argumentowości operatorów (czy
operator jest jedno-, czy dwuargumentowy)
Nie można zmienić łączności operatorów
Przynajmniej jeden z typów argumentów operatora musi
być typu zdefiniowanego przez użytkownika
2.1. Kompilacja i interpretacja języków
programowania, porównanie i przykłady
zastosowania
Kompilacja

Proces automatycznego tłumaczenia kodu
napisanego w
języku programowania
na
kod
maszynowy
.

Dane wejściowe nazywa się
kodem źródłowym
.
Jeśli operator definiujemy jako funkcję składową klasy, to
ma ona zawsze o jeden argument mniej niż ta sama funkcja
napisana w postaci funkcji globalnej. Ten „brakujący”
argument – w wypadku funkcji składowej – spowodowany
jest istnieniem wskaźnika this.
Interpretacja

Przekształcanie instrukcji
programu
na bieżąco do
kodu maszynowego lub innej formy pośredniej i
natychmiastowe ich wykonywanie.

Zmusza to do ustawicznego tłumaczenia
wykonywanych instrukcji, co wielokrotnie
wydłuża czas działania programu.

Łatwość dokonywania zmian w programie w
trybie
konwersacyjnym
.
Funkcja operatorowa (jako zwykła funkcja globalna) nie
musi być przyjacielem klasy. Można definiować operatory
dla klas już wcześniej napisanych (na przykład w
bibliotekach). Dopiero jeśli f. operatorowa chce mieć dostęp
do składników prywatnych klasy trzeba ją z klasą
zaprzyjaźnić.
Istnieją operatory predefiniowane, które automatycznie
generowane są dla każdej klasy (= , & new delete)
Porównanie

Wykonanie programu za pomocą interpretera jest
wolniejsze

zajmuje więcej zasobów systemowych niż
wykonanie kodu skompilowanego

może zająć relatywnie mniej czasu niż kompilacja i
uruchomienie.
Operatory, które muszą być niestatycznymi funkcjami
składowymi: = [] () ->
Przykład
Dodanie dwóch obiektów może oznaczać dodanie ich
jakiegoś głównego składnika.
2.3. Mechanizm dziedziczenia.
Dziedziczenie jedno i wielokrotne.
Podaj
przykład wykorzystania.
Zastosowania kompilacji

Tłumaczenie kodu programu w postaci czytelnej
dla człowieka na zbiór rozkazów maszynowych,
które mogą być wykonane przez procesor
komputera lub
maszynę wirtualną
.

Konwersja między językami programowania.
Dziedziczenie
pozwala klasie przejmować właściwości
(metody, atrybuty) innych klas. Dzięki temu nowe klasy
muszą implementować jedynie dodatkowe właściwości
(tworząc klasę wystarczy wskazać, czym różni się ona od
już istniejącej).
Rozwiązanie takie umożliwia nie tylko redukcję rozmiarów
kodu, ale pozwala także zachować jego spójność, ponieważ
identyczne właściwości przestają pojawiać się w wielu
miejscach kodu.
2.2 Mechanizm przeładowania operatorów
w językach obiektowych. Podaj przykład
Działa podobnie jak przeładowanie funkcji.
Pozwala na łatwiejsze i bardziej intuicyjne dodawanie,
odejmowanie obiektów (lub używanie innych operacji).
Różnice:
- funkcja musi nazywać się operator+, operator- itp.
Klasa pochodna nie dziedziczy
:
* Konstruktorów
* Destruktorów
* Operatora przypisania
Funkcja będąca przeładowaniem operatora:
- nazywa się operator@ - gdzie @ to np. +, -, *, &, >>, <<,
New, delete, () [])
- co najmniej jeden z argumentów przyjmuje obiekt danej
klasy (
nie wskaźnik!
)
Dziedziczenie jednokrotne
Klasa może mieć tylko jedną klasę nadrzędną (Java)
Dziedziczenie wielokrotne (polimorfizm)
Klasa może mieć wiele klas nadrzędnych (pozwala na
tworzenie klas o niemal dowolnych zachowaniach) (C++)
Funkcja operatorowa może być:
- Zwykłą funkcją globalną (zwykle gdy nie chcemy
modyfikować obiektu)
- Niestatyczną funkcją składową klasy (zwykle gdy chcemy
modyfikować składniki prywatne obiektu)
Zastosowanie
Odwzorowanie hierarchiczności modelu rzeczywistego.
Nie można przeładowywać: . .* :: ?:
3
2.3 Klasy astrakcyjne i funkcje wirtualne w
językach obiektowych. Przykład
praktycznego zastosowania.
Zakres ważności obiektu
Zakres lokalny
– zmienna jest ważna w obrębie jakiegoś
bloku
Funkcje wirtualne
Zakres: blok funkcji
– taki zakres ma etykieta (jest znana
w całej funkcji, nawet w linijkach poprzedzających). Z tego
faktu wynika, że nie można instrukcją goto przeskoczyć z
wnętrza jednej funkcji do wnętrza innej.
Def. Wskaźnik do obiektu klasy podstawowej nadaje się
także do pokazania na obiekt klasy pochodnej.
virtual
obok funkcji w klasie podstawowej mówi, że od tej
pory we wszystkich dalszych pokoleniach kompilator ma
użyć swojej inteligencji i używać funkcji definiowanych w
tych dalszych pokoleniach (tak jakby funkcja była
wywołana na rzecz konkretnego obiektu (z pokolenia))
Zakres: obszar pliku
– jeśli w jednym z plików, na
zewnątrz jakiegokolwiek bloku (także bloku funkcji)
zadeklarujemy jakąś nazwę, to mówimy wówczas, że taka
nazwa jest
globalna
(ale od miejsca deklaracji, do końca
pliku). Ma ona zakres ważności pliku.
Aby mieć zakres ważności w kilku plikach, należy w
plikach, które chcą korzystać ze zmiennej np. int i, wszędzie
podać
deklarację
extern int i;
Jeżeli chcemy, aby zmienna
globalna
nie była dostępna z
innych plików, stawiamy przed nią słowo
static
.
Przykład
Klasa instrument posiada wirtualną funkcję
wydaj_dzwiek
,
która zwraca nieokreślony dźwięk. Klasa trąbka
dziedzicząca po klasie instrument posiada funkcję
wydaj_dzwiek
, która zwraca dźwięk trąbki. Jeżeli
utworzymy wskaźnik na instrument i pokażemy nim na
trąbkę, po wywołaniu funkcji wydaj dźwięk otrzymamy
dźwięk trąbki. Gdyby funkcja nie była wirtualna
otrzymalibyśmy nieokreślony dźwięk.
Zakres: obszar klasy
(tam atrybuty widoczności
składników)
Zasłanianie nazw:
zmienne lokalne przesłaniają globalne,
do globalnej można się odnieść przez operator ::zmienna.
Do innej lokalnej nie da się.
Fragment kodu, w którym wywołuje się funkcję wirtualną
wykazuje
polimorfizm
(wielość form). UWAGA:
wywołanie funkcji wirtualnej jest polimorficzne, nie sama
funkcja.
Atrybuty widoczności i konsekwencje
Etykieta private
– oznacza, że deklarowane za nią
składniki (funkcje i dane) są dostępne tylko z wnętrza klasy.
Tylko funkcje będące składnikami klasy mogą te prywatne
dane odczytywać i modyfikować (nie licząc funkcji
zaprzyjaźnionych z tą klasą)
Tylko funkcja składowa może być wirtualna. Funkcja
globalna
nie może
być wirtualna.
Funkcja wirtualna nie może być typu static (o tym którą
wersję funkcji wywołać decyduje się na podstawie obiektu a
nie klasy)
Etykieta public
– publiczne składniki oprócz wnętrza klasy
mogą być używane spoza zakresu klasy (funkcje również).
Zwykle składnikami public są funkcje składowe, dzięki
którym z zewnątrz dokonuje się operacji na danych
prywatnych
Funkcje wirtualne pozwalają na pisanie programów, o
których już w momencie pisania wiadomo, że w przyszłości
będą musiały być ciągle modyfikowane.
Klasy abstrakcyjne
Etykieta protected
– jak private, ale dostępne dla klas
wywodzących się od tej klasy (tam składnik też staje się
private)
Klasa abstrakcyjna to klasa, która nie reprezentuje żadnego
konkretnego obiektu (np. klasa ssak).
Istnieje tylko po to, aby mieć, aby ją dziedziczyć. Wspólne
cechy dla kilku klas definiujemy jednokrotnie.
W takiej klasie możemy zdefiniować funkcję
czysto
wirtualną
(taką która nigdy nie zostanie wywołana – ale
będą występować jej definicje w każdej klasie pochodnej)
Przez domniemanie składniki są
private
Dziedziczenie składników:
Private –
niedostępny z klasy pochodnej, oprócz
odziedziczonej funkcji publicznej
Protected
– dostępny z klasy pochodnej jak by był public
Public –
public
Definicja funkcji czysto wirtualnej:
void virtual
funkcja() = 0;
2.4 Obiekty lokalne i globalne. Atrybut
widoczności i konsekwencje jego
wykorzystania.
4
3. SO

Wektor bitowy
- Każdy blok dyskowy (jednostka
alokacji) jest reprezentowany przez jeden bit w
wektorze superbloku. Wartość „1” bitu oznacza, że
dany blok jest wolny.

Lista powiązana
- wszystkie wolne bloki są
powiązane w taki sposób, że w bloku poprzednim
znajduje się indeks bloku następnego. Indeks
pierwszego bloku znajduje się w specjalnym
miejscu w systemie plików.

Grupowanie
- Pierwszy wolny blok zawiera
indeksy n innych wolnych bloków, z których n-1
dotyczy bloków do alokacji przez pliki, a n-ty blok
zawiera znowu n kolejnych indeksów kolejnych
wolnych bloków.

Zliczanie
- W przypadku kilku kolejnych,
przylegających do siebie wolnych bloków
pamiętany jest tylko indeks pierwszego z nich oraz
liczba wolnych bloków znajdujących się
bezpośrednio za nim.
3.1. Organizacja pamięci pomocniczej -
metody przydziału miejsca na dysku;
przykłady znanych sy
stemów
plikowych.
Metody przydziału miejsca na dysku
Przydział ciągły -
plik zajmuje ciąg kolejnych bloków
(jednostek alokacji)
Zalety:

dostęp do plików jest efektywny – niewielkie ruchy
głowic dyskowych

szybka lokalizacja bloków pliku zarówno przy
dostępie swobodnym (dostęp do dowolnej
jednostki alokacji w tym samym czasie) i
sekwencyjnym (taśma magnetyczna)
Wady:

Fragmentacja zewnętrzna – po plikach zostają
dziury

Problemy z rozszerzaniem plików – trzeba
przenieść w inne miejsce
Metoda w Linux
Bloki (podstawowa jednostka) łączone są w grupy
(zwiększa to lokalność plików)

Podczas przydziału i-węzła plikowi, który jest
katalogiem wyszukiwana jest grupa z największą
liczbą wolnych i-węzłów.

Jeżeli nie jest to katalog to zaczyna się szukać
wolnego i-węzła od grupy, w której znajduje się i-
węzeł katalogu tego pliku.
Algorytmy przydziału i-węzłów i bloków danych powodują
ich równomierne rozłożenie w grupach.
Przydział listowy
- plik jest listą powiązanych bloków,
dowolnie rozproszonych w dostępnej przestrzeni adresowej
Zalety:

brak fragmentacji zewnętrznej,

łatwy dostęp sekwencyjny
Wady:

Dostęp swobodny utrudniony (aby przejść do
poprzedniego bloku trzeba przeglądać listę od
początku)

Utrata jednego bloku uniemożliwia dostęp do
kolejnych bloków
3.3.
Algorytmy planowania przydziału
procesora.
Przydział indeksowy
– indeksy do bloków dyskowych
skupione są w bloku indeksowym (tablicy).
Zalety :

Łatwy dostęp swobodny i sekwencyjny

Brak problemu fragmentacji zewnętrznej
Wady:

Część przestrzeni adresowej przeznaczona na blok
indeksowy
Planowanie przydziału procesora
– którym procesom z
kolejki procesów gotowych do działania ma być
przydzielona jednostka centralna
FCFS
– First Come First Server – kto pierwszy przyjdzie,
ten pierwszy będzie obsłużony
SJF
– Shortest Job First - najpierw najkrótsze zadanie

Niewywłaszczający – żaden proces nie jest
wywłaszczany podczas wykonywania fazy
procesora

Wywłaszczający (SRTF – Shortest remaining time
first) – proces jest wywłaszczony jeśli jego faza
procesora jest krótsza od następnej fazy
Algorytm priorytetowy
– procesor jest przydzielany
procesowi o najwyższym priorytecie

Może dojść do zagłodzenia – aby zapobiec, stosuje
się podwyższanie priorytetów dla procesów długo
oczekujących
Algorytm rotacyjny
(round-robin) – FCFS z cykliczną
kolejką (przydzielany jest kwant czasu procesora)
Wielopoziomowe planowanie kolejek
– każda kolejka ma
swojego planistę, między kolejkami również planuje się
przydział
Przykłady znanych systemów plikowych

FAT (File allocation table) – tablica alokacji
plików

EXT3 (third extended filesystem) –
wielopoziomowy przydział indeksowy +
księgowanie

NTFS (New technology filesystem) – ACL,
dziennik operacji dyskowych, wsparcie
metadanych
3.2.
Metody zarządzania wolną
przestrzenią na dysku; omów metodę
stosowaną w systemie Linux
3.4.
Algorytmy zastępowania stron
Metody:
5
[ Pobierz całość w formacie PDF ]