CATEGORII DOCUMENTE |
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:
S(n) |
Xn |
|
S0 |
S1 |
S0 |
S1 |
S0 |
S3 |
S2 |
S4 |
S2 |
S3 |
S4 |
S0 |
S4 |
S0 |
S3 |
-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.
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1281
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved