Logică și structuri discrete

Curs, marți 14-16, D1
Consultații: în sesiune, zilnic orele 16-18: 2 feb., A204, mulțimi
16-18h, A109: 3 feb: relații, grafuri, arbori; 4 feb: logică propozițională; 5 feb: logica predicatelor; 6 feb: automate, expresii regulate, gramatici
în timpul semestrului: miercuri 19-20 A109
Platforma online (Piazza)
Situația la laborator
Notele la parțial
Examen (prezentarea 1)
Examen (prezentarea 2)
Examen (prezentarea 3)
Examen (prezentare specială)
Regulamentul de studii (în special sec. 3, 5, 6)

Materiale de curs

1. Funcții.
   Scurte explicații despre limbaj
2. Recursivitate. Exerciții rezolvate
   fractalul cruce
3. Liste. Notițe de curs. Câteva observații
4. Mulțimi. Notițe de curs.
5. Relații. Notițe de curs.
6. Logică propozițională
   Exemple de parcurgeri recursive pentru formule
7. Logică propozițională (cont.)
8. Arbori
   prelucrări, traversare
9. Logica predicatelor. Rezoluție. Câteva observații despre formalizare.
10. ---
11. Limbaje regulate și automate. Exerciții comentate
12. Gramatici. Exemple: expresie prefix (ML), expresie infix (C)
13. Grafuri. Exemple: componente conexe, parcurgere
14. Logica predicatelor. Calculabilitate

Laborator

1. Tema 1 pentru Laboratorul 1
   Exerciții propuse
2. Tema 2 pentru Laboratorul 2
   Exerciții propuse.
3. Tema 3 pentru Laboratorul 3
   Exerciții rezolvate segmentarea unei liste
   Exerciții simple cu recursivitate și liste
4. Tema 4 pentru Laboratorul 4
   Exemple simple cu mulțimi
   Exerciții rezolvate. combinări de k elemente
   Exerciții propuse.
5. Tema 5 pentru Laboratorul 5
   Exemple:compunere de două dicționare.
   Exerciții propuse.
6. Tema 6 pentru Laboratorul 6
   Exerciții propuse.
7. Laboratorul 7
8. Tema 8 pentru Laboratorul 8
9. Tema 9 pentru Laboratorul 9
10. Tema 10 pentru Laboratorul 10
    Exerciții propuse
11. Tema 11 pentru Laboratorul 11
    Exerciții propuse
12. Tema 12 pentru Laboratorul 12
    Exercițiu propus (opțional)
13. Tema 13 pentru Laboratorul 13

Resurse

Limbajul ML

• Try OCaml: interpretor online: rulați exemple proprii sau urmăriți scurte lecții
• Instrucțiuni de instalare pentru folosirea OCaml din Emacs.
• Un tutorial detaliat de Andrei Tenescu pentru instalarea OCaml sub Cygwin
• Compilatorul OCaml.
• Manualul OCaml, funcțiile predefinite și modulele din biblioteca standard
• Documentația de pe ocaml.org
• O scurtă introducere în OCaml (Scott Smith, Johns Hopkins U.)
• O carte introductivă: Think OCaml de Allen Downey și Nicholas Monje
• 99 de probleme rezolvate (vezi și alte tutoriale)
• Real World OCaml -- o carte de la introductiv la avansat

Cărți

• Alfred V. Aho, Jeffrey D. Ullman. Foundations of Computer Science, 1992. O carte clasică de introducere în informatică.
• Alan Doerr, Kenneth Levasseur. Applied Discrete Structures version 2.0, 2013. O carte cu definiții detaliate și multe exemple.
• 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.

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)