Wykład 3 Algebry



Pobieranie 151,55 Kb.
Data29.10.2017
Rozmiar151,55 Kb.

Wykład 3
3.1. Algebry

Niech na zbiorze U określone są funkcje:

f1: Uk1  U, .., fn: Ukn  U

i D jest rodziną funkcji D={f1,...,fn}.


Algebrą (algebrą ogólną, algebrą uniwersalną) nazywamy krotkę

=1,...,fn >,



  • gdzie zbiór U jest zwany nośnikiem algebry,

  • natomiast D jest rodziną działań (funkcji) podstawowych {f1,...,fn}.,

  • a ciąg liczb naturalnych k1,...,kn nazywa się jej charakterystyką.

Można algebrę przedstawić jako parę =.



Przykład 3.1.

  • Algebra liczb naturalnych o charakterystyce (2, 2):

+: NNN,

*: NNN


  • Algebra zbiorów <2N, {,,\,-}> o charakterystyce (2, 2, 2, 1)

Podalgebry

Podzbiór A zbioru U jest zamknięty ze względu na działanie

D: Uk  U,

jeżeli dla każdego układu (a1,...,ak) elementów zbioru A wynik działania D(a1,...,ak) jest także elementem podzbioru A.

Takie działanie nazywamy indukowanym przez działanie D i oznaczamy symbolem DA. Stąd mamy DA(a1,...,ak)= D(a1,...,ak).

Jeśli podzbiór A jest zamknięty ze względu na wszystkie działania algebry =1,...,fn>, to algebrę 0=1A,...,fnA> nazywamy podalgebrą algebry .


Zbiory generujące:

  • Niech A0 będzie niepustym podzbiorem U i weźmy rodzinę podzbiorów zbioru U zawierających podzbiór A0 i zamkniętych ze względu na wszystkie działania podstawowe algebry .

  • Rodzina nie jest pusta, ponieważ zawiera co najmniej zbiór U.

  • Przekrój podzbiorów rodziny zawiera podzbiór A0 i jest zamknięty ze względu na działania algebry .

Jest to najmniejsza podalgebra algebry , którą nazywamy algebraicznym domknięciem zbioru A0 w algebrze  i oznaczamy symbolem A0.


Jeżeli A0=, to algebra  jest generowana prze podzbiór A0, a sam podzbiór A0 nazywamy zbiorem generującym algebrę , lub zbiorem generatorów algebry .

Przykład 3.2

  • algebra liczb naturalnych z dodawaniem jest generowana przez zbiór {1}

  • podalgebra liczb naturalnych parzystych jest generowana przez zbiór {2}

  • podalgebra liczb naturalnych większych od 1 jest generowana przez zbiór {2,3}

  • algebra liczb naturalnych z mnożeniem nie jest skończenie generowana, gdyż najmniejszym podzbiorem generującym tę algebrę jest zbiór liczb pierwszych (nieskończony).


Przykład 3.3
Algebra typu int w języku podobnym do C jest zdefiniowana T=(int, +,-,*,/,=,<), gdzie:

int ={-32768,...,0,...,32767}

+ : int int int {error}

  • : int int int {error}

* : int int int {error}

/ : int int int {error}

== : int int int {error}

  • : int int int {error}


Systemem relacyjnym nazywamy krotkę < U1,...,Un, R1,...,Rr , f1,...,fm >,

  • gdzie R1,...,Rr są relacjami w postaci Ri  U1k1...Unkn,

  • oraz f1,...,fm są funkcjami w postaci fi  U1k1...Unkn.

3.2. Abstrakcyjne typy danych
Przykład 3.4
Kolejka: Queue [6]


  1. opis nieformalny operacji kolejki

EMPTY: Inicjowanie pustej kolejki

ADD: Dodanie nowego elementu na końcu kolejki

FRONT: Wskazanie elementu na początku kolejki

REMOVE: Usunięcie elementu z początku kolejki

IS_EMPTY?: Sprawdzenie, czy kolejka jest pusta


  1. syntaktyczny opis operacji kolejki

EMPTY:  Queue

ADD: Queue  Item  Queue

FRONT: Queue  Item

REMOVE: Queue  Queue

