Logică și structuri discrete

Curs, luni 16-18, Amf. V. Vlad (Construcții)
Consultații: marți 14-16 B426, marți 19-20 A115 + la cerere

Materiale de curs

1. Funcții
   Scurte explicații despre limbaj
2. Recursivitate.
   fractalul cruce
3. Liste. Notițe de curs
4. Mulțimi. Notițe de curs
   Exemple simple
5. Relații. Notițe de curs
6. Logică propozițională. Exemplele de la curs.
   Alte exemple de parcurgeri recursive pentru formule
7. Logică propozițională. Verificarea realizabilității. Demonstrații.
8. Logica predicatelor. Câteva observații despre formalizare.
9. Logica predicatelor. unificare de termeni
10. Automate finite și expresii regulate. Exerciții rezolvate
11. Gramatici
    paranteze echilibrate (vezi și: trei feluri), expresie prefix (sau în ML), expresie numerică
12. Arbori. diverse prelucrări; parcurgeri
13. Grafuri. Parcurgeri cu tipărirea nodurilor sau afișare în format DOT
14. Complexitate și calculabilitate

Laborator

1. Tema 1 pentru Laboratorul 1: Funcții
2. Tema 2 pentru Laboratorul 2: Recursivitate
   Alte exerciții propuse
3. Tema 3 pentru Laboratorul 3: Liste
4. Tema 4 pentru Laboratorul 4: Mulțimi
   Exerciții rezolvate: permutări pentru șiruri și elemente oarecare
5. Tema 5 pentru Laboratorul 5: Relații. Dicționare
6. Tema 6 pentru Laboratorul 6: Logică propozițională
7. Tema 7 pentru Laboratorul 7: Logică propozițională
8. Tema 8 pentru Laboratorul 8: Logica predicatelor
9. Laboratorul 9. Exemple cu rezoluție (Casandra Holotescu, curs an I Info)
10. Tema 10
11. Laboratorul 11: Automate finite, expresii regulate, gramatici.
12. Laboratorul 12: Arbori
13. Tema 13 pentru Laboratorul 13: Grafuri

Resurse

Limbajul ML

• Try OCaml: interpretor online: rulați exemple proprii sau urmăriți scurte lecții
• Un curs online, Introduction to Functional Programming in OCaml (începe tot din 26 sept.). Pentru cei care doresc să aprofundeze programarea funcțională.
• Instrucțiuni de instalare pentru folosirea OCaml din Emacs.
• 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

• Mathematical Foundations of Computing (Stanford University)
• 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)