Texte pagina webAnaliza si sinteza sistemelor numerice -

Fac: Automatica si calculatoare

Analiza si sinteza sistemelor

numerice

-proiect-

Profesor ASDN:

1.Tema proiectului

Generarea partitiilor inchise pentru un automat cu cel putin 17 stari.

2.Introducere

Automatul este caracterizat printru-un tabel ca cel ce urmeaza:

-Xn se va citi intrarea pt. tactul n

-S(n) sunt starile in care se poate afla automatul la un moment dat

-in tabel sunt reprezentate tranzitiile intre starile

in care se afla automatul in fn. de intrare(0,1)

-partitiile sunt formate din blocuri de stari

-un bloc este alcatuit dintr-o multime de stari care pt.

o anumita intrare nu efectueaza tranzitii divergente, toate starile unui bloc pt. un x dat fac tranzitie in acel bloc

-prin identificarea unei variabile de stare cu blocuri ale unor partitii inchise obtinem dependente simplificate pt. aceste variabile de stare

3.Prezentare pe scurt

Functiile folosite in acest program sunt:

int **matrice(int l, int c) //aloca spatiu pt. un tablou

void free_matrice(int **a) //elibereaza spatiul

void citire(int *n,int ***tabel)// citeste din fisier

void scrie(Multime& m)//scrie in fisier

void pas1(int n, int **tablou, Multime& solutie)//ef.    pasul_1 din algoritmul de generare

void pas_k(Multime& solutie)//ef. pasii 1..

void sol_imd(int n, Multime& solutie) //obtine partitiile eterne

o functie principala:

void main(void)

in aceste functii apar apeluri ale altor functii definite in intr-o biblioteca 'multime.h'

proiectul contine listingul programului principal si al

bilotecii de functii folosite

4.Prezentare in detaliu al proiectului

In primul rind prezentarea algoritmului:

pas1. Pornind de la toate perechile distincte de stari se urmaresc tranzitiile autonome si se cauta partitiile inchise, in acest pas partitiile gasite se numesc partitii inchise fundamentale

pas2. Prin adunarea partitiilor inchise fundamentale in toate modurile se calculeaza noi partitii inchise.

In pasii urmatori se aduna la fel partitiile pina cand la un moment nu se vor mai obtine partitii inchise noi.

#2.Elaborarea programului:

Datele se citesc dintr-un fisier cu urmatoarea structura

-pe prima linie numarul de stari ale automatului

-urmatoarele linii corespund fiecare cate unei stari a automatului si contin cate 2 numere intregi reprezentand numerele identificand starile urmatoare starii respective pentru cazul cand la intrare se aplica 0 respectiv 1

Se foloseste POO, solutia finala, partitiile, blocurile din partitii toate sunt

obiecte de tipul 'Multime'

Starea este definita tot clasa derivata din clasa 'Obiect' care este o clasa generica pura neputind fi folosita decat doar pentru mostenire de la ea

-locarea acestor obiecte este dinamica, se lucreaza doar cu pointeri si referinte

-clasa 'Multime' este derivata din clasa generica 'Obiect'

-multimea este implementata ca o lista dublu inlantuita care are cimpul info un pointer catre un obiect din clasa 'Obiect"

#3.Explicarea functiilor din program

prototipul    int **matrice(int l, int c)

-functia 'matrice()' aloca memorie pentru o matrice de intregi de dimensiune lxc si intoarce adresa zonei de memorie alocata in aceasta zona de memorie se va memora tabloul tranzitiilor

prototipul void free_matrice(int **a)

Functia free_matrice() elibereaza memoria alocata cu 'matrice'.Primeste ca parametru pointerul catre zona de memorie ce trebuie eliberata

prototipul void citire(int *n,int ***tabel)

Functia citire() citeste dintr-un fisier al carui nume este introdus de la tastatura , numarul de stari ale automatului (*n) precum si tabloul de stari (***tabel) al automatului. (variabila tablou este un pointer la adresa de

memorie alocata cu functia matrice())

Formatul fisierului cu date de intrare este urmatorul:

-pe prima linie numarul de stari ale automatului

-urmatoarele linii corespund fiecare cate unei stari a automatului si contin cate 2 numere intregi reprezentand numerele identificand starile urmatoare starii respective pentru cazul cand la intrare se aplica 0 respectiv 1.

Obs: Numerotarea starilor incepe de la 0.

prototipul void scrie(Multime& m)

Functia scrie() scrie, intr-un fisier al carui nume este introdus de la tastatura, solutia problemei, adica partitiile inchise pe multimea starilor automatului cate o partitie pe linie.Blocurile partitiilor sunt incadrate intre acolade, iar starile blocurilor sunt despartite prin spatiu.

Aceasta functie este folosita pentru scrierea solutii intr-un fisier, deci

m este un pointer catre multimea solutiilor.

prototipul void tranzitie(int **tablou, int intr, Multime *bloc,Multime *rezultat)

Fn. tranzitie() pune intr-o anumita zona a memoriei(rezultat) multimea de stari in care se trece in fn. de intrare si multimea de stari initiale (var bloc).

Variabila 'tablou' este un pointer la matricea tranzitiilor.

prototipul void pas1(int n, int **tablou, Multime& solutie)

Aceasta functie este cea mai importanta a proiectului si are algoritmul cel

mai complex.

Fn. pas1() determina multimea partitiilor inchise fundamentale.

Primeste ca parametri: numarul de stari (n), tabloul de tranzitii (tablou)

si multimea in care va depune partitiile gasite (transmisa fn. ca referinta).

Pornind da la toate perechile distincte de stari se urmaresc tranzitiile

autonome si se cauta partiriile inchise(partitii inchise fundamentale).

Pentru intelegerea acestei functii tb. parcurs textul sursa al programului.

prototip void pas_k(Multime& solutie)

Prin adunarea in toate modurile posibile a partitiilor inchise

se obtin noi partitii inchise.

Algoritmul de adunare a doua partitii este

PI1=

PI1+PI2    se porneste cu primul bloc PI1 care este intersectat cu primul

bloc din PI2.Daca intersectia este <diferita de multimea vida, atunci

se efectueaza reuniunea celor doua blocuri, acest bloc va fi primul

bloc al partitiei suma

prototip void sol_imd(Multime& solutie)

Functia 'sol_imd' introduce in multimea solutiilor partitiile PI(0)

si PI(1). Aceste partitii fiind partitii evidente PI(0) este partitia

in care exista o echivalenta intre blocuri si starile automatului

PI(0)= }, PI(1)este partitia cu un singur

bloc =s1..sn PI(1)=}

5.Concluzii

Programul in sine ar fi trebuit sa fie mai lizibil si mai i usor de inteles, mai ales algoritmul functiei pas1(). Poate ar fi trebuit implementat fara OOP.

Interfata cu utilizatorul ar fi putut fi mai prietenoasa nu doar cateva mesaje scurte.Iar afisarea rezultatul adica a partitiilor cu blocuri si stari este destul de deficitara si destul de greu urmarit.Se mai putea lucra.