Vladimir Andrunachievici Institute of Mathematics and Computer Science

RO EN

PhD admission exam programme: Computer Science

Program pentru examenul de admitere in doctorantura Institutului de Matematică şi Informatică al AŞM, specialitatea "Informatica".

Analiza matematică.
Algebra liniară. Metode numerice în algebra liniară.
Logica matematică.
Analiza numerică.
Programarea matematică, control optimal.
Cercetări operaţionale.
Probabilitate şi statistică.
Teoria algoritmilor.
Bazele tehnice ale calculatoarelor, sisteme de operare.
Baze de date.
Reţele de calculatoare.
Proiectarea şi programarea reţelelor (PPS).
Inteligenţa artificială.
Limbaje formale şi automate. Tehnici de compilare (LFA).
Reprezentarea, stocarea şi procesarea informaţiei (RSPI).
Programarea obiect orientată (POO).
Programare funcţională. Programare logică (PP, PL).
Programare paralelă.
Literatura de specialitate.

Analiza matematică

Funcţii de o singură şi mai multe variabile. Funcţii continui şi proprietăţile de bază. Diferenţiala funcţiei. Aplicarea diferenţialei la estimarea erorilor. Formula lui Taylor şi aplicarea ei. Cercetarea funcţiilor la extrem. Extrema condiţionat. Funcţii implicite.
Integralele. Primitiva funcţiei şi integrala definită. Sensul geometric şi fizic, aplicarea integralelor. Integralele improprii. Integralele ce depind de parametri, diferenţierea şi integrarea după parametru.
Şiruri numerice şi funcţionale. Criteriile de convergenţă a seriilor. Diferenţierea şi integrarea seriilor funcţionale. Seriile de puteri şi proprietăţile lor. Seriile Fourie, criteriile de convergenţă.

Algebra liniară. Metode numerice în algebra liniară

Sisteme de ecuaţii liniare. Teorema de existenţă şi unicitate a soluţiei sistemului de ecuaţii liniare. Metodele numerice de aflare a soluţiilor sistemelor de ecuaţii liniare (Metoda Gauss, Jordan Gauss). Metodele iterative de aflare a soluţiilor sistemelor de ecuaţii liniare (Metoda lui Goues-Zeidel, metoda gradienţilor conjugaţi).
Matricele şi proprietăţile lor de bază, operaţiile asupra lor. Rangul matricei. Teorema despre rangul matricei. Matricea inversă şi aflarea ei.
Vectori proprii şi valori proprii. Polinomul caracteristic. Metodele de aflare a valorilor proprii şi a polinomului caracteristic. Forma diagonală a matricei.
Operatori liniari ai spaţiilor vectoriale. Matricele operatorilor liniari. Operatori liniari nedegeneraţi. Algebra operatorilor liniari.
Funcţii pătratice. Metoda lui Lagrange de reducere la forma canonică. Forma normală peste C şi R. Legea inerţiei. Metoda lui Jacobi de reducere la forma canonică. Funcţii pătratice pozitiv definite. Criteriul lui Sylvester.
Spaţii euclidiene. Inegalitatea Cauchy-Buneacovski-Schwartz. Sisteme ortogonale de vectori. Baze ortonormate. Grupul matricelor ortogonale.

Logica matematică

Operaţiile algebrei propoziţionale. Exprimarea unor operaţii prin altele.
Formulele calculului propoziţional. Axiome şi reguli de deducţie. Deducţia dintr-o listă de formule.
Teorema deducţiei şi aplicaţiile ei. Teorema echivalenţei. Necontradicţia calculului propoziţional şi completitudinea lui.
Logica predicatelor: funcţii logice, cuantificatori. Formule normale. Problema realizabilităţii.
Calculul predicatelor: axiomele şi regulile de deducţie. Necontradicţia calculului predicatelor. Principiul dualităţii.
Forme normale şi forme normale Scolem. Teorema Scolem. Problema completitudinii calculului predicatelor. Teorema Gödel.

Analiza numerică

