Programa de examen pentru disciplina informatică

Programa de examen pentru disciplina informatică, în cadrul admiterii la Facultatea de Automatică și Calculatoare, valabilă pentru anul 2020, urmează programa de la examenul de bacalaureat stabilită prin Anexa nr. 2 la OMECTS nr. 4800/31.VIII. 2010.

Link programe clasele IX-XII

Algoritmi

1. Noţiunea de algoritm, caracteristici
2. Date, variabile, expresii, operaţii
3. Structuri de bază (liniară, alternativă şi repetitivă) - videoclip teorie 1, videoclip teorie 2
4. Descrierea algoritmilor (programe pseudocod)
   1. Prelucrare secvente de valori: videoclip teorie 1, videoclip teorie 2

Complexitatea algoritmilor

1. Complexitatea timp a algoritmilor - lecție FMI Unibuc - videoclip teorie, slide-uri teorie

Elementele de bază ale unui limbaj de programare (Pascal sau C, la alegere)

1. Vocabularul limbajului
2. Constante. Identificatori
3. Noţiunea de tip de dată. Operatori aritmetici, logici, relaţionali
4. Definirea tipurilor de date
5. Variabile. Declararea variabilelor
6. Definirea constantelor
7. Structura programelor. Comentarii
8. Expresii. Instrucţiunea de atribuire
9. Citirea/scrierea datelor
10. Structuri de control (instrucţiunea compusă, structuri alternative şi repetitive)

Subprograme predefinite

1. Subprograme. Mecanisme de transfer prin intermediul parametrilor
   1. Teorie subprograme - partea 1
   2. Teorie subprograme - partea 2
2. Proceduri şi funcţii predefinite

Subprograme definite de utilizator

1. Proceduri şi funcţii – declarare şi apel – parametri formali şi parametri efectivi – parametri transmişi prin valoare, parametri transmişi prin referinţă – variabile globale şi variabile locale, domeniu de vizibilitate

2. Proiectarea modulară a rezolvării unei probleme

Tipuri structurate de date

1. Tipul tablou
   1. Tablou unidimensional - vectori - clip 1 teorie, clip 2 teorie
   2. Vectori - probleme rezolvate
   3. Vectori de frecventa
   4. Vectori de frecventa - probleme rezolvate
   5. Tabloul bidimensional - matrice - clip 1 teorie, clip 2 teorie/partea I, clip 2 teorie/partea II
   6. Matrice pătratice
   7. Probleme rezolvate cu matrice date la bacalaureat
   8. Probleme rezolvate de generare de matrice date la bacalaureat
2. Tipul şir de caractere – operatori, proceduri şi funcţii predefinite pentru: citire, afişare, concatenare, căutare, extragere, inserare, eliminare şi conversii (şir ⟷ valoare numerică)
   1. Probleme rezolvate Siruri de Caractere
3. Tipul înregistrare
   1. Probleme rezolvate - Struct

Structuri dinamice de date - liste, stive, cozi

Liste simplu înlănțuite

• Alocarea dinamică a memoriei. Liste simplu înlănțuite - partea I
• EXTRA: (avansat) - Pointers in C - course for beginners
• Liste simplu înlănțuite - lecția a II a
• Liste simplu înlănțuite - partea a III a

Aplicații avansate liste (nu e în programă)

• Liste simplu înlănțuite circulare
• Liste liniare dublu înlănțuite
• Linked lists for Technical Interviews

Coadă

• Structura de date de tip coada
• Structura liniara Coada - aplicații practice

Stiva

• Stack Data Structure Tutorial – Solve Coding Challenges

Fişiere text

Videoclipuri cu probleme rezolvate

1. Fişiere text. Tipuri de acces
2. Proceduri şi funcţii predefinite pentru fişiere text

Algoritmi elementari

1. Algoritmi elementari - Teorie si exemple de probleme
2. Probleme care operează asupra cifrelor unui număr
3. Oglinditul unui număr
4. Divizibilitate
5. Aplicații - divizibilitatea numerelor naturale
6. Numere prime. Algoritmul lui Euclid - partea 1, partea 2
7. Şirul lui Fibonacci. Calculul unor sume cu termenul general dat
8. Determinare minim/maxim
9. Metode de ordonare (metoda bulelor, inserţiei, selecţiei, numărării)
10. Interclasare
11. Metode de căutare (secvenţială, binară)
12. Analiza complexităţii unui algoritm (considerând criteriile de eficienţă durata de executare şi spaţiu de memorie utilizat)
13. Exemple de probleme REZOLVATE din BAC
14. Algorithms and Data Structures Tutorial - Full Course for Beginners

Recursivitate

1. Prezentare generală subprograme recursive
2. Proceduri şi funcţii recursive - aplicații

Metoda backtracking (iterativă sau recursivă)

1. Prezentare generală
2. Probleme de generare. Oportunitatea utilizării metodei backtracking
3. Aplicații grile bacalaureat 1
4. Aplicații grile bacalaureat 2
5. Aplicații grile bacalaureat 3
6. Aplicații grile bacalaureat 4
7. Aplicații grile BAC 2009 variante 1
8. Aplicații grile BAC 2009 variante 2
9. Aplicații grile BAC 2009 variante 3
10. Backtracking BAC 2010
11. Backtracking BAC 2011
12. Backtracking BAC 2012
13. Backtracking BAC 2012

Generarea elementelor combinatoriale

1. Permutări, aranjamente, combinări
2. Backtracking - anagrame cuvânt
3. Produs cartezian, submulţimi

Grafuri

Formule și teoreme - Grafuri orientate și neorientate

Grafuri neorientate

Videoclip telescoala

– terminologie (nod/vârf, muchie, adiacenţă, incidenţă, grad, lanţ, lanţ elementar, ciclu, ciclu elementar, lungime, subgraf, graf parţial) – proprietăţi (conex, componentă conexă, graf complet, hamiltonian, eulerian) – metode de reprezentare (matrice de adiacenţă, liste de adiacenţă)

Grafuri orientate

– terminologie (nod/vârf, arc, adiacenţă, incidenţă, grad intern şi extern, drum, drum elementar, circuit, circuit elementar, lungime, subgraf, graf parţial) – proprietăţi (tare conexitate, componentă tare conexă) – metode de reprezentare (matrice de adiacenţă, liste de adiacenţă)

• aplicații cu grafuri orientate date la BAC

Arbori

Videoclip telescoala

– terminologie (nod, muchie, rădăcină, descendent, descendent direct/fiu, ascendent, ascendent direct/părinte, fraţi, nod terminal, frunză) – metode de reprezentare în memorie (matrice de adiacenţă, liste ”de descendenţi”, vector ”de taţi”)