IS_EMPTY?: Queue  Boolean


  1. aksjomatyczny opis operacji kolejki

  1. IS_EMPTY? (EMPTY )= true

  2. IS_EMPTY?(ADD(q, i)) = false

  3. FRONT(EMPTY) = error

  4. FRONT(ADD(q,i))= if IS_EMPTY?(q) then i

else FRONT(q)

  1. REMOVE(EMPTY)=error

  2. REMOVE(ADD(q,i))= if IS_EMPTY?(q) then EMPTY

else ADD(REMOVE(q),i)
Uwaga:

Wszelkie operacje na kolejce niezainicjowanej dają w wyniku błąd, czyli: ADD, FRONT, REMOVE, IS_EMPTY?, gdyż operacje na argumentach błędnych są błędne.


Dowód niesprzeczności:
Ponieważ znaczenie operacji jest określone przez zbiór zdań (aksjomatów), specyfikacja jest sprzeczna, jeżeli jakiekolwiek dwa z tych zdań są sprzeczne
Na podstawie (5) i (1) mamy:

IS_EMPTY?(REMOVE(EMPTY)) = IS_EMPTY?(error)

=error

Na podstawie (5) i (2) mamy:



IS_EMPTY?(ADD(REMOVE(EMPTY),i))) =IS_EMPTY?(ADD(error,i))

=IS_EMPTY?(error)

=error

Na podstawie (6) i (1) mamy:



IS_EMPTY?(REMOVE(ADD(EMPTY,i)))= IS_EMPTY?(EMPTY)

=true


Na podstawie (6) i (2) mamy:

IS_EMPTY?(REMOVE(ADD(q,i)))=IS_EMPTY?(ADD(REMOVE(q),i))

=IS_EMPTY?(ADD(EMPTY,i))

=false


Na podstawie (3) i (5) mamy:

FRONT(REMOVE(EMPTY)) =FRONT(error)

=error

Na podstawie (3) i (6) mamy:



FRONT(REMOVE(ADD(EMPTY,i)))=FRONT(EMPTY)

=error


Na podstawie (4) i (6) mamy:

FRONT(REMOVE(ADD(q,i)))=FRONT(ADD(REMOVE(q),i))

=FRONT(ADD(EMPTY,i))

=i

oraz



FRONT(REMOVE(ADD(q,i)))=FRONT(ADD(REMOVE(q),i))

=FRONT(ADD(q1,i))

=FRONT(q1)
Opis jest niesprzeczny.

Przykład 3.5
Vector [6]


  1. opis nieformalny operacji na wektorze elementów

EMPTY: Zainicjowanie wektora pustego

ASSIGN: Przypisanie do zainicjowanego wektora na wybranej pozycji elementu

READ: Pobranie z zainicjowanego wektora elementu z wybranej pozycji

IS_EMPTY?: Sprawdzenie, czy zainicjowany wektor jest pusty




  1. opis syntaktyczny operacji na wektorze elementów

EMPTY:  Vector

ASSIGN: Vector  Index  Item  Vector

READ: Vector  Index  Item

IS_EMPTY?: Vector  Boolean




  1. opis aksjomatyczny operacji wektorze elementów

  1. IS_EMPTY?(EMPTY)=true

  2. IS_EMPTY?(ASSIGN(v,i,a))=false

  3. ASSIGN(v,i,a)=v

  4. READ(ASSIGN(v,i1,a),i2)=if IS_EQUAL? (i1,i2) then a

else READ(v,i2)

Dowód niesprzeczności:
Na podstawie (2) mamy

IS_EMPTY?(ASSIGN(EMPTY,i,a))=false

Na podstawie (1) i (3)

IS_EMPTY?(ASIGN(EMPTY,i,a))=IS_EMPTY?(EMPTY)

= true

czyli false=true, czyli wystąpiła sprzeczność.


Dowód zupełności:

Brak określenia wartości READ(EMPTY,i), czyli:


READ(EMPTY,i)=error
Odpowiednikiem ADT jest system algebraiczny składający się z nośnika i zbioru operacji.

W przypadku typów danych nośnik jest rozkładalny na niejednorodne podzbiory, co znajduje swój odpowiednik w zdefiniowanych algebrach wielorodzajowych (niejednorodnych).


Specyfikacja algebry niejednorodnej T=(V, F) na podstawie [6]

