Przegląd podstawowych pojęć (1)
Program komputerowy to sekwencja instrukcji wykonywanych przez
komputer w pewnym ustalonym porządku
Podstawy informatyki (3)
instrukcje programu zapisane są w kodzie maszynowym
dr inż. Sebastian Pluta
Oprogramowanie jest pojęciem szerszym od programu: jest to zbiór
[e-mail]
jednego lub kilku programów i danych potrzebnych w czasie ich
działania
Instytut Informatyki Teoretycznej i Stosowanej
Proces (ang. process) to twór abstrakcyjny, który składa się z:
wykonywanego (działającego) programu zapisanego w sekcji kodu
bieżących danych o jego stanie i zasobach:
licznika rozkazów reprezentującego bieżącą czynność
stosu przechowującego dane tymczasowe
sekcji danych
Podstawy informatyki (3)  p.1
Przegląd podstawowych pojęć (2) Przegląd podstawowych pojęć (3)
Wątek (ang. thread) jest podstawową jednostką wykorzystania System operacyjny (ang. Operating System, OS) to oprogramowanie
procesora składającą się z: odpowiedzialne za bezpośrednią kontrolę i zarządzanie zasobami
sprzętowymi. OS zapewnia dla innych aplikacji (programów):
licznika rozkazów
możliwość ich uruchomienia
stosu
dostęp do zasobów sprzętowych
wątek współużytkuje wraz z innymi równorzędnymi wątkami:
w przypadku systemów wieloprocesowych i wieloużytkownikowych
sekcję kodu
podział zasobów i ich ochronę.
sekcję danych
Jądro systemu operacyjnego (ang. kernel) to centralna część
niektóre zasoby systemu operacyjnego, np. otwarte pliki i sygnały
systemu operacyjnego, działająca zawsze. Realizuje:
równorzędne wątki wraz z współdzielonymi zasobami to zadanie
zarządzanie pamięcią
zarządzanie procesami
zarządzanie urządzeniami wejścia wyjścia
obsługę systemu plików
Podstawy informatyki (3)  p.2 Podstawy informatyki (3)  p.3
Algorytmy (1) Algorytmy (2)
Algorytm  jest to sformalizowany zestaw czynności które należy poziom szczegółowości algorytmu musi być tak dobrany, aby być
wykonać żeby uzyskać dany rezultat, w szczególności aby wyliczyć zrozumiałym dla  sprzętu  algorytm musi się składać z zestawu akcji
wynik na podstawie danych, np.: podstawowych
 Ciasto bananowo-jabłkowe  Pychotka
