Probleme pentru examenul de licenţă - INFORMATICĂ Introducere în programarea calculatoarelor / Tehnici de programare 1. Daţi o soluţie recursivă, în limbajul de programare C, pentru Algoritmul lui Euclid de aflare a celui mai mare divizor comun a două numere întregi. Formularea în cuvinte a algoritmului este următoarea: Dacă unul dintre numere este zero, c.m.m.d.c. al lor este celălalt număr. Dacă nici unul dintre numere nu este zero, atunci c.m.m.d.c. nu se modifică dacă se înlocuieşte unul dintre numere cu restul împărţirii sale cu celălalt. Răspuns: int cmmdc(int m, int n) { int r; r=m % n; while (r != 0) { m=n; n=r; r=m % n; } return n; } 2. Să se scrie o funcţie care inversează conţinutul unui şir de caractere; şirul iniţial va fi returnat ca rezultat al apelului funcţiei. Se vor folosi operaţii cu pointeri. Răspuns: char *strrev (char *sir) { char *initial = sir; char *urmator = sir; char temp; while (*sir) sir++; while (urmator < sir) { temp = *(--sir); *sir = *urmator; *urmator++ = temp; } return (initial); }
Transcript
Probleme pentru examenul de licenţă - INFORMATICĂ
Introducere în programarea calculatoarelor / Tehnici de programare
1. Daţi o soluţie recursivă, în limbajul de programare C, pentru Algoritmul lui Euclid de aflare a celui mai mare divizor comun a două numere întregi. Formularea în cuvinte a algoritmului este următoarea: Dacă unul dintre numere este zero, c.m.m.d.c. al lor este celălalt număr. Dacă nici unul dintre numere nu este zero, atunci c.m.m.d.c. nu se modifică dacă se înlocuieşte unul dintre numere cu restul împărţirii sale cu celălalt.
Răspuns: int cmmdc(int m, int n) {
int r; r=m % n; while (r != 0) {
m=n; n=r; r=m % n;
} return n;
}
2. Să se scrie o funcţie care inversează conţinutul unui şir de caractere; şirul iniţial va fi returnat ca rezultat al apelului funcţiei. Se vor folosi operaţii cu pointeri.
Răspuns:
char *strrev (char *sir) {
char *initial = sir; char *urmator = sir; char temp; while (*sir) sir++; while (urmator < sir) {
Sa se implementeze funcţia care ordonează alfbetic după nume, folosind sortarea prin selectie, un tablou de articole de tip A2 (de dimensiune 10) .Prototipul funcţiei este:
void ordonare_selectie(A2 tablou[]); Obs: Se va folosi limbajul de programare C.
NumeProdus Producator Defect NrPieseInlocuite PieseInlocuite NumeProdus-sir de 9caractere Producator-sir de 9 caractere Defect-sir de 9 caractere NrPieseInlocuite -int PieseInlocuite -tablou siruri de caractere, maxim 10 siruri de 9 caractere Să se definească următoarele TDA-uri:
A1-articol cu câmpurile : Prod,TipDefect, NrPieseInloc, PieseInloc; A2- articol cu câmpurile : NumeProd, inf(A1); Să se implementeze funcţia ce caută un produs într-un tablou de articole de tip A2 (de dimensiune 10) folosind tehnica fanionului. .Prototipul funcţiei este:
void Tehnica_Fanion(A2 tablou[], char*nume); Obs: Se va folosi limbajul de programare C.
(15minute)
Rezolvare: #include <string.h> …… #define N 11 typedef struct{ char Prod[10]; char TipDefect[10]; int NrPieseInloc; char PieseInloc[10][10]; }A1; typedef struct{
char NumeProd[10]; A1 Inf; }A2; void Tehnica_Fanion(A2 tablou[], char*nume){ int i=0; int n=strlen(nume); if (n<=9){ strcpy(tablou[N-1].NumeProd, nume); while(strcmp(tablou[i].NumeProd, nume)!=0) i++; if(i<N-1)printf("Produsul cautat se afla pe pozitia %d",i); else printf("Elementul nu a fost gasit"); } else{ printf(“\n Sirul are mai mult de 9 caractere”); exit (1); } }
Arhitectura calculatoarelor
Sisteme de operare
1: Realizaţi un program în C ce funcţionează pe baza următorului scenariu: Un proces P afişeaza cifre de la 0 la 9. Va începe afişarea cu cifra 0 (cifra va fi afişată în buclă de câte ori e posibil într-o secundă) iar la fiecare secundă va incrementa cifra afişată. Procesul de afişare se va încheia când se ajunge la 10 şi va afişa numărul total de cifre tipărite.
2: Realizaţi un program C ce funcţionează pe baza următorului scenariu: Un proces părinte P şi un proces fiu F. Procesul P va citi un fişier primit ca şi argument şi îl va trimite printr-un pipe procesului F. F va număra caracterele primite într-un contor pe care îl va afisa în terminal.
Rezolvare: #include<stdio.h> #include<string.h> #include<unistd.h> #include<fcntl.h> int main(int argc, char**argv){ int ppf[2];//pipes int fd;//file descriptor char buffer[2]; pipe(ppf); if(fork()){ //close unused pipe ends
close(ppf[0]); //open file fd = open(argv[1], O_RDONLY); if(fd == -1){ perror("File read error"); _exit(1); } int n; while((n = read(fd,buffer, strlen(buffer)+1)) != 0){ write(ppf[1], buffer, n); } close(ppf[1]); int rc; wait(&rc); }else{ //close pipe ends close(ppf[1]); int contor = 0,n; while((n = read(ppf[0],buffer, strlen(buffer)+1)) != 0){ contor += n; } printf("\nContor:%d\n",contor); } return 0; } 3: Realizaţi un program shell script ce va primi ca şi argument un nume de director D şi un cuvânt C. Programul va căuta cuvântul C parcurgând recursiv directorul D iar pentru fiecare fişier întâlnit care conţine cuvântul C va afişa calea relativă a acestuia.
Rezolvare: #!/bin/sh word=$2 lst(){ for i in $1/* do if [ -d $i ] then lst $i elif [ -f $i ] then count=`grep $word $i | wc -l` if [ $count -gt 0 ] then echo $i fi fi done } lst $1
Programare orientată pe obiecte
1. Într-o aplicaţie de conducere de proces se utilizează senzori de tip analogic şi optic. Toţi senzorii trebuie resetaţi şi calibraţi, respectiv periodic citiţi. Citirea presupune şi filtrare folosind valoarea anterioară citită, dar metodele de filtrare sunt diferite pentru senzori de tip diferit. Toate valorile citite sunt întregi. Fiecare operaţie de citire este specifică senzorului respectiv, resetarea este comună tuturor tipurilor de senzori iar calibarea este diferită pentru senzorii analogici şi optici. Senzorii permit şi o operaţie identică de interogare a stării. Senzorii optici mai necesită o operaţie specifică de aducere la zero, alta decât reset, iar senzorii analogici necesită o operaţie specifică de selectare a canalului.
Proiectaţi o ierarhie de clase (se cer doar declaraţiile, nu şi implementările) care să modeleze fragmentul corespunzător de realitate, în cadrul aplicaţiei software de conducere de proces. Sugeraţi care vor fi metodele publice şi unde vor fi folosite acele funcţii care nu sunt publice. Comentati fiecare variabilă şi fiecare funcţie membră. R. class senzor{ int status; // starea protected: int val_citita; // valoarea citita (va fi setata de citire) int val_anterioara; // valoarea anterioara va fi transferata din val_citita // in timpul apelului metodei de citire int val_filtrata; // valoarea prelucrata prin filtrare (va fi returnata de get) virtual int filtru()=0; public: virtual void calibrare()=0; // calibrarea este o functie virtuala pura virtual void citire()=0; // citirea este si ea o functie virtuala pura void reset(); // operatia de reset int status(); // returneaza starea int get(); // returneaza valoarea filtrata }; class senzor_analog public: senzor { // clasa specializata pentru senzori analogici int filtru(); // functia de filtrare nu va fi accesata de afara public: void calibrare(); // calibrarea specifica senzorului analogic void citire(); // aici se va apela si filtrul specific void select_canal(int ); // extensie pentru selectia canalului analogic }; class senzor_optic public: senzor { int filtru(); public: void calibrare(); // calibrarea specifica senzorului optic void citire(); // aici se va apela si filtrul specific void zero(); // extensie pentru operatia specifica de aducere la zero }; 2. Valorile citite într-un sistem de monitorizare trebuie stocate într-o stivă. Creaţi pentru aceasta o stivă cu alocare dinamică care să funcționeze (incremental) astfel: dacă se atinge dimensiunea curentă a stivei, se alocă memorie pentru ca să poată stoca stiva existentă și încă câteva valori și se copiază stiva în noua zonă de memorie, eliberând apoi vechea zonă.
R: class CStack { int *m_p; // stiva propriu-zisa va fi aici
int m_nStored; // indicator varf stiva int m_nDepth; // dimensiunea temporara a stivei enum {GROW_BY=5}; // pasul de crestere a stivei public: CStack( ); // constructor virtual ~CStack(); // destructor int IsEmpty() const; // test stiva goala void Push(const int &item); // introducere in stiva int Pop(); // extragere din stiva }; // Constructori CStack::CStack() { m_p=0; m_nStored=0; m_nDepth=0; } CStack::~ CStack() { delete []m_p; } // Operatii int CStack::IsEmpty() const { return m_nStored==0; } void CStack::Push(const int &item) { if(m_nStored==m_nDepth) // stiva alocata s-a terminat {
Int *p=new int[m_nDepth+GROW_BY]; // trebuie una mai mare for (int i = 0; i<m_nDepth; i++) // stiva se replica in cea noua { p[i]=m_p[i]; } m_nDepth+=GROW_BY; // dimensiunea temporara creste delete [ ]m_p; // stiva anterioara este eliberata m_p=p;
} m_p[m_nStored]=item; // introducerea in stiva m_nStored ++; // si avansul indicatorului de varf stiva } int CStack::Pop( ) { m_nStored--; // indicatorul de varf al stivei merge inapoi return m_p[m_nStored]; // scoaterea din stiva } … CStack stivaMea; // utilizare
3. Prezentaţi declararea clasei/claselor care permit implementarea unei liste înlănţuite, pentru stocarea unor informaţii despre variabile citite de senzori. Acestea cuprind: denumirea variabilei de proces, valoarea sa întreagă şi valoarea sa prelucrată. Valoarea întreagă se setează la citirea de către senzor. Valoarea prelucrată este de tip double, se obţine prin apelarea unei metode de procesare şi trebuie furnizată în exterior prin apelul unei metode.
R: (una din solutiile simple) class var_proc{ // un nod stocheaza date specifice unei citiri si valoarea procesata // pentru lista inlantuita static var_proc *cap; // capul listei var_proc *urm; // pointer catre urmatorul element din lista // mai departe, valorile stocate in nod char *denumire; // denumirea int val; // valoarea citita double val_proc; // valoarea prelucrata // metode private double procesare(); // metoda nu trebuie apelata de afara public: var_proc(char* ); // constructor care va apela si functia de citire a senzorului virtual int citire(); // citirea va trebui redefinita la implementarea concreta (in // cadrul unei clase derivate var_proc_concreta double getval(); // aici va fi apelata si procesarea, se va seta val_proc si // valoarea este furnizata apelantului }; var_proc *var_proc::cap=NULL;
Analiza algoritmilor
1. Se cere să se implementeze tipul de date abstract Arbore Binar Ordonat. În acest scop se cere:
1. Să se definească o structură de date care defineşte în manieră recursivă structura Arbore Binar Ordonat;
2. Să se implementeze pe această structurră, în forma unor funcţii C operatorii Caută, Inserează şi Suprimă definiţi peste TDA Arbore Binar Ordonat;
3. Să se dezvolte operatorul Inordine, care să afişeze cheile unui Arbore Binar Ordonat în inordine.
R1: typedef int T_cheie; typedef void (*T_prelucrare)(T_cheie); void Initializare(T_arbore *A); int ArboreVid(T_arbore A); int Cauta(T_arbore A, T_cheie k); T_arbore Insereaza(T_arbore A, T_cheie k); T_arbore Suprima(T_arbore A, T_cheie k); void Preordine(T_arbore A, T_prelucrare f); void Inordine(T_arbore A, T_prelucrare f); void Postordine(T_arbore A, T_prelucrare f); [1] typedef struct nod T_nod; /* tipul nodurilor */ typedef T_nod *T_arbore; /* tipul arbore binar ordonat */ struct nod { T_cheie ch; /* cheia unica per nod */ T_nod *st; /* pointer subarbore stang */ T_nod *dr; /* pointer subarbore drept */ }; [2] int Cauta(T_arbore p, T_cheie k) { int gasit = 0; while (p) { if (k < p->ch) p = p->st; else if (p->ch < k) p = p->dr; else { gasit = 1; break; } } return gasit; } T_nod* alocaNod(T_cheie k)
{ T_nod *p = malloc(sizeof(T_nod)); p->st = p->dr = NULL; p->ch = k; return p; } T_arbore Insereaza(T_arbore p, T_cheie k) { if (!p) p = alocaNod(k); else if (k < p->ch) p->st = Insereaza(p->st, k); else if (p->ch < k) p->dr = Insereaza(p->dr, k); return p; } T_nod *supred(T_nod **p) { T_nod *q; while (q = *p, q->dr) p = &q->dr; *p = q->st; return q; } T_arbore Suprima(T_arbore p, T_cheie k) { if (!p) return NULL; if (k < p->ch) p->st = Suprima(p->st, k); else if (p->ch < k) p->dr = Suprima(p->dr, k); else { T_nod *q = p; if (!p->st) p = p->dr; else if (!p->dr) p = p->st; else { q = supred(&p->st); p->ch = q->ch; } free(q); } return p; } [3] void Inordine(T_arbore p, T_prelucrare f) { if (!p) return; inordine(p->st);
(*f)(p->ch); inordine(p->dr); } static void afisNod(int k) { printf(“%-8d”, *k); /* maxim de ordinul sutelor de mii */ } int main() { T_arbore rad; Initializare(&rad); /* . . . */ Inordine(rad, &afisNod); return 0; } 2. Se cere să se redacteze o aplicaţie care realizează următoarele activităţi:
1. Defineşte structura de date aferentă unui graf; 2. Implementează operatorii CautăNod, InserNod, SuprimaNod, InserArc,
SuprimArc, Crează, Afişează, TraversareInAdancime; 3. Acceptă la intrare un graf precizat prin mulţimea nodurilor şi arcelor sale; 4. Crează graful; 5. Listează nodurile în ordinea parcurgerii lor pe baza căutării în adâncime.
R2: #include <stdio.h> #include <stdlib.h> #define VAR * #define REF & #define BUF while(fgetc(file) != ‘\n’) typedef void (*T_traversare)(char); [1] #define MAX 100 typedef int MatrAdj[MAX][MAX]; typedef struct graf T_graf; struct graf { int contor; /* contorul nodurilor */ char nume[MAX]; /* numele nodurilor (litera) */ MatrAdj madj; /* matricea de adiacenta */ int marc[MAX]; /* tabloul vizitat */ }; [2] void Initializare(T_graf VAR graf) { graf->contor = 0; }
int CautaNod(T_graf *graf, char nume) { int i, n = graf->contor; for (i = 0; i < n; ++i) if (graf->nume[i] == nume) break; return i; } void InserNod(T_graf VAR graf, char nume) { int i = CautaNod(graf, nume), n = graf->contor; if ((i < n || n >= MAX)) return; graf->nume[n] = nume; for (i = 0; i <= n; ++i) { graf->madj[i][n] = 0; graf->madj[n][i] = 0; } ++graf->contor; } void SuprimNod(T_graf VAR graf, char nume) { int i = CautaNod(graf, nume), j, n = graf->contor; if (i == n) return; n = --graf->contor; for (j = 0; j < n; ++j) { graf->madj[i][j] = graf->madj[n][j]; graf->madj[j][i] = graf->madj[j][n]; } } void InserArc(T_graf VAR graf, char nod1, char nod2) { int i = CautaNod(graf, nod1), j = CautaNod(graf, nod2), n = graf->contor; if (i == n || j == n) return; graf->madj[i][j] = 1; } void SuprimArc(T_graf VAR graf, char nod1, char nod2) { int i = CautaNod(graf, nod1), j = CautaNod(graf, nod2), n = graf->contor; if (i == n || j == n) return; graf->madj[i][j] = 0; } void adancime(T_graf g, T_traversare f, int i) { int j, n = g.contor; g.marc[i] = 1; (*f)(g.nume[i]); for (j = 0; j < n; ++j)
if (!g.marc[j] && g.madj[i][j]) adancime(g, f, j); } void TraversareInAdancime(T_graf graf, T_traversare func) { int i, n = graf.contor; for (i = 0; i < n; ++i) graf.marc[i] = 0; for (i = 0; i < n; ++i) if (!graf.marc[i]) adancime(graf, func, i); } void Creaza(FILE* file, T_graf VAR graf) { int i, n; if (file == NULL) return; fscanf(file, “%d”, &n); BUF; for (i = 0; i < n; ++i) { InserNod(graf, fgetc(file)); BUF; } while (!feof(file)) { char nod1, nod2; nod1 = fgetc(file); BUF; nod2 = fgetc(file); BUF; InserArc(graf, nod1, nod2); } } static void afisareNod(char nume) { printf(“%c\n”, nume); } void Afiseaza(T_graf graf) { TraversareInAdancime(graf, &afisareNod); } int main() { T_graf g; char f[] = “?.txt”; Initializare(graf); puts(“Nume fisier text: ”); f[0] = getchar(); Creaza((f[0] == ‘\n’) ? stdin : fopen(f, “rt”), REF g); Afiseaza(g); return 0; }
3. Se consideră o structură graf orientat ponderat. Se cere:
1. Să se descrie o structură de graf orientat ponderat. 2. Să se implementeze procedura care determină lungimile drumurilor minime între toate
perechile de noduri ale grafului. 3. Să se implementeze procedura care determină traseul drumului de lungime minimă între
două noduri precizate ala grafului. Indicaţie: În implementare se va utiliza algoritmul FLOYD. R3: [1] #define INF 1000 #define MAX 100 struct graf { int contor; /* numarul de noduri */ float COST[MAX][MAX]; /* matrice costuri arce (lipsa=INF) */ }; [2] float A[MAX][MAX]; /* mattrice lungim drumuri minime */ int Drum[MAX][MAX]; /* reconstituire traseu */ void FLOYD(struct graf *Graf) { int i, j, k, n = Graf->contor; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) { A[i][j] = Graf->COST[i][j]; Drum[i][j] = 0; } for (i = 0; i < n; ++i) A[i][i] = 0; for (k = 0; k < n; ++k) for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) if (A[i][k] + A[k][j] < A[i][j]) { A[i][j] = A[i][k] + A[k][j]; Drum[i][j] = k; } } [3] void Traseu(int i, int j) { int k = Drum[i][j]; if (k != 0) { Traseu(i, k); printf(“%d\n”, k) Traseu(k, j); } }
Proiectarea microsistemelor digitale
1. Prezentați schema pentru o interfață serială de tip RS 232 . 2. Prezentați schema pentru o interfață paralelă de tip CENTRONIX. 3. Prezentați schema pentru conectarea a 64 led‐uri la o unitate centrală cu microprocesorul
8086. R:
1. Schema este alcătuită din un decodificator de porturi, un circuit specializat 8251 şi un circuit
MAX 232 pentru translatarea nivelelor de tensiune din TTL în EIA şi invers. Oricare din ieşirile
decodificatorului poate fi folosită pentru selectarea circuitului 8251.
2. Schema este alcătuită din un decodificator de porturi, un circuit specializat 8255 şi porți
pentru amplificarea/separarea liniilor între circuitul specializat şi periferic. Oricare din ieşirile
decodificatorului poate fi folosită pentru selectarea circuitului 8251.
3. Schema este alcătuită din un decodificator de porturi, 8 circuite registru, fiecare cu câte 8
ieşiri. La fiecare ieşire de registru se conecteză catodul unui led iar anodul acestuia se leagă prin
o rezistență la alimentare. Aprinderea/stingerea led‐urilor se va comanda prin intermediul
informațiilor înscrise în registre prin intermediul magistralei de date. Pentru ca un led să
lumineze ieşirea la care este conectat va trebui să aibă 0 logic iar pentru ca un led să fie stins,
ieşirea la care este conectat va trebui să aibă 1 logic.
Fundamente de inginerie software
1. Să se reprezinte o diagramă „use case” ce implementează un sistem web on-line de achiziţii publice care acţionează în următorul fel:
- pe site-ul web există conturi de contractori, de prestatori şi un cont special de administrare;
- contractorii şi prestatorii se pot înregistra şi pot să-şi modifice doar datele proprii. Contul de administrator este predefinit şi poate administra şi conturile de contractori şi prestatori;
- pentru acces utilizatorii se vor autentifica (prin logare);
- beneficiarul poate posta un anunţ pentru o lucrare;
- contractorii care doresc acea lucrare, îşi postează oferta, care cuprinde preţul propus, termen de timp şi descrierea soluţiei. Ulterior ei pot să îşi modifice oferta;
- beneficiarul poate să renunţe la o lucrare (să o şteargă);
- în caz că o oferta este acceptată ea intră în execuţie. Prestatorul o va executa iar contractorul o va recepţiona.
R:
Sistem on-line
Creare cont
Logare
Administrare conturi
Administrare cont propriu
Lucrare
Ofertă
Execuţie
înregistrare
autentificare
administrare
administrare
administrare
postare/ ştergere
acceptare
recepţionare
postare/modificare/ştergere executare
Vizitator
Administrator
Contractor
Prestator
autentificare
2. Considerând următorul formular de introducere date, cu validările specificate, specificaţi un set de date eronate pentru a se verifica funcţionarea corecta a sistemului de validare:
cod utilizator - intre 6 si 20 caractere, format doar din litere si cifre, trebuie sa fie unic in baza de date
parola - intre 4 si 15 caractere, doar litere si cifre
e-mail - trebuie sa fie un e-mail scris corect (daca notam cu S setul de caractere permise, trebuie sa avem: S @ S(.S)+, adică după @ trebuie sa fie minim 2 grupe de caractere S, despărţite prin .)
nume - trebuie sa conţină doar litere, cu minim 2 caractere pentru un cuvânt si minim 2 cuvinte
telefon intern - trebuie sa fie un număr valid de 5 până la 10 cifre, fără prefix internaţional (00), putând cuprinde opţional pentru lizibilitate liniuţe şi puncte.
R: a) 1. Codul sa fie format din mai puţin de 6 caractere 2. Codul sa fie format din mai mult de 20 caractere 4. Codul sa conţină şi alte caractere pe lângă litere si cifre 3. Codul sa fie duplicat b) 1. Parola să fie formată din mai puţin de 4 caractere 2. Parola să fie formată din mai mult de 15 caractere 4. Parola să conţină şi alte caractere pe lângă litere si cifre c) 1. Să conţină si alte caractere pe lângă cele permise 2. Sa nu existe @ 3. După @ urmează un singur S 4. Sa fie @ la început sau la sfârşit 5. După @S sau @S. nu mai urmează nimic d) 1. Numele să conţină şi alte caractere în afara de litere 2. Numele are mai puţin de două caractere 3. Numele este format dintr-un singur cuvânt e) 1. Număr incorect de telefon cu mai puţin de 5 sau mai mult de 10 cifre 2. Să conţină 00 in fata 3. Să conţină alte caractere decât cifre, liniuţe şi puncte
3. Se cere diagrama de clase UML care implementează un sistem de gestiune al angajaţilor dintr-o companie considerând următoarele precizări:
- fiecare angajat are un cod personal, nume, adresa, telefon, data angajării si observaţii;
- un angajat poate ocupa unul din trei posturi posibile: salariat, şef de echipă sau director de departament;
- fiecare angajat are un salariu rezultat printr-o procedură de calcul;
- există trei departamente (tipuri de angajaţi): producţie, vânzare şi achiziţii;
- angajaţii din producţie mai au în plus şi o calificare specifică;
- la vânzare si achiziţii, angajaţii mai trebuie să cunoască o limbă străină şi pot să muncească în alte locaţii, decât la sediul firmei;
- la achiziţii, unii angajaţi pot avea şi calificarea de testor pentru a testa lotul achiziţionat.
La proiectare se va utiliza conceptul de moştenire şi se va respecta principiul open-close.
R:
În plus fiecare clasă va mai conţine câte o metodă set, respectiv get pentru fiecare atribut.
Productie - calificare : String
Angajat - codPersonal : int - nume : String - adresa : String - dataAngajare : Date - observatii : String - post + salariu()
1. Precizati succesiunea operatiilor pentru obtinerea cheilor publice utilizand o „autoritate pentru distribuţia cheilor publice” (fig.1)
(1) Request || Time1
(2) EKRauth [ KUb || Request || Time1 ]
(3) EKUb [IDA || N1]
(7) EKUb [ N2 ]
(6) EKUa [N1 || N2]
(4) Request || Time2
(5) EKRauth [ KUa || Request || Time2 ]
A
Chei publiceAutoritate
B
Fig.1 . Distribuţia cheilor folosind o autoritate pentru chei publice
R: Fiecare participant cunoaşte cheia publică a autorităţii, care va fi folosită pentru autentificarea părţilor participante. Pentru a primi o cheie se urmează paşii descrişi în continuare: A trimite un mesaj datat (mesajul include Time1) autorităţii conţinând o cerere (Request) pentru cheia publică curentă a lui B. [mesajul (1)] Autoritatea răspunde cu un mesaj [mesajul (2)] criptat cu cheia sa privată, mesaj pe care A îl poate decripta fiind în posesia cheii publice a autorităţii. Astfel A poate fi sigur că mesajul primit este autentic, mesajul fiind criptat cu cheia privată a autorităţii KRauth. Mesajul include următoarele: Cheia publică a lui B, KUb. Cererea originală pentru ca A să determine dacă aceasta nu a fost modificată. Datarea mesajului, astfel A poate determina dacă mesajul primit nu este un mesaj vechi de la autoritate, conţinând o cheie diferită de cheia curentă a lui B. A salvează cheia publică a lui B şi îi transmite acestuia un mesaj care conţine un identificator IDA şi un anunţ N1, care este folosit pentru identificarea tranzacţiei. [mesajul (3)] B recepţionează cheia publică a lui A de la autoritate în aceeaşi manieră cum A a recepţionat cheia lui B. [mesajele (4) si (5)] B transmite un mesaj lui A criptat cu cheia publica a lui A si care contine un raspuns N2 la anuntul N1 [mesajul (6)] In final A ii retransmite mesajul N2 inapoi lui B, criptat cu cheia publica a lui B. Astfel A si B au ajuns in posesia cheilor publice ale celuilalt si s-au anuntat unul pe altul despre acest lucru. [mesajul (7)]
2. Aplicati transformarea ShiftRows( ) – Fig.2. – din algoritmul de criptare AES urmatorului tablou de stare:
AB90F1A7
1523A57B
1225E377
1B3F32A2
S
Fig. 2. Transformarea ShiftRows( )
R: În această transformare, octeţii din liniile tabloului de stare sunt rotiţi spre stânga astfel: cu 0 octeţi pentru linia 1, cu 1 octet pentru linia 2, cu 2 octeţi pentru linia 3 şi respectiv cu 3 octeţi pentru linia 4, rezultand tabloul de stare S’.
90F1A7AB
A57B1523
771225E3
1B3F32A2
'S
3. Aplicati transformarea InvSubBytes( ) din algoritmul de decriptare AES, bazat pe substitutia S inversa din Fig.3, a urmatorului tablou de stare:
AB90F1A7
1523A57B
1225E377
1B3F32A2
S
Figura 3. Descrierea substituției octetului xy (in hexazecimal) utilizând cutia
inversă S
R: Pentru fiecare byte se obtine x (prima cifra hexa) si y (a doua cifra hexa) si se utilizeaza Fig.3 pentru a obtine valoarea noua a octetului respectiv. De ex. Pentru S0,0=2A, x=2, y=A, rezultand S’0,0=95. Astfel rezulta:
E096CBBD
F2324620
392C1D02
56E71A95
'S
Rețele de calculatoare
1. Se considera adresa ip v4 172.16.0.150 având masca 255.255.255.192. Se cere:
a) Adresa rețelei respectiv adresa de broadcast a rețelei din care face parte adresa ip; b) Adresa subrețelei respectiv adresa de broadcast a subrețelei din care face parte adresa ip; c) Numărul de hosturi din subrețeaua din care face parte adresa ip; d) Numărul de subrețele definite de masca adresei ip dată. R: a) Adresa IP definește o rețea de clasa B rezultă că masca rețelei este 255.255.0.0 . Făcând operațiile pe biți vom avea: 10101100.00010000.00000000.10010110 Adresa IP 11111111 .11111111 .00000000.00000000 Mască rețea -------------------------------------------------- 10101100.00010000.00000000.00000000 Adresa rețelei -------------------------------------------------- 10101100.00010000.11111111 .11111111 Adresa de broadcast a rețelei Adresa rețelei este 172.16.0.0 Adresa de broadcast a rețelei este 172.16.255.255 b) Făcând operațiile pe biți vom avea: 10101100.00010000.00000000.10010110 Adresa IP 11111111 .11111111 .11111111 .11000000 Masca subrețea -------------------------------------------------- 10101100.00010000.00000000.10000000 Adresa subrețelei -------------------------------------------------- 10101100.00010000.00000000.10111111 Adresa de broadcast a subrețelei Adresa subrețelei este 172.16.0.128 Adresa de broadcast a subrețelei este 172.16.0.191 c) Numărul de hosturi din subrețea: NH = 26-2 = 62 hosturi d) Numărul de subrețele: NSR = 210-2 = 1022 subrețele
2. Se considera adresa ip v4 192.168.10.125/28. Se cere:
a) Adresa rețelei respectiv adresa de broadcast a rețelei definite de perechea adresă ip / mască rețea. b) Numărul de hosturi din rețeaua determinată la punctul a). R: a) Făcând operațiile pe biți vom avea: 11000000.10101000.00001010.01111101 Adresa IP 11111111 .11111111 .11111111 .11110000 Masca rețea -------------------------------------------------- 11000000.10101000.00001010.01110000 Adresa de rețea -------------------------------------------------- 11000000.10101000.00001010.01111111 Adresa de broadcast a rețelei Adresa rețelei este 192.168.10.112 Adresa de broadcast a rețelei este 192.168.10.127 b) Numărul de hosturi din subrețea: NH = 24-2 = 14
Baze de date
Nota: Pentru rezolvarea problemelor propuse se poate folosi şi limbajul SQL sau PL/SQL, dar cu definirea
cheilor primare şi externe.
1. Se consideră două fişiere dintr‐o bază de date existentă pentru rezervare locuri la avion. Fişierul Curse
conține datele pentru fiecare cursă din orarul de zbor.
Fişierul Pasageri conține datele pentru toți pasagerii din toate cursele. Toți pasagerii unei curse vor avea
acelaşi cod cursă CodC.
Curse
CodC Pilot Copilot Avion Oras1 Ora1 Oras2 Ora2 PretR NrLoc
Pasageri
CodC CNP NumeP Adresa DataN Tel Pret
Să se afişeze informațiile despre o cursă de avion şi lista pasagerilor din acea cursă folosind comenzi
simpe din limbajul XBase. Se recomandă forma de afişare:
CodC Oras1 Ora1 Oras2 Ora2 Pilot Copilot TipAv
Ro234‐
0609
Timisoara
TSR
8:30 Bucuresti 9:30 Popescu Adam B747
Lista Pasageri
CNP Nume Pas Adresa Telefon DataN Pret
R.
SET TALK OFF
CLEAR
USE Curse INDEX Icodc IN 1 ALIAS CS
USE Pasageri INDEX Icodc, Inume IN 2 ALIAS PS
SET RELATION TO Codc INTO PS
ACCEPT ’Cod cursa: ’ TO Vcodc
SEEK VCodc
? ’CodC Pilot Copilot Avion Oras1 Ora1 Oras2 Ora2 ‘
3. Considerăm o bază de date normalizată pentru evidență studenți care cuprinde tabelele:
STUD
CodS Nume Adresa DataN Bursa Telefon CNP ......
NOTE
CodS CodC NOTA Data
CURS
CodC Titlu NumeProf
Folosind comenzile XBase elementare pentru dialog şi SQL pentru căutarea informațiilor, să se scrie
secvențe de program care realizează funcțiile:
Afişare Cods, Nume student, Bursa, pentru toți studenții care au medii mai mari decât o valoare N
Afişare pentru un student dat prin Cods toate notele, Titlul cursului pentru fiecare notă şi Nume profesor.
Se va ține cont că rezultatul unei comenzi SQL se obține într‐o zona de lucru din care se poate afişa
direct folosind comanda BROWSE, iar variabilele citite sunt externe precedate de “:”.
R.
ACCEPT ‘ Media minima: ‘ TO N
SELECT ST.Cods,ST.Nume, AVG(NT.Nota) Media FROM Stud ST, Note NT
WHERE ST.Cods=NT.Cods GROUP BY ST.Cods,ST.Nume,ST.Bursa,
HAVING AVG(NT.Nota)>:N
Browse && ‐ afisare rezultat
Wait
ACCEPT ‘ Dati Cod student’ TO Vcods
SELECT ST.Cods, ST.Nume,NT.Nota,CS.Titlu,CS.NumeP Profesor
FROM Stud ST, Note NT, Curs CS
WHERE ST.Cods=:Vcods AND ST.Cods=NT.Cods AND NT.Codc=CS.CODC
BROWSE
Wait
Proiectarea interfeţelor utilizator şi grafică 1. Analizati din punctul de vedere al uzabilității mesajul de eroare de mai jos: Mesaj de “help” al unui site al unei companii (Midwest Microwave) care apare atunci când utilizatorii doresc să parcurgă catalogul de produse de pe site. Mesajul apare înainte de prezentarea catalogului. Are scopul de a completa câteva lucruri care nu au fost precizate anterior în catalog.
R:
Supraîncărcarea utilizatorului cu detalii; nu reiese ce este important şi ce este mai puţin important (-minus la design minimalist).
Aspect dezastruos: fără paragrafe, fără titlu, fără spaţii care să ghideze privirea (- la design estetic) Materialul nu este organizat pe module, astfel încât să fie parcurs ușor şi utilizatorul să aleagă din
ceea ce este prezentat ceea ce ştie şi nu ştie deja (- la flexibilitate şi eficienţă). Informaţia prezentată este inutilă şi în afara contextului atât timp cât utilizatorul nu a văzut încă
despre ce este vorba (- la suport şi documentare) Fiind o casetă de dialog modală, aceasta va dispărea îndată ce utilizatorul va continua şi va ajunge la
catalog, atunci când de fapt va avea nevoie de a-şi aduce aminte de cele scrise în casetă (- la minimizarea încărcării memoriei).
Utilizarea termenilor precum modem V.90 (nu vorbeşte în limbajul utilizatorului general). 2. Analizați interfața de mai jos și propuneți o variantă mai bună, conform regulilor de design cunoscute.
R.:
Prea multe culori, fără reguli asociate; Prea multe fonturi, prea mult bold; Nu e nevoie de umbrire în titlu; Bara orizontală nu este necesară în prima zonă de text; butonul Close – care apare ca secundar aici – este mai mare decât butonul Send – cel mai des
folosit.
3. Indicați elementele din proiectarea interfețelor utilizator de tip web care caracterizează o proiectare reuşită. R: Text Fondul nu creează discontinuităţi ale textului Textul este suficient de mare pentru a fi bine citit, dar nu prea mare Ierarhizarea informaţiei este clară Coloane textului sunt mai înguste decât într-o carte pentru a facilita citirea mai uşoară de pe ecran. Navigarea Butoanele de navigare sunt uşor de înţeles şi folosit Navigarea este consistentă în tot web-site-ul Butoanele de navigare conţin o indicaţie pentru a informa utilizatorul unde se găseşte, în ce pagină Daca se folosesc frame-uri, acestea nu sunt obtruzive (stridente, deranjante) Un site mare are un index sau o hartă a site-ului. Links Culorile link-urilor sunt corelate cu culorile paginilor Link-urile sunt subliniate şi astfel sunt imediat vizibile utilizatorului. Grafica Butoanele nu sunt prea mari şi greoaie Fiecare element grafic are asociat un “alt label” (descriere prin text atunci când trecem peste acesta) Fiecare link grafic are un corespondent link text Elementele grafice şi fondurile folosesc culori care nu sunt denaturate de browser Elementele de grafica animată se opresc automat Proiectarea generală Paginile se încarcă rapid Prima pagină şi pagina ’Acasă’ (Home) intră într-un spaţiu de 800x600 pixeli Restul paginilor au un impact vizual imediat în legătură cu relaţia 800x600 Utilizarea corectă a elementelor grafice pentru a “sparge” zone mari de text Fiecare pagină din site arată ca o parte a unui întreg; există elemente repetitive care sunt menţinute în toate paginile.
Medii şi tehnologii de programare
1. Se propune crearea unei aplicaţii de grafică vectorială. Operaţiile grafice suportate de către aplicaţie sunt: desenarea de linii, dreptunghiuri şi elipse. Utilizatorul va putea de asemenea seta culoarea de fundal, culoarea de desenare, grosimea contururilor. Desenele realizate cu ajutorul acestei aplicaţii vor putea fi salvate/încărcare pe/de pe disc. Toate elementele grafice desenate vor fi memorate într-o listă de obiecte (clasa Figura).
Public Class Figura Public x1, y1 As Integer 'coordonatele punctului 1 Public x2, y2 As Integer 'coordonatele punctului 2 Public shape As Integer 'tipul formei desenate Public width As Integer 'grosimea conturului Public color As Color 'culoarea de desenare Public Sub New(shape As Integer, x1 As Integer, y1 As Integer, x2 As Integer, _ y2 As Integer, width As Integer, color As Color) 'initializarea membrilor clasei End Sub Public Sub DrawMe(gr As Graphics) 'desenarea figurii End Sub End Class
a) Descrieţi o modalitate simplă prin care se pot implementa operaţiile de Undo/Redo. b) Descrieţi o modalitate prin care poate fi implementată funcţia de scalare a desenului (zoom in, zoom out). Factorul de scalare poate fi atât supraunitar cât şi subunitar. Exemplu: 3 (mărire de trei ori). 1/4 (micşorare de patru ori).
Rezolvare:
Voi expune în continuare o posibila rezolvare a problemei, deşi aceasta ar putea suporta mai multe soluţii.
a) Din moment ce toate elementele grafice desenate pe planşă sunt memorate într-o listă (lista 1), pentru implementarea operaţiilor Undo/Redo vom avea nevoie de încă o listă (lista 2) în care să memorăm elementele grafice şterse de pe planşă ca urmare a comenzii Undo. Astfel:
Comanda Undo va muta ultimul element din lista 1 în coada listei 2. Comanda Redo va muta ultimul element din lista 2 în coada listei 1.
b) Pentru scalarea desenului va trebui să redesenăm conţinutul planşei înmulţind, pentru fiecare element grafic, proprietăţile x1, y1, x2, y2 şi width ale acestuia cu factorul de scalare dorit. Funcţia DrawMe, membră a clasei Figura poate fi modificată prin adăugarea unui parametru suplimentar, care să reprezinte factorul de scalare.
2. Se cere crearea unei aplicaţii pentru afişarea subtitrării unui fişier video. Aceasta trebuie citită dintr-un fişier text şi afişată peste un control care afişează conţinutul video (Figura 1).
Figura 1
Se presupune că fişierului video îi este asociat un singur fişier de subtitrări (având extensia *.sbt), iar la pornirea aplicaţiei se deschide automat fişierul video şi fişierul de subtitrări asociat. Fereastra aplicaţiei mai conţine două butoane asociate comenzilor Play şi Pause. Butonul Play porneşte rularea fişierului video iar butonul Pause întrerupe rularea fişierului video.
Fişierul de subtitrări are următoarea structură:
start1-stop1 continut_text_1 start2-stop2 continut_text_2 ... startN-stopN continut_text_N unde: startN reprezintă momentul de timp la care va fi afişat mesajul text, stopN reprezintă momentul de timp (măsurat în secunde) la care mesajul text va fi ascuns, iar continut_text_N reprezintă mesajul text care trebuie afişat.
Se presupune că start1 < stop1 < start2 < stop2 < … < startN < stopN, iar toate momentele de timp sunt măsurate în secunde de la începerea rulării fişierului video.
Se cere descrierea modului în care poate fi afişată subtitrarea şi implementarea comenzilor Play şi Pause. Nu se cere tratarea modului în care este afişat conţinutul fişierului video.
Rezolvare: Voi expune în continuare o posibila rezolvare a problemei, deşi aceasta ar putea suporta mai multe soluţii. Pentru a putea afişa conţinutul text al subtitrării la anumite momente de timp este nevoie de un componentă Timer (denumită Timer1) care să aibă setată proprietatea Interval la valoarea 1000 (1000 ms = 1 s). Aceasta va porni cronometrarea (Timer1.Start) la apăsarea butonului Play şi o va opri (Timer1.Stop) la apăsarea butonului Pause. Intervalul de timp scurs de la pornirea rulării fişierului video va trebui stocat într-o variabilă de tip întreg:
Dim time As Integer şi incrementat la fiecare secundă în procedura eveniment Timer_Tick. La deschiderea aplicaţiei va fi citită din fişierul de subtitrări prima secvenţă de tip: start1-stop1 continut_text_1 Când time=start1 textul continut_text_1 va fi afişat într-un control de tip Label, iar când time=stop1 textul va fi şters din controlul de tip Label. Această secvenţă se va repeta până la parcurgerea completă a fişierului de subtitrări.
3. Se cere realizarea unei aplicaţii pentru afişarea graficelor unor funcţii polinomiale. După introducerea de către utilizator a gradului funcţiei, a parametrilor şi a intervalului pe care aceasta să fie reprezentată, va fi afişat graficul funcţiei (într-un control de tip PictureBox).
Indicaţi cât mai detaliat două metode prin care puteţi afla valoarea funcţiei în orice punct de pe intervalul dat. Presupunem că valorile de pe axa X pot fi numai numere întregi.
Rezolvare: Voi expune în continuare două soluţii ale problemei, deşi aceasta ar putea avea mai multe soluţii. Se introduce de la tastatură (într-un control TextBox) valoarea lui X pentru care va fi afişată (în alt control TextBox), prin calcul, valoarea lui f(X). Se plasează cursorul de mouse deasupra graficului, iar la evenimentul MouseMove al controlului PictureBox se calculează, în funcţie de originea axelor, valoarea abscisei în punctul în care este plasat cursorul de mouse. Tot în cadrul codului asociat evenimentului MouseMove va fi afişată (eventual într-un control TextBox) valoarea funcţiei calculată pentru abscisa dată.
Limbaje formale şi tehnici de compilare
1. Se dă gramatica:
G1:E → E+ E | E * E | (E) | i Să se arate că această gramatică este ambiguă. 2. Se consideră definiţia regulată pentru identificatori:
identif → litera(litera|cifra)* Să se deseneze diagrama de tranzitii (automatul finit) corespunzătoare, incluzând şi cuvintele cheie şi menţionând procedurile semantice necesare. 3. Se dă gramatica:
E → T | E+T T → F | T*F F → (E) | id
Să se elimine recursivitatea de stânga din această gramatică.
Răspunsuri
1. Se consideră şirul de intrare: i + i * i
Pentru acest şir există 2 arbori de derivare:
În concluzie, gramatica este ambiguă.
2. Tratarea identificatorilor:
3. Pentru relaţiile recursive, se foloseşte formula:
AA AA’ A’A’
În acest fel, mulţimea de şiruri derivate din A nu se schimbă. Se obţine următoarea gramatică transformată:
EE+TT ETE’ E’TE’ TTFF TFT’ T’FT’ F(E)id F(E)id
E
E + E
i E E *
i i
E
E * E
iE E+
i i
Programare WEB
1. În cadrul unei baze de date cu numele RESURSE_UMANE, stocată pe un server MySQL (localhost, user “root”, fără parolă), se consideră tabela PERSONAL, creată cu comanda SQL următoare:
CREATE TABLE personal ( cnp CHAR(13) PRIMARY KEY, nume VARCHAR(20), prenume VARCHAR(20); salar INTEGER); Să se scrie o aplicaţie Web (structurată sub forma a două fişiere script, unul HTML, celălalt PHP) care permite interogarea parametrizată a tabelei după o informaţie din coloana CNP (cod numeric personal) introdusă de la tastatura (prin intermediul unui formular HTML). Parametrul de interogare va fi transmis spre scriptul PHP, acesta realizând interogarea efectivă a tabelei şi afişarea pe o coloană a datelor returnate. Dacă nu se găseşte nici o înregistrare, se va semnala acest lucru printr-un mesaj. Se vor trata eventualele erori/excepţii prin afişarea unor mesaje. Alegerea numelor fişierelor este la latitudinea programatorului.
R. (o soluţie posibilă, aceasta nefiind unică): fisier.html <html> <form action="fisier.php" method="POST"> CNP:<input type="text" name="cnp" size="13"><br> <input type="SUBMIT" value="Cauta"> </form> </html> fisier.php <?php $link=mysql_connect("localhost","root","") or die ("Eroare: Conectare esuata la server MySQL"); mysql_select_db("resurse_umane") or die ("Eroare: Nu se poate deschide baza de date"); $cnp=$_POST['cnp']; $query=mysql_query("select * from personal where cnp='$cnp'"); $contor_linii=0; while($row=mysql_fetch_row($query)) { $contor_linii++; //gasit o linie foreach ($row as $value) echo $value." <br>"; } if ($contor_linii==0) echo "Nu s-a gasit nici o linie!"; mysql_close($link); ?> 2. În cadrul unei baze de date cu numele BAZA, stocată pe un server MySQL (localhost, user “root”, fără parolă), se consideră tabela EVIDENTA, creată cu comanda SQL următoare:
CREATE TABLE evidenta(nume CHAR(20), varsta INTEGER, localitate CHAR(20));
Să se scrie un script PHP care permite interogarea tabelei, respectiv afişarea în format tabelat al întregului ei conţinut. Se vor trata eventualele erori/excepţii prin afişarea unor mesaje. Secvenţa de cod PHP se va comenta succint.
R. (o soluţie posibilă, aceasta nefiind unică): <?php //conectare la server si selectie baza de date $link=mysql_connect("localhost","root","") or die ("Eroare: Conectare esuata la server MySQL"); mysql_select_db("baza") or die ("Eroare: Nu se poate deschide baza de date"); //interogare tabela $query=mysql_query("select * from evidenta"); //creare antet tabel echo "<table border='1'>"; echo "<tr>"; echo "<th>Nume</th>"; echo "<th>Varsta</th>"; echo "<th>Localitate</th>"; echo "</tr>"; //ciclare dupa numarul de inregistrari/linii gasite si afisarea lor, element cu element while ($row=mysql_fetch_row($query)) { echo "<tr>"; foreach ($row as $value) { echo "<td>$value</td>"; } echo "</tr>"; } echo "</table>"; //inchidere conexiune la baza de date mysql_close($link); ?> 3. În cadrul unei baze de date cu numele MAGAZIN, stocată pe un server MySQL (localhost, user “root”, fără parolă), se consideră tabela PRODUSE, creată cu comanda SQL următoare:
CREATE TABLE produse (id INTEGER PRIMARY KEY, nume_produs VARCHAR(20), stoc INTEGER);
Să se scrie o aplicaţie Web (structurată sub forma a două fişiere script, unul HTML, celălalt PHP) care permite introducere de la tastatură (prin intermediul unui formular HTML) a datelor privitoare la un produs din tabela bazei de date (id, nume_produs, stoc). Aceşti parametrii se vor transmite către un script PHP, realizând adăugarea efectivă a noului articolului în tabela bazei de date. Reuşita sau nereuşita operaţiei se va semnala prin afişarea unui mesaj corespunzător. Alegerea numele fişierelor este la latitudinea programatorului.
R. (o soluţie posibilă, aceasta nefiind unică): fisier.html <html> <form action="fisier.php" method="POST"> Id:<input type="text" name="id" size="5"></p> Nume Produs:<input type="text" name="nume_produs" size="20"><br> Stoc:<input type="text" name="stoc" size="5"><br>
<input type="SUBMIT" value="Trimite"> </form> </html> fisier.php <?php $link=mysql_connect("localhost","root","") or die ("Eroare: Conectare esuata la server MySQL"); mysql_select_db("magazin") or die ("Eroare: Nu se poate deschide baza de date"); $id=$_POST['id']; $nume_produs=$_POST['nume_produs']; $stoc=$_POST['stoc']; mysql_query("insert into produse values ($id, '$nume_produs', $stoc)") or die ("Eroare: Nu se poate finaliza operatia"); echo "Informatiile au fost introduse in baza de date"; mysql_close($link); ?>