Algebrą wielorodzajową (niejednorodną) nazywamy krotkę 1,...,Vn, f1,...,fm >, gdzie:

  • V jest zbiorem niepustych zbiorów Vi, 1  i  m, zwanych gatunkami (nośnikami)

  • F jest skończonym zbiorem odwzorowań:

fjn: Vi1 k1  Vi2 k2  ...  Vin kn  Vk,

      • gdzie 1 h n Vih  V, Vk V

      • i co najmniej jeden element ze zbioru (Vi1,Vi2,...,Vin, Vk} jest wyróżnionym gatunkiem, nazywany interesującym nas typem INT

        • k1,...,kncharakterystykami algebry i są liczbami naturalnymi



Przykład 3.6

Dla typu QUENE mamy:



  • F={EMPTY, ADD, FRONT, REMOVE, IS_EMPTY?}, m=3

  • V zawiera {...,-2,-1,0,1,2,...} oraz {true, false} oraz INT, który nie spełnia roli nośnika, lecz generatora jako zbioru pustego. Stąd mamy:

V={{...,-2,-1,0,1,2,...} , {true, false} , {}}
W przypadku algebry niejednorodnej każdy gatunek jest niepusty, stąd musi istnieć co najmniej jeden operator

fjn: Vi1  Vi2  ...  VinINT,



  • gdzie każdy Vix  V-INT

  • oraz I=V-INT jest zbiorem gatunków.

Zbiór operacji F można podzielić na dwa rozłączne zbiory S i O operacji:



  • S   zawiera te i tylko te operacje ze zbioru F, których przeciwdziedziną jest zbiór INT

  • O  jest zbiorem pozostałych operacji.

Stąd definiowany typ jest algebrą

T= (CI(I), S  O),

gdzie CI(I) jest domknięciem przechodnim zbioru I względem operacji należących do SO.

Operacje w zbiorze O są postaci:

fjn: Vi1  Vi2  ...  Vin  Vk, gdzie każdy Vix  I  INT, 1xn, Vk  I
Semantyka typu jest określona funkcją częściową:

Me: O (IINT)p  Vi  I,

gdzie p jest największą liczbą argumentów funkcji ze zbioru O.
Dla wszystkich fO i w(IINT)p, Me(F,w)= error, jeżeli w nie jest zawarte w dziedzinie F, zaś Me(F,w)=y, gdzie yVi dla pewnego Vi  I, jeżeli w jest w dziedzinie F.
Stąd mamy algebrę typu Queue:


  • T=(CI(Integer,Boolean),{EMPTY,ADD,REMOVE}{FRONT,IS_EMPTY?})

  • oraz aksjomat wewnętrzny Me:

(fjn, x1,...,xn)(xi = error  1 i  n)  Me(fjn, x1,...,xn) =error
Opis uważamy za niewystarczający, gdy żadna kombinacja zdań nie wyczerpuje całości ważnych informacji dotyczących znaczenia operacji na typie.
Problem zupełności algebry typów jest nierozstrzygalny, jednak gdy jest ograniczony do

  • kwantyfikatorów ogólnych,

  • równości

  • i konstrukcji if..else,

to możliwe jest sformułowanie warunków wystarczających, gwarantujących wystarczającą zupełność aksjomatyzacji.
Zbiory I oraz SO algebry typu T definiują algebrę słów L(T).

Mając aksjomatyzację A, mówimy że A jest wystarczająco zupełna wtedy i tylko wtedy, gdy dla każdego słowa fjn(x1 ,..., xn ) zawartego w L(T), gdzie fjn 0, istnieje wyprowadzalne z A twierdzenie postaci fjn(x1 ,..., xn )=u, gdzie uViI


3.3. Dodatek

3.3.1. Elementy języka C++ wspomagające abstrakcję danych
Pojęcia podstawowe:

  1. Deklaracje będące definicjami mogą wystąpić tylko raz programie:

opis typu strukturalnego (struct, union), wyliczeniowego(enum), definicja

ciała funkcji itp

np.

struct KSIAZKA

{char autor[MAXNAZ];

char tytul[MAXNAZ];

int cena;

};

union A

{double z;

int x;

void (*a) ();

void (*b) (char *s);

};

enum kolory {R, G, B};



int suma(int a, int b) { return a+b;}

