Elementy funkcjonalne komputera IAS

Składniki struktury komputera IAS:

1. Pamięć (Memory),

2. Jednostka arytmetyczno-logiczna (Arithmetic - Logic Unit),

3. Jednostka sterująca (Control Unit),

4. Jednostka wejściowa (Input),

5. Jednostka wyjściowa (Output).

Informatyka - zespół dyscyplin naukowych i technicznych zajmujących się

automatycznym przetwarzaniem, przechowywaniem i przesyłaniem

informacji oraz projektowaniem i budową do tego celu środków

technicznych.

Informatyka - dyscyplina naukowa zajmująca się badaniem, dla potrzeb

całej nauki, praw rządzących kodowaniem, zapisywaniem,

przetwarzaniem i przesyłaniem danych oraz wykorzystaniem tych

praw do tworzenia dla potrzeb ludzi urządzeń, metod i systemów.

Informatyka (lata 60-te) - Informatyka „Maszyny matematyczne i

przetwarzanie informacji”.

Informatyka - dziedzina nauki o tworzeniu właściwego modelu

reprezentującego problem i opracowaniu techniki

jego rozwiązania.

IEEE Computer Society (IEEE, Institute of Electrical and Electronic

Engineers, 1963) - organizacja ds. standa-ryzacji w

informatyce.

Informacja - każdy czynnik zmniejszający stopień niewiedzy o

badanym zjawisku, umożliwiający człowiekowi,

organizmowi Żywemu lub urządzeniu automatycznemu

polepszenie znajomości otoczenia i w

sprawniejszy sposób przeprowadzenie celowego

działania.

Informacja (G. Bateson) - różnica, która czyni różnicę.

Informacja - przyrost wiedzy, który może być uzyskany na podstawie

danych.

Dane - fakty, zdarzenia wyrażone w postaci jednostek

(abstrakcyjnych symboli, znaków).

Algorytm (algorithm) - sposób rozwiązania zagadnienia podany w formie

jednoznacznego, sformalizowanego zestawu czynności jakie należy

wykonać aby z poprawnych danych otrzymać oczekiwany wynik.

Algorytm - precyzyjna i jednoznaczna specyfikacja sekwencji operacji, które

przekształcają dane wejściowe na oczekiwane dane wyjściowe

(wyniki).

Program (program) - reprezentacja algorytmu w określonym języku :

np. binarnym (wewnętrznym), symbolicznym, proceduralnym,

obiektowym.

Program - ciąg zrozumiałych dla komputera instrukcji (rozkazów),

przeznaczonych do wykonywania. Obiekt pasywny.

Język programowania (program language) - zestaw zasad do

opisu algorytmu, umożliwiających komunikatywność

człowiek - komputer.

Kod źródłowy programu (source code) - Implementacja

algorytmu, zapis algorytmu w wybranym języku

programowania.

Proces (process) - wykonywanie programu, związane z

wykorzystaniem: licznika rozkazów (program counter), stosu

procesu (process stack), sekcji danych (data section). Obiekt

aktywny.

Algorytmy

Algorytm - ściśle określona procedura obliczeniowa, która dla

poprawnych danych wejściowych „produkuje” właściwe

wyniki.

Algorytm - skończona sekwencja reguł, która aplikuje się na

skończonej liczbie danych, pozwalająca rozwiązywać

określony problem (klasę problemów).

Algorytm - zespół reguł w procesie obliczeniowym (przetwarzania

danych)

Cechy algorytmu

-Określoność (Definiteness),

-Jednoznaczność (Uniqually determined),

-Skończoność (Finiteness),

-Ogólność (Generality),

-Efektywność (Effectiveness).

Algorytmiczne rozwiązywanie problemu

Układ kategorii: koncepcja - środki - realizacja

1. Postawienie problemu:

Definicja problemu,

Sprecyzowanie wymagań dotyczących rozwiązania,

Opis danych wejściowych (Input) i wyników(Output).

2. Budowanie algorytmu:

Koncepcja rozwiązania,

Zapis algorytmu i stopniowe precyzowanie,

Analiza algorytmu.

3. Tworzenie programu:

Wybór języka i struktur danych,

Kompilacja, testowanie.

Specyfikacja algorytmów

Formy specyfikacji algorytmów

Werbalna, opisowa (descriptive),

Schemat blokowy, sieć działań, (flow diagram, flow chart),

Pseudokodowa (pseudocode),

Języki programowania (programming languages).

Konstrukcje algorytmiczne

Elementarne konstrukcje algorytmiczne:

Bezpośrednie następstwo,

Wybór warunkowy,

Iteracja warunkowa,

Iteracja ograniczona.

Elementy analizy algorytmu