dane potrzebne do przeprowadzenia procesu muszą być dopuszczalne
4 jajka ubić z 1 szklanką cukru na puszystą pianę, następnie mieszając
dla algorytmu opisującego proces czyli muszą być zgodne z pewną
1
dodawać po łyżeczce 1 i szklanki mąki zmieszanej z łyżeczką proszku
4 specyfikacją
do pieczenia. 200g margaryny rozpuścić i ostudzić, następnie dodać do
algorytm dla  sprzętu pozbawionego czynnika ludzkiego wymaga
ciasta. Na blachę tortową z kominkiem (natłuszczoną i posypaną mąką)
precyzyjnego określenia każdej akcji podstawowej
wylać połowę ciasta, na to pokrojone w cienkie plasterki 4 jabłka
algorytmy są rozwiązaniami pewnych rodzajów zadań zwanych
(obrane i pozbawione gniazd nasiennych), na to pokrojonego w plasterki
zadaniami algorytmicznymi lub obliczeniowymi
banana, następnie rodzynki i wiórki kokosowe (w ilości wedle uznania).
Przykryć to pozostałym ciastem i posypać wiórkami kokosowymi
(również w ilości wedle uznania). Piec 45 60 minut w temp.
200 stopni C.
Podstawy informatyki (3)  p.4 Podstawy informatyki (3)  p.5
Algorytmy (3) Struktury sterujące (1)
algorytm powinien dać poprawne rozwiązanie dla każdych Bezpośrednie następstwo   wykonaj A a potem B
dopuszczalnych danych, w tym nieskończonych
Wybór warunkowy   jeśli Q, to wykonaj A, w przeciwnym razie
proces opisywany przez bardzo krótki algorytm może trwać wykonaj B , lub  jeśli Q, to wykonaj A , gdzie Q jest pewnym warunkiem
bardzo długo, np. algorytm sumowania wydatków i przychodów w firmie:
Iteracja:
zanotuj  na boku liczbę 0;
ograniczona   wykonaj A dokładnie N razy , gdzie N jest pewną
przewertuj kolejno faktury w firmie, dodając kwotę z faktury do
liczbą
liczby  na boku przyjmując kwotę z faktur wystawionych dla firmy
warunkowa (nieograniczona)   wykonuj A aż do Q lub  dopóki
jako ujemne, a kwoty z faktur wystawionych przez firmę jako
Q, wykonuj A , gdzie Q jest pewnym warunkiem
dodatnie;
kiedy  obsłużysz ostatnią fakturę, przedstaw wartość  na boku
jako wynik;
Podstawy informatyki (3)  p.6 Podstawy informatyki (3)  p.7
Struktury sterujące (2) Struktury sterujące (3)
Algorytm sumowania wydatków i przychodów w firmie, dla listy N faktur:
sprawdz
, czy wskazana faktura jest wystawiona dla firmy,
zanotuj  na boku liczbę 0;
jeśli tak, to dodaj do liczby  na boku kwotę z
wskaż na pierwszą fakturę z listy;
wskazanej faktury pomnożoną przez -1;
wykonaj co następuje N - 1 razy:
w przeciwnym razie dodaj do liczby  na boku kwotę ze
sprawdz
, czy wskazana faktura jest wystawiona dla
wskazanej faktury;
firmy, jeśli tak, to dodaj do liczby  na boku kwotę
podaj wartość liczby  na boku jako wynik;
ze wskazanej faktury pomnożoną przez -1;
w przeciwnym razie dodaj do liczby  na boku kwotę
ze wskazanej faktury;
Przedstawiony algorytm działa dla danych wejściowych o N > 0
wskaż na następną fakturę;
Podstawy informatyki (3)  p.8 Podstawy informatyki (3)  p.9
Struktury sterujące (4) Schematy blokowe
Start
algorytmy mogą zawierać iteracje zagnieżdżone,
np.:  wykonaj A dokładnie N razy , gdzie A jest w postaci
zanotuj "na boku" 0;
 wykonuj B aż do Q
wskaż na pierwszą fakturę;
 wykonaj A dokładnie N razy jest tu pętlą zewnętrzną
 wykonuj B aż do Q jest pętlą wewnętrzną