2) Definicje mogą wystąpić tylko raz w programie:

tworzenie zmiennych:



  • lokalnych (w klasie pamięci automatycznej, przydzielonej blokowi),

  • zewnętrznych, istniejących przez czas działania programu (w klasie pamięci statycznej),

  • lokalnych statycznych (static), istniejących przez czas działania programu (w klasie pamięci statycznej), lecz dostępnych w bloku funkcji

np. int liczba;

extern const stala = 100;

static float ulamek;

3) Deklaracje, które nie są definicjami, mogą wystąpić w programie wielokrotnie:

gdy nie wywołuje się funkcji ani nie pobiera się jej adresu itp

np. extern int a;

extern const stala;

int suma (int, int);

struct KSIAZKA;

typedef union A unia_A;

3.3.2. Paradygmaty programowania (wg B. Stroustrup . Język C++)
1) Programowanie proceduralne

Zadecyduj, jakie chcesz mieć procedury; stosuj najlepsze algorytmy, jakie możesz znaleźć.

Wspomaganie paradygmatu:



  • mechanizm przekazywania argumentów do funkcji i wyników z funkcji

  • zasięg obowiązywania zmiennych:

lokalny:

Nazwa zadeklarowana w bloku jest lokalna dla tego bloku, stąd można jej używać tylko w tym bloku i wewnątrz bloków w niej zawartych, począwszy od miejsca deklaracji. Nazwy argumentów funkcji należą do najbardziej zewnętrznego bloku w tej funkcji.



funkcji:

Etykiet można używać jedynie wewnątrz funkcji, w której zostały zadeklarowane (etykiety instrukcji goto)



pliku:

Dla nazwy, zadeklarowanej na zewnątrz wszystkich bloków zasięgiem jest plik. Są to nazwy globalne.

Oprogramowanie w realizacji jednoplikowej ogranicza się do jednokrotnego zastosowania w ograniczonym obszarze zastosowań.
2) Programowanie modularne + abstrakcja danych

Zadecyduj, jakie chcesz mieć moduły; podziel program w taki sposób, aby ukryć informację w modułach + zadecyduj, jakie chcesz mieć typy; dla każdego dostarcz pełny zbiór operacji.

Zasady abstrakcji i ukrywania informacji:

programowanie modularne umożliwia abstrakcję danych, ale jej nie wymusza

wszystkie operacje na danych statycznych lub niestatycznych wykonywane są jedynie za pośrednictwem funkcji stanowiący zbiór pełny operacji wzajemnie niesprzecznych:

programowanie modularne wspiera ukrywanie danych

dane typu static w plikach modułowych (ogranicza dane do jednego lub kilku egzemplarzy umieszczonych w plikach modułowych, dostępnych jedynie przez funkcje niestatyczne, wywoływane poza plikiem modułowym np. w pliku z funkcją main)

programowanie modularne wspiera ukrywanie funkcji

funkcje typu static w plikach modułowych (ukrywanie funkcji o charakterze pomocniczym w plikach modułowych, dostępnych pośrednio przez funkcje modułowe niestatyczne)


3) Programowanie obiektowe + abstrakcja danych

Zadecyduj, jakie chcesz mieć klasy; dla każdej klasy dostarcz pełny zbiór operacji; korzystając z mechanizmu dziedziczenia, jawnie wskaż to, co jest wspólne

  • ustalenie wspólnej części wspomaganej dziedziczeniem i polimorfizmem - brak tej części ogranicza korzyści z zastosowania programowania obiektowego

 w przypadku braku części wspólnej wystarcza abstrakcja danych (stosowanie klas bez dziedziczenia i polimorfizmu)

3.3.3. Pliki nagłówkowe
Pliki nagłówkowe powinny zawierać:

  • stałe jawne #define TRUE 1

  • funkcje makra #define MAX(x, y) ((x) > (y) ? (x) : (y))

  • dyrektywy #include

  • prototypy funkcji np. void wyswietl_float(float);

  • deklaracje definicyjne typów np.

class punkt

{ float x, y;



public: punkt (float, float);

void przesun (float, float);

};


  • definicje stałych const int max = 3;

  • definicje funkcji typu inline