Cele analizy algorytmu:

Porównanie różnych algorytmów rozwiązujących te same problemy,

Przewidywanie wydajności w nowym środowisku,

Określenie wartości parametrów.

Aspekty analizy algorytmu:

Złożoność obliczeniowa (czasowa, pamięciowa),

Poprawność (semantyczna, syntaktyczna).

Operacje podstawowe (Basic operations)

Cechy operacji:

1. Proporcjonalność do czasu wykonania programu implementującego algorytm,

2. Proporcjonalność do liczby wszystkich operacji algorytmu,

3. Tego samego rzędu, co całkowita liczba wszystkich operacji algorytmu,

Problem:

Złożoność obliczeniowa algorytmu

Złożoność pesymistyczna (worst-case complexity),

Złożoność optymistyczna (best-case complexity),

Złożoność oczekiwana (average-case complexity).

Poprawność algorytmów

Sposoby dowodzenia:

Metoda empiryczna (testy funkcjonalne),

Formalne dowodzenie poprawności.

Specyfikacja danych wejściowych i wyników - warunki wstępne:

Asercja początkowa (precondition) - dotycząca danych wejściowych,

Asercja końcowa (postcondition) - dotycząca wyników.

Poprawność algorytmów

Wymagana:

1. Własność stopu (halting property) - algorytm zatrzymuje się i wyprowadza wynik (obliczenia nie są przerywane).

2. Poprawność wyniku (data correctness).

Poprawność częściowa (partial corectness) - spełnienie p. 2,

Poprawność całkowita (full corectness) - spełnienie p. 1, 2.

Poprawność algorytmów

Algorytm jest poprawny jeśli:

1. Posiada własność określoności obliczeń względem asercji początkowej.

2. Posiada własność stopu względem asercji początkowej.

3. Dla każdego zestawu danych wejściowych spełniających asercję

początkową obliczenie zakończy się i wyniki spełniają asercję

końcową.

Niezmienniki pętli (Loop invariants).

Niezmiennik pętli: warunki i relacje spełniane przez zmienne i

struktury danych na początku lub końcu każdego przebiegu pętli.

Etapy dowodzenia poprawności:

-Wybór niezmiennika pętli,

-Dowód prawdziwości niezmiennika względem liczby

przebiegów pętli.

Złożoność pamięciowa

 Złożoność pamięciowa oczekiwana (expected space complexity)

 Złożoność pamięciowa najgorszego przypadku (worst case space complexity)

Metody obniżania złożoności pamięciowej:

 Wielokrotne obliczanie wartości,

 Stosowanie struktur rozproszonych,

 Kompresja danych,

 Strategie przydziału pamięci.

Metody projektowania algorytmów

 Strategia „dziel i rządź” (Divide-and-conquer strategy)

 Rekurencja (Recursive approach)

 Programowanie dynamiczne ( Dynamic Programming)

 Metoda przyrostowa (Constructive method)

 Metoda zachłanna (Greedy approach).

Definicja rekurencyjna:

1. Przypadek podstawowy - wyszczególnia obiekty podstawowe

2. Reguła rekurencyjna (indukcyjna) - umożliwia konstruowanie nowych obiektów z

wcześniej zbudowanych lub podstawowych.

Algorytmy rekurencyjne (Recursive algorithms)

Wymagania przy układaniu algorytmów rekurencyjnych:

 Określenie warunku kończącego algorytm

 Dekompozycja problemu.

Implementacja rekurencji

Rekord aktywacji (activation record):

 Parametry wywołania

 Wartość zwracana

 Zmienne lokalne

 Dynamiczne dowiązanie - wskaźnik do rekordu wywołania

procesu wywołującego

 Adres powrotu do procesu wywołania.

Wielopoziomowa organizacja komputera

 Poziom 0 - poziom układów logicznych (digital logic level)

 Poziom 1 - poziom mikroarchitektury (microarchitecture level)

 Poziom 2 - poziom architektury listy rozkazów (ISA, Instruction set architecture level)

 Poziom 3 - poziom systemu operacyjnego (operating system machine level)

 Poziom 4 - poziom języka asemblera (assembler language)

 Poziom 5 - poziom języków wysokiego poziomu (high-level languages).

System operacyjny

Definicje systemu operacyjnego:

1. System operacyjny (system: sterujący, nadzorczy, nadrzędny) -

zorganizowany zespół programów, które pośredniczą między sprzętem a

Użytkownikiem, dostarczając zestawu środków ułatwiających

projektowanie, kodowanie, uruchamianie i eksploatację programów.

2. System operacyjny - warstwa oprogramowania operująca bezpośrednio na

sprzęcie, której celem jest zarządzanie zasobami systemu komputerowego i