Rezolvarea aproximativă a ecuaţiilor algebrice şi transcendente. Metoda coardelor, tangentelor, iteraţiei simple. Convergenţa.
Rezolvarea aproximativă a sistemelor de ecuaţii algebrice liniare. Metode exacte (Gauss, Gauss modificat, rădăcinii pătrate).
Rezolvarea aproximativă a sistemelor de ecuaţii algebrice liniare. Metode iterative (iteraţiei simple, Seidel). Convergenţa.
Interpolarea funcţiilor. Construirea polinoamelor de interpolare Lagrange, Newton. Eroarea de interpolare.
Integrarea numerică. Formule de cuadraturi (dreptunghiului, trapezului, Simpson). Estimarea erorilor.
Rezolvarea aproximativă a problemei Cauchy pentru ecuaţia diferenţială de ordinul întâi. Metode de tip Runge-Kutta.

Programarea matematică, control optimal

Extreme condiţionate şi necondiţionate ale funcţiilor de mai multe variabile. Condiţiile necesare şi suficiente de extrem necondiţionat, metodele gradient. Metodele funcţiilor de penalizare de aflare a extremelor condiţionate.
Problema programării matematice. Metoda factorilor Lagrange. Teorema Kuhn-Tucker. Metoda simplex de soluţionare a problemei programării liniare. Problema duală, teoremele de dualitate.
Problema transporturilor, metoda potenţialelor.
Problema programării matematice în numere întregi, metoda Gomory, metoda bound and branch. Problema fluxului maximal. Teorema Ford-Fulkerson. Problema de transport pe reţele.
Noţiune de joc. Jocurile matriceale, strategii pure şi mixte. Teorema Neumann. Legătura dintre jocurile matriceale şi programarea liniară.
Programarea dinamică. Principiul de optim al lui Bellman.
Problema de bază a calculului variaţional. Noţiune de prima şi a doua variaţie. Condiţii necesare de extrem. Ecuaţiile Euler.
Problema controlului optimal. Principiul lui Pontreaghin. Sisteme liniare. Problema de sinteză.

Cercetări operaţionale

Noţiune de graf, definiţii, proprietăţi generale, moduri de reprezentare. Tipuri de arbori, reprezentare, proprietăţi. Algoritmi de parcurgere a nodurilor unui graf. Partiţionarea grafului.
Problema drumului optimal în graf. Algoritmul lui Bellman-Kalaba.
Algoritmul Ford-Fulkerson pentru determinarea fluxului maximal în reţea. Teorema lui Ford-Fulkerson.
Modele de aşteptare cu două staţii. Ecuaţiile stărilor a lui Kolmogorov.
Modele de gestionare a resurselor. Modelul determinist fără deficituri. Parametri optimali.
Modele de planificare optimă a unei lucrări complexe cu resurse limitate.

Probabilitate şi statistică

Axiomatica Kolmogorov. Variabile aleatoare. Funcţii de repartiţie. Repartiţiile de bază (binomială, Poisson, geometrică, hipergeometrică, normală, exponenţială, X, Student).
Caracteristici numerice ale variabilelor aleatoare. Variabile aleatoare independente. Inegalitatea Cebisev. Legea numerelor mari. Legea tare a numerelor mari. Funcţii caracteristice. Teorema limita-centrală. Estimaţii de punct ale parametrilor repartiţiei, estimaţii nedeplasate, consistente.
Metoda pătratelor minimale. Metoda verosimilităţii maxime. Interval de încredere.
Verificarea ipotezelor statistice. Metoda Monte-Carlo. Procese stocastice, procese cu creşteri independente, brouniene, de fuziune. Ecuaţia Kolmogorov directă şi indirectă.

Teoria algoritmilor

Noţiune de algoritm, proprietăţile lui. Maşina Turing, problema decidabilităţii. Noţiune despre complexitatea algoritmilor, clasele de complexitate.
Calculabilitate. Funcţii primitiv recursive. Mulţimi recursive şi recursiv enumerabile.

