Funcții: Domeniul funcției

Funcții

• O funcție este o corespondență între două mulțimi, domeniul și codomeniul, astfel încât fiecărui element din domeniu îi corespunde exact un element din codomeniu.
  • O funcție primește o valoare de intrare și produce o singură valoare de ieșire.
• Funcțiile pot fi reprezentate prin ecuații, grafice, tabele sau descrieri verbale.

Domeniul

• Domeniul unei funcții $f(x)$ este mulțimea tuturor valorilor de intrare posibile (valori ale lui x) pentru care funcția este definită și rezultă o valoare de ieșire reală.
• Pentru a găsi domeniul:
  • Funcțiile polinomiale au domeniul format din toate numerele reale, $(-\infty, \infty)$.
  • Dacă funcția are un numitor, valorile lui x care fac numitorul zero trebuie excluse din domeniu.
    • Exemplu: $f(x) = \frac{1}{x-2}$, Domeniu: $(-\infty, 2) \cup (2, \infty)$
  • Pentru funcțiile cu radicali de ordin par, expresia din interiorul radicalului trebuie să fie mai mare sau egală cu zero.
    • Exemplu: $f(x) = \sqrt{x+4}$, Domeniu: $[-4, \infty)$
  • Pentru funcțiile logaritmice, argumentul logaritmului trebuie să fie mai mare decât zero.
    • Exemplu: $f(x) = \ln(x-3)$, Domeniu: $(3, \infty)$

Codomeniul

• Codomeniul unei funcții $f(x)$ este mulțimea tuturor valorilor de ieșire posibile (valori ale lui y) pe care funcția le poate produce.
• Pentru a găsi codomeniul:
  • Reprezentați grafic funcția și observați valorile posibile ale lui y.
  • Rezolvați ecuația pentru x în termeni de y, apoi găsiți domeniul expresiei rezultate; acest domeniu este codomeniul funcției originale.
  • Alternativ, utilizați tehnici de calcul (calculând puncte critice) pentru a determina codomeniul.

Exemple de calcul al domeniului:

• Pentru $f(x) = \frac{\sqrt{x+5}}{x-3}$:
  • Numeratorul: $x+5 \geq 0 \Rightarrow x \geq -5$
  • Numitorul: $x-3 \neq 0 \Rightarrow x \neq 3$
  • Domeniu: $[-5, 3) \cup (3, \infty)$
• Pentru $f(x) = \sqrt{25-x^2}$:
  • Domeniu: $25-x^2 \geq 0 \Rightarrow x^2 \leq 25 \Rightarrow -5 \leq x \leq 5$, Domeniu: $[-5, 5]$
  • Codomeniu: Deoarece $f(x)$ este o rădăcină pătrată, $f(x) \geq 0$. Valoarea maximă apare la $x=0$, $f(0) = \sqrt{25} = 5$. Astfel, codomeniu: $[0, 5]$
• Pentru funcția $f(x) = x^2 - 4x + 7$:
  • Completați pătratul: $f(x) = (x-2)^2 + 3$.
  • Deoarece $(x-2)^2 \geq 0$, valoarea minimă a lui $f(x)$ este 3.
  • Codomeniu: $[3, \infty)$

Funcții definite pe porțiuni

• O funcție definită pe porțiuni este definită de mai multe sub-funcții, fiecare aplicându-se unui anumit interval al domeniului.
• Exemplu:
  • $f(x) = \begin{cases} x^2, & x < 0 \ x+1, & 0 \leq x \leq 2 \ 3, & x > 2 \end{cases}$
• Pentru a evalua o funcție definită pe porțiuni, determinați în ce interval se află valoarea de intrare și utilizați sub-funcția corespunzătoare.
  • $f(-1) = (-1)^2 = 1$
  • $f(1) = 1+1 = 2$
  • $f(3) = 3$

Compunerea funcțiilor

• Compunerea funcției $f$ cu $g$ este notată ca $(f \circ g)(x) = f(g(x))$.
• Pentru a evalua o funcție compusă, evaluați mai întâi funcția interioară $g(x)$, apoi utilizați rezultatul ca intrare pentru funcția exterioară $f(x)$.
• Exemplu:
  • $f(x) = x^2$ și $g(x) = x-3$
  • $(f \circ g)(x) = f(g(x)) = f(x-3) = (x-3)^2$
  • $(g \circ f)(x) = g(f(x)) = g(x^2) = x^2 - 3$