stworzenie Użytkownikowi przyjaznego środowiska.

3. System operacyjny - oprogramowanie, które udostępnia maszynę

rozszerzoną (maszynę wirtualną) łatwiejszą do programowania.

System operacyjny:

 Zarządza zasobami systemu komputerowego

 Stworzą środowisko wygodne dla Użytkownika

Zadania systemu operacyjnego

 Definiuje interfejs Użytkownika

 Definiuje i udostępnia system plików

 Udostępnia środowisko do uruchamiania programów

 Udostępnia mechanizmy synchronizacji i komunikacji procesów

 Steruje urządzeniami wejścia-wyjścia

 Obsługuje błędy zaistniałe w sprzęcie i oprogramowaniu

Jądro systemu operacyjnego (Kernel)

Elementy jądra systemu operacyjnego:

 Zarządca plików (File manager)

 Zestaw programów obsługi urządzeń peryferyjnych (Device driver)

 Zarządca pamięci (Memory manager)

 Moduł szeregujący (Scheduler)

Usługi systemu operacyjnego

Usługi dla Użytkownika:

 Wykonanie programu: załadowanie do pamięci, uruchomienie, zakończenie

 Operacje we/wy: na pliku lub urządzeniu

 Manipulowanie systemem plików: tworzenie, usuwanie, zapisywanie, odczytywanie pliku

 Wykrywanie błędu

Usługi systemu operacyjnego

Usługi do optymalizacji działania systemu:

 Przydzielanie zasobu

 Rozliczanie: przechowywanie danych wykorzystaniu zasobów systemu do wystawiania rachunku lub celu statystycznych

 Ochrona: nadzorująca nad dostępem do zasobów systemu,

zabezpieczenie systemu przed niepożądanymi czynnikami

zewnętrznymi (uwierzytelnienie tożsamości Użytkownika w

systemie)

Funkcje systemowe

Nadzorowanie procesów:

 Zakończenie (end), zaniechanie (abort)

 Załadowanie (load), wykonanie (execute)

 Utworzenie procesu (create process), zakończenie procesu

