Programarea calculatoarelor 2 - Laborator 4

Problema 1a Calculaţi rădăcina ecuaţiei f(x) = 0 cu o precizie dată, prin metoda înjumătăţirii intervalului, când f este o funcţie continuă şi monotonă pe un interval pe care schimbă semnul. Exemplu: f(x) = e^x + x^2 - 5 pe intervalul [1, 2], cu o precizie de 10^-5.
Indicaţie: dacă f(x1) < 0 şi f(x2) > 0, calculaţi valoarea lui f în mijlocul intervalului [x1, x2] şi continuaţi cu subintervalul pe care f schimbă semnul, până la precizia dorită. Se pot folosi funcţiile standard declarate în math.h, de exemplu exp.

Problema 1b În matematică, se doreşte adesea aproximarea cât mai precisă a unui număr real cu unul raţional. Din antichitate se ştia că pi ~= 22/7, cu o precizie de 1 la mie. O astfel de aproximare se poate face cu fracţii continue: un număr 0 < x < 1 se poate aproxima succesiv cu 1 / a1, 1 / (a1 + 1 / a2), 1 / (a1 + 1 / (a2 + 1 / a3)), unde a1, a2, a3, ... sunt numere naturale. Dacă în aproximarea iniţială, a1 este parte întreagă din 1/x, şi se continuă folosind aceeaşi regulă (pentru partea fracţionară a numitorului aproximat cu a1, etc.), se obţine o secvenţă de numere raţionale p0/q0, p1/q1, p2/q2 ... care şi îl aproximează pe x din ce în ce mai bine, alternativ din ambele părţi şi satisfac următoarea recurenţă:
p_n+1 = a_n+1 * p_n + p_n-1 pentru n >= 0, cu p_-1 = 1, p_0 = 0
q_n+1 = a_n+1 * q_n + q_n-1 pentru n >= 0, cu q_-1 = 0, q_0 = 1
Să se scrie un program care, pentru un număr real între 0 şi 1 calculează cea mai bună aproximaţie în fracţie continuă pentru care numitorul nu depăşeşte o valoare dată. Opţional, verificaţi că nici o fracţie cu numitorul mai mic nu este o aproximaţie mai bună (o proprietate matematică cunoscută şi demonstrată).
Indicaţii: La fiecare pas rămâne de aproximat sub forma 1 / a_n un nou număr fracţionar între 0 şi 1. Determinaţi întâi relaţia care leagă acest număr de valoarea anterioară. Pentru partea întreagă, puteţi folosi funcţiile floor sau trunc declarate în math.h (pentru numere pozitive, ele dau acelaşi rezultat).

Problema 2a Scrieţi un program care calculează o sumă de control pe 16 biţi pentru o linie de text citită de la intrare, în felul următor: octetul inferior se obţine prin SAU exclusiv din toate caracterele de pe poziţii pare (începând cu 0), iar octetul superior prin SAU exclusiv din toate caracterele de pe poziţii impare în text. Rezolvaţi problema prelucrând pe rând fiecare caracter, fără a folosi tablouri.

Problema 2b Scrieţi un program care calculează o sumă de control CRC (cyclic redundancy check) pentru un text, conform standardului POSIX.
Fundamentul matematic este următorul: textul e asimilat unui şir de L biţi, pentru care se calculează o sumă de control pe W biţi. Orice şir de n biţi poate fi asociat cu un polinom de grad < n, în care bitul k este coeficientul lui x la puterea k. Se ia textul, privit ca un astfel de polinom, şi se calculează restul împărţirii la un polinom prestabilit de grad W, considerând toţi coeficienţii modulo 2. De exemplu, pentru textul pe L=8 biti 10011100, adică x^7 + x^4 + x^3 + x^2 şi polinomul x^4 + x^3 + x^0 (11001, de grad W=4) obţinem:
x^7 + x^4 + x^3 + x^2 = (x^3 + x^2 + x^1)*(x^4 + x^3 + x^0) + x^1 (mod 2)
deci restul x^1 interpretat pe W=4 biţi este 0010. Împărţirea poate fi implementată prin algoritmul clasic cu deplasare şi scădere succesivă. Exprimând totul în calcule pe biţi, avem nevoie de o valoare pe W biţi în care ţinem minte restul curent. Scăderea pentru polinoame modulo 2 (identică cu adunarea) se face prin SAU exclusiv bit cu bit (nu există deplasare, fiecare bit corespunde unui coeficient separat). Dacă bitul superior (poziţia W-1) este 1, atunci în iteraţia curentă, după deplasarea la stânga şi aducerea următoarei cifre din deîmpărţit, bitul W va fi 1 şi împărţitorul (de grad W) va "intra" în rest (poate fi "scăzut" prin XOR, coeficientul în cât este 1). Dacă nu, se continuă fără scădere cu următoarea iteraţie (cifra din cât este 0). Cum ne interesează doar restul, nu trebuie să reţinem câtul; calculul se încheie când au fost consumaţi toţi biţii din deîmpărţit (textul dat).
În cazul particular al standardului POSIX, suma de control se calculează pe 32 de biţi, iar polinomul de grad 32 folosit ca împărţitor are următorii biţi pe 1 (coeficienţi): 32, 26, 23, 22, 16, 12, 11, 10, 8, 7, 5, 4, 2, 1, 0. (Asemenea polinoame se aleg pentru proprietăţile bune de detectare a erorilor). Şirul de biţi codificat e format din caracterele textului, în ordine, fiecare începând cu bitul cel mai semnificativ; apoi lungimea textului, în caractere, pe numărul minim necesar de octeţi, începând cu cel mai puţin semnificativ; apoi 32 de biţi 0 (4 caractere nule). Suma de control e restul pe 32 de biţi, negat bit cu bit (pentru că, adăugată la mesaj, permite verificarea faptului că acelaşi algoritm ar trebui să dea restul 0).
Indicaţii: Din descrierea algoritmului, rezultă că vom manipula un număr pe 32 de biţi (restul curent), de exemplu un long. Testul valorii 1 pentru bitul cel mai semnificativ trebuie făcut înainte de deplasarea la stânga, care va provoca dispariţia lui. Din acelaşi motiv, nu vom reprezenta bitul 32 al împărţitorului, calculele descrise ţinând cont implicit că acesta e 1. Împărţirea poate fi făcută pas cu pas, pe măsură ce se citesc caractere din text, însă nu poate începe până când în deîmpărţitul iniţial nu s-au acumulat 32 de biţi (4 caractere), şi e disponibil încă un caracter din care şă se "aducă" biţii următori. La sfârşitul textului, se continuă algoritmul cu octeţii reprezentând lungimea textului, şi cei 4 octeţi finali de zero (care ne asigură că deîmpărţitul va avea >= 32 de biţi chiar dacă textul e mai scurt).
Textul poate fi citit la alegere, fie până la linie nouă, fie până la sfârşit de fişier, cu un ciclu de tipul

 while ((c = getchar()) != EOF) { /* prelucreazâ c */ }