Rezolvarea Algoritmică a Problemelor

Ce înseamnă "Rezolvarea Algoritmică a Problemelor"?

• Utilizarea algoritmilor computerizați pentru a rezolva probleme.
• Accent pe eficiență.
• Proiectarea algoritmilor și a structurilor de date.
• Transformarea ideilor în cod.

Modalitate de evaluare

• Exerciții de laborator săptămânale (20%).
• Două teme (40%).
• Examen final (40%).

Exerciții de laborator săptămânale

• O serie de probleme mici de rezolvat în fiecare săptămână.
• Termen de predare: Duminică, ora 23:59.
• Valorează 2% din nota finală fiecare.

Teme

• Două teme mai mari.
• Un amestec de proiectare și implementare a algoritmilor.
• Valorează 20% din nota finală fiecare.

Examen final

• Nu se admit materiale ajutătoare.
• Un amestec de teorie și implementare.
• Valorează 40% din nota finală.

Ce este un algoritm?

• O procedură bine definită.
• Primește o anumită intrare.
• Produce o anumită ieșire.
• Exemplu:
  • Intrare: O listă de numere
  • Ieșire: Aceeași listă, sortată în ordine crescătoare

Descrierea algoritmilor

• În limba engleză
  • Ușor de înțeles, dar nu precis.
• Pseudocod
  • Mai precis decât engleza, dar mai ușor de înțeles decât codul.
• Cod
  • Cel mai precis, dar mai greu de înțeles.

Subșir maxim

• Intrare: Un tablou de numere, de exemplu, $[-2, 1, -3, 4, -1, 2, 1, -5, 4]$.
• Ieșire: Suma maximă a oricărui subșir contiguu, de exemplu, $6$ (pentru $[4, -1, 2, 1]$).

Algoritmul 1: Forța brută

• Pentru fiecare subtablou posibil, se calculează suma sa.
• Se urmărește suma maximă observată până acum.
• Se returnează suma maximă.

Algoritmul 2: Divide și cucerește

• Se împarte tabloul în două jumătăți.
• Se găsește recursiv subtabloul maxim în fiecare jumătate.
• Se găsește subtabloul maxim care traversează punctul de mijloc.
• Se returnează maximul dintre cele trei.

Algoritmul 3: Programare dinamică

• Se urmărește suma maximă care se termină la fiecare poziție.
• Suma maximă este maximul acestor valori.

Analiză

• Forța brută: $O(n^2)$
• Divide și cucerește: $O(n \log n)$
• Programare dinamică: $O(n)$

De ce contează eficiența

• Problemele din lumea reală pot fi foarte mari.
• Un algoritm lent poate dura zile, săptămâni sau ani pentru a rula.
• Un algoritm eficient poate rezolva aceeași problemă în câteva secunde.

Căutare

• Intrare: O listă de numere și o valoare țintă.
• Ieșire: Adevărat dacă valoarea țintă se află în listă, Fals altfel.
• Dacă lista este sortată, putem folosi căutarea binară: $O(\log n)$
• Dacă lista nu este sortată, trebuie să folosim căutarea liniară: $O(n)$

Sfaturi pentru rezolvarea algoritmică a problemelor

• Înțelegeți problema.
• Proiectați un algoritm.
• Implementați algoritmul.
• Testați algoritmul.
• Analizați algoritmul.

Descompunerea problemelor

• Împărțiți problema în subprobleme mai mici.
• Rezolvați fiecare subproblemă independent.
• Combinați soluțiile la subprobleme pentru a rezolva problema inițială.

Tehnici algoritmice comune

• Divide și cucerește
• Programare dinamică
• Algoritmi grafici
• Backtracking
• Branch and Bound

Nu reinventați roata

• Utilizați algoritmi și structuri de date existente.
• Biblioteci precum STL și Boost.
• Resurse online precum Stack Overflow.

Practică, practică, practică

• Rezolvați multe probleme.
• Participați la concursuri de codare.
• Citiți codul altor persoane.