Intrebari Licenta 2024.pdf

Întrebări Licență 2024 Calculatoare Limbaje de Programare (Pitic A., Ciurea S. - Anul I) Operatori în C/ C++ Operatorii se clasifică în 3 categorii: - Operatori UNARI = un operand, de ex. +1 - Operatori BINARI= 2 operanzi, de...

Întrebări Licență 2024 Calculatoare Limbaje de Programare (Pitic A., Ciurea S. - Anul I) Operatori în C/ C++ Operatorii se clasifică în 3 categorii: - Operatori UNARI = un operand, de ex. +1 - Operatori BINARI= 2 operanzi, de ex. 1+1 - Operatori TERNARI ( operatorul de in-line if: ?), de ex. A > B ? True : False. În funcție de scopul operatorilor aceștia pot fi împărțiți în mai multe categorii: - Op. Aritmetici: +, -, *, /, % - Op. Relaționali: , = - Op. de Egalitate: ==, != - Op. Logici: && (și), || (sau) - Op. la nivel de bit: &, ^ (XOR), | - Op. de incrementare sau decrementare: ++, - - - Op. de atribuire: =, *=, += - Op. de shiftare: >>,. Tipul pointer: declarare, proprietăți (tipuri de pointeri) Pointer= o variabilă care conține adresa altei variabile. Declarare: un pointer se declară folosind tip *numePointer, astfel pointer-ul va indica spre o variabilă de tipul specificat. La nivel de pointeri se definesc doi operatori uzuali: * și &. & = op. de referențiere - întoarce adresa din memorie a operandului. *= op. de dereferențiere - întoarce valoarea înregistrată la adresa respectiva. Proprietăți ale pointerilor: - Se pot face atribuiri; - Pointerul poate primi valoarea null; - Se pot face comparații între pointeri de același tip; - Se poate face adunarea între un pointer și un întreg; - Se poate face incrementare și decrementare; - Se poate face diferența între doi pointeri de același tip; - Se pot crea pointeri la funcții. Tipuri de pointeri: int, float, char și void. Pointerul void specifică absența unui tip, deci poate pointa la orice tip. Acest tip de pointer nu pot fi dereferențiați direct, deci trebuie făcută conversie la un tip concret mai întâi. Alocarea dinamică a memoriei Se referă la alocările de memorie efectuate în timpul execuției programului cu ajutorul unor rutine de management a memoriei. În limbajul C, alocarea dinamică se realizează prin diversele variante ale funcției malloc(), iar eliberarea zonelor dinamice se face prin funcția free(). În C++ s-a introdus alocarea dinamică în structura limbajului, astfel avem operatorii new și delete. Operatorul new alocă memorie în heap și dacă alocarea s-a făcut cu succes returnează adresa zonei de memorie alocată, sau 0 dacă alocarea nu s-a putut face. HLL Mechanism în contextul alocării dinamice: - Se declară o variabilă pointer p; - Se alocă variabila dinamică prin operatorul new aplicat unui tip, iar rezultatul e atribuit lui p; - Orice acces la variabilă alocată se face prin intermediul lui p. Programare orientată pe obiect (Breazu M. - Anul II) Explicați de ce se spune că moștenirea multiplă creează un graf orientat aciclic Prin moștenire o clasă poate folosi funcționalitățile unei alte clase. Clasa din care se moștenește se numește clasa de baza, iar clasa care moștenește altă clasă se numește clasa derivată. Relația dintre cele două clase este unidirecțională (clasa de baza —> clasa derivată). O clasă poate să fie clasă de bază pentru mai multe clase, astfel se crează o structură de tip arbore. În cazul moștenirii simple, ramurile arborelui nu se unesc pe nivelele inferioare. În C++ o clasă poate să aibă mai multe clase de bază, astfel ramurile arborelui ajung să se unească, formând un graf orientat. Graful este aciclic deoarece legăturile nu se pot întoarce asupra altor clase care sunt deja clase de bază. Care este legătura între moștenire și abstractizare? Clasa abstractă = clasa care are un scop atât de general că nu conține suficiente atribute sau operații pentru a reprezenta un obiect al lumii reale. Clasa abstractă există doar pentru a putea fi moștenită de alte clase. Compilatorul nu permite crearea obiectelor din clasa abstractă. O clasă abstractă are cel puțin o metodă pură. Metodă pură= metodă fără corp, neimplementată, are următoarele caracteristici: La declarare, funcția este practic inutilă, clasa nefiind moștenită; Clasa care conține o metodă pură este abstractă; Clasele care moștenesc clasa abstractă trebuie să implementeze metodele pure; Fiecare clasă derivată este o formă mai concretă a clasei de bază, obiectele claselor derivate pot fi folosite oriunde este așteptat un obiect al clasei de bază (polimorfism); Permite reutilizarea codului definit în clasa de bază. Care este legătura între polimorfism și moștenire? Principalul avantaj al moștenirii este că putem trata clasele din ierarhia de moștenire ca și cum ar fi instanțe ale clasei din vârful ierarhiei. Acest lucru se numește polimorfism - obiectele cu caracteristici comune pot fi tratate unitar. Polimorfismul în C++ apare doar în contextul moștenirii. În C++ polimorfismul este introdus prin intermediul funcțiilor virtuale. Moștenire= crearea unei clase numită extinsă sau derivată, din altă clasă numită clasă de bază. Polimorfism= poli- multe; morphos- forme. Polimorfism= tratarea uniformă a obiectelor din clase diferite. Cu ajutorul moștenirii se asigură implementarea conceptului de polimorfism. Diferența dintre overloading și overriding Ambele se referă la metodele claselor. Supraîncărcarea (overloading) = permite definirea mai multor metode cu același nume, însă lista parametrilor trebuie să fie diferită (alte tipuri, altă ordine între tipuri). Redefinire (overriding) = supraîncărcarea unor metode dobândite prin moștenire; metoda nouă trebuie să aibă același prototip ca cea pe care o redefinește. Clase și obiecte Clasa = entitate asemănătoare cu o structură, cu diferența că membrii unei structuri sunt implicit publici, iar membrii unei clase sunt impliciți privați; grupează într-o entitate o listă de variabile și metode care să opereze asupra lor. Obiect = instanță a unei clase. Drepturi de acces într-o clasă În general: Public: membrii cu acest atribut pot fi accesați atât din interiorul clasei cât și din afara acesteia;  Privat: membrii cu acest atribut pot fi accesați doar din interiorul clasei. În contextul moștenirii, pe lângă public și privat mai avem și protected. Acesta se comportă ca și privat pentru incapsulare, dar ca și public pentru moștenire. Moștenirea Moștenirea la nivelul claselor este folosită pentru refolosirea codului unei clase de către una nouă. Prima este clasa de bază, a doua este cea derivată. Drepturile de acces când aplicăm derivarea: - Public: public și protected rămân neschimbate, private este inaccesibil; - Protected: public și protected devin protected, private este inaccesibil; - Private: public și protected devin private, private este inaccesibil. Incapsularea = ascunderea caracteristicilor și a modului de funcționare a unor obiecte: se realizează prin modificatorii de acces private și protected. Metodele și membrii private nu sunt accesibili decât din interiorul obiectului. Polimorfism Apare în contextul moștenirii. = tratarea uniformă a obiectelor din clase diferite, însă legate printr-o clasă de bază comună. Clasele derivate pot fi tratate ca și clasele de bază, referințe la clasele de bază pot referi obiecte de tipul claselor derivate. Constructori și destructori Constructor = metoda cu numele clasei și care nu are tip returnat. Destructor = metoda cu numele clasei precedat de caracterul tilda, fără tip returnat. Constructorul se apelează primul la instanțierea unui obiect (new) și este de regulă pentru inițializarea membrilor. Destructorul se apelează când obiectul este șters din memorie (delete) și este folosit pentru acțiuni de eliberare de memorie alocată dinamic și care ar rămâne blocată altfel. Operatorul new, constructor și rol Operatorul new permite alocarea dinamică a memoriei în heap pentru un obiect. Dacă are succes returnează un pointer la structura de date, dacă nu returnează 0 sau aruncă o excepție. Legături statice și dinamice la apelul funcțiilor Metodele statice, cele non-statice și cele non-virtuale sunt legate static la compilare. Adresa de salt este calculată la compilare și este aceeași la fiecare rulare a programului. Metodele virtuale au adresele păstrate într-o tabelă VMT. Legarea este dinamică, adresele metodelor fiind cunoscute și calculate doar la rulare. Nu vor fi aceleași pentru rulări diferite. Tabela metodelor virtuale VMT Tabela VMT este folosită pentru a păstrat referințele la funcțiile declarate virtual. Există pentru fiecare clasă ce conține o metodă virtuală. În cazul unui apel al unei funcții virtuale, adresa acesteia este căutată în tabelă și apoi lansată. Această legare se face runtime. La derivarea unei clase noi dintr-una cu metode virtuale, tabela VMT este copiată și acesteia. În cazul în care o metodă este redefinită, intrarea corespunzătoare din VMT este înlocuită cu adresa acesteia. Vechea metodă poate fi lansată și ea însă explicitând clasa de care aparține. Soluții de tratare a excepțiilor Se folosește mecanismul try catch. În blocul try adăugăm secvența de cod care ar putea arunca o excepție, iar în blocul catch prindem excepția și o gestionăm, fie prin trimiterea unui mesaj de eroare sau prin alte metode care permit continuarea rulării programului. Se poate adăuga și un bloc finally, care se execută indiferent dacă avem o excepție sau nu. Dacă avem mai multe blocuri catch (secvența din try poate arunca mai multe excepții) acestea sunt parcurse în ordine. Durata de viață și vizibilitatea variabilelor Se pot defini mai multe tipuri de variabile: - Variabile globale - Durata de viață: pe toată durata execuției programului; - Vizibilitate: în toate metodele, însă doar în modulul curent. - Variabile locale - Durata de viață: de la locul declarării și până la ieșirea din corpul funcției sau a structurii delimitată cu acolade; - Vizibilitate: în interiorul funcției sau al structurii în care a fost declarată. - Variabile statice - Durata de viață: valorile lor rămân și la ieșirea din funcție, iar la apelul următor aceasta poate fi folosită în continuare; - Vizibilitate: doar în interiorul funcției. - Variabile externe - Durata de viață: pe toată durata execuției programului; - Vizibilitate: în toate modulele unde este declarată. Transfer prin valoare și transfer prin referință Se referă la transferul parametrilor la apelul metodelor. Transferul prin valoare copiază valorile parametrilor în parametrii formali, cadrul de stivă aferent apelului funcției. Modificările aduse asupra acestor metode nu influențează valorile variabilelor originale. Transferul prin referință transmite funcției referințele la variabilele care se doresc a fi parametri pentru funcție. Modificările asupra parametrilor în interiorul funcției se păstrează la ieșire. Sintaxa pentru referință: tip& nume_variabilă la declarare, normal la folosire (C++), în C# se folosește cuvântul cheie ref Ce structuri de date se folosesc la funcții? Dar în cazul structurilor obiectuale? Funcții: structura de stivă. Obiecte: structura heap. Fiecare obiect are o stare și o comportare și o identitate. Explicați propoziția. Metodele îi dau obiectului comportamentul, iar membrii îi dau identitatea. !!! BONUS !!! - Poze cu cod ce trebuie explicate (moștenire, polimorfism, ce afișează?) Paradigme de programare (Sima D.) Ce relație există între structurile: coadă cu priorități, listă sortată și min/max heap? Lista sortată - structură de forma unui lanț formată din noduri conținând valori ordonate; Heap - structură bazată pe arbori, cu proprietatea că dacă B e copil pentru A atunci A e >= sau îmbunătățire a vitezei de operare; Nu mai este necesară suprapunerea operațiilor TLB peste operațiile cache, fiindcă nu mai este necesară translatarea adresei virtuale în adresă reală în cazul ciclurilor cu hit în cache. Dezavantaje: Existența unor legături între anumite adrese virtuale, care aparțin unor procese și care coexistă în cache. Este posibil ca două adrese virtuale diferite, care aparțin a două procese diferite să conducă (prin translatare) la aceeași adresă reală. În sistemul de gestiune a memoriei identificăm algoritmi de înlocuire relativi la: memoria cache, memoria virtuală, TLB. Pentru fiecare caz explicați rolul algoritmului și modul principal de implementare. Pentru cache: Înlocuire aleatoare: de exemplu, un numărător asociat întregului cache poate fi incrementat periodic. Valoarea curentă din acesta reprezintă linia de înlocuit. First-in First-out: selectează pentru înlocuire linia care se află de cel mai mult timp în cache. Algoritmul FIFO poate fi implementat în mod natural cu o memorie FIFO sau cu un numărător; LRU: se înlocuiește linia din cache cea mai puțin recent referită (utilizată). Se implementează prin numărătoare, stiva de regiștri, matrice de biți de stare. Pentru memoria virtuală: Înlocuire aleatoare: la activarea excepției page fault, acest algoritm realizează o selecție aleatoare asupra paginii care va fi evacuată din MP;  FIFO: la activarea excepției page fault, FIFO va evacua pagina din MP care se află de cea mai lungă durată. Se poate implementa printr-o coadă circulară; LRU: la page fault, va evacua din MP pagina care n-a mai fost referită de cea mai lungă perioada de timp; Working Set: se bazează ca fiecare program are propriul working set, astfel înlocuiește pagina care n-a mai fost referită în intervalul T. Pentru TLB: Algoritmii sunt similari cu cei de la cache. Algoritmul de înlocuire a unei intrări în TLB este însa complet hardware. Rezumați caracteristicile esențiale ale arhitecturilor RISC și CISC. Evidențiați avantaje și dezavantaje ale fiecărei arhitecturi. RISC: - Set redus de instrucțiuni care include instrucțiuni simple. Memorii cache on chip, număr mare de registre, un compilator care maximizează utilizarea registrelor și încearcă optimizarea cu structura pipeline; - A: viteză de procesare, timpul de proiectare și costul proiectării sunt mici; - D: necesită memorie rapidă, performanța e dependentă de eficiența compilatorului. CISC: - Set amplu de instrucțiuni, multe moduri de adresare, formate de instrucțiuni de lungime variabilă; - A: nu necesită compilator complicat, lucrează mai eficient cu memoria folosind mai puține instrucțiuni ca la RISC. - D: performanța per total mai scăzută (frecvențe CPU mai mici), complexitate hardware din chip pentru a putea satisface toate funcțiile. În concluzie, proiectarea procesoarelor RISC ar putea fi îmbunătățită prin utilizarea anumitor principii CISC. OPM + SOAC + AA (Florea A. - Anul III + IV) De ce nu este suficientă doar optimizarea unităților secvențiale de program- obiect (basic-blocks), fiind necesară optimizarea (globală a) întregului program? În ce constau dificultățile optimizării globale? Soluții de principiu. Paralelismul la nivelul basic-blockurilor este relativ scăzut, la fiecare 2/3 instrucțiuni una fiind de salt. Așadar, pentru mărirea nivelului de paralelism este necesară suprapunerea execuției unor instrucțiuni situate în basic-blockuri diferite (software pipelining, loop unrolling), ceea ce conduce la ideea optimizării globale. Care sunt motivele pentru care microprocesoarele superscalare au un succes comercial superior celor cu paralelism exploatat prin optimiz ri de program (“scheduling” static – spre exemplu microprocesoare tip VLIW, EPIC etc.) ? Microprocesoarele cu scheduling dinamic al instrucțiunilor (superscalare) au un succes comercial net superior celor cu paralelism exploatat prin optimizări de program deoarece sunt mai ușor de scalat, de “programat”. Dacă se vrea a se modifica un cod pentru a face altă operație, trebuie modificată optimizarea la nivelul arhitecturii, pe când la cele superscalare nu este nevoie de acest lucru, optimizarea se face la nivel de compilator. Astfel, microprocesoarele superscalare sunt mult mai bune în domeniul calculatoarelor de uz general. Procesoare superscalare Procesoarele care inițiază execuția mai multor operații într-un ciclu se numesc procesoare cu execuție multiplă a instrucțiunilor. Un astfel de procesor aduce don cache-ul de instrucțiuni una sau mai multe instrucțiuni simultan și le distribuie spre execuție în mod dinamic sau static, multiplelor unități de execuție. Principiul acestor procesoare constă în existența mai multor unități de execuție paralele, care pot avea latențe diferite. Pentru a facilita procesarea acestor instrucțiuni, acestea sunt codificate pe un singur cuvânt de 32/64 biți. Dacă decodificarea, detecția dependențelor, rutarea și lansarea lor în ă execuție din buffer-ul de prefetch înspre unitățile funcționale se fac prin hardware ==> procesor superscalar. Arhitectura lui Tomasulo Arhitectura este una de tip superscalar având deci mai multe unități de execuție, iar algoritmul de control al acestei structuri stabilește, relativ la o instrucțiune adusă, momentul în care aceasta poate fi lansată în execuție și respectiv unitatea de execuție care va procesa instrucțiunea. Arhitectura permite execuția multiplă și Out of Order a instrucțiunilor și constituie modelul de referință în reorganizarea dinamică a instrucțiunilor într-un procesor superscalar. De asemenea, algoritmul de gestiune aferent arhitecturii permite anularea hazardurilor WAR și WAW prin redenumirea regiștrilor, fiind deci posibilă execuția Out of Order a instrucțiunilor și în aceste cazuri. Așadar, singurele hazarduri care impun execuția In Order sunt cele de tip RAW. BTB (Branch Prediction) Deși o predicție poate fi corectă, de multe ori adresa de salt nu este disponibilă în timp util (la finalul fazei IF). Timpul necesar calculului noului PC are un efect defavorabil asupra ratei de procesare. Soluția la această problemă este dată de metoda de predicție numită “branch target buffer” (BTB). Un BTB este constituit dintr-un BPB (branch prediction buffer) care conține lângă biții de predicție noul PC de după instrucțiunea de salt. Astfel ar crește performanța, nefiind nevoie de un ciclu de aducere a acestei instrucțiuni, dar în schimb ar crește costurile de implementare. Arhitecturi superscalare vs paralele Procesoare paralele = existența mai multor unități de execuție paralele care pot avea latențe diferite. Procesoare superscalare = procesoare paralele pentru care decodificarea instrucțiunilor, detecția dependențelor de date dintre ele, rutarea și lansarea lor în execuție din bufferul de prefetch se fac prin hardware.  Limit ri arhitecturale ale paradigmei superscalare și independente de caracteristicile microarhitecturale, referitoare la: maximizarea ratei de aducere a instruc iunilor din memorie și maximizarea ratei de execu ie a instruc iunilor. Soluții de principiu. a) Maximizarea ratei de aducere a instrucțiunilor din memorie Rata de aducere a instrucțiunilor este limitată de instrucțiunile de salt. Procesul poate aduce din memorie doar un singur basic block (= secvență de instrucțiuni dinamice) în medie 6 instrucțiuni/ ciclu din cauza instrucțiunilor de salt. Această limitare se numește fetch bottleneck (sau limitarea producătorului) Soluția: folosim o structură trace cache (TC) = o memorie cache de instrucțiuni care conține basic blockuri succesive, pe care procesorul le-a executat anterior. O intrare în TC conține un trace de basic blockuri. b) Maximizarea ratei de execuție a instrucțiunilor Rata de execuție a instrucțiunilor este limitată de calea critică din program (= cel mai lung lanț de dependențe prin hazarduri RAW măsurat în cicli CPU). Această limitare se numește issue bottleneck (sau limitarea consumatorului). Alte limitări sunt: hazarduri structurale, hazarduri de ramificație și mecanismul de aducere a instrucțiunilor din memorie. Soluția: reutilizarea dinamică a instrucțiunilor (= instrucțiunile cu același input să nu se mai calculeze de mai multe ori) și predicția valorilor. Care sunt principalele avantaje ale tehnicilor de reutilizare dinamic a instruc iunilor ? De ce este dificil detectarea reutilizabilit ții unei funcții HLL (High Level Language) prin schemele actuale de reutilizare dinamic a instruc iunilor ? Avantaje: - La reutilizarea unei instrucțiuni rezultatul său devine cunoscut mai devreme decât în situația în care s-ar procesa normal, scurtcircuitând unele nivele de structură pipeline, permițând altor instrucțiuni dependente de aceasta să fie procesate mai rapid; - Reducerea penalităților datorate predicției eronate a adreselor destinate în cazul instrucțiunilor de salt, prin reutilizarea codului succesor punctului de convergență; - Îmbunătățește timpul de execuție al instrucțiunilor, crește gradul de paralelism al arhitecturii. ă ţ ţ ţ ă ă ţ ă ă ţ Detectarea reutilizabilității unei funcții HLL prin schemele de reutilizare dinamică a instrucțiunilor este dificilă deoarece se folosesc apeluri indirecte de funcții (prin pointeri) și switch case-uri (se poate și polimorfism din programarea obiectuală). HLL, HSA HSA (Hatfield Superscalar Architecture) Caracteristica principală este exploatarea paralelismului la nivelul instrucțiunii, într-un mediu superscalar, prin scheduling agresiv aplicat codului sursă în momentul compilării. HLL Un limbaj de programare de nivel înalt este un limbaj de programare cu o puternică abstracție din detaliile computerului. În comparație cu limbajele de programare de nivel scăzut, poate folosi elemente de limbaj natural, poate fi mai ușor de utilizat sau mai portabil pe alte platforme. Astfel de limbaje ascund detaliile operațiunilor CPU, cum ar fi modelele de acces la memorie și gestionarea domeniului de aplicare. Limitarea issue-bottleneck. Reutilizarea dinamică a instrucțiunilor Rata de execuție a instrucțiunilor este limitată de calea critică din program (= cel mai lung lanț de dependențe prin hazarduri RAW măsurat în cicli CPU). Această limitare se numește issue bottleneck (sau limitarea consumatorului). Pentru a evita această limitare există tehnica de reutilizare dinamică a instrucțiunilor. Mai multe instrucțiuni, având aceleași intrări, nu trebuie să fie executate în mod repetat - rezultatele lor pot fi obținute dintr-o structură de date cache în care au fost salvate anterior. Care sunt principalele avantaje ale tehnicilor de predicție dinamică a valorilor? Ce tipuri de asemenea predictoare există? (Ce tipuri de asemenea predictoare … lipsesc?) Avantaje: - Se reduc hazardele RAW; - Datorită exploatării gradului de localitate pentru instrucțiunile ALU se reduce timpul de execuție pentru instrucțiunile mari consumatoare de timp (DIV/ MUL) dar și hazardele RAW; - Exploatează vecinătatea valorii prin predicția acestei valori, reducând atât timpul mediu de acces la memorie cât și necesarul de lărgime de bandă al memoriei; - Predicția valorii nu scurtcircuitează execuția - instrucțiunile trebuind să se execute pentru a verifica ulterior predicția. Timpul total de execuție a unei instrucțiuni va fi limitat astfel de latența sa de execuție și verificare. Câștigul constă în faptul că se deblochează instrucțiuni dependente prin procesul de predicție a valorii. Tipuri de predictoare: - Computaționale: prezic pe baza unor valori anterioare, folosind o formula recurentă, de exemplu predictorul LastValue sau Incremental; - Contextuale: prezic următoarele valori pe baza unui pattern care e generat repetitiv în secvența de valori. De exemplu PPM și predictoarele adaptive pe 2 nivele; - Hibride: folosesc 2 sau mai multe predictoare diferite, ideea de bază e următoarea - dacă un predictor greșește celălalt predictor e lăsat să prezică. Optimizarea dinamică a procesării programelor Pentru fetch bottleneck - TC, pentru issue bottleneck - DIR și VP (a se vedea întrebările despre fb și ib) Predicția statică și dinamică Statică Caracterizată de faptul că predicția saltului pentru o anumită istorie a sa este fixă, bazată în general pe studii statistice ale comportamentului salturilor. Astfel, dacă un salt la care anterioarele trei instanțe au fost taken (T) poate fi predicționat că și saltul curent se va face (T). Dinamică Datorită faptului că predictorul propriu-zis este implementat prin automate finite de stare, mai multe sau mai puțin complexe, aceste scheme au un caracter dinamic, comportarea lor adaptându-se funcției de “istoria” saltului respectiv. Predictori de salturi BPB - reprezintă o mică memorie adresată cu cei mai puțini semnificativi biți ai PC-ului aferent unei instrucțiuni de salt condiționat. Cuvântul BPB este construit în principiu dintr-un singur bit. Dacă acesta e 1 logic, atunci se prezice că saltul se face (T), iar dacă e 0 se prezice că saltul nu se va face. GAg - e alcătuit dintr-o tabelă PHT (Prediction History Table) care este adresată cu un index rezultat din concatenarea PClow + HR (History Register pe k biți = contextul în care se situează saltul în program) PAg - predicționează pe baza a 3 informații ortogonale, toate disponibile pe timpul fazei IF: istoria HRg a anterioarelor salturi corelate (taken/ not taken), istoria saltului curent și PC-ul acestui salt. PPM - predicția partial matching se bazează pe algoritmul de predicție prin potrivire parțială (PPM). Algoritmul PPM de ordin m este alcătuit din m+1 predictoare Markov. Un predictor Markov de ordinul j predicționează bit-ul următor pe baza pattern-urilor precedente de j biți. Predictori de valori Principalele tipuri de predictoare sunt: Computaționale, Contextuale și Hibride. (A se vedea întrebarea unde se discută despre ele) Predictoarele Computaționale pot predicționa secvențe constante și incrementale. Predictoarele contextuale pot predicționa și secvențe non-incrementale. Sisteme de Operare (SO) - (Breazu M. - Anul III) Partiționarea HDD: scop și metoda de realizare Partiția = zona contiguă pe disc delimitată de două adrese. Prin operația de partiționare discul fizic este împărțit în mai multe discuri logice. Fiecare dintre acestea se comportă ca și cum ar fi un disc fizic separat. Informațiile despre partiționarea discului sunt stocate într-un tabel de partiție principală - localizat pe primul sector fizic al discului (0,0,1). Scopul partiționării: - Organizarea discului; - Folosirea discurilor mai mari decât pot fi manipulare de structura logică a SO; - Permite stocarea de SO și sisteme de fișiere diferite pe același disc; Avantaj al partiționării: organizarea datelor, toleranța la defecte crescută deoarece fiecare partiție are un sistem de fișiere diferit. Descrieți noțiunea de preemptivitate în planificarea unității centrale Preemptivitate = trăsătura SO de a putea interveni și de a muta cu forța un proces în defavoarea celorlalte. SO este preemptiv. Fire de execuție vs Procese Proces = program aflat în execuție. Fir de execuție = succesiunea secvențială de instrucțiuni care se execută în cadrul unui proces. Un fir de execuție este similar unui proces în sensul că are un început, o secvență de execuție și un sfârșit. Diferența dintre acestea constă în faptul că un fir de execuție nu poate rula independent ci trebuie să ruleze în cadrul unui proces. În cadrul unui proces se pot executa simultan mai multe fire de execuție. Deosebiri: - Fiecare proces are propria sa memorie (spațiu propriu de adrese); - La crearea unui nou proces se copiază datele și codul procesului inițial, firele de execuție copiază doar codul; - Firele de execuție au acces la aceleași date (datele procesului care le conține). Sincronizarea proceselor: metode de realizare = înlănțuirea automată a stărilor unor procese concurente, prin blocarea și deblocarea automată a proceselor în execuție. Avem două mecanisme de sincronizare: semafor și monitor. Semafor: - Pentru fiecare resursă partajată din sistem există un bit semafor s inițializat cu 1 și o listă de procese în așteptarea resursei; - Alocare: cerere de la un proces (s - -), dacă s=0 atunci resursa este alocată și procesul este pus în coada de așteptare; - Dezalocare: un proces eliberează resursa (s + +), primul proces din coadă primește resursa mai departe; - Funcțiile de A și D trebuie să fie concurente. Monitor: - Conține un set de variabile și operatori definiți de programator; - Un singur proces poate fi activ în cadrul unui monitor; - Sincronizarea se face prin variabile de tip condition și operatorii wait() și signal(). Wait suspendă procesul pană când alt proces folosește signal. Mecanisme de sincronizare directă (prin comunicare între procese): Cu ajutorul unor funcții preemptive ale sistemului de operare, care permit deblocarea unui proces care a intrat în starea de așteptare. Concomitent, se poate realiza și schimbul de date între cele două procese, utilizând directive ale sistemului de operare de tipul SEND, RECEIVE. Memoria virtuală: implementare la nivelul SO Memoria reală (MR)= capacitatea memoriei interne Memoria virtuală (MV) = MR este suplimentată de cea externă, prin tehnica de swapping (= un proces aflat în așteptare se evacuează temporar pe disc, eliberând MP ocupată; reluarea execuției se face prin reîncărcarea sa de pe disc în memorie) Avantaje: - Se simulează o memorie mai mare decât cea fizică existentă; - Se îmbunătățește folosirea resurselor sistemului de calcul (CPU + memorie). Implementare: - Folosind o tabelă de pagini (indică adresele de început ale paginilor în memorie, memoria putând fi alocată astfel noncontiguu). Ajutor hardware - TLB - cachează intrările din tabela de pagini. Rolul SO și hardware în tratarea unei excepții page fault Page fault = întreruperea determinată de încercarea de accesare a unei pagini care nu este în memorie și va trebui adusă pe disc. Rutina de tratare a întreruperii de pagină execută: - Se examinează adresa solicitată pentru a vedea dacă este o adresă permisă (nivel H); - Dacă adresa e invalidă procesul este încheiat anormal, altfel se cere SO-ului să încarce pagina (nivel H); - Se caută un cadru liber (nivel SO); - Se solicită o operație I/O de încărcare a paginii (nivel SO); - Modifică tabela de pagini pentru a indica existența paginii în memorie; - Reînceperea instrucțiunii care a determinat page fault. SO: rolul resurselor H și S Un sistem computer poate fi împărțit în: - Hardware (H): CPU, memorie, dispozitive I/O; - SO; - Aplicații; - Utilizatori. SO se comportă ca un intermediar între utilizator și H. Scopul lui este de a furniza un mediu în care un utilizator poate executa aplicațiile. În plus, trebuie să folosească în mod eficient resursele pe care le alocă aplicațiilor. O definiție mai comună este aceea că SO este un program care rulează tot timpul pe calculator, de obicei numit kernel, toate celelalte programe fiind aplicații. H - componentele care realizează fizic calculele și acțiunile cerute de utilizator prin intermediul aplicațiilor, intermediate de SO. S - modul în care sunt folosite resursele H de către SO pentru a servi aplicațiile și utilizatorii. Baze de Date (Butean A. + Crăciunean V. - Anul III) Caracteristicile modelului relațional pentru baze de date DB reprezintă o modalitate de stocare și organizare a datelor pe un suport extern, cu posibilitatea regăsirii acestora. DB sunt relaționale deoarece sunt compuse din tabele care sunt interconectate între ele. În modelul relațional datele sunt memorate în tabele. Pe lângă tabele, o DB relațională mai poate conține: indecși, proceduri stocate, triggers, utilizatori și grupuri de utilizatori, tipuri de date, mecanisme de securitate și de gestiune a tranzacțiilor, etc. Ce se înțelege prin concurență și cum se rezolvă aceasta la nivelul unui SGBD relațional? SGBD = o colecție de programe care gestionează structura unei DB, controlează accesul la date, translatează cererile utilizate în codul necesar pentru procesarea acelor cereri, le procesează și returnează rezultate către utilizator. Concurența DB apare atunci când mai mulți utilizatori vor să acceseze aceleași date simultan => SGBD trebuie să mențină integralitatea DB. În esență, un SGBD asigură concurența la modul următor: - Când 2 sau mai multe persoane vor să vizualizeze aceleași date fără a le modifica însă, totul este în ordine și nu trebuie luate măsuri; - Când cel puțin o persoană dorește să facă modificări asupra unor date care în același timp sunt vizualizate de către alte persoane, atunci SGBD-ul trebuie să stocheze mai multe copii ale datelor și să transfere toate modificările copiilor într-o singură versiune atunci când întreaga operațiune este terminată; - Când mai mulți utilizatori încearcă să facă modificări asupra acelorași date un SGBD rezolva problema folosind mecanismul de locking. Utilizatorul care a efectuat primul modificarea datelor le blochează, ceilalți utilizatori neputându-le modifica până când operația efectuată de acesta nu este încheiată. Care sunt etapele de proiectare a unei DB? Proiectare = transformarea modelelor informaționale în modele dependente de sisteme de gestiune a bazelor de date. Etape: - Proiectarea conceptuală: procesul de construire a unui model al informațiilor utilizat în cadrul unui domeniu de interes, independent de toate considerațiile fizice. - Proiectarea logică: procesul de constituire a unui model al informațiilor utilizat la modelarea unui domeniu de interes bazat pe un anumit model specific de date. - Proiectarea fizică: procesul de descriere a implementării DB pe mediile secundare stocate. Sunt descrise structurile de stocare și metodele de acces utilizate pentru a obține un acces eficient la date. Ce este o tranzacție și ce proprietăți are aceasta? ACID, proprietăți Tranzacție = secvență de acțiuni dintr-un program care citește și/ sau scrie date în baza de date și care satisface testul ACID, ea este încadrată în delimitatorii begin transaction și end transaction. ACID (Atomicitate, Consistență, Izolare, Durabilitate) Atomicitate: o tranzacție este executată fie în întregime fie deloc. Consistență: numai date valide vor fi scrise în DB. Dacă din anumite motive este executată o tranzacție care încalcă regulile de consecvență ale DB, întreaga tranzacție va fi reintrodusă și DB va fi restabilită la o stare compatibilă. Izolare: protejarea rezultatelor intermediare ale operațiilor din cadrul unor tranzacții concurente. Durabilitate: actualizările tranzacțiilor executate cu succes nu sunt niciodată pierdute. Ce se înțelege prin baze de date distribuite? Dar prin baze de date orientate obiect? DB distribuite = DB logic integrate dar fizic distribuite pe mai multe sisteme de calcul. Utilizatorul unei asemenea DB o vede ca pe o DB unică, compactă la nivel logic, cu toate că în realitate ea este distribuită pe mai multe calculatoare legate între ele la nivel fizic. DB orientate pe obiect = permit crearea de obiecte complexe din componente simple, fiecare având propriile atribute și propriul comportament. Un mode de date orientat pe obiect are la baza noțiunea de entitate conceptuală și definește un obiect ca o colecție de proprietăți care descriu entitatea. Rețele de Calculatoare (Brad R. - Anul III + IV) Care sunt nivelele ISO-OSI (Stiva OSI) ale rețelei de calculatoare și care este rolul lor? 1. Nivelul fizic: transmite datele de la un calculator la altul prin intermediul unui mediu de comunicare; 2. Nivelul legătură de date: corectează erorile de transmitere apărute la nivelul 1, realizând o comunicare corectă între două noduri adiacente ale rețelei. Biții se transformă în cade, cărora le sunt adăugate informații de control; 3. Nivelul rețea: asigură dirijarea unităților de date între nodul sursă și nodul destinație; 4. Nivelul transport: face conexiunea între 2 host-uri detectând și corectând erorile pe care nivelul 3 nu le tratează; 5. Nivelul sesiune: permite utilizatorilor de pe mașini diferite să stabilească între ei sesiune de comunicare. Rezolvă modalitatea de transfer a datelor simplex sau duplex. Gestionează jetonul. 6. Nivelul prezentare: face operații de transformare a datelor în formate înțelese de entitățile care intervin într-o conexiune. 7. Nivelul aplicație: rol de fereastră de comunicare între utilizatori. Medii de comunicație. Enumerare. Topologii de rețea. Principalele medii de transmisie: - Fire torsadate; - Cablu coaxial; - Fibră optică; - Unde radio (Wi-Fi). Topologia unei rețele = amplasarea fizică a host-urilor și a celorlalte componente. Poate fi: - Tip magistrală (bus): constituită dintr-un singur cablu la care sunt conectate toate nodurile; - Tip stea: toate nodurile sunt conectate la un nod central care joacă rol particular în funcționarea rețelei; - Tip inel: noduri interconectate cu ajutorul unui cablu de transmisie comun și formează o buclă închisă; - Tip plasă (mesh): fiecare nod e conectat cu celelalte noduri; - Tip arbore; - Fără fir (wireless). Rolul protocoalelor de acces la mediu. Exemple de protocoale. Protocol = ansamblu de convenții și reguli pe baza cărora se realizează transmiterea datelor. Rol - transmiterea mesajelor și tratarea coliziunilor care apar. Exemple: - Aloha (e cam la hoha asta, de aia se zice Aloha): fiecare stație poate să emită când dorește, dacă se intră în coliziune cu altă stație, stațiile vor detecta coliziunea datorită proprietății de reacție a difuziunii, vor aștepta o perioadă aleatoare de timp, după care vor încerca din nou să transmită; - CSMA: se ascultă în permanență mediul de comunicație, dacă e liber se poate emite, toate stațiile pot oricând să acceseze mediu de comunicație. Poate fi cu/ fără collision detection. - Token Ring; - Token Bus. Nivelul rețea. Funcționare. Rol. Exemplu de protocol. Nivelul de rețea = nivelul 3, răspunde cererilor de servicii ale nivelului de transport și adresează cereri ale nivelului legătura de date. El adresează mesaje și traduce adrese logice în adrese fizice. Acesta asigură livrarea pachetelor și alegerea optima a căilor de transmitere (rutare sau routing). Nivelul rețea trebuie să gestioneze traficul de rețea, congestiile și ratele de transfer de-a lungul linilor de transmisie. IP (Internet Protocol) este cel mai cunoscut protocol la acest nivel și este utilizat pentru interconectarea rețelelor de Internet. Este un protocol fără conexiune care permite transmiterea unor blocuri de date (datagrame). Nivelul aplicație. Servicii. Exemple de protocoale de serviciu. Nivelul aplicație = nivelul 7, cel mai înalt nivel. Acesta stabilește serviciile ce stau la dispoziția utilizatorilor rețelei. Este responsabil cu: - Inițierea și verificarea fiabilității transferului de date; - Refacerea erorilor; - Stabilește acordul de comunicare între parteneri; - Accesul la rețea; - Alocarea dinamică a adreselor IP (DHCP); - Transferul de fișiere (FTP). !!! BONUS !!! Cum sunt ultimele două întrebări pot să vină întrebări despre orice nivel din stiva OSI. Inteligența Artificială (Kretzulesku R. + Morariu D. - Anul III + IV) Căutarea euristică = metodă de căutare care folosește informație euristică. Informația euristică = acea informație despre proprietățile domeniului specific care ne ghidează spre soluție. Aceste informații sunt de obicei utilizate prin intermediul unei funcții, numită funcție de evaluare care indică măsura în care nodul respectiv este indicat pentru expandare. O metodă euristică s-ar putea să nu găsească întotdeauna cea mai bună soluție, dar soluția va fi bună și găsită într-un timp rezonabil. Este utilă pentru problemele a căror rezolvare ar lua foarte mult timp. Tehnici de învățare. Învățarea pe de rost. Învățare supervizată Algoritmul produce o funcție care stabilește corespondența între datele de intrare și rezultate scop. Un exemplu ar putea fi o problemă de clasificare, în cazul în care sistemul de învățare este de a eticheta o serie de valori folosind mai multe clase. Învățare nesupervizată Procesul de modelare se realizează pe un set de exemplu format numai din intrări de sistem. Nu există informații despre categoriile acestor exemple. Prin urmare, sistemul trebuie să fie capabil să recunoască modele, pentru a fi capabil de a eticheta noile intrări. Învățare parțial supervizată Combină cele două tipuri menționate mai sus cu scopul de a clasifica datele în mod corespunzător. Acesta ia în considerare date etichetate și neetichetate. Învățare pe de rost = memorare - se referă la salvarea cunoștințelor noi astfel încât atunci când sunt din nou necesare singura problemă va fi găsirea lor și nu un calcul repetat). Poate fi văzută ca un proces elementar de învățare, nu suficient de puternic pentru a obține o învățare inteligentă în Since, dar reprezintă o parte importantă în orice sistem de învățare. Cadre și scenarii Cadru = șablon general, în care datele noi sunt interpretate în termenii sau conceptele experienței dobândite anterior. Pentru a analiza o experiență nouă, se utilizează o structură deja existentă, în care se particularizează cu detaliile situației curente. Reprezentarea prin cadre favorizează prelucrarea bazată pe așteptare, deoarece nu contrazice orizontul de așteptare. Scenariu = modalitate de reprezentare a cunoașterii ce descrie o secvență stereotipă de evenimente într-un anumit context, adică situații care se repetă, păstrând aceeași structură. Scenariile sunt utile deoarece în lumea reală există diferite modele de apariție a evenimentelor, modele datorate relațiilor cauzale dintre evenimente. Aceste evenimente descrise într-un scenariu alcătuiesc un lanț cauzal (punct de start: condiții inițiale, punct final: rezultate). Arbori de joc Se aplică doar în cazul jocurilor care: - Au 2 jucători care mută pe rând, cunoscând la fiecare mutare pozițiile și alegerile posibile ale adversarului; - Jocul începe cu o stare specifică și se termină cu victoria unui jucător, sau egalitate; - Există reguli care definesc dacă o mutare e legală și care sunt efectele ei; Arborele de joc= reprezentare a tuturor partidelor posibile, starea inițială e în nodul rădăcină. Fiecare cale de la rădăcină la un nod final cu toate mutările ei = o partidă. Aplicații ale inteligenței artificiale - Rezolvă probleme dificile în chimie, matematică, geologie, inginerie, biologie, medicina la nivelul de performanță al experților umani; - Manipulează roboții pentru a realiza sarcini motoare repetitive; - Recunoașterea automată a formelor și sunetelor; - Algoritmi genetici; - Teoria jocurilor; - Rețele neuronale; - Sistemele expert; - Agenți inteligenți. Subdomenii ale inteligenței artificiale - Rezolvarea problemelor, de exemplu în domeniul jocurilor (dame, șah); - Înțelegerea limbajului, de exemplu programe de traducere care acumulează cunoștințe prin citirea de texte scrise și prin construirea unei DB interne; - Programare automată, folosite la sistemele care pot scrie programe pentru a descrie scopul lor, de exemplu descrierea în engleză a algoritmilor; - Robotică: mișcarea brațului unui robot, recunoașterea obiectelor și a umbrelor în scene vizuale. Reprezentarea cunoștințelor Reprezentare = mulțime de convenții pentru a descrie obiectele, în IA reprezintă o combinație de structuri de date pentru memorarea informației în programe și de proceduri de utilizare a acestor structuri pentru realizarea de interfețe. Reprezentările sunt alese de programator în funcție de date. Reprezentările sunt de două tipuri: - Declarative: cunoștințele sunt specificate prin descrierea lor, fără a indica modul în care vor fi utilizate; - Procedurale: cunoștințele de control necesare rezolvării problemei sunt înglobate în însăși reprezentarea dată. Algoritmi de căutare De obicei spațiul stărilor este reprezentat printr-un graf orientat în care fiecare nod este o stare și fiecare arc reprezintă aplicarea unui operator de transformare a unei stări într-o stare succesor. O soluție este o cale de la p stare start la o stare scop. Căutarea oarbă în spațiul stărilor: Dacă ordinea în care se iau în considerare stările e arbitrară, nefolosind informația specifică domeniului pentru a presupune (sau calcula) unde este mai probabil să se găsească soluția căutarea se numește oarbă. Căutarea oarbă în grafuri AND/OR: Se folosesc la problemele unde este nevoie de descompunerea unei probleme în probleme mai simple. Succesorii unui nod notat cu AND sunt subprobleme și trebuie rezolvate pentru a satisface nodul părinte. Nodurile notate cu OR sunt subprobleme alternative și fiecare dintre ele poate satisface nodul părinte. Căutarea euristică în spațiul stărilor: Dacă ordinea în care se iau în considerare se face ținând cont de o informație suplimentară despre proprietățile domeniului specific (informație euristică) avem o căutare euristică. Căutarea euristică într-un graf AND/OR: La fel ca și la căutarea oarbă în grafuri AND/OR, doar că se ține cont de informația euristică. Căutarea în arborii de joc: Este generat un arbore de joc, fiecare nod reprezintă o poziție în joc. Cea mai bună mutare este cea care duce la un nod cu valoare maximă. Rețele semantice Folosite ca o formă de reprezentare a cunoștințelor. Este reprezentată printr-un graf care are noduri (notate în figuri prin puncte, cercuri sau dreptunghiuri) și arce (notate cu săgeți). În mod normal nodurile reprezintă obiecte, concepte sau situații ale domeniilor, iar arcele sunt relații între acestea. Popularitatea folosirii rețelelor semantice a apărut datorită faptului că se pot deduce ușor ierarhiile moștenitoare. Regula min-max și alfa Procedura min-max e o tehnica de căutare în arbori de joc. Numele acestei proceduri vine din felul în care sunt evaluate nodurile. Dacă avem doi jucători A și B și presupunem că avem un arbore de joc în care A este max (A e max pt ca arborele este desenat din punctul de vedere al lui A) și B este min: - Valoarea pentru jucătorul A a unui nod cu succesori OR (un nod în care A alege următoare mutare) este maximul dintre valorile succesorilor săi; - Valoarea pentru jucătorul A a unui nod cu succesori AND (un nod în care B alege următoarea mutare) este minimul dintre valorile succesorilor săi. Nodurile notate cu OR - sunt alegeri pe care A le poate face, iar cele cu AND sunt alegeri pe care le face B și cărora A trebuie să le răspundă. Procedura alfa-beta încearcă să optimizeze numărul de noduri care sunt evaluate prin folosirea procedurii min-max. Procedura alfa-beta nu schimbă rezultatele algoritmului min-max, ea doar îl optimizează. Procedura se oprește să evalueze o mișcare atunci când s-a găsit cel puțin o posibilitate care e mai rea decât cele examinate anterior.