(terminate process)

 Czekanie czasowe (wait for time)

 Czekanie na zdarzenie (wait for event)

 Sygnalizacja zdarzenia (signal event)

 Przydział i zwolnienie pamięci (allocate, free memo

Operacje na plikach:

 Utworzenie / usunięcie pliku (create / delete file)

 Otwarcie (open), zamknięcie (close)

 Czytanie (read), pisanie (write), zmiana położenia (reposition)

 Pobranie atrybutów pliku (get file attributes), określenie

atrybutów pliku (set file attributes)

Operacje na urządzeniach:

 żądanie / zwolnienie urządzenia (request / release device)

 Czytanie (read), pisanie (write), zmiana połoŜenia (reposition)

 Pobranie / ustawienie atrybutów urządzenia (get / set device

attributes)

 Logiczne przyłączenie / odłączenie urządzeń (logically attach /

detach devices)

Utrzymywanie informacji:

 Pobranie czasu, daty (get time, date) ustawienie czasu, daty (set

time, date)

 Ustawienie atrybutów procesu, pliku, urządzenia (set process,

file, device attributes)

Komunikacja:

 Utworzenie, usunięcie połączenia komunikacyjnego (create,

delete communication connection)

 Nadawanie, odbieranie komunikatów (send, receive messages)

 Przekazanie informacji o stanie (transfer status information)

 Przyłączanie, odłączanie urządzeń zdalnych (attach, dettach

remote devices)

Zasoby i zarządzanie zasobami

Zasób (resource) - dowolny obiekt sprzętowy programowy lub informacyjny, który

może być Używany przez system komputerowy.

Zasoby systemu komputerowego:

 Procesor: czas pracy procesora

 Pamięć: przestrzeń adresowa, programy ochrony i transformacji adresu

 Urządzenia we/wy: przestrzeń adresowa dla pamięci masowych, sterowniki

urządzeniami pamięci masowych, drukarek, skaner itp., wirtualne pliki

we/wy

 Informacja: system plik

Zarządzanie zasobami:

 Planowanie dostępu do zasób

 Przydział zasobu

 Ochrona i autoryzacja dostępu do zasobu

Zadanie, program, proces, wątek

 Program - obiekt pasywny (zawartość pliku)

 Programy Użytkownika (user programs) - prace (tasks)

 Proces - wykonujący się program

 Zadania (jobs) - programy, procesy

 Proces - obiekt aktywny: licznik rozkazu, zbiór przydzielonych zasobów.

Dysponuje przestrzenią adresu, posiada podstawowy priorytet i

przypisanie do dostępnych procesorów, ma jeden lub więcej wątku

 Wiele procesu może być uruchomionych w oparciu o jedną kopię

programu

 Wykonywany proces może tworzyć procesy potomne

Zadanie, program, proces, wątek

Wątek: jednostka wykonywania zarządzana przez jadro.

Stany procesu:

 Gotowości: oczekiwanie na wykonywanie

 Pogotowia (standby): proces o najwyższym priorytecie będzie

wykonywany w pierwszej kolejności

 Wykonywania: wykonywany, do czasu wywłaszczenia

 Oczekiwania

 Przejściowy (transition): nowy proces czekający na zasoby

 Zakończenia: kończy działanie

Zarządzanie procesami

Stany procesu:

 Nowy - proces został utworzony

 Aktywny - są wykonywane instrukcje

 Czekający - proces czeka na zakończenie zdarzenia (np. operacja we/wy)

 Gotowy- proces czeka na przydział procesora

 Zakończony - proces zakończył działanie

Planowanie procesów

 Procesy w systemie są ulokowane w kolejkach (process queue)

 Procesy oczekujące w pamięci głównej gotowe do

działania są w kolejce procesów gotowych (ready queue)

• Procesy czekające na przydział konkretnego urządzenia

w kolejkach do urządzeń (device queue), każde

urządzenie ma własną kolejkę

Planowanie procesów

• Planista, program szeregujący (scheduler) - proces

systemowy, który odpowiada za wybrany proces z kolejek

• Planista długoterminowy (long-term scheduler), wybiera

procesy z pamięci masowej i ładuje je do pamięci w celu

wykonania

• Planista krótkoterminowy (short-time scheduler), planista

przydziału procesora (CPU scheduler) - wybiera jeden proces

spośród procesów gotowych do wykonania i przydziela mu

procesor;

Planowanie procesu

Rodzaje procesów:

• Procesy ograniczone przez we/wy - spędzają większość

czasu na operacjach we/wy

• procesy ograniczone przez procesor - spędzają większość

czasu na obliczeniach zajmując procesor

Zadanie planisty długoterminowego: dobranie dobrej mieszanki

procesów (process mix) zawierającą procesy obydwu

rodzajów

Planista średnioterminowy (medium-term scheduler) -

odpowiada za usuwanie procesów z pamięci w celu

zmniejszenia stopnia wieloprogramowości, takie

postępowanie - wymiana (swapping)

Planowanie przydziału procesora

Decyzje o przydziale procesora zapadają w sytuacjach:

 Proces przeszedł od stanu aktywności, do stanu czekania

 Proces przeszedł od stanu aktywności do stanu gotowości

 Proces przeszedł od stanu czekania, do stanu gotowości

 Proces kończy działanie

Planowanie przydziału procesora

1. Planowanie niewywłaszczeniowe (non-preemptive)

 Proces, który dostał procesor, nie odda go zaś do swego

zakończenia lub przejścia w stan czekania

 Nie wymaga wsparcia sprzętowego (np. zegara)

2. Planowanie wywłaszczeniowe (preemptive)

 Kosztowne - wymaga mechanizmów koordynacji

Kryteria planowania

 Wykorzystanie procesora - procesor powinien być zajęty pracą

 Przepustowość (throughput) - liczba procesów kończonych w

jednostce czasu

 Czas cyklu przetwarzania (turnaround time) - czas upływający

między nadejściem procesu do systemu i zakończeniem

przetwarzania procesu

 Czas oczekiwania - suma okresów oczekiwania przez proces w

kolejce procesów gotowych do wykonania

 Czas odpowiedzi (response time) - czas upływający między

wysłaniem Żądania i pierwszą odpowiedzią

algorytmy planowania

Strategia FCFS (First Come- First Served)

Proces, który pierwszy żąda procesor, pierwszy go otrzymuje

Wada: średni czas oczekiwania bywa długi

Algorytmy planowania

Najpierw najkrótsze zadanie SJF (Shortest Job First)

Wolny procesor zostaje przydzielony procesowi mającemu

najkrótszą wstępną fazę

Algorytmy planowania

Planowanie priorytetowe.

Każdemu procesowi przypisuje się priorytet.

Procesor przydziela się temu procesowi, którego priorytet jest

najwyższy w razie różnych priorytetów wg FCFS

Proces Czas trwania fazy Priorytet

Algorytmy planowania

Planowanie rotacyjne RR (Round Robin).

Podobny do FCFS, dodano wywłaszczanie:

• Ustala się małą jednostkę czasu - kwant czasu (time quantum),

10-100 ms

• Kolejka procesów gotowych do wykonania - kolejka cykliczna

• Każdy proces dostaje procesor na odcinek czasu, nie dłuższy

od kwantu czasu, kiedy jest generowane przerwanie od zegara

proces jest usuwany na koniec kolejki procesów gotowych

• Planista pobiera procesy w kolejności przyjścia FCFS

Klasyfikacja systemów komputerowych

Klasyfikacja systemów ze względu na sposób przetwarzania:

1. Systemy wsadowe (off-line processing systems, batch

processing) - przetwarzanie pośrednie niemożliwa ingerencja

człowieka w wykonywanie zadania.

2. Systemy interakcyjne (on-line processing systems) -

przetwarzanie bezpośrednie występuje bezpośrednia interakcja

pomiędzy Użytkownikiem a systemem.

Klasyfikacja systemów komputerowych

Klasyfikacja systemów ze względu na liczbę wykonywanych

programów:

1. Systemy wielozadaniowe (multitask processing) - dopuszczalne

jest istnienie wielu zadań (procesu), którym zgodnie z pewną

strategią na przemian przydzielany jest procesor.

2. Systemy z podziałem czasu (time-sharing systems) - wielu

Użytkowników, każdy uzyskuje dostęp do procesora przez pewną

małą porcję czasu; każdy Użytkownik ma przynajmniej jeden

proces w pamięci.

Klasyfikacja systemów komputerowych

1. Systemy wieloprocesorowe (multiprocessor systems) - pewna liczba

procesorów współpracuje ze sobą dzieląc szynę, zegar, niekiedy

pamięć i urządzenia zewnętrzne. Systemy ściśle powiązane (tightly

coupled systems).

2. Systemy czasu rzeczywistego (real-time system) - zorientowane na

przetwarzanie z uwzględnieniem uwarunkowań czasowych.

Wymagane zakończenie zadań przed liniami krytycznymi

(deadlines).

3. Systemy sieciowe i rozproszone (network and distributed systems),

luźno połączone (loosely coupled) - umożliwiają zarządzanie zbiorem

rozproszonych jednostek przetwarzających (komputerów), które są

zintegrowane siecią komputerową i nie współdzielą fizycznie

zasobów.

Translatory

 Asembler (Assembler)

Symboliczna reprezentacja języka maszynowego. Zadanie

asemblera polega na zestawieniu (assemble) rozkazów maszynowych

z kodów ich operacji i wartości argumentów otrzymanych przez

przetłumaczenie nazw mnemonicznych.

Język źródłowy to język asemblera (assembly languages).

 Kompilator (Compiler)

Translator języków wysokiego poziomu. Praca kompilatora polega na

łączeniu (compile) ze sobą rozkazów języka maszynowego.

Środowisko programistyczne

Narzędzia:

 VisualStudio.Net

VS - platforma programistyczna wykorzystująca język C++, C# do

szybkiego tworzenia aplikacji dla systemu MS Windows.

Java, C# stanową podstawę platformy .NET.

 Borland Delphi.

Delphi - pakiet tworzenia obiektowych programów przy wykorzy-staniu

języka Object Pascal.

 Borland C++ BuilderX.

Borland C++ BuilderX - wykorzystanie C++ do tworzenia aplikacji dla

systemów: Linux, MS Windows.

 Borland JbuilderX.

Środowisko programistyczne języka Java dla platform:

MS Windows, Linux.

Środowisko programistyczne

Narzędzia:

 RAD (Rapid Application Development).

Umożliwiają tworzenie programu z gotowych komponentów:

osadzonych w bibliotekach, diagramów UML (Unified Modeling

Language).

 Eclipse.

Zintegrowane środowisko tworzenia projektów Java. Możliwości

integracji z programami pomocniczymi np. cvs (concurrent

versions system), svn (subversion).

 Magic eDeveloper.

Koncepcja szybkiego tworzenia portali internetowych,

wykorzystujących bazy danych. Środowisko RAD dla Internetu.

Hierarchia języków programowania

 Mikroprogramowanie (Microprogramming)

 Język maszynowy (wewnętrzny) ( Machine language)

 Język asemblerowy (symboliczny) (Assembly language)

 Programowanie strukturalne (proceduralne ) (Structured programming)

 Programowanie modularne (Modular programming)

 Programowanie obiektowe (Object-oriented programming)

 Programowanie komponentowe (Component-object model)

Język maszynowy

Język maszynowy, język wewnętrzny (Internal code)

Rozkaz maszynowy:

 Rozkazy w postaci binarnej, kod operacji (operation code)

 Adresy absolutne - binarne (operand field)

Budowa słowa maszynowego:

Programowanie strukturalne i proceduralne

Aspekt strukturalizacji:

 Struktury sterujące języka programowania

 Przejrzystość algorytmów i programów

Aspekt proceduralny:

 Systematyczny podział na części składowe, których powiązania

wzajemne są dobrze określone (procedury, funkcje)

 Ułatwienie uruchamiania i modyfikacji programów

 Projektowanie zstępujące (top-down), E. Dijkstra

 Refaktoryzacja kodu źródłowego (XP, Extreme Programming)

Modularność

Modularość - podział programu na oddzielne moduły o określonych funkcjach,

w celu umożliwienia pracy nad jednym programem wielu programistom

(opracowywanie, pielęgnowanie i uruchamianie).

Kompletna translacja programu odbywa się w dwóch etapach:

 Kompilacja (asemblacja) modułów źródłowych

 Konsolidacja skompilowanych modułów

Programowanie komponentowe

Programowanie komponentowe - definiowanie obiektów samoopisujacych się

(komponentów programowych) niezależnie od języka programowania.

Umożliwienie włączenie do aplikacji obiektów należących do innych

programów, przy zachowaniu pewności, że każdy z komponentów będzie w

stanie komunikować się i „rozumieć” funkcje pozostałych.

Technologia COM (Component-object model):

 OLE (Object Linking and Embedding) - łączenie i osadzanie obiektów,

standard współużytkowania informacji miedzy aplikacjami, dający możliwość

tworzenia obiektów w jednej aplikacji i włączania ich do innych.

 ActiveX - zbiór protokołów i interfejsów programowych API (Application

Programming Interface) służących do tworzenia scalania i udostępniania

komponentów oprogramowania.

 DCOM (Distributed Component-object model) - podstawa do tworzenia

środowiska rozproszonego przetwarzania danych poprzez przesyłanie i

udostępnianie komponentów w sieci.

Paradygmaty programowania

Podstawowe paradygmaty:

 Imperatywny

 Funkcyjny

 Deklaratywny (programowanie w logice)

 Obiektowy

Założenia:

 Mechanizmy są implementowane w realnych systemach komputerowych.

 Komputery działają w oparciu o imperatywną architekturę von Neumanna.

 Każdy uruchomiany program musi być najpierw przetłumaczony do ciągu rozkazów w języku wewnętrznym konkretnej maszyny.

Paradygmat imperatywny

Postulaty paradygmatu:

 Stan maszyny wyznaczają zawartości rejestrów procesora oraz pamięci

 Instrukcja imperatywna zmienia stan maszyny

 Program - ciąg instrukcji, których realizacja jest zgodna z cyklem

maszynowym, rozkaz: <pobierz-dekoduj-wykonaj>

Języki imperatywne wysokiego poziomu:

Pascal, Fortran, Cobol, C, Ada

 Programowanie imperatywne (pierwotny sposób programowania), w którym

program (procedura) postrzegany jest jako ciąg poleceń dla komputera.

 Proces programowania sprowadza się do utworzenia ciągu instrukcji

imperatywnych (poleceń).

Paradygmat funkcyjny

Cechy paradygmatu:

 Program - złożona funkcja (w sensie matematycznym), która otrzymuje dane

wejściowe i wylicza wynik

 Brak imperatywnych pętli

 Brak stanu maszyny i zmiennych

 Przyjazne środowisko do konstruowania dużych pakietów oprogramowania.

Programowanie funkcyjne - składanie funkcji z wykorzystaniem

rekurencji.

Program jest złożeniem wielu zagnieżdżonych elementarnych funkcji

(wymuszona modułowość budowanych programów).

Paradygmat deklaratywny (programowanie w logice)

Cechy paradygmatu:

 Program - zbiór zdań początkowych, na bazie których algorytm dokonuje

wnioskowania dedukcyjnego.

 Algorytm oparty jest na cyklicznie stosowanej zasadzie rezolucji

(wnioskowaniu dedukcyjnym).

Składniki, z których konstruuje się zdania początkowe to predykaty.

Predykat składa się z identyfikatora predykatu, po którym w

nawiasach umieszcza się argumenty predykatu.

Przykład predykatu reprezentującego fakt: jan jest ojcem jerzego:

ojciec (jan, jerzy).

Zdania w Prologu są albo faktami albo regułami. W obu przypadkach

zdanie jest zakończone kropką.

Fakt składa się z pojedynczego predykatu.

Prolog odróżnia stałe od zmiennych w ten sposób, że nazwy stałych

rozpoczynają się małymi literami a zmienne dużymi.

Paradygmat obiektowy

Paradygmat obiektowy (programowanie obiektowe OOP (Object-oriented

programming).

Obiekt- odrębna jednostka stanowiąca powiązanie danych z operacjami na nich.

Program - zbiór powiązanych ze sobą obiektów, zawierających dane i umiejących

wykonywać na nich pewne operacje.

klasa (class) - rozszerzeniem struktury danych o funkcje (metody) operujące na

polach klasy.

Obiekt - egzemplarz klasy umieszczony w pamięci (instancja klasy).

CORBA (Common Object Request Broker Architecture) - standard obiektowych

architektur programowych.

Paradygmaty programowania

Paradygmaty inne:

 Programowanie na poziomie wartości

 Programowanie skalarne i macierzowe

 Paradygmat programowania proceduralnego

Konkretny język programowania reprezentuje jeden lub więcej

paradygmatów:

 Fortran, Pascal i C - języki pozwalające stosować paradygmat programowania

imperatywnego.

 Java, C# - języki obiektowe, w których typowe programowanie imperatywne

zostało mocno ograniczone.

 C++ - język zarówno obiektowy jak i imperatywny.

 Programowanie imperatywne - szczególny, wynaturzony przypadek

programowania obiektowego.

Język formalny

Elementy języka formalnego:

 Alfabet A = {a1, a2, …, an} - dowolny zbiór symboli, z których zestawiane są

słowa języka,

 Słowo - uporządkowany ciąg symboli alfabetu,

 Język A* - podzbiór zbioru możliwych słów nad alfabetem A,

 Gramatyka - zbiór reguł umożliwiających generowanie słów i zdań.

Przykład:

Alfabet: A={a, b}

Gramatyka: reguła R1 - a jest poprawne,

reguła R2 - Jeżeli  jest poprawne to ab jest poprawne.

Poprawne słowa:

a - na podstawie R1

aab - na podstawie R1 i R2

aaabb - na podstawie R1 i dwukrotnie stosowanej R2

Język A* = {aab, aaabb, a, b}.

Gramatyki bezkontekstowe

Gramatyka bezkontekstowa:

G = < T, N, P,  >

 T- zbiór symboli końcowych (terminal symbols ), z których budowane są słowa

generowane przez gramatykę G,

 N - zbiór symboli pomocniczych, nieterminalnych używanych przy określaniu

reguł opisujących konstruowanie słów poprawnych w sensie gramatyki G,

 P - Lista produkcji (list productions): zestaw reguł tzw. produkcji,

 ∈N: aksjomat języka, kategoria syntaktyczna (syntactic category), podaje z jakiej

konstrukcji można wyprowadzić wszystkie generowane przez gramatykę napisy.

Kategoria syntaktyczna

Gramatyka składa się z co najmniej jednej produkcji.

Każda produkcja składa się z trzech części:

 Części nagłówkowej, symbolu początkowego (head, start symbol), która jest

kategoria syntaktyczną,

 Metaznaku (metasymbol)

 Części zasadniczej (body).

Produkcje wchodzące w skład zbioru P są postaci:

x >u, x(należy)N, u(należy)(N(suma)T)*

Gramatyka wyrażenia arytmetycznego

Elementy składowe gramatyki:

 Zbiór T: T = {a, b, d, +, *, (, )}

 Zbiór N: N = {W, S, C}

Semantyka symboli: W - wyrażenie, S - składnik, C - czynnik.

 Kategoria syntaktyczna :  = W

 Lista produkcji:

P = { W>S; W>W+S; S>C; S>C*S;S>S*C; C>a; C>b; C>d;

C>W) }

Przykład: (a+b)*d

W

S

C*S

(W)*S

(W+S)*C

(S+S)*C

(C+C)*C

(a+c)*d

Sposoby opisu składni

Notacje:

 BNF (Backus-Naur Form)

 EBNF (Extended Backus-Naur Form)

 Diagramy syntaktyczne (Syntactic diagram)

Notacje: BNF, EBNF

Notacja BNF:

 Symbole terminalne,

 Symbole nieterminalne,

 Produkcje,

 Metasymbole

< > symbol pomocniczy,

::= symbol produkcji,

 symbol alternatywy,

( ) powtórzenie, { } - EBNF

Wyrażenie arytmetyczne:

<W> ::= <S> <W> + <S>  <S> + <W>

<S> ::= <C> <C> * <S>  <S> * <C>

<C> ::= (<W> )a  b 

Odwrotna Notacja Polska ONP

Beznawiasowe algebry Łukasiewicza

Gramatyka wyróżnia arytmetycznego w ONP:

Zbiór T: T = {a, b, d, +, *}

P: <W> ::= <Z> <Z> <O> | <Z>

<Z> ::= <X> <X> <O> | <X>

<X> ::= a | b | d

<O> ::= + | *

Przykład:

(a+b)*d ≡ ab + d*

Maszyna Turinga - algorytmy

 Maszynę Turinga możemy w rzeczywistości traktować jako komputer z jednym

ustalonym programem,

 Oprogramowaniem jest diagram przejść,

 Sprzęt składa się z głowicy, taśmy oraz (ukrytego) mechanizmu, który

faktycznie przechodzi diagram przejść zmieniając stany i sterując czynnościami

czytania, pisania, wymazywania i ruchu głowicy.

Algorytmiczne problemy P, NP:

 P - klasa zawierająca problemy rozwiązywalne przez deterministyczne

maszyny Turinga w czasie wielomianowym.

 NP - klasa zawierająca dokładnie te problemy decyzyjne, które są

rozwiązywalne przez niedeterministyczne maszyny Turinga w czasie

wielomianowym.

Teza Churcha-Turinga

Teza Churcha-Turinga:

Maszyna Turinga potrafi rozwiązać każdy efektywnie rozwiązywalny problem

algorytmiczny

Interpretacja: Każdy problem algorytmiczny, dla którego możemy znaleźć

algorytm dający się zaimplementować w dowolnym języku, wykonujący się na

dowolnym komputerze, nawet na takim, którego jeszcze nie zbudowano, ale

można zbudować, (nawet na takim, który wymaga nieograniczonej ilości

czasu i pamięci dla coraz większych danych) jest także rozwiązywalny przez

maszynę Turinga.

Własności entropii

Funkcja H(X):

 Ciągła na odcinku [0, 1] i symetryczna

 Posiada dolne i górne ograniczenie

0 = H(1, 0,..., 0)H(p1,..., pn)=<H(1/n,..., 1/n) = lg n.

 Własność grupowania.

Jeśli w zbiorze X = {x1,..., xn} symbole x1,..., xi tworzą podzbiór Xi, to:

H(p1,..., pi, pi+1,..., pn) = HX-Xi + HXi

Kodowanie informacji

 Kod wynikowy nazywamy jednoznacznie dekodowalnym jeżeli istnieje

tylko jeden sposób podziału ciągu kodowego na oddzielne słowa kodu.

 Kod jest kodem przedrostkowym jeśli nie możemy otrzymać żadnego

słowa kodu z innego słowa kodu poprzez dodanie do niego zer lub

jedynek.

 Kodem optymalnym dla danego rozkładu prawdopodobieństwa

nazywamy kod, dla którego liczba Lc posiada najmniejszą wartość.

Systemy kodowania danych

Reprezentacja danych alfanumerycznych.

 Nośnikami danych są sygnały elektryczne przetwarzane przez system układów

elektronicznych.

 Układy pracują w logice dwuwartościowej i nazywane są logicznymi układami

cyfrowymi.

Elementy tych układów pozostają w dwóch stanach:

 Stanie wysokim (istnieje wartość amplitudy napięcia - Umax, prądu - Imax)

 Stanie niskim (istnieje wartość amplitudy napięcia - Umin, prądu - Imin)

Stany te oznaczamy odpowiednio: stan wysoki - 1, stan niski - 0 (konwencja logiki

dodatniej).

Cechy kodu binarnego:

 Duża niezawodność układów dwustanowych.

 Łatwość opisu, analizy i syntezy tych układów.

Stany 1 oraz 0 utożsamiane są z cyframi binarnymi

 Mała ilość przekazywanej informacji charakterystyczna dla elementów

dwustanowych (logiki dwuwartościowej).

Kody danych alfanumerycznych

Standardy:

 ASCII (American Standard Code for Information Interchange),

 ISO (International Standard Organisation),

 ANSI (American National Standard Institute),

Extended ASCII (IBM, 1981) 8-bitowy kod znaków:

 Alfanumerycznych,

 Matematycznych,

 Symboli specjalnych,

 Znaków sterujących.

Pozycyjne systemy liczbowe

Systemy stałobazowe ( Radix-based systems) - systemy pozycyjne, w których

poszczególne wagi są potęgami stałej całkowitej, zwanej podstawą lub bazą.

Format stałopozycyjny (Radix notation) - reprezentacja ustalonej pozycji kropki

oddzielającej części całkowitą od ułamkowej.

Binarny system liczbowy

Kod NBC (Natural Binary Code). Liczba całkowita.

Ciąg cyfr binarnych:

an-1 an-2 … an-2 … a1 a0

wyraża wartość liczby całkowitej będącej odpowiednikiem liczby dziesiętnej:

A = an-1 2n-1 + an-2 2n-2 + … + a1 21 + a0 20

ai - wartość i-tego bitu liczby

a0 - najmniej znaczący bit lsb (least significant bit)

ai - najbardziej znaczący bit msb (most significant bit)

1 1 0 1(2) ->13(10)

---