Logică și structuri discrete

Curs, luni 16-18, ASPC
Consultații: marti 14-16 B426

Situația notelor
Rezultatele la parțial
Rezultatele la examen (prezentarea 1)
Căteva explicații despre erori frecvente la examen. O problemă de formalizare.
Rezultate la examen (prezentarea 2)
Rezultate la examen (prezentarea 3)

Materiale de curs

1. Funcții.
   Scurte explicații despre limbaj
2. Recursivitate.
   Fractal cruce (pătrat) Exerciții rezolvate
3. Liste. Notițe de curs
4. Mulțimi. Notițe de curs
5. Relații. Notițe de curs
   Dicționar din listă, Frecvența cuvintelor
6. Logică propozițională. Exerciții rezolvate
   Verificarea realizabilității (cod ML)
7. Logică propozițională.
   exemple de formule în CNF (format DIMACS); program ML pentru rezolvare
   program C pentru codificat jocul 3x3 în format SMT2; rezolvitorul Z3 de la Microsoft
8. Logica predicatelor.
9. Logica predicatelor. Metoda rezoluției.
   union-find (unificare și substituție) doar pentru variabile și pentru termeni
10. Limbaje regulate și automate.
11. ---
12. Gramatici.
    Expresii numerice prefix în ML și C. Fractalul dragon în ML
13. Arbori.
    arbore binar de căutare, arbore binar complet, formule propozitionale ca s-expresii
14. Grafuri. Calculabilitate.
    construire/parcurgere de graf

Laborator/Seminar

1. Funcții. Temă pentru laborator: ex. 1 și 4
2. Recursivitate. Temă pentru laborator: ex. 2 (lab 1), ex. 1 (lab 2)
3. Liste. Temă pentru laborator: ex. 1a, 7, 9
4. Mulțimi. Temă pentru laborator: ex. 1 (mulțimi) + un exercițiu nefăcut de la liste
   Exemplu rezolvat: submulțimi de k elemente
5. Relații. Temă pentru laborator: inversa compunerii (curs) + ex. 3
6. Logică propozițională, include tema
7. Logică propozițională, include tema. Exemple de funcții recursive pentru formule fișier ML
   Exemplu rezolvat: transformarea Tseitin
8. Logica predicatelor, include tema
9. Demonstrarea teoremelor
10. Automate finite, include tema
11. Expresii regulate, include tema
    Exemplu rezolvat: derivata expresiei regulate
12. Gramatici, include tema
    Exemple rezolvate: derivare de n ori, simboluri de inceput pentru neterminale
13. Arbori, include tema
    Exemple rezolvate: traversare, reconstruire arbore din liste

Resurse

Alte cursuri

• Theory of Computation (Wayne Goddard, Clemson University).
  (cursurile 1-5 pentru limbaje și automate).
• Introduction to Theoretical Computer Science (Zdeněk Sawa, TU Ostrava)
  (p. 105 ff. pentru limbaje și automate)

Cărți

• Robert M. Keller. Computer Science: Abstraction to Implementation, 2001. O imagine foarte bună asupra științei calculatoarelor: cuprinde atât fundamente, căt și cunoștințe care vor fi parcurse ulterior.
• Alan Doerr, Kenneth Levasseur. Applied Discrete Structures version 2.0, 2013. O carte cu definiții detaliate și multe exemple.

Limbajul ML

• Compilatorul OCaml și documentația. Instrucțiuni despre folosirea OCaml din Emacs.
• Try OCaml: interpretor online, cu lecții și exemple de programe
• O scurtă introducere în OCaml (Scott Smith, Johns Hopkins U.)
• 99 de probleme rezolvate (vezi și alte tutoriale)