Al voltant del comptar |
Hi ha altres aspectes relacionats amb els nombres però no tant amb el seu ús quantificador. Són d’especial interès els que es refereixen a l’ordre i a la identificació.
A la nostra societat els nombres es fan servir amb intencionalitats diferents. Són bons per codificar, breus i clars per identificar i fàcilment ordenables. D’aquí que els trobem arreu. La diferència entre codi i identificació (quan parlem de casos com els codis de barres, l'ISBN dels llibres, els números de comptes bancaris, números telefònics...) és més subtil del que sembla, ja que una part del nombre funciona com a codi segons normatives acordades (prefixos telefònics, dos o tres primers dígits dels codis de barres per indicar el país, o els primers dels números de compte que indiquen l’entitat bancària...) i l’altra és purament identificativa i gestionada per les empreses en particular. Per tant a l’activitat corresponent se’n parla d’això però no es separa codi d’identificació.
Al nostre país hem triat la paraula "ordinador" per anomenar el que altres països anomenen "computadora". El segon nom destaca la gran capacitat de càlcul. El primer sembla fer-ho amb la d’ordenar. Però, no és així: el nom significa que és una màquina capaç de donar ordres. Tot i així es pensa que els ordinadors dediquen una quarta part del temps de càlcul en activitats d’ordenació. Per tant és una qüestió important pels programadors informàtics.
|
Tots, en un moment o un altre, ens hem enfrontat al problema de l’ordre i hem viscut en pròpia pell que ordenar és fàcil quan hi ha poc elements però feixuc quan n'hi ha molts. Pensem sinó en quant triguem en ordenar unes poques cartes de la baralla quan estem jugant o quant si el que hem de fer és ordenar tota la baralla per comprovar si tenim totes les cartes. L’estratègia serà diferent: segurament dividirem per colls (espases, copes...) i ordenarem cada coll. |
 |
El problema al que s’enfronten els ordinadors és que quan més elements (registres) es tenen per ordenar més es triga en fer-ho. Però l’augment de temps no creix de forma proporcional sinó que ho fa exponencialment. Mirem-ho:
Ordenar, especialment informàticament, implica dos tipus d’accions:
Un mètode per ordenar s’anomena algorisme d’ordenació. Amb l'algorisme que rep el nom de bombolla ordenar 1000 registres pot implicar unes 750 000 accions; fer-ho amb el doble obliga a fer-ne tres milions. Les accions a fer han augmentat 4 vegades. El temps que trigarem, per tant, també serà el quàdruple. La quantitat d’accions a fer depèn molt directament de la disposició dels registres ja que de vegades podem trobar-los quasi ordenats. De cada algorisme d’ordenació s’estudia el millor cas, el pitjor i el cas promig. A la majoria d’algorismes més senzills si tenim n registres, en el pitjor dels casos, caldran n2 accions.
En el món de la informàtica els algorismes d’ordenació tenen una gran importància i, encara que ens pugui sorprendre hi ha de molt diferents i amb noms molt curiosos: de bombolla, de sacseig, de desgranament, d'apilament, suau, de pentinat... No hi ha un algorisme millor per tots els casos i, com que no sabem quina és la situació inicial dels registres s’han de triar segons altres criteris. Alguns d’aquests criteris poden ser la quantitat de dades, la facilitat de programació, l’ús de memòria addicional o no...
|
L’objectiu de fer conèixer aquest tema a l’alumnat no és tant que coneguin els algorismes com la naturalesa del problema, especialment les condicions en que es planteja i la qüestió de l’increment de complexitat relacionat amb l’augment de registres a ordenar. |
Finalment es veu com actuen quatre algorismes diferents d’ordenació.