BMC, cu Mihaela Lupea.

Biletul 1

Să se demonstreze printr-o metodă prin respingere că axioma a doua a calculului propozițional este o teoremă. Teoria aferentă metodei. Ce este o teoremă?

 2. Ce este cel mai general unificator a doi atomi? Care este algoritmul de unificare a doi atomi? Încercați să unificați următoarele perechi de atomi:

       $ P(a,h(x,a),g(z)) $ și $ P(y,h(y,f(z)),g(x)) $

       $ P(x,f(a),b) $ și $ P(y,z,g(b)) $

       $ P(x,y(x),f(x)) $ și $ P(y,z,y) $

   Metoda schimbării de bază prin substituție. Schimbați numărul 22103 în baza 5 cu calcule în baza 5. Scrieți numărul 670418 în baza 16 cu calcule în baza 16.

   Folosind metoda lui Quine simplificați următoarea funcție: $ f(x,y,z) = m_0 vee m_1 vee m_3 vee m_4 vee m_5 $ Construiți circuitul asociat funcției originale cât și circuitele corespunzătoare tuturor formelor simplificate.

Au fost multe bilete, vreo 15. Rezultatele s-au dat în aceași zi, după vreo 3-4-5 ore. Cei între două note au primit câteva întrebări pentru a determina nota finală. Notele au fost în general puternic influențate de tema electronică, activitatea de seminar și de prezența la curs (profesorii au fost Mihaiela Lupea și Mihiș Andreea).

Arhitectura Calculatoarelor:

sau arhitectura sistemelor de calcul. Că așa le tot schimbă ăștia
    Prof. Vancea Alexandru

~~Well, sorry folks, nu am reușit să fac rost de nicio foaie cu subiect. :| Proful confiscă tot și nici nu ai timp să copiezi subiectul că scrii de te rupi la examen.~~Edit: Aparent unii colegi mai neînfricați au făcut o poză la subiectul lor. Și subiectul lor (grupa 213-214) e aproape identic cu al nostru (grupa 215-216) =)). La noi la II se era octetul al treilea în loc de al doilea :)). Mersi Alexandru!

Dar așa pe scurt ce ne-o dat și câteva impresii despre această materie.

I. Efectuați o analiză asupra conceptului de „depășire” la nivelul operațiilor aritmetic scoțând apoi în evidență cum reacționează arhitectura 80x86 la apariția unei astfel de situații în cazul fiecăruie dintre cele 4 tipuri de operații aritmetice de bază: adunare, scădere, înmulțire și împărțire. Care sunt situațiile considerate de către limbajul de asamblare „depășiri” și cum reacționează procesorul? Prezentați pentru fiecare din cele 4 cazuri câte 1-2 exemple de cod sursă adecvate și sugestive pentru apariția unor astfel de situații, explicați care este reacția sistemului de calcul în fiecare caz și ce poate face programatorul ulterior apariției unei astfel de situații la nivelul programului.

II. Se dă un șir de valori numerice întregi reprezentate pe dublucuvinte. Să se tipărească pe ecran stringul pozițiilor dublucuvintelor din șirul de dublucuvinte care au cel de-al doilea octet al reprezentării în baza 16 strict negativ, precum și suma acestor octeți în baza 10. Explicați algoritmul, justificați și comentați corespunzător codul sursă. Insistați în explicații asupra aspectelor dificile sau problematice implicate în soluția prezentată.

Ex: Se dă șirul de dublucuvinte: sir dd 12A63478h, 12345678h, 1A2B3C4Dh, FEDC9876h Cel de-al doilea octet al reprezentării în baza 16 este: A6h, 34h, 2Bh și respectiv DCh. Valorile lor numerice corespunzătoare sunt: -90, 52, 43 și respectiv -36, deci dublucuvintele ce au cel de-al doilea octet al reprezentării în baza 16 strict negativ sunt pe pozițiile 1 și 4 în șirul dat, așadar trebuie afișat pe ecran stringul „14”, precum și suma celor 2 octeți în baza 10 (-126).

III. Se dau următoarele secvențe ASM: a) x db -128,128, -1 y dd -128 z dw 128 ... mov ax,word ptr x+1 not ah neg al mov bx, word ptr x+2 xchg bh,bl neg bx cbw xor ax,bx xor bx,ax sub ax,bx les di,y+1 inc di push ds pop es mov ch,es:[di] inc di mov dx,es:[di]

b) mov ax,-129 cbw and ax,-1 cwd shl ax,2 sar al,2 or ax,dx div al

Explicați și justificați efectul fiecărei linii sursă (în măsura în care o considerați corectă sintactic - dacă nu, explicați de ce este incorectă și treceți mai departe...), arătând cum funcționează exact fiecare instrucțiune și care va fi conținutul regiștrilor implicați, în fiecare dintre bazele de numerați 2, 10 și 16 (și în interpretarea cu semn și în cea fără semn).

IV. Definiți și explicați semnificația și importanța noțiunilor de cod de apel, cod de intrare și cod de ieșire în contextul general al limbajelor de programare. Analizați cum se reflectă acestea la nivelul limbajului de asamblare 80x86 și respectiv la nivelul sitvei de execuție în cadrul rulării unui program.

Timp de lucru: 2h 30' Punctaj: I - 2p; II - 3p; III - 2p; IV - 2p; (+1p din oficiu)

La acest examen am scris cel mai mult. La I am scris vreo 3 pagini, și asta după ce m-am prins că îmi ia prea mult și tre să mai încep să nu mai fiu vorbăreț. La 2 am scris vreo 4-5 pagini de cod bine comentat. Nu aș vrea să fiu proful corector.  La 3 am scris vreo 3 pagini, și am greșit undeva la început la calcule, așa că jumate din rânduri îs tăiate peste și deasupra înghesuit rezultatul corect. Și m-am plictisit să tot scriu FF80, 80FF, 1111111110000000 și alte numere binare. :| La 4 deja nu mai prea aveam chef (și cunoștințe) așa că am scris doar 1 pagină  :)))

Și încă o fază tare: fix înainte de noi aveau examen cei din grupa 213-214 tot la AC. Cum am mers și noi mai repede, am mai vorbit cu unii din ei pe măsură ce au ieșit și am aflat ce li s-a dat: overflow și cod de apel, intrare, ieșire. Noooo buuuun, nu ne dă aia, nu mai îngrășăm porcu'n ajun cu chestiile ăstea. Privind în urmă, am un sentiment că singura diferență dintre subiectele noastre și ale lor o fost ce scria după cuvântul „Grupa” sus în titlu. :D

Săptămâna asta, în timp ce îmi învățam am avut câteva epifanii legate de această materie.

   Programarea în assembly îi diferită de high-level programming... conceptual, în moduri mind-blowing. În limbaje de nivel înalt nu ai chestia aia cu segmente diferite (mă rog, aici s-ar putea să fie un pic de vină real addressing mode). În limbaje de nivel înalt împărțirea nu îți dă în veci eroare decât dacă împarți la 0. Până și if-urile necesită o mică schimbare de mentalitate  în assembly (mai ales cele un pic mai complexe). Dar e super fun. Chiar îmi place assembly-ul și sper să am ocazii în care să mai lucrez în el.

   M-am prins (cred) de ce facem noi asamblare pe stackul tehnologic 80x86, Turbo Debugger și MS-DOS și răspunsul are un singur cuvânt: întreruperi. În acele vremuri bune, you could shoot yourself in the foot with assembly. Or the computer. Amu' nu mai îi așe simplu. Ai protected/paged/virtual memory mode => canci acces la toată memoria. Dar asta nici nu îi așa mare problemă, că noi oricum nu prea ne jucăm cu acces la memorie în afară de datele pe care noi le-am alocat. Daaaar, în procesoarele mai noi și în sitemele de operare mai noi, există inele de securitate care limitează accesul la resurse al programelor. Kernelul rulează în inelul 0 și face ce vrea, pe când user-loser programs rulează în inelul 3 și... well nu fac prea multe și nu au acces direct la hardware și nu pot executa întreruperi. Cum întreruperile sunt niște chestii esențiale și cu care trebuie să ne și jucăm, nu doar să ni se predea teoria, lucrăm într-un mediu de dezvoltare de 30 de ani. Oh well......

   Instrucțiunile jmp nu au aceași lungime (când îs asamblate). Vroiam să testez diferitele moduri de adresare pentru sărituri și am pus mai multe jumpuri unul după altul. Diferența dintre adresele lor (dacă le etichetam) nu era constantă. Îi perfect logică această chestie, dar still, a fost un moment de revelație când mi-am dat seama de ce îmi tună „Divison by 0” când aveam doar jumpuri în tot programul. Și încă ceva legat de jumpuri: așa bine merge callu și la o etichetă și la fel de bine returnează d-acolo ca și de la o „procedură”. Și și procedurile îs flexibile. Li totuna că le scrii \<nume> proc sau proc \<nume> (cum  îi în orice alt limbaj).

După multe bătăi la cap, Mădă m-a convins să public și rezolvarea problemei de AC. Pe Github

Teorie nu o să mă pun să vă scriu, iar la problema 3, n-aveți decât să băgați în Turbo Debugger.

Geometrie: A doua lucrare în semestrul 2 :D/. Sâmbătă de la 8 dimineața :D/.

Să se calculeze $ a\cdot b - \left|\left|a times b\right|\right| $, unde $ a = (2,3,-5), b= (1,2,3) $ 2. $ A(2,3) $ este piciorul perpenendicularei din origine pe o dreaptă. Calculați ecuația acestei drepte. 3. Verificați dacă dreptele date de ecuațiile: $ Delta_{1} begin{cases} x-y+z+1=0 \ 2x-y-z+2=0 end{cases}

Delta_{2} begin{cases} 3x+y+z=0 \ x+y-2z+1=0 end{cases} $ sunt necoplanare. În caz afirmativ, calculați ecuația perpendicularei comune a celor două drepte.

Primele două sunt simple. A treia este mai grea și necesită calcularea a doi determinanți lungi. Cred că am greșit că mi-o dat coeficienți de ordinul sutelor :-S

Sper ca la următoarea lucrare să mă descurc mai bine (și să învăț mai mult).

O fost mai simplu decât mă așteptam:

Să se calculeze ecuațiile tangentelor la hiperbola $ \frac{x^2}{15}-\frac{y^2}{6}-1=0 $ paralele cu $ x-2y=0 $.

Să se calculeze ecuația normalei în punctul P(-2,2,-1) la hiperboloidul cu două pânze $ frac{x^2}{8} - frac{y^2}{2} + frac{z^2}{2} +1=0$. Se cere și celălalt punct de intersecție dintre dreaptă și suprafață.

Să se calculeze ecuația suprafeței cilindrice generate de curba directoare $ x^2 +y^2+z^2-4=0; x+y+z=0 $ și paralele cu dreapta $ (D): \frac{x}{1}=\frac{y}{2}=\frac{z}{-1} $.

PLF:

Azi a fost examenul de Prolog.

Subiectul meu din memorie:

Se dă următorul predicat:

f([],0). f([H|T],S):-!,H mod 2 = 0, f(T,S1),S=S1*H. f([_|T],S):- f(T,S1),S.{lang="prolog"}

Ce va rezulta în urma execuției f([1,2,3,4,5,6,7,8,9],S)? Modificați funția astfel încât să returneze numărul de numere impare din listă.

Scrieți două metode prin care să verificați dacă un număr este prim sau nu. Explicați cele două metode.

Scrieți un predicat care dintr-o listă de numere întregi returnează o listă cu submulțimile de k elemente aflate în progresie aritmetică. Explicați algoritmul. Exemplu pentru [1,3,2,5,9,8] și k=3 => [[1,2,3],[1,5,9],[2,5,8]]

Dacă știe cineva două metode pentru a verifica primalitatea unui număr, să lase un comment please.