Bazele tehnice ale calculatoarelor, sisteme de operare

Particularităţile arhitecturale ale calculatorului, principiul lui von Newmann. Evoluţia calculatoarelor moderne: structura, clasificarea.
Componentele fizice ale unui calculator: procesorul, memoria operativă, discuri dure, dischete, dispozitive periferice.
Noţiune de produs program: programe de sistem, programe aplicative, sisteme de programare, sisteme de operare, utilite.
Sisteme de operare (SO). Componentele unui SO: gestionarea proceselor, procesarea întreruperilor, gestionarea memoriei, planificarea funcţionării procesorului, sistemul de fişiere.
Sistemul de operare MS DOS. Componentele sistemului, funcţiile de bază, regimul pachet, configurarea sistemului, structura ierarhică a fişierelor.
Familia SO Windows: Windows 3.x, Windows 9x, Windows NT. Studiu comparativ MS DOS - WINDOWS. Principiile Plug and Play, Drag and Drop.
SO UNIX. Setarea şi resetarea sistemului. Componentele sistemului: nucleul (gestionarea proceselor, planificarea activităţii procesorului, procesarea evenimentelor şi a semnalelor, gestionarea memoriei) gestionarea fişierelor, instrucţiuni de intrare-ieşire. Studiu comparativ UNIX - MS DOS - Windows.

Baze de date

Modelul lumii reale şi baza de date. Structura şi componentele bazei de date. Modele de date. Modelul relaţional al datelor. Metode de acces la date. Indexare.
Teoria mulţimilor şi a conceptelor de bază ale modelului relaţional de date. Relaţie. Atributele, domeniile, tuplurile relaţiei. Algebra relaţională. Compactitudinea algebrei relaţionale. Operatorii algebrei relaţionale.
Integritatea modelului relaţional de date. Null -valori. Integritatea entităţilor şi integritatea referirilor. Strategii de menţinere a integrităţii referenţiale. Proiectarea bazelor de date. Anomalii în baze de date. Dependenţa funcţională între atributele relaţiei. Primele forme normale (FN1, FN2, FN3). Algoritmul normalizării.
Sisteme de gestiune a bazelor de date (SGBD). Structura şi funcţiile componentelor constituente al SGBD. Limbajul SQL de manipulare cu bazele de date. Versiuni concrete a limbajului. Categoriile de comenzi SQL.
Obiectele bazei de date. Tabele ca forma principală de prezentare a datelor. Manipularea cu tabele şi cu datele din tabele în limbajul SQL. Accesul concurent la baze de date. Tranzactii şi manipularea lor în standardul SQL.
Baze de date dinamice. Baze de date relaţionale în PROLOG. Manipularea datelor.

Reţele de calculatoare

Reţele de calculatoare. Metode de proiectare, funcţionarea şi clasificarea reţelelor. Arhitectura reţelelor.
Metode de marşrutizare a comunicărilor în reţea. Serverul reţelei, funcţiile de bază, componenţa.
Noţiune de LAN, tipuri de LAN, topologii de LAN. Modelul de referinţă ISO-OSI.
Hardware-ul LAN -urilor. Medii de transmitere, cabluri, hub, conectori etc. Standardul 802 LAN -802.3, 802.4, 802.5.
Noţiuni de bază despre protocoalele de reţea. Metode de acces la mediu. IP adrese.

Proiectarea şi programarea reţelelor (PPS)

Cerinţele către un Produs Program (PP). Clasificarea PP. Etapele ciclului de viaţă a PP. Documentaţia PP.
Planul proiectului unui Sistem Informatic (SI). Construirea proiectului logic şi a sarcinii tehnice a SI.
Modele de realizare a ciclului de viaţă a PP. Particularităţile metodei RAD.
Teorema de bază a programării şi consecinţele ei.
Metode generale şi clasice de soluţionare a problemelor. Clasificarea problemelor în funcţie de complexitatea logică de soluţionare a lor cu ajutorul calculatorul electronic.
Particularităţile funcţionale şi de arhitectură a sistemelor instrumentale pentru automatizarea construirii SI. Sisteme CASE.
Tipuri de date, nivele de abstractizare a lor, modul de definire a diferitor nivele.
Verificarea PP şi testarea lor.

