Fundamente de informatică - Tema 6

  1. Lucrul cu liste și iteratori
    Implementați algoritmul mergesort care sortează o listă, despărtind-o în două jumătăți, și apoi combinând prin interclasare părțile sortate recursiv, folosind același algoritm.
    Exemplu de soluție
  2. Mulțimi și relații
    Scrieți o funcție recursivă care calculează un punct fix al unei funcții crescătoare f (o valoare pentru care f(x) = x), pe un domeniu finit, aplicând succesiv funcția pănă valoarea nu se mai schimbă.
    Implementați apoi o funcție care calculează închiderea tranzitivă a unei relații (valoarea pentru care Rk = Rk+1). Relația e dată printr-o funcție (map) care dă pentru fiecare element x mulțimea elementelor y pentru care R(x, y).
    Folosiți această abordare pentru a determina clasele de echivalență ale unei relați. (În cazul unui graf orientat, acestea sunt componentele puternic conectate ale grafului).
  3. Citirea de termeni
    Scrieți o funcție care citește o expresie regulată (folosind semnul | pentru alternativă și alăturarea pentru concatenare).
Marius Minea
Last modified: Sat Dec 8 10:30:00 EEST 2012