Flashcards: Pensament computacional

Totes les targetes del tema

Per fer-hi una ullada ràpida o repassar-les en paper.

1. 1.Què és un algorisme?

   Una seqüència finita d'instruccions precises i ordenades que, a partir d'unes dades d'entrada, resol un problema i s'acaba en un nombre finit de passos.

2. 2.Quins són els quatre pilars del pensament computacional?

   Descomposició (partir el problema en parts), reconeixement de patrons, abstracció (quedar-te amb l'essencial) i disseny d'algorismes (escriure els passos).

3. 3.Què fa una instrucció d'assignació com «s ← s + x»?

   Calcula el valor de la dreta amb els valors actuals i el guarda a la variable de l'esquerra, substituint el que hi havia. No és una equació.

4. 4.Què vol dir fer la traça d'un algorisme?

   Executar-lo a mà pas a pas, anotant en una taula el valor de cada variable després de cada instrucció o de cada volta del bucle.

5. 5.Per a què serveix una estructura condicional «si … llavors … si no …»?

   Per triar quines instruccions s'executen segons si una condició és certa o falsa. Amb «si no, si…» encadenats, s'executa només la primera branca que es compleix.

6. 6.Quina diferència hi ha entre un bucle «per» i un bucle «mentre»?

   El bucle «per» repeteix un nombre de vegades conegut d'entrada. El bucle «mentre» repeteix mentre una condició és certa, sense saber per endavant quantes voltes farà.

7. 7.Què ha de passar dins d'un bucle «mentre» perquè s'acabi?

   Alguna variable de la condició ha de canviar a cada volta i acostar-se al punt en què la condició és falsa. Si no, el bucle és infinit.

8. 8.Què és un error «de fora d'un»?

   Un bucle que fa una volta de més o de menys, per exemple anar fins a $n - 1$ en lloc de fins a n. Es detecta comprovant el primer i l'últim valor del comptador.

9. 9.Què és un comptador i què és un acumulador?

   Comptador: variable que comença a 0 i suma 1 cada vegada que passa alguna cosa. Acumulador: comença a 0 (o a 1 si multiplica) i hi vas afegint valors.

10. 10.Llei de De Morgan: a què equival «no (A i B)»?

    A «(no A) o (no B)». I, a l'inrevés, «no (A o B)» equival a «(no A) i (no B)».

11. 11.Què és una funció recursiva i què necessita sempre?

    Una funció que es crida a si mateixa amb un cas més petit. Necessita un cas base que retorni un valor sense cridar-se, i que cada crida s'hi acosti.

12. 12.Què passa si una recursió no arriba mai al cas base?

    Les crides no s'aturen mai. En un ordinador real, la memòria de les crides pendents s'esgota i surt un error de desbordament de pila.

13. 13.Per què el càlcul recursiu directe de Fibonacci és tan lent i com es millora?

    Perquè recalcula moltes vegades els mateixos valors. Es millora guardant els resultats en una taula (memorització) o amb un bucle que només fa n sumes.

14. 14.Què és el cost d'un algorisme?

    El nombre d'operacions bàsiques (comparacions, multiplicacions…) que fa en funció de la mida n de les dades. Serveix per comparar algorismes que fan el mateix.

15. 15.Quantes vegades s'executa la instrucció interior de dos bucles imbricats «per i d'1 a n, per j d'i a n»?

    $\dfrac{n(n+1)}{2}$ vegades. El cost creix com $n^2$ (quadràtic): si dobles n, el temps es multiplica gairebé per 4.

16. 16.Què és el mètode de Horner i quantes multiplicacions fa per a un polinomi de grau n?

    Una manera d'avaluar un polinomi traient factor comú x successivament: $b \leftarrow b \cdot x + a_k$. Fa només n multiplicacions (cost lineal).

17. 17.En què es basa el mètode de la bisecció per trobar una arrel?

    Si f és contínua i $f(a)$ i $f(b)$ tenen signes diferents, hi ha una arrel a $(a, b)$ (Bolzano). Parteixes l'interval pel punt mitjà i et quedes amb la meitat on hi ha canvi de signe.

18. 18.Com disminueix l'error en el mètode de la bisecció?

    A cada iteració l'amplada de l'interval es divideix per 2. Després de k iteracions, l'amplada és $\dfrac{b - a}{2^k}$.

19. 19.Fórmula del mètode babilònic per aproximar $\sqrt{a}$?

    $x \leftarrow \dfrac{x + a/x}{2}$. Si x és una aproximació per defecte, $a/x$ ho és per excés, i la mitjana s'acosta molt ràpidament a l'arrel.

20. 20.Per què un bucle numèric s'ha d'aturar amb un llindar, com $|y - x| < 10^{-6}$, i no amb «y = x»?

    Perquè l'ordinador treballa amb precisió finita i la igualtat exacta pot no arribar mai: el bucle no s'acabaria. El llindar l'atura quan la millora ja és irrellevant.

21. 21.Com estima $\pi$ el mètode de Monte Carlo amb punts a l'atzar al quadrat $[0, 1] \times [0, 1]$?

    La proporció de punts amb $x^2 + y^2 < 1$ s'acosta a l'àrea del quart de cercle, $\pi/4$. Multiplicant-la per 4 s'estima $\pi$. Amb més punts, millor estimació.

22. 22.Què és un algorisme voraç i quin inconvenient té?

    El que a cada pas tria l'opció que sembla millor en aquell moment, sense mirar endavant. És ràpid, però no sempre troba la solució òptima.

23. 23.Què és un invariant d'un bucle?

    Una propietat que és certa abans de començar el bucle i que es manté després de cada volta. Juntament amb la condició de sortida, permet justificar que el resultat final és correcte.

24. 24.Error típic: calcular una mitjana com «s / n» sense comprovar res. Què és el correcte?

    Preveure els casos límit: si la llista és buida, $n = 0$ i es dividiria entre 0. Cal una condició que tracti aquest cas abans de dividir.

Altres flashcards de Matemàtiques 1r Batxillerat

• Nombres reals, polinomis i nombres complexos
• Àlgebra
• Trigonometria
• Geometria analítica al pla
• Successions
• Funcions
• Límits i continuïtat
• Derivades
• Estadística i probabilitat
• Estadística bidimensional: regressió i correlació
• Distribucions de probabilitat: binomial i normal
• Matrius (introducció)