aprenentatge de programació · 2020. 11. 10. · calcularia nombres de bernoulli, també va...
TRANSCRIPT
Aprenentatge de
programació
Creació i resolució de laberints
Autor: Abel Batalla Ferrés
Tutor: Miquel Llaràs
2n Batxillerat B
IES Front Marítim
2019-2020
1
Resum
Català
Aquest treball de recerca consisteix en l’aprenentatge de programació en llenguatge
Python i en la seva implementació. He desenvolupat dos programes informàtics, l’objectiu
dels quals és la creació d’un laberint, que pot ser de diversos tipus, i la resolució del
laberint, de dues maneres diferents, perquè el robot pugui trobar-hi la sortida. La
resolució del laberint està dissenyada aplicant el Machine Learning (Aprenentatge
Automàtic) de tal manera que el programa aprèn per si mateix la solució del laberint a
partir de les dades que va obtenint dels seus propis errors. Per a assolir aquests objectius
he hagut d‘aprendre a programar i dissenyar algoritmes.
El treball consta d’una part d’introducció que conté la història de la informàtica i els
ordinadors i una explicació del que és la programació. El cos del treball està constituït
per l’explicació dels dos programes, el de creació i el de resolució. Com a informació
complementària, he afegit uns càlculs estadístics per a poder avaluar l’eficiència de les
dues maneres diferents que he programat de resoldre el laberint.
English
This research work consists of learning how to program in Python and in its
implementation. I have developed two computer programs whose purpose is the creation
of a maze, which can be of different types, and the resolution of that maze, in two different
ways, so that the robot can find the exit. The solving of the maze is designed to apply
Machine Learning in such a way that the program learns for itself the solution of the maze
based on the data it obtains form its own errors. To achieve these goals, I had to learn
how to code and design algorithms.
The work consists of an introductory part which contains the history of computing and
computer science and an explanation of what programming is. The body of the work is
constituted by the explanation of both programs, the one for creation and the one for
resolution. As a complementary information, I have added some statistical calculations to
evaluate the efficiency of the two different ways that I have programmed, of solving the
maze.
2
Castellano
Este trabajo de investigación consiste en el aprendizaje de la programación en el
lenguaje Python y en su implementación. He desarrollado dos programas informáticos,
cuyo objetivo es la creación de un laberinto, que puede ser de varios tipos, y la resolución
de este mismo, de dos maneras diferentes, para que el robot pueda encontrar la salida.
La resolución del laberinto esta diseñada aplicando el Machine Learning (Aprendizaje
Automático) de tal manera que el programa aprende por sí mismo la solución del laberinto
a partir de los datos que va obteniendo de sus propios errores. Para alcanzar estos
objetivos he tenido que aprender a programar y diseñar algoritmos.
El trabajo consta de una parte de introducción que contiene la historia de la informática
y los ordenadores y una explicación de lo que es la programación. El cuerpo del trabajo
está constituido por la explicación de los dos programas, el de creación y el de resolución.
Como información complementaria, he añadido algunos cálculos estadísticos para poder
evaluar la eficiencia de las dos maneras diferentes, que he programado, de resolver el
laberinto.
3
Índex
1. Introducció .......................................................................................................... 4
2. Història de la Informàtica i la Computació ....................................................... 6
2.1 Introducció ..................................................................................................... 6
2.2 Computació Mecànica ................................................................................... 6
2.3 Computació Electromecànica ........................................................................ 7
2.4 Computació Digital Moderna ....................................................................... 11
2.4.1 Primera Generació - Tubs de Buit ..................................................... 11
2.4.2 Segona Generació - Transistors ........................................................ 13
2.4.3 Tercera Generació - Circuits Integrats ............................................... 14
3. Introducció a la programació .......................................................................... 16
- Intel·ligència Artificial i Machine Learning
4. Programació amb Python ................................................................................ 20
4.1 Creació del Laberint ..................................................................................... 20
- Explicació General - Funcions Recursives - Explicació Detallada
4.2 Solució del Laberint ..................................................................................... 33
- Versió fixa - Versió dinàmica - Perquè és Machine Learning
4.3 Anàlisi Estadístic ......................................................................................... 41
5. Conclusions ...................................................................................................... 47
6. Bibliografia ........................................................................................................ 49
7. Annex ................................................................................................................ 51
4
1. Introducció
Sempre he trobat fascinant la informàtica i la tecnologia electrònica, tot i que encara no
he arribat a entendre al detall el funcionament dels ordinadors, al llarg de la meva vida
m’han despertat una forta curiositat. En part, la tecnologia moderna ha donat forma al
món i les societats en les quals vivim, els ordinadors i la informàtica han marcat la forma
de vida moderna. Tot i la seva elevada complexitat, tenim un ordinador o un dispositiu
electrònic potent al nostre abast la major part del nostre dia a dia.
En aquest treball de recerca, la meva intenció era aprendre a programar. Havia fet uns
cursos de programació amb Python fa uns anys però no vaig arribar a consolidar els
coneixements i volia aprofitar aquesta oportunitat per aprendre una habilitat molt útil i que
cada cop ho és més. La programació és una àrea molt àmplia i complexa, cal recórrer un
llarg camí per a dominar-la, el meu objectiu, però, era adquirir una habilitat i uns
coneixements bàsics que poguessin actuar com a fonaments pel meu futur en la
programació.
Vaig decidir fer el treball de recerca sobre la programació i la creació d’un programa
informàtic perquè volia fer un treball que em resultés útil de cara al futur i on aprengués
habilitats noves. També, la programació em semblava un tema molt interessant, útil i amb
un bon potencial per ser recercat i explicat.
El meu treball de recerca consisteix en, i té l’objectiu de, la creació d’un programa
informàtic per mitjà de la programació. El programa estarà fet en un llenguatge de
programació anomenat Python, un llenguatge d’ús general i utilitzat àmpliament avui en
dia. Per a aprendre a programar vaig fer una barreja de dos cursos, sense incloure el
que havia fet anteriorment. Així, com ja havia fet un curs anteriorment, no començava
des de zero i partia d’unes idees molt bàsiques de programació que van anar ressorgint
a mesura que estudiava amb més profunditat per aquest treball de recerca. El primer
curs que vaig fer fa uns anys era de Coursera, els altres dos eren de CodeAcademy i
Snakify.
L’objectiu del meu treball és crear un programa principal que inclou dos programes
diferents. El primer programa consisteix en la construcció d’un laberint, mentre que el
5
segon consisteix en la resolució d’aquest laberint utilitzant l’aplicació del Machine
Learning. He triat, com a programa per a fer, la creació i resolució de laberints perquè
m’ha semblat quelcom molt interessant, inusual i complex, però alhora sense una
dificultat excessiva. Cal remarcar que la resolució del laberint és completament
independent a la creació, comença des de zero i no rep cap informació del programa de
creació que el pugui ajudar. A més a més, he dissenyat i programat dues maneres
diferents tant de construir el laberint com de resoldre’l.
El treball està iniciat per una introducció que consta, primerament, de la història de la
informàtica i els ordinadors i, en segon lloc, d’una explicació de la programació, no per a
aprendre a programar, sinó per poder entendre-la. En cos del treball he explicat els
programes de creació i de resolució de laberints. Com he dissenyat dues maneres de fer
i de resoldre laberints, m’ha semblat interessant afegir, de forma complementària, una
part de càlcul estadístic per a poder comparar els diferents tipus de programes de
construcció i resolució dissenyats.
6
2. Història de la Informàtica i la Computació
2.1. Introducció
Tot i que els ordinadors electrònics són relativament moderns, la necessitat de processar
i calcular informació no ho és. Durant la història de la humanitat, s'han desenvolupat
màquines cada cop més complexes i potents, amb més capacitat de processament i
automatisme. La informàtica i l'ordinador modern no són, per tant, una invenció puntual
d'una sola persona sinó que són producte d'un esforç acumulat i del desenvolupament
col·lectiu fet pels humans al llarg de la història, sobretot els últims 400 anys.
L'àbac, la primera eina creada per ajudar als humans a processar informació, va ser
creada al voltant del 2500 aC pels antics Sumeris, i va ser utilitzada per la majoria de les
principals civilitzacions antigues. L'àbac era una eina molt simple que consistia en fileres
de 10 boles cada una. Cada fila representava una potència de 10 diferent, es comptaven
el nombre d’unitats, de desenes, de centenars, milers, ... Aquesta èina facilitava
considerablement la tasca de comptar sumar i restar i, precisament, es va inventar i va
ser uilitzat quan l'escala de la societat era, simplement, massa gran per a una sola
persona pogués emmagatzemar i manipular amb la seva ment.
2.2. Computació Mecànica
Milers d'anys després de la invenció de l'àbac, s'arriba a l'inici de la computació
mecànica, que va crear els fonaments per al que estava per arribar. L'any
1642, Blaise Pascal inventa una calculadora mecànica pel seu pare, que era recaptador
d'impostos. Aquesta calculadora mecànica, anomenada Pascalina, era capaç de sumar
i restar nombres introduïts amb l'accionament una manovella i podia multiplicar i dividir a
través de sumes i restes repetides. Entre el 1660 al 1700, Gottfried Leibniz, "el primer
informàtic", va crear la seva pròpia màquina de càlcul capaç de fer les quatre operacions
aritmètiques (suma, resta, multiplicació, i divisió) directament. També va ser el primer a
establir els conceptes de l'aritmètica binària.
Quasi 200 anys més tard, al S. XIX, Charles Babagge, "el pare de la informàtica",
dissenya diverses màquines de càlcul. L'any 1820 comença a construir la Màquina de
Diferència o Difference Engine en anglès, que havia de tenir una sèrie d'instruccions
7
fixes, estaria accionada amb una màquina de vapor i imprimia els resultats en una taula.
Una dècada més endavant atura el desenvolupament de la Màquina de Diferència i
comença a treballar en la Màquina Analítica o Analitical Engine en anglès. Aquesta
màquina era una versió més complexa i potent que l'anterior, podia emmagatzemar
dades i llegir instruccions de cartes perforades, essencialment fent-lo un ordinador
mecànic programable. Per motius econòmics cap dels seus dissenys mai van
poder prendre forma física.
Ada Lovelace, “La primera programadora”, treballava junt amb Charles Babagge i l’any
1842 va idear un algoritme dissenyat per a la Màquina Analítica de Babagge que
calcularia nombres de Bernoulli, també va establir alguns dels fonaments de la
programació com l’anàlisi de dades, looping (repeticions) i memory adressing
(Organització de la memòria o dades emmagatzemades, perquè siguin d’accés fàcil per
la Unitat Central de Processament (CPU)).
2.3. Computació Electromecànica
Mig segle després de Babagge, es comença a aplicar l’electricitat a la mecànica dels
ordinadors anteriors, augmentant enormement el seu potencial. L’any 1890, Herman
Hollerith dissenya exitosament, amb la inspiració de Babagge, una de les primeres
màquines electromecàniques, un census tabulator (tabulador del cens). Aquesta
màquina es va aplicar als EUA per a fer el cens de població1 de l’any 1890. Als EUA es
feia un cens de població cada deu anys; per a l’últim havíen tardat set anys en recol·lectar
totes les dades, es va calcular que, amb el cens del 1890, tardaríen uns tretze anys.
Aquesta tasca demandava una eficiència que només podien proporcionar ordinadors, i
doncs, es va utilitzar la màquina de Hollerith, que va acabar el recompte en dos anys i
mig. Per a fer el recompte, la màquina llegia dades de targetes perforades, fins a 65 a la
vegada i comptava i ajustava els resultats. Va tenir molt d’èxit i va crear la seva empresa
per a vendre aquesta màquina. Aquesta empresa, a l’unir-se amb altres empreses,
acabaria transformant-se en IBM, un dels gegants del mercat dels ordinadors del segle
1 Els resultats del cens de població és una de les principals informacions utilitzades per a entendre les situacions socials,
econòmiques i demogràfiques tant nacionalment com localment.
8
passat. Per a fer el cens de població, se’ls hi donaven unes cartes als enquestats a les
quals feien uns forats a les respostes que volien marcar. Un cop es tenia la targeta
perforada, s’introduïa a la màquina i una sèrie de pins intentaven fer contacte amb els
seus receptors corresponents per a deixar passar corrent; segons on eren els forats de
la targetes només uns pins determinats arribaven a fer contacte, això accionava un motor
que manipulava el comptador. La màquina de Hollerith va tenir molt èxit en facilitar
enormement la tasca del Census Bureau, la qual anteriorment es feia mà.
Durant les següents dècades, les màquines de càlcul van ser aplicades en molts governs
i empreses per la seva eficiència i reducció de la dificultat d’algunes tasques.
L’any 1936 Konrad Zuse, un enginyer alemany, inventa el Z3, el primer ordinador
programable. Aquest ordinador llegia instruccions d’una cinta perforada i era el primer
ordinador que utilitzava lògica booleana i el sistema binari a través de l’ús del relé.
Com funciona un relé?
El relé, o relay en anglès, és un interruptor mecànic de corrent que està activat
per un corrent secundari. És electromecànic perquè interromp el circuit a través
de moviment físic i tarda mil·lisegons en ser actuat. Funciona de la següent forma:
Un material conductor genera un camp magnètic quan corrent elèctric passa per
ell. Aquest principi s’utilitza en el funcionament del relé: quan el corrent de control
és activat, passa per una bobina i genera un camp magnètic. Aquest camp
magnètic atrau i mou un braç metàl·lic que, en canviar de posició, provoca un
contacte amb el terminal que obre el circuit principal.
9
Sistema Binari
Els relés, tubs de buit i transistors són variacions d’un mateix principi que és, bàsicament,
un interruptor que controla el pas d’electricitat a través d’un segon canal d’electricitat.
Amb només dos estats d’electricitat podem representar informació. Aquesta
representació s’anomena representació binària que literalment vol dir “de dos estats”. En
informàtica, aquests estats prenen el valor d’1 i 0, una representació numèrica, i en
àlgebra booleana prenen true i false.
Aquests dos estats de l’electricitat impliquen que totes les dades que manipula un
ordinador estan en forma binària. Un transistor equival a = 1 BIT (Binary digiT), i 1 Byte
= 8 bits. Com un byte té vuit dígits, pot “comptar” des de 0 fins a 255. Generalment, una
dada individual (número o lletra) s’emmagatzema en un byte (si es necessita més es
poden sumar bytes o adjuntar-los per a crear fins a 16 xifres binàries).
Els números es poden passar fàcilment a base 2 (binari), per exemple: el número 1
equival a 1, el 2 a 10, 3 a 11, el 8 a 1000, el 53 a 110101 i el 255 a 11111111. Si escrivim
aquests nombres en bytes sencers, serien 00000001, 00000010, 00000011, 0001000,...
Les lletres i els caràcters es passen a binari mitjançant el codi ASCII (American Standard
Code for Information Interchange), que converteix les dades d’un ordinador, que només
pot estar en nombres binaris, a lletres i viceversa. Cada caràcter (puntuació, lletres,
números, etc.) li correspon una combinació d’un byte.
Per exemple, la lletra “A”, en majúscula, té un número ASCII de 65, el 65 equival a unes
8 xifres binàries determinades. (“A”: num ASCII = 65 -> 01000001). Si en un processador
de text escrius “A”, vol dir que en algun lloc del teu ordinador hi ha una filera de transistors
amb el patró 0 1 0 0 0 0 0 1.
Si necessitem vuit transistors per a un sol caràcter, el número de transistors que es
necessiten per a fer una sola cosa tan simple com pujar un estat al Facebook és
absolutament enorme. Per sort, el progrés de la tecnologia permet incloure als ordinadors
i als seus processadors cada cop més transistors, més ràpids, més petits, més barats i
amb menys consum. Com a referència, l’ordinador mateix amb el qual estic escrivint
aquest text té una CPU amb uns 2.160 Milions de transistors.
10
Àlgebra Booleana
L’àlgebra booleana va ser creada per George Boole al S XIX, i es basa en àlgebra on les
variables poden prendre valors True (veritat o 1) I false (mentida o 0) i les operacions no
són matemàtiques sinó lògiques.
Hi ha una varietat d’operacions, les més bàsiques són les següents:
NOT, canvia el valor al seu contrari. (True a False i False a True)
AND, dona True com a resposta si, i només si, les seves dues entrades són True.
OR, dona True com a resposta si una de les entrades és True.
XOR, dona True com a resposta si, i només si, una de les seves entrades és True.
Totes aquestes operacions es poder fer físicament amb transistors i quan aquestes
operacions lògiques es posen en un sistema ordenat i es desenvolupen es pot arribar a
crear un sistema lògic capaç de fer operacions matemàtiques i, amb més
desenvolupament, es poden crear les bases per als ordinadors potents com els d’avui
dia.
Seguint amb el desenvolupament dels ordinadors, uns anys després del Z3, Zuse
utilitzaria cintes perforades per a codificar informació en binari, essencialment
convertint-los en els primers dispositius d’emmagatzemament de dades. L’any 1942,
Zuse treu al mercat el primer ordinador comercial (Z4) i per això se’l coneix com “l’inventor
de l’ordinador modern”.
Al 1937 Howard Aken junt amb els seus companys de Harvard i la col·laboració d’IBM
van començar a construir el Harvard Mark I. Era una calculadora programable inspirada
en la màquina analítica de Babagge. Era extremadament gran i complex, capaç
d’emmagatzemar 72 números de fins a 23 dígits (decimals) de llarg, podia fer tres sumes
o restes per segon, una multiplicació en sis segons, una divisió en quinze segons i
logaritmes o funcions trigonomètriques en un minut.
11
2.4. Computació Digital Moderna
2.4.1. Primera Generació - Tubs de Buit
La investigació i recerca dels anys trenta i quaranta, va proporcionar al món de la
informàtica i la computació una eina que va resultar molt útil, els tubs de buit com a
substitut dels antics relés. Els tubs de buit eren completament electrònics (digitals) i eren
més eficients, ràpids i fiables.
Com funciona un tub de buit?
Un tub de buit consisteix en una petita cambra de vidre (similar a una bombeta
tradicional) que està al buit o ple amb un gas inert. A l’interior del tub es troben
tres components: un escalfador, un ànode (envia electrons) i un càtode (rep
electrons). L’ànode i el càtode formen part de la línia elèctrica principal però no
estan en contacte, estan separats pel buit o el gas inert, fet que impedeix el pas
d’electrons. El moment que l’escalfador rep un corrent elèctric (un corrent
secundari, separat de la línia principal) calenta l’ànode. Aquesta escalfor provoca
que l’ànode “expulsi” els electrons a gran velocitat cap al càtode (Emissió
Termoiònica). El càtode, però, només rep electrons si està carregat positivament,
això permet la introducció d’un cable de control que, quan estava carregat,
provocava el pas d’electrons de l’ànode al càtode; si no tenia una càrrega, el pas
d’electrons, restava impedit.
Des de l’any 1937 fins al 1942 John Atanasoff i Cliford Berry van construir el primer
ordinador digital, anomenat l’ABC. Al contrari que els ordinadors construïts prèviament,
com els de Zuse, aquest no utilitzava relés, sinó els tubs de buit, per tant era
completament digital. Aquest ordinador estava dissenyat per a resoldre equacions lineals
i implementava matemàtica binària i lògica booleana per a resoldre fins a 29 equacions
simultàniament.
L’any 1943, amb la col·laboració d’Alan Turing es va construir el Colossus. Prèviament,
l’any 1940, Alan Turing havia desenvolupat The Bombe basant-se en uns dissenys del
criptologista polonès Marian Rejewski. The Bombe era un dispositiu electromecànic que
ajudava als criptologistes anglesos a desxifrar missatges alemanys encriptats amb
12
L’Enigma, una màquina, també electromecànica, que utilitzaven els alemanys durant la
segona guerra mundial per encriptar i desencriptar els seus missatges secrets.
L’aplicació de The Bombe va donar als aliats un molt valuós avantatge durant la guerra.
El Colossus era un ordinador digital que també s’utilitzava per a desxifrar codis críptics
alemanys, aquest, però, desxifrava quelcom molt més difícil, el Xifrat de Lorenz, que era
producte d’unes altres màquines electromecàniques, les SZ40, SZ42a i SZ42b.
Implementava tubs de buit, no com The Bombe que utilitzava relés. Al contrari de, l’ABC
el Colossus era completament programable, titulant-lo el primer ordinador digital
completament programable. La programació, en aquest cas, es feia connectant cents de
cables en un panell d’una forma determinada i, així, preparant a l’ordinador per a fer les
operacions adequadament, per tant havia d’estar configurat per a resoldre un càlcul
específic i s’havia de reconfigurar si es volia fer un càlcul diferent.
L’any 1946, es va finalitzar la construcció de l’ENIAC (Electrical Numerical Integrator And
Computer), el primer ordinador de propòsit general que podia resoldre una gran varietat
de problemes numèrics a través de la reprogramació, que en el seu cas, es feia
manipulant les conneccions d’un panell i amb una sèrie d’interruptors. Pel seu temps
tenia una potència elevada i tenia una velocitat mil vegades més gran que els ordinadors
electromecànics.
Durant el desenvolupament del ENIAC, John Von Neumann va idear el principi d’un
programa integrat emmagatzemat a la memòria electrònica del mateix ordinador que
podia ser manipulat i modificat de la mateixa forma que les dades i ser descodificat en
binari. Això contrastava amb els altres ordinadors del moment, on les instruccions i la
programació estaven emmagatzemades en panells amb conneccions o en cintes
perforades. Aquest principi ideat va portar a l’Arquitectura Von Neumann, que formula un
model que ha de segur un ordinador, que consisteix en una CPU (element central de
processament), una memòria interna i uns dispositius d’ entrada i sortida; aquesta
arquitectura és una implementació física dels estudis de Turing. Von Neumann va assistir
en el desenvolupament de l’EDVAC (Electronic Discrete Variable Automatic Computer),
el successor l’ENIAC, completat l’any del 1950. Aquest ordinador va ser el primer amb
programa emmagatzemat i podia executar mil instruccions per segon.
13
2.4.2. Segona Generació - Transistors
Tot i que els tubs de buit eren una gran millora respecte als relés, seguien sent cars de
produir, utilitzaven molta energia i eren poc fiables, ja que es cremaven sovint. Els tubs
de buit també ocupaven i pesaven molt, aquest és la raó per la qual els ordinadors
d’aquell temps pesaven tones i ocupaven habitacions senceres.
L’any 1947 es va inventar el primer transistor de silici i el 1954 el primer ordinador de
transistors digital va ser creat. Aquest ordinador, anomenat Tradic, consistia de 800
transistors, ocupava un espai radicalment menor que l’ENIAC, consumia molta menys
energia que els seus predecessors i podia executar un nombre d’operacions per segon
molt més elevat que els seus germans anteriors als transistors.
Com funciona un transistor?
Els transistors funcionen d’una forma semblant als relés o els tubs de buit, és a
dir, són uns interruptors que poden estar oberts o tancats segons si s’aplica
energia elèctrica a través d’un cable de control. Els transistors eren molt més
ràpids i petits que els seus avantpassats i no patien desgast físic com els relés ni
eren tan fràgils com els tubs de buit. La física darrere dels transistors és complex
però, bàsicament, consisteix en dos electròdes separats per un semiconductor. La
conductivitat d’aquest semiconductor pot ser manipulada a través del cable de
control. La invenció del transistor va significar l’inici d’una revolució tecnològica.
Amb aquesta nova era es comencen a veure grans desenvolupaments, tant del hardware
com del software. Recordem que el hardware és tot el maquinari físic de l’ordinador i el
software és tot el programari. Pel costat del hardware veiem la introducció del Random
Access Magnetic Core Store o, com el coneixem avui dia, el RAM l’any 1951. També
veiem el primer disc dur, produït per IBM l’any 1957; pesava una tona i podia
emmagatzemar fins a 5Mb. Pel costat del software es va progressar molt, gràcies a que
es va estandarditzar el hardware i l’arquitectura dels ordinadors. Fins aquell moment el
programa d’un ordinador estava escrit en machine code que podia ser executat
directament per l’ordinador. Però des de llavors es van crear llenguatges de programació
d’alt nivell i de baix nivell. Els llenguatges de programació d’alt nivell són els que
14
s’adaptaven millor als humans i com a conseqüència, són els més utilitzats avui en dia.
També existeixen els llenguatges de baix nivell, que s’aproximen més al machine code.
El primer llenguatge de programació, l’Assembly, es va crear l’any 1949 i era un
llenguatge de baix nivell que proporcionava una forma de comunicar-se amb la màquina
sense haver d’utilitzar machine code.
Tot i que els llenguatges de baix nivell eren menys complexes que el machine code, es
seguia necessitant un ampli coneixement de l’arquitectura del ordinador per a
desenvolupar-lo, aquest no era el cas amb els llenguatges d’alt nivell.
El primer llenguatge de programació d’alnt nivell utilitzat àmpliament va ser el Fortran,
creat l’any 1954 per IBM, el fet de que fós d’alt nivell va facilitar que s’estengués el seu
ús.
2.4.3. Tercera Generació – Circuits Integrats
Els transistors van significar un enorme avanç respecte tubs de buit, tot i això, havien
d’estar individualment connectats i soldats, això presentava molta dificultat i més
potencial per a errors, sobretot si es té en compte el ràpid creixement de la complexitat
de la tecnologia en aquells temps. Tot això va canviar l’any 1958 amb la invenció del
circuit integrat (Integrated Circuit) que proporcionava una forma d’incloure un gran
nombre de transistors en un sol xip, això reduïa notablement els costs de producció i
l’energia consumida. Els circuits integrats van significar una revolució en el hardware de
l’època, gràcies a la miniaturització que proporcionaven i no només ho va ser per als
ordinadors sinó també per a tots els altres tipus de components, com per exemple el
ratolí que va ser creat el 1964.
La velocitat, el rendiment, la memòria i la capacitat d’emmagatzemament es va veure
augmentada exponencialment gràcies als circuits integrats a mesura que es podien
instal·lar més transistors en superfícies cada cop més petites.
De la mà del desenvolupament del hardware va venir un progrés en el món del software
i es va crear infinitats de llenguatges de programació com el BASIC (1964) o el C (1971).
15
El progrés de la tecnologia al llarg dels últims segles i, sobretot, des de la invenció del
transistor i el circuit integrat, han permès a la tecnologia i la informàtica arribar al punt on
ara estan. Com a curiositat, una calculadora no científica actual té una potència de
processament similar a l’ordinador de 30 kg utilitzat a les missions Apollo2 de la NASA,
l’Apollo Guidance Computer.
2 L’Apollo 11 és la missió on, per pimera vegada a la hisòria, un humà va estar a la superfície de la lluna.
16
3. Introducció a la programació
En l'actualitat tenim una infinitat d'aplicacions informàtiques a la nostra disposició, moltes
de les quals, ni ens adonem que les estem fent servir. Acostumem a donar per fet el
funcionament de la tecnologia, però què és realment el que fa que la tecnologia moderna
funcioni? Què hi ha darrere de les pantalles i la resta de hardware? La resposta és el
software, o, en altres paraules, els programes.
Avui en dia trobem programes a tot arreu, des dels processadors de text com el Word,
als programes d'un cotxe intel·ligent de conducció pròpia, passant per les aplicacions
que tenim al mòbil, els sistemes de reconeixement de cares que utilitzen els serveis
d'intel·ligència, els videojocs moderns o, fins i tot, per controlar el Mars Pathfinder de la
NASA a més de 200 milions de km de nosaltres. I doncs, què són els programes, aquest
quelcom que sembla omnipresent en el nostre món?
La programació és el procés del desenvolupament i creació d'un programa informàtic,
una sèrie d'instruccions que fan o resolen una tasca específica o que controlen l'operació
d'un ordinador en ser executades. Un algoritme és una llista ordenada d'instruccions que
resolen un problema en particular, en general un programa informàtic està construït amb
un gran nombre d'algoritmes diferents.
Un ordinador és un sistema electrònic amb una CPU (element central de processament)
que és capaç de processar i tractar informació. Treballa i manipula aquesta informació
en forma binària (1=corrent elèctric i 0=absència de corrent elèctric) i ho fa a través de
l'execució de programes. Un programa informàtic està escrit per un programador en una
forma comprensible pels humans mitjançant un llenguatge de programació (C, C++,
Java, Python, Fortan Pascal, ...). El programador desenvolupa el que es coneix com
a source code, aquest codi està escrit en llenguatge de programació humà i cal passar-
lo a un llenguatge que pugui "entendre" l'ordinador. Això és el que fa un compilador, un
altre programa informàtic que deriva o tradueix el source code a machine code, que
consisteix en un conjunt d'instruccions que l'ordinador pot executar directament. Mentre
que el source code està escrit en un llenguatge d'alt nivell (adaptat per a humans),
el machine code és un llenguatge comprensible per un ordinador. El machine code és un
17
llenguatge estrictament numèric que està dissenyat per a ser executat el més ràpid
possible. Tot i que és possible escriure un programa directament en machine code, és
una tasca extremadament complexa que només es fa servir en algunes circumstàncies
per a correcció de certs errors en un programa o si s'ha d'invertir el procés de compilació
(passar de machine code a source code).
Per entendre què és la programació, es podria comparar a donar ordres a una persona,
per exemple: -aixeca el braç dret -analitza aquesta frase
-digues: “Hola, bon dia!” -fes un dibuix d’una casa
-resol aquesta equació
La diferència és que un ordinador no té intuïció per sí sol i no pot fer res que no li hagis
ordenat, un ordinador es podria equiparar a una persona molt capaç i amb molt potencial
però sense cap coneixement, ni intuïció, ni intel·ligència. Posem un exemple: si li volem
dir a una persona que es renti les dents és tan simple com dir-li “renta’t les dents”, però
a un robot li hauríem d’ordenar d’una forma molt diferent. En primer lloc hauríem de dividir
la tasca de rentar-se les dents en vàries subtasques més simples, per exemple, “troba el
raspall de dents”, “troba el dentífric”, “posa la pasta de dents a sobre el raspall”, etc. Però
no és tan simple, només estem començant, doncs cada una d’aquestes tasques més
simples s’han de tornar a dividir en subtasques i així progressivament fins que la tasca
sigui executable per l’ordinador i que la compilació d’aquestes tasques petites ens doni
el resultat que vulguem. Per exemple, si volem posar la pasta de dents sobre el raspall,
hauríem de dividir la tasca i dir “agafa i mou el raspall de dents i el dentífric davant teu”,
“apreta el dentífric amb 0,3N de força durant 1 segon”, etc. Cada cop simplifiquem més
la tasca perquè sigui més fàcil d’executar. Aquestes últimes ordes estan lluny, però, de
que les pugui executar un robot, hauríem de dividir-les molt més amb un programa
d’identificació d’imatges que pogués trobar el raspall i el dentífric, amb un accionament
dels motors per a ser capaços de realitzar cada moviment, etc. Un enriquiment que es
podria afegir a aquest programa de rentar-se les dents és posar una condició a l’inici: “Si
són les 10 de la nit i has sopat segueix el programa:”. Una altra ampliació que podríem
aplicar-li seria introduir un bucle a l’ordre de raspallar-se les dents:
“Repeteix durant 2 minuts:”
“Mou el raspall horitzontalment endavant i enrere.”
18
Fig. 1: Programa simple, amb una condició, que retorna el
número més gran donats dos nombres introduïts per l’usuari.
Fig. 2: El que retorna el programa
anterior (output). En verd: els dos
nombres introduïts per mi.
Totes aquestes ordres són exemples que semblen evidents o trivials per a nosaltres, els
humans, però una màquina no les podria executar per falta del coneixement, i intuïció si
no se li indiquen perfectament desglossades
La complexitat d’un programa pot variar molt, des d’aquest petit programa de sumes que
he escrit fins a la creació d’una consciència artificial, fita en la qual s’està treballant
actualment.
Per a programar hi ha una gran varietat de llenguatges de programació disponibles, amb
alguns llenguatges l’única diferència és la sintaxi (la forma en la qual s’escriu), en altres,
canvia l’especialització i el que pot fer en si. Per exemple, trobem llenguatges de
manipulació de dades com el SQL, especialitzats per a les matemàtiques com el Fortan,
dissenyats per a la representació gràfica com l’HTML, també en trobem d’alguns més
generals com el C++ i el Python. El Python serà el llenguatge de programació que
utilitzaré per a fer dos programes, un que creï un laberint i un altre que el resolgui.
Intel·ligència Artificial i Machine Learning
La intel·ligència artificial és una de les àrees de les ciències informàtiques que consisteix
en el desenvolupament de sistemes informàtics que poden executar tasques que
requereixen intel·ligència, alguns exemples poden ser reconeixement d’imatges o de veu,
resolució de problemes, aprenentatge, planificació, ... Aquests programes no estan fets
per executar repetidament una sola tasca, sinó que estan dissenyats per a poder-se
adaptar a diferents situacions.
19
Fig. 3: Dibuix que representa les diferències de la programació tradicional i una que implementa machine
learning. A l’esquema de la dreta, que implementa machine learning es veu com el machine learning modifica el
programa segons l’imput que se li dóna i els outputs anteriors.
Machine learning, o aprenentatge automàtic en català, és una de les àrees de la
intel·ligència artificial. Es basa en el fet que és més eficient “ensenyar” als ordinadors a
aprendre que “ensenyar-los” a fer qualsevol tasca possible. Machine learning pretén
donar als ordinadors l’habilitat d’aprendre sense ser programats explícitament, recolzant-
se, en canvi, en patrons; això s’aconsegueix mitjançant la modificació i millora contínua
del seu programa a mesura que se li introdueixen dades. Per tant, es necessiten unes
dades determinades que serveixen d’entrenament, llavors el programa anirà aprenent i
ajustant-se segons les noves iteracions. Un exemple d’això que s’ha utilitzat en la vida
real és, com un robot apren a caminar mitjançant la prova i error. El robot té l’objectiu
d’arribar a una certa distància, farà un nombre elevat de proves on a cada prova farà una
petita modificació i calcularà un ajustament segons les conseqüències de la modificació.
Amb moltes iteracions es va perfeccionant el programa fins a poder arribar a l’objectiu.
3
Més endavant veurem com el programa de resolució del laberint implementa un cert
machine learning molt bàsic.
Fig. 3, Font: Seminari Lisboa de Machine Learning i Inteligència Artificial (2018), Cisco Systems
20
Fig. 4: Algoritme que crea la quadrícula.
“mx” i “my” són les seves dimensions.
Fig. 5: Representació de la llista de llistes, on tots els valors
són 1. En aquest cas, es forma una quadrícula de 5x5.
4. Programació amb Python
4.1. Creació del Laberint
Creació de la quadrícula
L’objectiu és programar dos programes diferents, un que crea un laberint i l’altre que el
resol independentment. El llenguatge de programació que he utilitzat és el Python i ho
he fet a través d’un programa informàtic anomenat PyCharm, que m’ha servit de
plataforma per a treballar-hi. PyCharm es podria descriure com un processador de text
dissenyat per programació que pot executar els programes ell mateix.
En primer lloc caldrà crear la taula / quadricula on dibuixarem el nostre laberint. Això ho
farem a través d’una llista de llistes. Una llista d’elements on cada element serà una altra
llista, creant, per tant, una llista de dues dimensions o una quadrícula.
De moment, tots els valors de les llistes secundàries seran 1. Tots els valors 1
representaran un camí i tots els valors 0 representaran una paret.
21
Fig. 7: Representació d’una quadrícula 11x11 després
d’aplicar l’algoritme anterior. A la dreta podem veure com
queda a la interfície gràfica que programarem més endavant.
Fig. 10: Imatge de la represenació feta per
la interfície gràfica on es veu la quadrícula
amb l’entrada i la sortida.
Fig. 8: Algoritme que tria aleatòriament l’entrada
i la soritda i les pinta a través d’un canvi de valor.
Fig. 6: Algoritme que canvia el valor de les parets laterals a 0.
Un cop tenim la quadrícula creada li introduirem les parets que envoltaran el laberint.
Recordem que les parets tenen un valor de 0.
Amb el procediment anterior hem acabat la quadrícula, ara només falta establir una
sortida i entrada aleatòriament a les parets superior i inferior. Un cop s’hagi fet això,
estem preparats per a pintar-hi el laberint.
22
Creació del Laberint
Hi ha una gran varietat de procediments
possibles per a crear un laberint. Em vaig
decidir per un sistema molt interessant i
relativament simple.
Explicació general
El programa de la creació del laberint es basa en una estructura recursiva on una funció
determinada es crida a ella mateixa amb uns paràmetres nous.
Per a crear el laberint dibuixarem a la taula dues línies perpendiculars que faran de
parets, i obrirem un forat (casella de camí) a tres dels fragments que s’han creat. Això
serà una iteració de l’algoritme, es a dir, una aplicació de la funció.
Fig. 12: Dues línies perpendiculars Fig. 13: Tres obertures a les línies
perpendiculars.
Fig. 11: Resultat utilitzant aquest sistema
23
Al dibuixar les línies perpendiculars, l’àrea inicial s'haurà dividit en quatre i s’hauran creat
quatre quadrants o àrees.
L’algoritme es repetirà a cada un dels quadrants (estructura recursiva) i a cada
subquadrant nou que crearan les noves línies; es seguirà repetint l’algoritme a cada
quadrant nou que es creï fins arribar al quadrant més petit possible. Al final, tota la
quadrícula s’haurà omplert de la mateixa funció (algoritme) i haurem creat un laberint.
4 3
2 1
Fig. 14: Els quatre quadrants creats.
2
1
3
4
1
2
3
4
Fig. 15: Els quatre quadrants creats on
s’aplicarà la funció Fig. 16: Els quatre quadrants més petits, creats
al aplicar la funció a un dels quadrants de la
imatge anterior. La funció també s’aplicarà a
aquests nous quadrants i als quadrants que es
crearan llavors i els que es crearan llavors, etc.
24
Per a simplificar la creació i minimitzar problemes farem que les línies de les parets
només es dibuixin en caselles imparelles (les línies veritcals en unes casellles x
imparelles, i les línies horitzontals en unes caselles y imparelles).
Funcions recursives
Una Funció recursiva és una funció que es crida a si mateixa. La idea general és resoldre
un problema dividint-lo en problemes més petits però que es solucionen de la mateixa
manera que el problema original. En el moment que ja no es pugui dividir en problemes
més petits s’arribarà a una solució simple, que serà la base de les solucions dels
problemes anteriors.
Una forma de representar-ho seria mitjançant aquest esquema:
A() és una funció recursiva, ja que es crida directament a ella mateixa, té aquesta forma
genèrica:
Def funció( arguments apropiats que es passen ):
if cas simple, return valor simple o base // condició de finalització, si es compleix,
es retornarà el valor simple.
Fig. 17: Laberint complert
25
else call funció (arguments més simples) // en el cas que no es compleixi la condició:
autocrida amb una versió més simple
Donada una funció recursiva, fa falta el que s’estableixi una condició de finalització, és a
dir, una condició que faci que la funció aturi el procés de cridar-se ella mateixa. Si no es
dóna el cas simple o condició de finalització, es torna a cridar la funció amb paràmetres
més simplificats.
Exemple: n!
Computar n! Recursivament.
Aquesta és la fórmula matemàtica per computar un factorial:
n! = n * (n - 1)!, per exemple 6! = 6 * 5! = 6 * 5 * 4 * 3 * 2 * 1
Per computar n! S’ha de computar (n - 1)!, és a dir, un problema més simple que es resol
de la mateixa manera. Per això es pot resoldre amb una funció recursiva.
La solució al cas més simple (condició d’aturada) és 0! = 1
Ara escrivim amb Python la funció que calcula el factorial d’un sencer donat. Apliquem la
funció general recursiva anterior:
Def Factorial(n):
if (n == 0): (Si n = 0, s’obtindrà [ 1 ] on s’ha cridat la funciò anteriorment)
return 1; // Cas simple: 0! = 1
else: (Si n ≠ 0, s’obtindrà [ n * (la funció factorial amb n-1) ] on s’ha cridat la funció.)
return (n * Factorial(n - 1)), // Funció General: n! = n * (n - 1)!
Aquí, 0! = 1 és el cas simple a la que la funció recursiva general arriba al simplificar el
problema original. La funció es pararà de cridar a ella mateixa quan es trobi amb el cas
simple.
26
Fig. 18: Part de la funció on es criden les noves funcions.
Les línies on posa són les de condició de sortida,
explicades més endavant.
Explicació en detall
El laberint es crea repetint una funció recursivament, el que farà aquesta funció serà:
- Dibuixar les línies perpendiculars
- Alliberar tres caselles determinades de les línies perpendiculars
- Cridar la mateixa funció amb uns nous paràmetres
La funció rep quatre paràmetres, a, b, c i d:
Aquests paràmetres són les coordenades (x1,y1) i (x2,y2) de la diagonal que defineix el
quadrant. En el moment inicial els paràmetres seran els de la quadrícula sencera.
Això permet que, a l’hora de cridar-se a ella mateixa, introdueixi als paràmetres els valors
x i y de les noves parets que s’han creat i la funció nova només actuarà en aquelles
dimensions. Per tant, cada funció es crida a ella mateixa ( ) quatre vegades diferents
per als quatre quadrants:
Com pintem les línies que dividiran el quadrant en 4 parts?
Triarem un número imparell que serà la posició a l’eix x de la línia vertical i un altre per a
l’eix y que serà la posició de la línia horitzontal. Canviarem el valor de tota la línia a 0 per
als dos casos.
(foto: paret i línia en forma de T. Paret té escrits els números imparells de l’1 a l’11, posarà
numero entre (3 i 9). Lina té escrit 0 a cada casella)
27
Fig. 20: Laberint aleatòri amb solució
única.
Fig. 21: Laberint fet amb valors
mitjans. Solució única.
Fig. 19: Algoritme que tria una posició per les línes horitzontal i
vertical i canvia el valor de les caselles de les dues línies a 0, és a
dir, paret. També pinta els quadrats a la interfície gràfica.
La posició x de la línia vertical serà un nombre imparell entre les parets dreta i esquerra,
i la posició y de la línia horitzontal serà un nombre imparell entre les parets superior i
inferior. Els valors es poden triar de forma aleatòria o poden ser el valor mitjà entre les
dues parets.
- tria un valor aleatori
- tria un valor mitjà (o un imparell proper).
Si fem a les línies a uns valors de posició aleatoris,
acabem amb un laberint de la següent forma:
Si fem les línies a uns valors de posició mitjans, acabem
amb un laberint de la següent forma:
28
Fig. 23: Els quatre trams ( ), els punts de
contacte amb la paret ( ) i el punt d’intersecció
de les línies ( ).
Fig. 22.1: Laberint fet amb valors mitjans
a la y i aleatoris a la x. Solució única. Fig. 22.2: Laberint fet amb valors
mitjans a la x i aleatoris a la y. Solució
única.
Si fem una línia amb un valor de posició aleatori i l’altra línia amb un valor de posició
mitjà, acabem amb un laberint de la següent forma:
Com alliberem les caselles?
Ara que ja tenim dibuixades les línies
que fan de parets cal fer que tres
caselles de les línies siguin camí.
Per a alliberar les tres caselles “dividim”
les dues línies perpendiculars en quatre
trams. Cada tram anirà d’una paret al
punt d’intersecció i identificarem
aquests dos punts.
Un cop tenim els quatre trams, triarem un nombre aleatori del 0 al 3. Aquest nombre serà
el tram al qual no li farem un forat. Si volguéssim fer un laberint amb múltiples solucions,
obriríem els quatre trams i saltaríem aquest pas.
29
Fig. 25: Part del programa que allibera tres caselles.
Sense la línia marcada amb ( ), s’alliberarien quatre
caselles.
Fig. 24.1: Laberint amb única solució. Fig. 24.2: Laberint amb múltiples solucions.
Per a cada tram, menys el que hem decidit aleatòriament que no, triarem un nombre
aleatori entre el punt de contacte amb la paret i el punt de tall de les dues línies principals,
aquest nombre serà la posició dins del tram del punt al qual canviarem el valor i on
crearem camí.
30
Fig. 27: Part de la funció amb la condició de sortida i
que crida de nou la funció per a cada quadrant, com
es pot veure, l’estructura es repeteix quatre vegades.
Fig. 26: Resultat désprés de canviar el valor a tres caselles per a crear camí.
Com repetim la funció als altres quadrants?
Ara que ja hem acabat de fer el que volíem per a una repetició de la funció, cal que es
torni a repetir el procés a cada un dels quatre quadrants nous i als quatre nous
subquadrants que creen cada un d’aquests, etc., així repetidament fins a tenir el laberint
creat (estructura recursiva).
Per tant necessitarem que la mateixa funció del laberint:
1 s’executi a ella mateixa quatre vegades diferents per als quatre quadrants. ( )
2. Sàpiga quan parar i que no es cridi més a ella mateixa. Això s’anomena condició de
sortida. ( )
Per saber quan parar, hem de mirar les
dimensions del nou quadrant que ens toca
treballar. Si el quadrant és massa petit, seria
impossible aplicar-li la funció i el programa
donaria error, per tant, hem d’inserir una
condició de continuació que, en el cas que
no es compleixi, no es cridi de nou a la
funció.
31
Fig. 28: Representació dels límits del nou quadrant, és a dir, els seus
paràmetres.
Si pensem en la diagonal que crea el quadrat ( ) definida per:
x1,y1 ( ) a (x2,y2) ( ), doncs, a = x1, b = x2, c = y1, d = y2.
Aquesta condició ( ) ha de mirar, per a cada quadrant, que les distàncies entre la
paret horitzontal i el tram horitzontal i, i entre que la distancia entre la paret vertical i el
tram vertical sigui major de dos quadrats. Si no és així, encara que es compleixi una de
les condicions, vol dir que el quadrant és massa petit i, per tant, no es cridarà la funció.
Un cop hem establert que el nou quadrant és prou gran per a aplicar-hi la funció, faltarà
cridar la funció ( ) introduint-hi els nous paràmetres. (recordem que els paràmetres
eren les quatre parets que delimiten els quadrants on s’aplica la funció). Aquesta vegada
els paràmetres seran dues de les parets del quadrant vell i dos dels trams creats per les
línies perpendiculars.
:
Ara que ja hem cridat de nou les funcions que havíem de cridar ja haurem acabat de
dissenyar la funció. Quan executem el programa tindrem el laberint fet.
Segons la forma en la qual està escrita el programa, la primera funció a ser cridada és la
del quadrant superior esquerra, per tant, es treballarà sempre aquest quadrant primer
abans que el superior dret i els dos inferiors. Això vol dir que abans de passar a treballar
el següent quadrant, primer han d’estar acabat tots els quadrants que inclou l’actual,
aquest comportament es compleix per a cada iteració de la funció, per tant, a mesura
que es van creant nous quadrants es resoldran primer sempre els superiors esquerra.
Això també vol dir que la primera iteració de la funció també serà l’última en acabar-se
d’executar, ja que no acabarà fins que es completi l’últim quadrant inferior-dreta (l’últim
en ser cridat) de tots els anteriors quadrants inferiors-dreta.
a
c
b
d
32
Fig. 30. Representació de les funcions que es separen en
quatre. El número de la branca significa l’ordre en que serà
executat.
Fins que no s’acaba una branca no es passa a la següent.
Bàsicament, s’executa d’esquerra a dreta i no per nivells.
Fig. 29. Representació de la prioritat i execució dels quadrants.
Fig. 31: Demostració de com els quadrans superior
esquerre es resolen primerla prioritat i execució dels
quadrants.
33
Fig. 33: “vista” del robot, les quatre
caselles que el rodegen.
= Robot
Fig. 32: Resolució d’un laberint. En verd està
la solució i en blau els camins per on ha
reculat.
4.2. Resolució del Laberint
Versió fixa
Ara que ja hem creat el laberint és hora de
fer el programa que el resoldrà. Recordem
els programes de creació i solució són dos
programes diferents i independents. El
programa que resol no obté cap mena
d’informació del que crea el laberint.
L’algoritme que resoldrà el laberint no tindrà una visió completa de tot el laberint sinó
només de les quatre caselles al voltant seu, per tant, haurà de resoldre el laberint des
d’un punt de vista de l’interior del laberint i no pas d’una vista vertical com la que temin
nosaltres quan en resolem un en un paper. No podrà planejar la ruta a priori, sinó que
haurà d’anar provant camins i reculant quan entri en un camí sense sortida fins que robi
el final del laberint.
L’estructura del programa consisteix en un algoritme repetitiu, un bucle, que farà una
iteració per a cada casella a la qual es mou el robot. Cada iteració consistirà d’una sèrie
de condicions i respostes per a cada condició. Hem de tenir en compte totes i cada una
de les possibilitats amb les quals es podrà trobar el robot a cada casella per a poder
formular una resposta adequada.
34
Per a establir per on ha passat el robot i per on ha reculat seguirem un principi similar a
les molles de pa de Hansel i Grettel. Recordem que quan una casella té valor 0 és una
paret i quan té un valor 1, és un camí. El que farà el robot serà incrementar el valor en
+1 cada casella que trepitgi (ja estigui descobrint camí nou o reculant), per tant, un cop
el robot descobreixi la sortida, haurà deixat tota una sèrie de caselles, que inicialment
tenien un valor d’1, amb valors de 2 i 3. Els valors 2 seràn la solució i els valors 3 serà
per on haurà reculat el robot. Totes les caselles amb valor 1 serà camí verge per on no
haurà passat el robot.
Com he dit, es farà una iteració del
bucle per a cada casella on està situat el robot. En aquest bucle s’executarà una fase
d’“exploració” on observarà les caselles que té al voltant, i una fase que consisteix en
una sèrie de comprovacions que, segons les condicions que es presentin al robot,
decidirà a quina casella avançar o si recular.
Ja que l’única informació que rebrà el robot serà quines són les caselles del seu voltant
i els seus valors, necessitem saber la posició i el valor de les quatre caselles que el
rodegen. També cal establir una prioritat en la qual avançar caselles. Per exemple, si el
robot arriba a una paret frontal i es troba amb una bifurcació que li permet anar a la dreta
o a l’esquerra, cap a on va?
Fig. 34: Aquí veiem la solució del laberint (valor 2),
en verd i tots els camins per on ha reculat (valor 3),
en blau.
35
Una possibilitat per a la prioritat és girar, sempre que pot, a l’esquerra (o a la dreta, és el
mateix). L’opció que he triat jo, és que el robot intenta anar endavant sempre que pot,
quan no pot gira a l’esquerra i si tampoc pot, gira a la dreta. Una altra opció seria fer que
avanci sempre que pugui i que decideixi la prioritat d’esquerra o dreta aleatòriament quan
té l’opció d’anar a un costat o l’altre simultàniament.
Saber quina és la casella “de la dreta” és més complex del que sembla. Primerament ens
referim a la casella dreta del robot, des del seu punt de vista, no pas a la de la dreta
absoluta segons la veiem nosaltres. Només serien les mateixes si el robot avança en
direcció vertical i cap amunt.
Com volem que les caselles siguin relatives al robot i no pas al nostre punt de vista
haurem de fer un algoritme que pugui calcular-les. Per a saber les caselles del voltant
del robot necessitarem una sèrie de paràmetres: primerament, la posició del robot (x1,
y1) i, en segon lloc, la direcció i sentit del moviment del robot (∆x, ∆y) (∆ vol dir increment
de ...), la qual es renovarà cada vegada que el robot avanci una casella*. El robot només
es pot moure en vertical i horitzontal, no en diagonal, per tant, sempre hi haurà un dels
increments de la direcció que serà 0, l’altre increment podrà prendre un valor d’1 o -1.
*Sempre que el robot canviï de direcció caldrà ajustar els increments, ja que hauran
variat.
Aquests eixos representen els increments (∆x, ∆y) que
se l’hi han d’aplicar a (x1, y1) per aconseguir les
coordenades de les quatre caselles del voltant.
Faltarà tenir en compte la direcció i el sentit del robot
per a saber quin increment aplicar si volem girar amb
el “punt de vista” del robot, és a dir, la seva dreta, la
seva esquerra, etc.
Fig. 35: Increments a aplicar a (x1,y1) per a obetnir les quatre caselles del voltant.
Nota: l’eix Y està invertit per la forma en la qual està construïda la quadrícula, és
a dir, el (0,0) el tenim dalt a l’esquerra, per tant, si ens desplacem verticalment i
cap dalt estarem restant -1 a la coordenada Y del robot.
36
Per a calcular la posició de la casella del davant del robot, és tan fàcil com [ (x1+∆x),
(y1+∆y) ], ja que els increments seran els mateixos que portava inicialment. Si el que
volem calcular és la casella del darrere del robot, també resulta fàcil: [ (x1-∆x), (y1-∆y) ].
Es complica més, però, quan volem calcular les caselles laterals, això dependrà de si el
valor de ∆x és igual a 0 o no, en altres paraules, si el robot s’està movent verticalment
(∆x = 0) o horitzontalment (∆x ≠ 0).
En el cas que vulguem el punt esquerre i s’estigui movent horitzontalment, la casella
esquerra serà [ (x1+∆x1), (y1+∆y1) ], tal que: ∆x1 = 0 i ∆y1 = -∆x. Si s’està movent
verticalment, la casella esquerra serà [ (x1+∆x1), (y1+∆y1) ], tal que: ∆x1 = ∆y i ∆y1 = 0.
Per acabar, per calcular el punt dret, serà [ (x1+∆x3), (y1+∆y3) ], tal que: ∆x3 = -∆y i ∆y3
= 0 si s’està movent verticalment, i [ (x1+∆x1), (y1+∆y1) ], tal que: ∆x3 = 0 i
∆y3 = ∆x si s’està movent horitzontalment.
Amb aquests càlculs podem saber la posició de les caselles que rodegen el robot i, per
tant, podem saber el seu valor. Des d’aquest punt, analitzarem les caselles del davant i
els costats i respondrem adequadament segons els seus valors. En el cas que el robot
es mogui cap enrere o lateralment caldrà canviar els valors dels increments (∆x, ∆y), ja
que haurà canviat de direcció. (∆x, ∆y) prendran el valor que li hem sumat a (x1,y1) per
a arribar a la casella actual.
37
Un cop tenim els valors de les caselles del voltant, hem arribat a l’hora de prendre
decisions segons aquests valors. Aquestes decisions es poden dividir en dues etapes:
les decisions que es prenen si el robot està explorant camí verge i les decisions que es
prenen en el cas que no hi hagi camí verge possible, on es recularà de casella en casella.
Cada vegada que es prengui una decisió i el robot es mogui una casella es reiniciarà de
nou tot el bucle i es repetirà per a la casella nova.
Les tres primeres decisions s’aplicaran a les
caselles del davant i laterals i seran en cerca de
camí verge (valors 1); si es troba camí verge, el
robot avançarà automàticament a aquella casella.
En el cas que hi hagi múltiples camins verges
s’avançarà segons la prioritat que s’hagi establert
mitjançant l’ordre de les comprovacions.
Seguint aquest algoritme el robot avançarà pels
camins i no passarà mai per una paret (valor 0).
Anirà deixant, a les caselles per on ha passat, un
valor de 2, ja que haurà incrementat el seu valor
en 1. Seguirà així fins que es trobi amb un camí
sense sortida, on llavors passarà a la segona fase
del bucle.
Fig. 36: les tres primeres comprovacions, que
miren si alguna de les tres caselles té valor 1 i
hi avança si és el cas. Es pot veure com l’ordre
de prioritat és davant, esquerra i dreta, ja que
és l’ordre en el qual s’executaran.
38
Si hem fet les tres comprovacions i cap d’elles és un
valor 1, això vol dir que estem en un camí sense
sortida, per tant, girarem cua i començarem a recular.
Quan estiguem reculant, el robot es mourà per
caselles de valor 2 i deixarà enrere caselles de valor
3 (els hi haurà incrementat un punt per a indicar que
ja hi ha passat, algoritme de molles de pa). Un cop
hem girat cua, aplicarem, a cada casella a la qual
reculem, tot el bucle sencer, per tant, mirarà, per
cada casella, si en té una als costats amb valor 1.
Quan trobi una casella amb valor 1, és a dir, camí
verge, haurà arribat a l’última bifurcació que hauria
deixat el robot i repetirà el procés per aquell nou
camí. Aquest bucle de resolució no s’acabarà fins
que el robot trobi la sortida del laberint.
Fig. 37: part de l’algoritme que
s’executa si no es troba caselles
amb valor 1.
39
Fig. 38.1: resolució amb el nou l’algoritme dinàmic Fig. 38. 2: resolució amb l’algoritme fix
Versió Dinàmica
Aquest mètode de resolució fix funciona i és eficaç, el robot sempre acaba trobant la
sortida. Tot i això, volia provar de fer un algoritme dinàmic i semi intel·ligent que fos més
eficient. Aquí podem veure als dos algoritmes diferents en acció
Aquest nou algoritme de resolució te en compte una informació que l’altre algoritme no
tenia, les coordenades de la sortida. L’algoritme consisteix, bàsicament, en decidir l’ordre
de prioritat a les bifurcacions de forma intel·ligent i no a l’atzar. Ho fa calculant la distància
que hi ha des de la sortida a cada una de les caselles 1 a les que es pot moure (caselles
del voltant que tenen valor 1), i tria la casella que tingui la distància més curta a la sortida
del laberint. Calcula la distància amb el Teorema de Pitàgores per a cada casella.
40
Aquesta imatge mostra el càlcul de la distància a la sortida per a cada casella, = robot.
En aquest cas, les caselles 1 i 2 serien caselles de camí i per això calcula la distància a
la sortida (h1 i h2). Si la casella 3 també fos camí, també en calcularia la distància, però
no ho he representat per a no dificultar la comprensió del dibuix. Segons si h1 < h2 o
h1 > h2 avançarà a la casella 1 o a la 2.
Perquè l’algorime de resolució és Machine Learning?
Ambdós algoritmes de resolució del laberint són una implementació molt bàsica i simple
del Machine Learning, o com es coneix en català, l’Aprenentatge Automàtic.
L’aprenentatge del robot consisteix en comprendre quan ha fet un error i tenir en compte
on l’ha fet per a no repetir el mateix error posteriorment, per tant, aprèn de les dades que
va obtenint dels seus propis errors i no els repeteix. Segueix aquest patró fins que acaba
trobant la sortida.
Fig. 39:
Representació del càlcul de les distàncies.
41
4.3. Anàlisi Estadístic En primer lloc, vull deixar clar que aquesta petita anàlisi no és pas la part de “recerca”
del meu Treball de Recerca, simplement és una obtenció de dades i de les seves
conclusions que permeten comparar els dos algoritmes de resolució.
Per a poder comparar els dos algoritmes, el de resolució fix i el de resolució dinàmica,
he fet una recol·lecció de dades i les he analitzat estadísticament per treure’n unes
conclusions. He aplicat certes modificacions al programa que consisteixen en uns
comptadors que miren el nombre passos totals (un pas = moure’s una casella) i el nombre
de passos correctes, és a dir, el nombre de caselles amb valor 2. Recordem que en el
laberint de múltiples solucions hi ha múltiples camins possibles per arribar al final, per
tant, els “passos correctes” són simplement el camí que ha seguit per a arribar al final,
valor que podrà variar, no essent així en el cas del laberint de solució única.
L’objectiu de l’estudi era observar si, en general, l’algoritme dinàmic feia menys passos
per a arribar a la sortida que l’algoritme fix.
La prova consistia en executar els dos programes de resolució diferents per a un mateix
laberint, i obtenir dues mesures per a cada solució:
1. El nombre de total de passos fets.
2. El nombre de passos correctes fets, és a dir, el nombre de caselles amb valor 2.
Utilitzant aquestes mesures volia calcular:
1. El percentatge d’eficiència per a cada algoritme en un mateix laberint,
𝑝𝑎𝑠𝑠𝑜𝑠 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑒𝑠
𝑝𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠× 100.
2. Tot aplicant el càlcul de percentatge d'eficiència del punt anterior en mil laberints
diferents, obtenir, mitjançant dos comptadors, el nombre de vegades que cada
algoritme ha sigut més eficient que l'altre.
3. La relació de passos totals de l’algoritme dinàmic respecte els de l’algoritme fix.
En forma de percentatge: 𝑝𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑒 𝑙′𝑎𝑙𝑔𝑜𝑟𝑖𝑡𝑚𝑒 𝑑𝑖𝑛à𝑚𝑖𝑐
𝑝𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑒 𝑙′𝑎𝑙𝑔𝑜𝑟𝑖𝑡𝑚𝑒 𝑓𝑖𝑥× 100,
(si el percentatge és <100%, ha fet menys passos en total el dinàmic, si és >100%,
ha fet menys el fix.)
42
He fet la prova en un laberint aleatori amb una única solució i en un laberint aleatori amb
múltimples solucions, amb quadrícula de 25x25. He repetit la prova mil vegades per a
cada laberint i he programat el càlcul per obtenir les mitjanes de totes les mesures. A
mode d’exemple, mostro a continuació cinc proves amb els valors obtinguts i les mitjanes
calculades, tant pel laberint de múltiples solucions com pel laberint d’única solució. En
finalitzar els exemples tenim els resultats per a l’estudi, les mil repeticions.
Prova de 5 repeticions
Per a cada tipus de laberint (solució única i solucions múltiples) he aplicat cinc vegades
cada un dels dos algoritmes de resolució (fixe i dinàmic). Aquí veiem els resultats:
Laberint d’una
sola solució
Algoritme
fix
Algoritme
dinàmic
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑖𝑛à𝑚𝑖𝑐𝑠
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑓𝑖𝑥𝑒𝑠
Passos totals 237 213 89,87%
Prova 1 Passos correctes 57
Eficiència 24,05% 26,76%
Passos totals 51 35 68,63%
Prova 2 Passos correctes 35
Eficiència 68,63% 100%
Passos totals 475 259 54,53%
Prova 3 Passos correctes 43
Eficiència 9,05% 16,60%
Passos totals 133 117 87,97%
Prova 4 Passos correctes 61
Eficiència 45,86% 52,14%
Passos totals 487 43 8,83%
Prova 5 Passos correctes 43
Eficiència 8,83% 100%
43
Algoritme
fix
Algoritme
dinàmic
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑖𝑛à𝑚𝑖𝑐𝑠
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑓𝑖𝑥𝑒𝑠
Mitjana
Passos totals 276,6 133,4 61,97%
Passos correctes 47,8
Eficiència 31,28% 59,1%
Visualització del les proves anteriors (exemple nou)
Observacions
Amb les dades que hem extret de les cinc proves anteriors podem veure que, en general,
l’algoritme dinàmic resol el laberint en un nombre total de passos molt menor, amb una
eficiència mitjana de 59,1% respecte al 31,28% en el cas de l’algoritme fixe. Podem
veure, també que en dos ocasions, a la prova 2 i la prova 5, l’algoritme dinàmic ha
Fig. 40: Resolució d’un mateix laberint amb l’algoritme fix (dreta) i el dinàmic
(esquerra)
Fig. 41: La presentació es dades que proporciona el programa. En aquest
cas són les dades per les resolucions anteriors.
44
aconseguit resoldre el laberint sense haver de recular (eficiència del 100%). Es pot
apreciar com la diferència de passos totals varia significativament entre proves, per
exemple, a la prova 1 es veu una relació de les dues mesures de quasi 90%, en canvi, a
la prova 5 es veu una relació al voltant del 9%
Si repetim el proccés anterior per a un laberint amb múltipes solucions, obtenim uns
resultats semblants:
Nota: ara els passos correctes seran el nombre de caselles que té la solució trobada.
Laberint amb
Múltiples solucions
Algoritme
fix
Algoritme
dinàmic
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑖𝑛à𝑚𝑖𝑐𝑠
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑓𝑖𝑥𝑒𝑠
Passos totals 421 135 32,07%
Prova 1 Solució trobada 55 67
Eficiència 13,06% 49,63%
Passos totals 243 165 67,90%
Prova 2 Solució trobada 119 67
Eficiència 48,97% 40,60%
Passos totals 497 119 23,94%
Prova 3 Solució trobada 51 71
Eficiència 10,26% 59,66%
Passos totals 107 125 116,82%
Prova 4 Solució trobada 47 95
Eficiència 43,93% 76%
Passos totals 429 59 13,75%
Prova 5 Solució trobada 107 59
Eficiència 24,94% 100%
45
Algoritme
fix
Algoritme
dinàmic
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑖𝑛à𝑚𝑖𝑐𝑠
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑓𝑖𝑥𝑒𝑠
Mitjana
Passos totals 352 120,6 50,90%
Solució trobada 75,8 71,8
Eficiència 28,23% 65,18%
Observacions
Amb les dades que hem extret de les 5 proves anteriors podem veure que, en general,
l’algoritme dinàmic resol el laberint en un nombre total de passos molt menor, quasi en
una tercera part dels passos, amb una eficiència mitjana del 65,18% respecte al
28,23% en el cas de l’algoritme fix. Podem veure, també que en una ocasió, a la prova
5, l’algoritme dinàmic ha aconseguit resoldre el laberint sense haver de recular
(eficiència del 100%). En una altre ocasió, a la prova 4, l’algoritme dinàmic ha trobat
una solució més llarga i en més passes totals (relació del 116,82%) que l’algoritme fix.
Test de 1000 repeticions
Mitjanes per a 1000 repeticions, laberint de multiples solucions
Algoritme
fix
Algoritme
dinàmic
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑖𝑛à𝑚𝑖𝑐𝑠
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑓𝑖𝑥𝑒𝑠
Mitjana
Passos totals 303,50 109,68 36,14%
Solució trobada 76,93 57,63
Eficiència 35,60% 71,43%
L’algoritme dinàmic resultava més
eficient en un 84,1% dels casos,
el fix en un 15,1%.
Nota: Vaig repetir la prova de les mil repeticions vàries vegades per comprovar si
donava uns valors més o menys constants, i sí que ho eren.
Conclusions del laberint amb múltiples solucions
Podem veure que, en general, l’algoritme dinàmic trobava una solució més curta que el
fix, amb una eficiència mitjana de quasi el doble i que en la majoria de casos (84%)
l’eficiència era millor en el dinàmic. També, el dinàmic trobava la sortida gairebé tres
vegades més ràpid que el fix.
46
Mitjanes per a 1000 repeticions, laberint d’una única solució
Algoritme
fix
Algoritme
dinàmic
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑑𝑖𝑛à𝑚𝑖𝑐𝑠
𝑃𝑎𝑠𝑠𝑜𝑠 𝑡𝑜𝑡𝑎𝑙𝑠 𝑓𝑖𝑥𝑒𝑠
Mitjana
Passos totals 285,95 180,56 63,14%
Solució trobada 62,50
Eficiència 27,72% 47,12%
L’algoritme dinàmic resultava més
eficient en un 81,3% dels casos,
el fix en un 18,7%.
Nota: Vaig repetir la prova de les mil repeticions vàries vegades per comprovar si
donava uns valors més o menys constants, i sí que ho eren.
Conclusions del laberint de solució única
Podem veure que, en general, l’algoritme dinàmic trobava la solució unes 1,6 vegades
més ràpidament, amb una eficiència mitjana propera al doble que el fix, i que, en la
majoria de casos, (81%) l’eficiència del dinàmic era millor.
Conclusions considerant els dos tipus de laberint
Amb les dades que hem extret dels dos laberints podem confirmar que l’algoritme
dinàmic és significativament més ràpid que el fix en la resolució de laberints, i que
aquesta diferència és molt més pronunciada en els laberints de múltiples solucions.
47
5. Conclusions del Treball de Recerca
El primer objectiu del meu treball de recerca era aprendre a programar i considero que
l’he assolit, ja que he adquirit un nivell bàsic de programació. Tot i que encara em queda
molt per a aprendre i descobrir, he arribat a un nivell que em permet dissenyar i construir
programes de certa complexitat i també em serveix com a fonaments per a la meva
programació més avançada en el futur.
El segon objectiu era construir un programa que desenvolupava un laberint i un altre
programa que el pogués solucionar utilitzant Machine Learning (Aprenentatge
automàtic), ja que considero és una de les branques més innovadores i interessants
de la informàtica actual. Vaig estar contemplant dues o tres formes de diferents de
construir laberints, i finalment em vaig escollir una que era prou flexible per poder crear
variants d'un mateix laberint (solució única o múltiple, dibuixar les línies en un valor
aleatori o mitjà, ...).
En general, la tasca ha resultat més difícil de l'esperat, ha presentat forts reptes per a
mi i m’ha obligat a emprar algoritmes d’estructura més complexa, com els recursius.
En tot cas, he pogut desenvolupar un programa prou efectiu tenint en compte el meu
nivell de programació.
El programa de resolució, el que fa que el robot trobi la sortida del laberint, ha resultat
també més complex de l'esperat. L'aplicació de l'algoritme de Hansel i Grettel, tot i que
és intuïtiu pels humans, no ha estat tan fàcil d'implementar en el robot. El programa
funciona i, fins i tot, he pogut fer una optimització a l’algoritme de resolució, creant així,
un segon algoritme de resolució que prenia decisions de forma intel·ligent.; també vaig
poder comparar aquests dos programes de resolució en els diversos tipus de laberints
mitjançant un estudi estadístic.
El programa de resolució de laberints (tant el fix com el dinàmic) és, essencialment un
sistema de navegació per un medi, que, en el meu cas seria de dues dimensions
espacials i amb obstacles que impedien el pas. Això vol dir que si el programa s’apliqués
a un robot real i s’adaptés per a la realitat, un entorn físic i no virtual, el robot podria
navegar per aquest medi. Seria capaç d’adaptar-se a diferents obstacles (és a dir, les
48
parets del laberint) i seria capaç d’arribar al seu objectiu, si és que en té, el qual seria
una localització, posició o coordenades determinades.
En general, estic molt satisfet amb el resultat del meu treball i especialment perquè he
aconseguit superar reptes que han resultat ser desafiants. En termes de l’aprenentatge,
he après a programar i, també, alguns dels conceptes principals sobre els ordinadors i la
informàtica.
Per acabar, m’agradaria remarcar que m’ho he passat molt bé programant i es podria dir
que, a part d’una habilitat adquirida, és també una nova afició i ja tinc pensats alguns
projectes que m’agradaria desenvolupar en un futur pròxim.
49
6. Bibliografia
Cursos de programació
RICE UNIVERSITY: www.coursera.org - “An Introduction to Interactive Programming in
Python”
CODE ACADEMY: www.codecademy.com - “Learn Python 3”
SNAKIFY: www.snakify.org - “Teach Python 3”
Dubtes de programació
CHUWIKI: chuwiki.chuidiang.org
PROGRAMIZ: www.programiz.com
Informació
BIOGRAFIAS Y VIDAS: www.biografiasyvidas.com
CIRCUIT GLOBE: www.circuitglobe.com
CRASH COURSE: www.thecrashcourse.com
EL-PRO-CUS: www.elprocus.com
EMERJ: www.emerj.com
EXPLAINTHATSTUFF: www.explainthatstuff.com
FISIKA ZONE: www.fisikazone.com
FORBES: www.forbes.com
GEEKS FOR GEEKS: www.geeksforgeeks.org
GREEK MYTHOLOGY: www.greekmythology.com
HOWSTUFFWORKS: www.computer.howstuffworks.com
KHAN ACADEMY: www.khanacademy.org
MEDIUM: www.medium.com
50
MICHIGAN STATE UNIVERSITY: www.canr.msu.edu
QUORA: www.quora.com
RAPIDTABLES www.rapidtables.com
RYANS TUTORIALS: www.ryanstutorials.net
SMITHSONIAN NATIONAL AIR AND SPACE MUSEUM: www.airandspace.si.edu
TECHOPEDIA: www.techopedia.com
THE VINTAGE NEWS: www.thevintagenews.com
UNIVERSITAT DE BARCELONA: www.ub.edu
UNIVERSE TODAY: www.universetoday.com
WIKIPEDIA: en.wikipedia.org
YOUTUBE: www.youtube.com
51
7. Annex
El programa sencer
52
53