30.Se cere sa se elimine prima aparitie a unui element e dintr-o lista neliniara ex: (elimin '1 '(2 3 (1 (4 5)) 1)) -> (2 3 ((4 5)) 1)

(defun elimin(el l) (cond ((null l) nil) ((and (numberp (car l)) (= el (car l))) (cdr l)) ((and (listp (car l)) (apare el (car l))) (append (list (elim el (car l))) (cdr l))) (t (cons (car l) (elim el (cdr l)))) ) ){lang="lisp"}

(defun apare(el l) (cond ((null l) nil) ((and (atom (car l)) (= el (car l))) t) ((listp (car l)) (or (apare el (car l)) (apare el (cdr l)))) (t (apare el (cdr l))) ) ){lang="lisp"}

Dacă a primit cineva problema cu permutări, evaluarea unei expresii date în formă prefixată, sau arbori, vă rog lăsați un comment, să avem o idee legată de distribuția subiectelor.

Subiectul 16

Macrodefinitii si apostroful invers - backquote(`). Explicati si exemplificati.

Sa se scrie un program LISP si sa se deduca complexitatea pt. urmat. cerinta. Se da o lista liniara numerica si se cere sa se scrie de 2 ori elem-le din N in N. De exemplu, pentru lista (1 2 3 4 5) si N=2 rezulta lista (1 2 2 3 4 4 5)

Se da o lista neliniara. Sa se scrie un program LISP pt determinarea numarului de subliste de la orice nivel pt care nr-ul atomilor nenumerici de pe nivelurile pare(de la orice nivel)este impar - nivelul superficial al listei se considera 1. Prelucrarea se va face folosind o functie MAP. De exemplu, lista A (B 2) (1 C 4) (1(6 F)) (((G)4)6)) are 3 astfel de subliste: lista, (1(6 F)) si ((G)4)

Subiectul lui Mădă

Argumente opționale. Explicații și exemplificați.

Un arbore n-ar se reprezintă în LISP în următorul fel: (nod subarb1 subarb2 ... subarb n). Se cere numărul de noduri de pe nivelul k. Nivelul rădăcinii se consideră 0. Exemplu: pentru (a (b (g)) (c (d (e)) (f))) și k=2 => 3 (g, d și f). k= 4 => 0

  1. Se dă o listă neliniară. Se cere un program LISP pentru determinare numărului de subliste de pe orice nivel pentru care primul atom numeric la orice nivel este număr par.

Cu ajutorul Domnului, am primit un subiect pe care deja îl făcusem, așa că sper la notă mare.

Algoritmica grafelor:

Îi materie de anul 3

1. Teorema de caracterizare a a arborilor de pondere minima cu ajutorul cociclurilor.

2. Fie n numar natural nenul Se da graful scara de ordin 2n G^n = ( X^n, U^n) , unde $ X^n = {x_1,x_2,..., x_n} cup {y_1,y_2,...,y_n} $ si $ U^n = { (x_i, x_{i+1}) | i = 1,n-1} cup { (y_i, y_{i+1}) | i = 1,n-1} cup { (x_i, y_i) | i = 1,n-1} $. Determinati numarul cuplajelor maxime ale lui G^n, adica $ | { K | K subset U^n, |K| = n text{ si } forall u,v in K text{nu sunt adiacente} } | = ? $

3. Se da graful orientat G = (X,U) prin arcele si valorile acestora>

ij                                   v_ij   18 78 74 45 43 53 65 61 62 63 21 28  52 24 27 42 90 42 26 34 41 26 24 38   32                                   27

a. determinati un drum de valoare minima de la varful 7 la varful 1; b. determinati un flux de valoare maxima.

La 3b, pentru că erau două surse, răspunsul corect era "Problema nu are sens".

ISS:

La seminar. A fost câte un subiect separat pentru fiecare din noi. Lucrarea a durat jumate de oră.

Subiectul C

  1. Descrieți pe scurt modelul RAD.
  2. Enumerați și descrieți succint pașii fazei de definiție din cadrul     ciclului de viață al unui program.
  3. Explicați termenii: granularitate, plan cu granularitate fină, plan     cu granularitate mare.
  4. Enumerați activitățile aferente modelării funcționalității - sarcină     generică a analizei.
  5. Definiți termenul de model. De ce se folosesc modelele? (enumerați 4     motive).
  6. Care este numărul minim de fluxuri de date asociate unui proces și     de ce?

Vive la Liberté!

C (40%) Raspundeti succint la urmatoarele intrebari

C1. Ce este coeziunea modulară și care sunt treptele acesteia? Care este cea mai bună? (1.5p) C2. Descrieți succint principiul separării interfețelor. Dați un exemplu sugestiv (1.5p) C3. Descrieți succint descompunerea OO a unui subsistem. (1.5p) C4. Descrieți pe scurt șablonul GRASP Creator. (1.5p) C5. Descrieți succint interfața om-calculator bazată pe meniuri. (1.5p) C6. Descrieți pe scurt testarea de integrarea ascendentă. (1.5p) (1p din oficiu)

D (60%). Se consideră problema de la punctul B (verso). Se cer următoarele lucruri:

D1. Trasați diagrama de secvență pentru scenariul ideal al procedurii de rezervare locuri. (2p) D2. Trasați diagrama de colaborare (comunicare) pentru același scenariu. (2p) La evaluare 1.5p sunt alocate pentru concordanța dintre cele două diagrame de mai sus. D3. Trasați diagrama detaliată de clase, care să includă și noile clase identificate mai sus. Diagrama va trebui să includă atât atributele și metodele claselor cât și relațiile dintre ele.(2p) La evaluare 1.5p sunt alocate pentru concordanța dintre diagrama de la D3 și cele de mai sus. (1p din oficiu)

Cu ajutorul Domnului, am mai terminat cu bine un an!

MPP:

Au fost trei subiecte.

I. Client-Server

Programul CLIENT trimite secvenţe de numere întregi (ce reprezintă coeficienţii a două polinoame, după primul polinom se pune un operator şi apoi coeficienţii celui de-al doilea polinom) la un SERVER. Programul SERVER afişează cele două polinoame în forma matematică şi efectuează operaţia. Dupa efectuarea operaţiei SERVERUL trimite înapoi rezultatul la client. Clientul afişează rezultatul în forma matematică. Să se rezolve această problemă în C#. Se pot trimite oricâte secvenţe de la oricâţi CLIENŢI. Se lucrează concurent, se pot lega la SERVER oricâţi CLIENŢI. (Comunicare prin socket).

Operaţiile pot fi (+,-,*) Exemplu: Client1: 2,0,0,4 * 1, -1, 1 (adică 2+4x^3 înmulţit cu 1-x+x^2) Rezultat primit 2,-2,2,4,-4,4 şi afisat 2-2x+2x^2+4x^3-4x^4+4x^5 Client2: 2,0,0,4 + 1, -1, 1 (adică 2+4x^3 adunat cu 1-x+x^2) Rezultat primit 3,-1,1,4 şi afisat 3-x+x^2+4x^3

Notare: a)dacă se rezolvă problema şi CLIENT are interfata grafica+ oricâți clienţi nota 10 b)dacă interfaţa CLIENT e de tip consolă + oricâți clienţi nota 9 c)dacă se rezolvă problema neconcurent (un singur CLIENT) nota 8 d)dacă nu se rezolvă problema decat parţial (de exemplu transmisia e bună dar operatia e deficitară, sau invers) nota 7 e)dacă se fac cele 2 tipuri de program şi în ansamblu nu e rezolvată problema (cele 2 tipuri nu au erori la compilare) nota 6

II. Client-Server

Mai multe programe CLIENT trimit secvenţe de numere întregi (o secvenţă conţine cel puţin un număr) la un singur program SERVER. Programul server le afişează, stochează cele 2 secvenţe (la începutul sesiunii secvenţa serverului e vidă) într-una singură, o sortează crescător şi o trimite înapoi la fiecare client. Secvenţa se afişează la fiecare client. Să se rezolve această problemă în C#. După afişare se repetă trimiterea de secvenţe de la programele CLIENT. Dacă se inchide conexiunea cu cel puţin un client, serverul dă un mesaj şi-şi termină execuţia. (Comunicare prin socket).

Exemplu: Se “leagă” la SERVER, cel puţin 3 CLIENŢI şi apoi avem: CLIENT1 trimite secvenţa 45,23,33,1 Cei 3 clienţi primesc: 1,23,33,45 şi afişează. Apoi al 2-lea client (CLIENT2) trimite: 3,2,1. La SERVER avem 1,23,33,45,3,2,1. După sortare cei 3 clienţi primesc: 1,1,2,3,23,33,45 şi afişează. Procesul continuă, până cel puţin un client îşi închide conexiunea.

Notare: a)dacă se rezolvă problema şi CLIENT are interfaţa grafică + oricâți clienţi nota 10 b)dacă interfaţa CLIENT e de tip consolă + oricâți clienţi nota 9 c)dacă se rezolvă problema neconcurent (un singur CLIENT) nota 8 d)dacă nu se rezolvă problema decat parţial (de exemplu transmisia e bună dar aranjarea e deficitară, sau invers) nota 7 e)dacă se fac cele 2 tipuri de program şi în ansamblu nu e rezolvată problema (cele 2 tipuri nu au erori la compilare) nota 6

III. Client-ServerMai multe programe CLIENT trimit secvenţe de numere naturale (o secvenţă conţine cel puţin un număr) la un singur program SERVER. Programul server le afişează, stochează cele 2 secvenţe (la începutul sesiunii secvenţa serverului e vidă) într-una singură, aranjează secvenţa astfel ca pe primele poziţii să fie numere palindroame şi o trimite înapoi la fiecare client. Secvenţa se afişează la fiecare client. Să se rezolve această problemă în C#. După afişare se repetă trimiterea de secvenţe de la programele CLIENT. Dacă se inchide conexiunea cu cel puţin un client, serverul dă un mesaj şi-şi termină execuţia. (Comunicare prin socket).

Exemplu: Se “leagă” la SERVER, cel puţin 3 CLIENŢI şi apoi avem: CLIENT1 trimite secvenţa 45,23,33,17,9 Cei 3 clienţi primesc: 9,33,45,23,17 şi afişează. Apoi al 2-lea client (CLIENT2) trimite: 32,11,1. La SERVER avem 9,33,45,23,17,32,11,1 După aranjare toţi clienţii primesc:9,33,11,1,45,23,17,32 şi afişează. Procesul continuă, până cel puţin un client îşi închide conexiunea.

Notare: a)dacă se rezolvă problema şi CLIENT are interfaţa grafică + oricâți clienţi nota 10 b)dacă interfaţa CLIENT e de tip consolă + oricâți clienţi nota 9 c)dacă se rezolvă problema neconcurent (un singur CLIENT) nota 8 d)dacă nu se rezolvă problema decat parţial (de exemplu transmisia e bună dar aranjarea e deficitară, sau invers) nota 7 e)dacă se fac cele 2 tipuri de program şi în ansamblu nu e rezolvată problema (cele 2 tipuri nu au erori la compilare) nota 6

VVSS cu domnul profesor Militon Frențiu:

Bilet nr. 9

Definiți:

  1. predicat de intrare
  2. arbore de execuție simbolică
  3. fiabilitate (reliability)

Comentați:

  1. „Limbajele viitorului vor fi limbaje cu aserțiuni”!

Răspundeți:

  1. Enumerați câteva modele de calitate.
  2. Ce diferențe există între validare și verificare?
  3. Ce trebuie să conține documentația de realizare a unui program?
  4. Scrieți condiția de verificare între două puncte de tăietură și     explicați elementele ce apar în această condiție.

Primele 7 puncte câte 1 pct, ultima întrebare 2 pct. Au fost mai mult de 26 de subiecte, dar unele întrebări se repetau între ele.