Una especificació no ambigua de com resoldre una classe de problemes. Exemple: sortir de casa.
Encara no parlem de programes!
algorisme + dades ⇒ programes
Activitat: algorisme per trobar el nombre més gran d’una llista desordenada (sense codi)
La notació O(...) gran permet classificar els algorismes en funció dels requisits de temps o espai quan les dades d’entrada creixen. Descriu el pitjor escenari.
Exemple: un dels n alumnes de la classe ha amagat la meva cartera
O(1): sé qui és l’alumne que ha amagat la cartera ⇒ li pregunto
O(n): només un alumne, que ha amagat la cartera, sap on és ⇒ he d’anar un a un preguntant
O(log n): tots els alumnes saben qui ha amagat la cartera, però només m’ho diran si endevino el nom ⇒ vaig dividint la classe i pregunto a tots si és a la dreta o a la esquerra
O(n2): a tota la classe, només un alumne sap a quina taula és la cartera ⇒ pregunto a cada alumne i li pregunto per la resta d’alumnes
Activitat: quina és la complexitat de l’algorisme per trobar el nombre més gran d’una llista desordenada? I si fos una llista ordenada?
És una forma d'organitzar i emmagatzemar dades per que que es puguin accedir i (opcionalment) modificar eficientment
quines operacions (queries) tenim? ⇒ quina estructura utilitzar
Operació habitual: trobar un registre que tingui un camp igual a un cert valor
Alguns tipus de dades:
Mètode iteratiu. Considera els conceptes en negreta:
Repetir, mentre no es trobi i quedin elements per buscar:
Reflexiona:
Veure vídeo:
Alguns algorismes senzills d'ordenació:
Reflexió: com podem ordenar un array?
Activitat: com faries una ordenació manualment? Descriu el teu algorisme perquè algú el pugui implementar en codi (taller).
Alguns algorismes coneguts:
Com sonen diversos algorismes:
https://www.youtube.com/watch?v=t8g-iYGHpEA
Activitat: implementa el selection sort.
Mètode iteratiu. Considera els conceptes en negreta:
Repetir, mentre hi hagi elements per ordenar:
Reflexiona: