Posts Tagged ‘universitat’

Apunts de Càlcul: Nombres reals i nombres complexos

1. Nombres reals Naturals [latex]\mathbb{N}=\left\{1,2,3,4,…\right\}[/latex] [latex] \begin{array}{ll}+: & \mathbb{N}\times\mathbb{N} \rightarrow \mathbb{N} \\ & (n, m) \mapsto n+m\end{array} [/latex] Propietats: [latex]\begin{cases} associativa: & a+(b+c) = (a+b)+c \\ commutativa: & a+b=b+a \;\;\;\;\;\; \forall a,b \in \mathbb{N} \end{cases}[/latex] [latex] \begin{array}{ll}\cdot: & \mathbb{N}\times\mathbb{N} \rightarrow \mathbb{N} \\ & (n, m) \mapsto n\cdot m\end{array} [/latex] Propietats: [latex]\begin{cases} associativa \\ commutativa \\ […]

Apunts d’Estructures de Dades i Algorismes: Programació dinàmica

1. Nombres de Fibonacci L'algorisme trivial per al càlcul dels nombres de Fibonacci repeteix molts càlculs. Podem evitar-ho desant tots els valors que calculem en una matriu i cercant-los allà quan ens calguin abans de calcular-los un altre cop (memoization). Si només ens cal obtenir un sol nombre de Fibonacci, podem construir una versió iterativa […]

Apunts d’Estructures de Dades i Algorismes: Les classes de problemes P i NP

Classes de problemes – P i NP Entrades Problemes Classes de problemes (no excloents) [latex]x[/latex] [latex]\pi[/latex] P Coneixem algorismes amb temps pitjor polinomial (o millor) per a decidir el problema. NP Coneixem algorismes en temps polinòmic indeterminista per a verificar si una solució és correcta. Exemples de problemes que estan en NP: HAM – és […]

Apunts d’Estructures de Dades i Algorismes: Cerca exhaustiva

Cerca exhaustiva La cerca exhaustiva és un mètode de disseny d'algorismes que consisteix en mirar-se sistemàtica i intel·ligentment totes les possibles solucions a un problema donat. Generalment els problemes que es resolen mitjançant aquesta tècnica són problemes d'optimització o combinatoris. La tècnica consisteix en generar implícitament un arbre representant totes les possibles solucions i explorar-lo […]

Apunts d’Estructures de Dades i Algorismes: Grafs

Definició i propietats Graf: [latex]\begin{array}{lll}G: & \small V\grave{e}rtexs/Nodes & V = \{1, 2, 3, 4\} \\ & \small Arestes & E = \left\{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{3, 4\}\right\}\end{array}[/latex] Graf dirigit (digraf): [latex]\begin{array}{lll}G': & \small V\grave{e}rtexs/Nodes & V = \{1, 2, 3, 4\} \\ & \small Arcs & E \subset VxV\ \small (un\ arc\ […]

 
Skip to toolbar