TAK czy faktura
NIE
jest dla
firmy?
dodaj wskazywaną kwotę dodaj wskazywaną
pomnożoną przez -1 kwotę do "na boku"
instrukcja skoku   skocz do G , gdzie G oznacza pewne miejsce w do "na boku"
algorytmie
TAK NIE
wypisz liczbę
czy koniec faktur?
"na boku"
Stop
Podstawy informatyki (3)  p.10 Podstawy informatyki (3)  p.11
Sortowanie (1) Sortowanie (2)
dane do sortowania: nieuporządkowana lista elementów algorytm sortowania przez liniowe wstawianie dla N elementów:
zapisz  na boku 0;
rezultat sortowania: lista elementów uporządkowana w ustalonej
kolejności, np. rosnącej wykonaj co następuje N - 1 razy:
znajdz
maksymalny element dla elementów od
algorytm sortowania bąbelkowego dla N elementów:
elementu 1 do elementu N-  na boku ;
wykonaj co następuje N - 1 razy:
zamień znaleziony maksymalny element z elementem
wskaż na pierwszy element;
ostatnim z przedziału poszukiwań z poprzedniego
wykonaj co następuje N - 1 razy:
punktu;
� porównaj wskazany element z następnym
dodaj do liczby  na boku 1;
elementem;
� jeśli porównane elementy są w niewłaściwej
kolejności, zamień je miejscami;
� wskaż następny element;
Podstawy informatyki (3)  p.12 Podstawy informatyki (3)  p.13
Sortowanie (3) Podprogramy
algorytm algorytm szukania największego elementu w odniesieniu do algorytmu
znajdowania maksymalnego elementu od elementu 1 do sortowania przez liniowe wstawianie jest podprogramem (procedurą)
elementu M:
zalety podprogramów:
zapisz  na boku pierwszy element;
możliwość wykonania tego samego algorytmu dla różnych danych
wskaż na pierwszy element;
uproszczenie zapisu większych algorytmów
wykonaj co następuje M - 1 razy:
znaczne uproszczenie czytania i analizowania algorytmów
wskaż na następny element;
podprogram jest rozszerzeniem istniejącej listy instrukcji
jeśli wskazany element jest większy od zapisanego
elementarnych
 na boku , zapisz wskazany element  na boku ;
łatwiejszy proces projektowania algorytmów  poprzez zbliżanie
się do celu stopniowo poprzez użycie podprogramów jeszcze
nieistniejących
Podstawy informatyki (3)  p.14 Podstawy informatyki (3)  p.15
Rekurencja (1) Rekurencja (2)
rekurencja to zdolność podprogramu do wywołania samego siebie algorytm iteracyjny obliczania n! (silnia):
algorytm rekurencyjny obliczania n! (silnia):
podprogram silnia z n
n! = n � (n - 1) � (n - 2) � ...� 2 � 1
zapisz  na boku 1;
n! = n � (n - 1)!
zapisz  na drugim boku 2;
wykonaj co następuje n - 1 razy:
algorytm podprogramu liczącego silnię dla liczby n
pomnóż  na drugim boku przez  na boku i wynik
podprogram silnia z n
umieść  na boku ;
jeśli n jest 0, to wynikiem jest 1
dodaj do  na drugim boku 1;
w przeciwnym razie wynikiem jest n pomnożone
wróć, wynik jest zapisany  na boku ;
przez wartość podprogramu silna z n - 1
algorytm  główny obliczający 10! :
wróć;
wywołaj silnia z 10
algorytm  główny obliczający 10! :
wywołaj silnia z 10
Podstawy informatyki (3)  p.16 Podstawy informatyki (3)  p.17
Wieże Hanoi (1) Wieże Hanoi (2)
zadanie polega na przeniesieniu wszystkich (N) krążków ze słupka A na
po uzyskaniu takiego stanu dalsze zadanie sprowadza się do  przenieś
słupek B przy pomocy słupka C w ten sposób, że na krążek mniejszy
wszystkie (N - 1) krążki ze słupka C na słupek B przy pomocy słupka A
nie można położyć większego
algorytm ma za zadanie wypisać sekwencję kroków potrzebnych do
wykonania zadania
Podstawy informatyki (3)  p.18 Podstawy informatyki (3)  p.19
Wieże Hanoi (3)
algorytm rekurencyjny podprogramu wypisującego sekwencję kroków
stanowiących rozwiązanie zadania Wież Hanoi:
podprogram przenieś N z X na Y używając Z
jeśli N jest 1, to wypisz  X ->Y ;
w przeciwnym razie wykonaj:
wywołaj przenieś N - 1 z X na Z używając Y;
wypisz  X ->Y ;
wywołaj przenieś N - 1 z Z na Y używając X;
wróć;
algorytm  główny dla 3 krążków:
wywołaj przenieś 3 z A na B używając C;
Podstawy informatyki (3)  p.20