Podprogram wyodr¦bniony zestaw instrukcji (osobny algorytm) realizuj¡cy pewne zamkni¦te dzieªo: ma dobrze1 zde niowany zestaw danych (parametrów) wej±ciowych, zestaw danych wyj±ciowych i relacji (zale»no±¢) pomi¦dzy nimi.
Kolejka jest strukturą liniowo uporządkowanych danych w której dołączać nowe dane można jedynie na koniec kolejki a usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka sama, jak w przypadku stosu, z tą różnicą, że usuwamy dane od początku a nie od końca. Pierwszy element (a dokładniej wskaźnik do jego miejsca w pamięci) musi zostać zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1). Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść wszystkie od elementu aktualnego (czyli ostatniego), co wymaga czasu O(n).
Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi np. w sklepie. Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.
Program Licznikowy:
-zmienne przechowują nieujemne liczby całkowite (tzw. liczniki)
-trzy rodzaje elementarnych operacji: X==0, x==y+1, x==y-1
-dwie instrukcje sterujące proste następstwo i skok warunkowy
jeśli x=0 skocz do L (L jest etykieta pewnej instrukcji)
-program licznikowy zatrzymuje się wtedy, gdy:
#wystepuje proba wykonania nieistniejacej instrukcji
#------II----- przejscia do nieistniejacej etykiety
#wyczerpana zostaje lista instrukcji
1. Algorytm A jest częściowo poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP, jeżeli algorytm A zatrzymuje się, to dane wyjściowe algorytmu spełniają warunek WK.
2. Algorytm A jest całkowicie poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP algorytm A zatrzymuje się i dane wyjściowe tego algorytmu spełniają warunek WK.
Zmienna to obszar pamięci przechowujący pewne dane. O sposobie prezentacji tych danych decyduje typ zmiennej.
System operacyjny (ang. skrót OS Operating System) - oprogramowanie zarządzające sprzętem komputerowym, tworzące środowisko do uruchamiania i kontroli zadań użytkownika.
Maszyna Turinga - stworzony przez Alana Turinga abstrakcyjny model komputera służący do wykonywania algorytmów. Maszyna Turinga składa się z nieskończenie długiej taśmy podzielonej na pola. Taśma może być nieskończona jednostronnie lub obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z M stanów. Zależnie od kombinacji stanu maszyny i pola maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną ilość takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan (M+1)-szy, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.
Tablice decyzyjne stanowią, jedną z podstawowych technik stosowanych w rozwiązywaniu problemów i podejmowaniu decyzji. Dzięki tablicom decyzyjnym można w zwięzły sposób określić, przy spełnieniu z góry określonych warunków, jakie czynności należy podjąć. Tablica decyzyjna jest określoną strukturą opisu zbioru związanych ze sobą reguł decyzyjnych.
Schemat blokowy (ang. block diagram, owchart) diagram, na którym procedura, system albo program komputerowy, s¡ reprezentowane przez opisane gury geometryczne poª¡czone liniami zgodnie z kolejno±ci¡ wykonywania czynno±ci wynikaj¡cych z przyj¦tego algorytmu rozwi¡zania zadania.
Stos (ang. Stack) - 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.
Drzewo - schemat wygladajacy jak drzewo, wychodzimy od korzenia, poprzez węzły do liści (z liści już nic nie wychodzi, może ich być dużo)
Odwrotna notacja polska (ang. Reverse Polish Notation, RPN) - jest sposobem zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach (zapis postfiksowy), a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym (zapis infiksowy), lub przed operandami jak w zwykłej notacji polskiej (zapis prefiksowy). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań. RPN bardzo ułatwia wykonywanie na komputerze obliczeń z nawiasami i zachowaniem kolejności działań. Zarówno algorytm konwersji notacji konwencjonalnej (infiksowej) na odwrotną notację polską (postfiksową), jak i algorytm obliczania wartości wyrażenia danego w RPN są bardzo proste i wykorzystują stos. Odwrotna notacja polska została opracowana przez australijskiego naukowca Charlesa Hamblina jako "odwrócenie" beznawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych.
Oprogramowanie użytkowe (zwane też aplikacyjnym, aplikacjami) - określają sposoby w jaki zostają użyte zasoby systemowe do rozwiązywania problemów obliczeniowych zadanych przez użytkownika (kompiler, systemy baz danych, gry, oprogramowanie biurowe), zazwyczaj program który ma bezpośredni kontakt z użytkownikiem i nie jest częścią większego programu, z technicznego punktu widzenia jest to oprogramowanie korzystające z usług oprogramowania systemowego.
Podprogram wyodr¦bniony zestaw instrukcji (osobny algorytm) realizuj¡cy pewne zamkni¦te dzieªo: ma dobrze1 zde niowany zestaw danych (parametrów) wej±ciowych, zestaw danych wyj±ciowych i relacji (zale»no±¢) pomi¦dzy nimi.
Kolejka jest strukturą liniowo uporządkowanych danych w której dołączać nowe dane można jedynie na koniec kolejki a usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka sama, jak w przypadku stosu, z tą różnicą, że usuwamy dane od początku a nie od końca. Pierwszy element (a dokładniej wskaźnik do jego miejsca w pamięci) musi zostać zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1). Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść wszystkie od elementu aktualnego (czyli ostatniego), co wymaga czasu O(n).
Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi np. w sklepie. Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.
Program Licznikowy:
-zmienne przechowują nieujemne liczby całkowite (tzw. liczniki)
-trzy rodzaje elementarnych operacji: X==0, x==y+1, x==y-1
-dwie instrukcje sterujące proste następstwo i skok warunkowy
jeśli x=0 skocz do L (L jest etykieta pewnej instrukcji)
-program licznikowy zatrzymuje się wtedy, gdy:
#wystepuje proba wykonania nieistniejacej instrukcji
#------II----- przejscia do nieistniejacej etykiety
#wyczerpana zostaje lista instrukcji
1. Algorytm A jest częściowo poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP, jeżeli algorytm A zatrzymuje się, to dane wyjściowe algorytmu spełniają warunek WK.
2. Algorytm A jest całkowicie poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP algorytm A zatrzymuje się i dane wyjściowe tego algorytmu spełniają warunek WK.
Zmienna to obszar pamięci przechowujący pewne dane. O sposobie prezentacji tych danych decyduje typ zmiennej.
System operacyjny (ang. skrót OS Operating System) - oprogramowanie zarządzające sprzętem komputerowym, tworzące środowisko do uruchamiania i kontroli zadań użytkownika.
Maszyna Turinga - stworzony przez Alana Turinga abstrakcyjny model komputera służący do wykonywania algorytmów. Maszyna Turinga składa się z nieskończenie długiej taśmy podzielonej na pola. Taśma może być nieskończona jednostronnie lub obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z M stanów. Zależnie od kombinacji stanu maszyny i pola maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną ilość takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan (M+1)-szy, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.
Tablice decyzyjne stanowią, jedną z podstawowych technik stosowanych w rozwiązywaniu problemów i podejmowaniu decyzji. Dzięki tablicom decyzyjnym można w zwięzły sposób określić, przy spełnieniu z góry określonych warunków, jakie czynności należy podjąć. Tablica decyzyjna jest określoną strukturą opisu zbioru związanych ze sobą reguł decyzyjnych.
Schemat blokowy (ang. block diagram, owchart) diagram, na którym procedura, system albo program komputerowy, s¡ reprezentowane przez opisane gury geometryczne poª¡czone liniami zgodnie z kolejno±ci¡ wykonywania czynno±ci wynikaj¡cych z przyj¦tego algorytmu rozwi¡zania zadania.
Stos (ang. Stack) - 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.
Drzewo - schemat wygladajacy jak drzewo, wychodzimy od korzenia, poprzez węzły do liści (z liści już nic nie wychodzi, może ich być dużo)
Odwrotna notacja polska (ang. Reverse Polish Notation, RPN) - jest sposobem zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach (zapis postfiksowy), a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym (zapis infiksowy), lub przed operandami jak w zwykłej notacji polskiej (zapis prefiksowy). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań. RPN bardzo ułatwia wykonywanie na komputerze obliczeń z nawiasami i zachowaniem kolejności działań. Zarówno algorytm konwersji notacji konwencjonalnej (infiksowej) na odwrotną notację polską (postfiksową), jak i algorytm obliczania wartości wyrażenia danego w RPN są bardzo proste i wykorzystują stos. Odwrotna notacja polska została opracowana przez australijskiego naukowca Charlesa Hamblina jako "odwrócenie" beznawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych.
Oprogramowanie użytkowe (zwane też aplikacyjnym, aplikacjami) - określają sposoby w jaki zostają użyte zasoby systemowe do rozwiązywania problemów obliczeniowych zadanych przez użytkownika (kompiler, systemy baz danych, gry, oprogramowanie biurowe), zazwyczaj program który ma bezpośredni kontakt z użytkownikiem i nie jest częścią większego programu, z technicznego punktu widzenia jest to oprogramowanie korzystające z usług oprogramowania systemowego.