Inteligenţa artificială

Domeniul studiilor inteligenţei artificiale. Testul Turing.
Reprezentarea cunoştinţelor. Reprezentarea cunoştinţelor prin cadre (frame). Reţele semantice. Reprezentarea cunoştinţelor în Prolog. Reprezentarea cunoştinţelor cu ajutorul producţiilor. Reţele neuronale artificiale.
Sisteme expert. Structura sistemelor expert. Descrierea componentelor de bază. Achiziţionarea cunoştinţelor.
Căutarea euristică. Algoritmul A*.
Arbori de jocuri. Procedura Minimax. Procedura alfa-beta.

Limbaje formale şi automate. Tehnici de compilare (LFA)

Gramatici şi limbaje formale, noţiuni preliminare. Metode de descriere a limbajelor. Clasificarea Chomsky.
Gramatici regulate şi automate finite. Definiţii, exemple. Automate finite deterministe şi nedeterministe. Echivalenţa gramaticilor regulate şi a automatelor finite. Lema de pompare şi aplicaţiile ei. Minimizarea automatelor finite. Expresii regulate. Automate finite deterministe şi nedeterministe. Teorema de echivalenţă.
Gramatici şi limbaje independente de context. Automate cu memorie stivă. Arbori de derivare, teorema de ramificare. Transformări echivalente asupra gramaticilor independente de context. Eliminarea simbolurilor inutile, redenumirilor. Gramatici independente de context cu e-producţii. Forma normală Chomsky. Recursia stângă. Forma normală Greibach. Teorema "uvwxy" şi aplicaţiile ei. Automate cu memorie stivă: definiţii, exemple. Echivalenţa gramaticilor independente de context şi a automatelor cu memorie stivă.
Proiectarea şi implementarea analizoarelor lexicale.
Analiza sintactică descendentă. Recursivitatea stângă şi factorizarea gramaticilor. Maşina de analiză predictivă. Gramatici şi analizoare LL(k). Analiza sintactică ascendentă. Maşina de analiză "deplasează-reduce". Gramatici cu relaţii de precedenţă. Algoritmul de construire a relaţiilor de precedenţă. Precedenţa slabă. Gramatici şi analizoare LR(k). Simplificări ale gramaticilor LR(k), SLR(k) şi LALR(k).
Analiza semantică şi generarea codului. Traducerea limbajelor, automate de traducere. Schema de traducere orientată pe sintaxă. Gramatici atributive. Generarea codului intermediar. Forma poloneză. Generarea codului pentru calculatoare cu registre generale. Optimizarea codului. Graful de flux al unui program.

Reprezentarea, stocarea şi procesarea informaţiei (RSPI)

Noţiune de structură de date. Matrici bidimensionale şi n -dimensionale. Metode de reprezentare a matricelor în memoria calculatorului.
Accesarea elementelor. Metode de accelerare a accesului la elementul unui tabel. Vectori definitori.
Structuri dinamice de date (liste, stive, cozi, arbori, grafuri) şi reprezentarea lor în memoria calculatorului. Operaţii de căutare, modificare, extragere.
Tipuri abstracte de date, obiecte.
Tabele liniare. Metode de reprezentare a tabelelor în memoria calculatorului. Căutarea consecutivă.
Căutarea binară. Adresarea dispersată (hash-coding).
Metode de sortare. Sortarea rapidă. Sortarea arborescentă.

Programarea obiect orientată (POO)