inline int Większy(int x, int y) {return x > y; }

  • deklaracje nazw struct kolo;

  • deklaracje zmiennych extern int zmienna;

  • wyliczenia enum Boolean {False, True};

  • szablony funkcji i klas template

class stos { // ..........}
Uwaga:
Nie należy nigdy wstawiać do pliku nagłówkowego:


  1. definicji zwykłych funkcji: int Większy(int x, int y) {return x > y; }

  2. definicji zmiennych: int zmienna;

  3. definicji stałych agregatów (tablica, obiekt bez konstruktorów, składowych prywatnych i chronionych, klas podstawowych i funkcji wirtualnych): const char tab[] =”aaa”;

3.3.4. Programy wieloplikowe

Dyrektywy preprocesora i kompilacja wieloplikowa (projekty)
Polecenia dla preprocesora:


  1. Dyrektywa #include oznacza dołączenie w miejscu wystąpienia polecenia standardowego pliku nagłówkowego z deklaracjami typów, funkcji itp, natomiast #include ”tablica1.h” dołączenie pliku nagłówkowego użytkownika




  1. Klauzula #define nazwa oznacza makrodefinicję, #undef nazwa unieważnia makrodefinicję




  1. Polecenia kompilacji warunkowej pozwalają na kompilację tylko jednej z sekcji instrukcji:


#if wyrażenie1

sekcja _instrukcji1

#elif wyrażenie2

sekcja _instrukcji2

....


#else

końcowa_sekcja_instrukcji

#endif
4) Polecenia warunkowej kompilacji uniemożliwiają wielokrotnego dołączania tego samego pliku nagłówkowego, lub jego fragmentu podczas kompilacji wieloplikowej:
#ifndef nazwa

#define nazwa

deklaracje //deklaracje czyta kompilator tylko raz, podczas definiowania makro nazwa

#endif,
#ifdef nazwa

deklaracje //kompilator czyta te deklaracje, gdy zdefiniowano makro nazwa

#endif

Schemat podziału programu na wiele plików

  • W
    czasie kompilacji i tworzenia pliku kolejka.obj zawartość pliku nagłówkowego strukt.h pojawi się dwukrotnie i wywoła błąd kompilacji wynikający z dwukrotnej definicji typu struct OSOBA. Plik ten należy więc objąć kompilacją warunkową.




  • W przypadku łączenia plików dodatki.obj oraz kolejka.obj, gdyby istniała definicja funkcji f oraz zmiennej z - wystąpi błąd w wyniku wystąpienia dwukrotnie definicji funkcji f oraz zmiennej z (w pliku dodatki.obj i w pliku kolejka.obj)



Tworzenie projektu umożliwiającego kompilację oraz łączenia plików (np. tworzenie programu z p. 4.1, wykład 4)


  1. Należy uruchomić Borland C++ i wybrać opcję Open Project z menu Project. Należy wpisać nazwę pliku projektowego w polu Open Project File z rozszerzeniem PRJ, np. kolejka.prj. Nazwa nadana plikowi PRJ będzie nadana programowi wynikowemu EXE czyli kolejka.exe. Po nadaniu nazwy należy nacisnąć klawisz ENTER. U dołu ekranu pojawi się okno o nazwie Project :  KOLEJKA




  1. Aby dodać pliki do projektu należy nacisnąć klawisz INSERT lub wybrać opcję Add Item z menu Project. Pojawi się okno o nazwie Add to Project List. W polu Name należy wpisać nazwy plików (przez wybór z listy), które należy dodać do projektu (w przykładzie pliki mkolejka.cpp, dodatki.cpp, we_wy.cpp oraz kolejka.cpp). Nie należy dodawać plików nagłówkowych. Po zakończeniu należy nacisnąć przycisk Done w oknie Add to Project List.




  1. Aby skompilować i połączyć pliki źródłowe podane w projekcie, należy wybrać opcję Make z menu Compile lub nacisnąć klawisz F9. Nastąpi kompilacja i utworzenie plików OBJ, a następnie połączenie tych plików i utworzenie programu wynikowego kolejka.exe. Można również uruchomić program w środowisku za pomocą polecenia Run z menu Run lub gotowego programu kolejka.exe na poziomie systemu operacyjnego.





Zofia Kruczkiewicz, Języki programowania 1, Wykład 3





©operacji.org 2019
wyślij wiadomość

    Strona główna