Logică și structuri discrete

Curs, luni 16-18, Amf. V. Vlad (Construcții)
Notare: 50% examen + 50% activitate pe parcurs Consultații: marți 18-19 D1 + la cerere

Materiale de curs

1. Funcții Exemple simple Forum Campus Virtual
2. Recursivitate. Opțional: program pentru fractalul cruce Forum Campus Virtual
   Exerciții rezolvate: variante recursive pentru calculul de aproximări/limite (rădăcina pătrată) și suma unei serii
3. Liste. Notițe de curs. Exemplu: județe și populația Forum Campus Virtual
4. Mulțimi. mulțimea părților. Notițe de curs Forum Campus Virtual
5. Relații. Dicționare. Notițe de curs. Exemplele de la curs și consultații Forum Campus Virtual
   Exerciții simple pentru recapitularea cursului.
6. Logică propozițională. Exemplele de la curs. Forum Campus Virtual
   Exemple de parcurgeri recursive
7. Logică propozițională. Forum Campus Virtual
   Consultații după parțial: săpt. 8, săpt. 9
8. Logica predicatelor. Metoda rezoluției. Forum Campus Virtual
   Observații despre formalizare. Exemplul detaliat cu formalizare și rezolutie de la curs. Exercițiu rezolvat.
9. Logica predicatelor. Cod pentru unificarea de termeni Forum Campus Virtual
10. Automate și expresii regulate. Exerciții rezolvate.
    regex101: expresii regulate online. Simulator și conversie pentru automate și expresii regulate. Echivalență de expresii regulate.
11. Gramatici. Programe C: paranteze echilibrate, expresii prefix
    Fractal definit prin gramatică
12. Arbori. Exemple de prelucrări
13. Grafuri. Parcurgere în adâncime. Parcurgere prin cuprindere
14. Complexitate și calculabilitate. Recapitulare.
    Exemplu de punct fix

Laborator

Puteți rula programe online aici: IOcamlJS (preluat de aici), Try Ocaml, sau Coding Ground

1. Tema 1 pentru Laboratorul 1: Funcții
2. Exerciții pregătitoare pentru Laboratorul 2: Recursivitate
3. Exerciții pregătitoare pentru Laboratorul 3: Liste
4. Exerciții pregătitoare pentru Laboratorul 4: Mulțimi
5. Laboratorul 5: Relații și dicționare
   Construiți relații și urmăriți proprietățile lor (Stanford CS 103 Mathematical Foundations of Computing)
6. Exerciții pregătitoare pentru Laboratorul 6: Logica propozițională
   Pagini cu transformări pentru formule: logictools.org (atenție, operatori făra precedență), U. of Utah (BDD-uri), Wolfram Alpha
7. Exerciții pregătitoare pentru Laboratorul 7: Logica propozițională
8. Exerciții pregătitoare pentru Laboratorul 8: Logica predicatelor
9. Laboratorul 9: Logica predicatelor (text comun cu lab. 8)
10. ---
11. Exerciții pregătitoare pentru Laboratorul 11: Automate și expresii regulate
12. Exerciții pregătitoare pentru Laboratorul 12: Gramatici
13. Laboratorul 13: Arbori

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.
• Alt tutorial de instalare, de Andrei Tenescu. E mai mult de făcut, dar are și poze.
• Pagina principală a distribuției OCaml (pachete software, documentație, etc.)
• Manualul OCaml, funcțiile predefinite și modulele din biblioteca standard
• 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 3.3, 2017. 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.
• Lawrence C. Paulson, ML for the Working Programmer, ed. 2. O carte clasică (folosind Standard ML, dar principiile sunt aceleași).

Alte cursuri

• Mathematical Foundations of Computing (Stanford University)