Iniţiere ăn POO. Noţiune de clasă şi de obiect. Proprietăţile principale ale limbajelor de programare POO. Incapsulare, moştenire, polimorfism, ierarhii de clase.
Declararea claselor în C++. Câmpuri şi funcţii de tip membru. Membrii publici, protejaţi, privaţi. Forma de moştenire. Moştenirea multiplă. Reprezentarea obiectelor în memoria operativă. Obiecte dinamice. Pointeri la obiecte.
Metodele obiectului. Funcţii statice, virtuale. Clase abstracte, funcţii pure. Constructori şi destructori. Tipuri de constructori. Supraâncărcarea funcţiilor şi a operatorilor.
Şabloanele (Template), funcţii şi clase generice. Exemple de aplicaţii ale claselor generice în C++ (stive, cozi, liste).
Iniţiere în programarea vizuală. Caracteristica generală a mediului VC++. Crearea aplicaţiilor de tipul SD, DB, MD. Crearea meniurilor şi a submeniurilor.

Programare funcţională. Programare logică (PP, PL)

Funcţii şi programe. Programarea funcţională şi procedurală. Prezentare generală a limbajelor programării funcţionale. Limbajul LISP – privire generală, aria aplicabilităţii.
Atomi şi expresii simbolice. Liste. Selectarea elementelor dintr-o listă. CAR şi CDR. Construirea de noi liste: CONS. Predicate primitive. Apostroful şi inhibarea evaluării. Atomi utilizaţi ca variabile.
Notaţia LAMBDA. Aplicarea LAMBDA -expresiilor. Construirea de noi funcţii, DEFUN.
Condiţionala COND. Variabile libere şi variabile legate. Transfer de parametri.
Aritmetica şi algebra limbajului LISP. Funcţii numerice definite recursiv. Operaţiile algebrice văzute ca prelucrări simbolice. Aritmetica raţională în LISP.
Limbajul PROLOG. Fapte. Reguli. Scopuri. Structura unui program. Concretizarea variabilelor. Unificare.
Procese iterative în PROLOG. Simulări de cicluri. Recursivitatea. Căutarea soluţiilor într-un graf.
Limbajul PROLOG. Obiecte simple şi obiecte compuse, liste. Operaţii asupra listelor (apartenenţa unui element la o listă, adăugarea elementelor, eliminarea elementelor, alipirea a două liste, inversarea listelor, intersecţia a două liste).

Programare paralelă

Excluderea reciprocă a proceselor în programarea concurentă. Utilizarea semafoarelor, monitoarelor şi canalelor pentru realizarea excluderii reciproce şi sincronizarea proceselor în programarea concurentă (exemplificaţi utilizând limbajul de programare concurenţa Pascal FC).
Clasificarea lui Flynn a sistemelor paralele de calcul (sistem de tipul SIMP, SISD, MISD, MIMD). Definiţia, reprezentarea şi complexitatea algoritmilor paraleli.
Utilizarea principiului "Divide et Impera" în calculul paralel. Utilizaţi acest principiu la elaborarea unui algoritm paralel pentru determinarea invelitoarei convexe a n puncte din plan şi determinaţi complexitatea acestui algoritm.
Descrierea algoritmului paralel pentru determinarea componentelor conexe ale grafurilor. Determinaţi complexitatea algoritmului descris. Analizaţi un exemplu concret.

Literatura de specialitate

Aho A., Ullman J. Теория синтаксического анализа, перевода и компиляции. v 1,2 M.: Mir, 1978.
Bauer F. L., Gooz G. Informatica. v 1,2. M.: Mir, 1990.
Березин И.С., Жидков Н.И. Методы вычислений. v.l, 2. 1959. (Rus.)
Боровков А.А. Курс теории вероятностей. M.: Nauca, 1972 (Rus.)
Боровков А.А. Математическая статистика. M.: Nauca, 1980 (Rus.)
Ceri S., Gotlib G., Teanche L. Логическое программирование и базы данных. M.: Mir, 1992.
Deitel G. Введение в операционную систему. M.: Mir, 1987, v 1, 2.
Dima G., Dima M. FoxPro prin meniuri şi ferestre. Bucureşti, Teora, 1995.
Dorin Bocu. Iniţiere în ingineria sistemelor soft. //Ed. ALBASTRA, Cluj-Napoca, 2001.
Фадеев Д.К., Фадеева П.И. Вычислительные методы линейной алгебры. M.1960. (Rus.)
Фихтенгольц Г.М. Курс математического анализа. v.l, 2. 1962. (Rus.)
Gheorghescu Ioan. Elemente de inteligenţă artificială. Bucureşti, 1985.
Gihnan I. I., Scorohod A. V. Введение в теорию случайных процессов. M.: Mir, 1977 (Rus.)
Grigoras Gheorghe. Limbaje formale şi tehnici de compilare. Universitatea „A.I.Cuza”, Iaşi, 1985.
Helfand N., Fomin S. Вариационное исчисление. M.: Nauca,1961 (Rus.)
Hincin A. Краткий курс математического анализа. M. 1951. (Rus.)
Iablonschii S. V. Введение в дискретную математику. M.: Nauca, 1979.
INFORMATICA. Coordonator ştiinţific Gh.Dodescu. Bucureşti, Ed. Academiei, 1987.
Karmanov B. G. Математическое программирование. M.: Nauca, 1980, 1986 (Rus.)
Klimov G. P. Теория вероятностей и математическая статистика. M.: Mir, 1988 (Rus.)
Malita Mihaela, Malita Mircea. Bazele inteligenţei artificiale. Bucureşti, Ed.Tehnică, 1987.
Marinescu Dan., Trandafirescu Mihai. PC, manualul începătorului. Bucureşti, Teora, 1994.
Marinescu Gh. Analiza numerică. Bucureşti, 1984.
Mendelison A. Введение в математическую логику. M.: Mir, 1985.
Militon Frentiu, Vasil Pîrv. Elaborarea programelor - Metode şi tehnici moderne. //Ed. PROMETEU, Cluj-Napoca, 1994.
Oprea Dumitru. Analiza şi proiectarea Sistemelor Informaţionale economice. //Ed. POLIROM , IASI, 1999.
Papadimitriu H., Steiglitz K. Комбинаторная оптимизация. M.: Mir,1985 (Rus.)
Petrescu A. ABC de calculatoare personale şi... nu numai atât. Bucureşti, 1990.
Pilat V. WINDIWS 3.1, Utilizare. Bucureşti, Teora, 1995.
Pontreaghin L. Теория оптимальных процессов. M.: Nauca, 1980. (Rus.)
Quatrani T . Visual Modeling With Rational Rose and UML. //Addison-Wesley, 1998.
Rumbaugh, J., Jacobson, I., and Booch G. Unified Modeling Language Reference Manual. // Addison Wesley, 1998.
Samoila Gheorghe. PC 386, o nouă generaţie de calculatoare personale. Bucureşti, Ed. Tehnică, 1992.
Serbanati Luca-Dan. Limbaje de programare şi compilatoare. Bucureşti, 1978.
Sireaev A. N. Вероятности. M.: Nauca, 1980 (Rus.)
Somnea D., Turturea D. Iniţiere în C++. Programarea orientată pe obiecte. Bucureşti, Ed. Tehnică, 1993.
Sou. Логическое проектирование операционных систем. M.: Mir, 1977.
Stefinescu A., Zidaroiu C. Cercetări operaţionale. Bucureşti 1981.
Stepan Aurel, Petrov Gh., Iordan V. Fundamentele proiectării şi realizării sistemelor informatice. //Ed. MIRTON, Timişoara, 1995.
Sterling L., Sapiro A. Искусство программирования на языке Prolog. M.: Mir, 1990.
Tapus N., Moisa Tr. Reţele de calculatoare. Bucureşti, Teora, 1995.
Vasilev P. V. Численные методы решения экстремальных задач. M.: Nauca, 1974, 1980 (Rus.)
Vaduva I. Ingineria programării (în două volume). // Ed AS RSR, Bucureşti, !985 (vol.1), 1986 (vol. 2).
Вендров А.М. CASE-технологии. Современные методы проектирования информационных систем. // http//www.citforum.ru./database/case/
Зиглер К. Методы проектирования програмных систем. // М.: МИР, 1985.