Lectura_2_-_Construccion_de_algoritmos
-
Upload
andreapine -
Category
Documents
-
view
213 -
download
0
description
Transcript of Lectura_2_-_Construccion_de_algoritmos
AdrianNicolásMalaverBarrera 1
2. Construccióndealgoritmos
Unavezexplicadoslosprocesosdemodeladoyespecificacióndealgoritmos,reconocidasu importancia y la manera de formalizar entradas, salidas, pre y poscondiciones,comenzaremosatrabajarensuconstrucción.Pensemosenlasiguientesituación:invitamosaunamigoaconocernuestronuevoapartamentoperocuandonospideladirección,soloconocemoselnúmerodelatorreydelapartamento,norecordamosladirecciónexacta¿Quéhacemosentonces?¡Ledamosinstrucciones!Debemostenerencuentaqueestasinstruccionestienenqueserclarasyprecisasparaquenuestroamigonosepierdaniseequivoque.Porejemplo:“TomelarutaD21deTransmilenioqueeslamásrápida,ocualquierrutaquelollevealportaldela80;luegosaledelportal,cruzaelpuentepeatonaldelacalle80,siguedoscuadrashaciaeloccidente,volteaalaizquierda,siguetrescuadrasyllegaaunconjuntocerradodetorresgrisesyblancasde15pisos.Miapartamentoesel904delatorre8”.Noesdifícil…Sitenemosclaralainformación,¡Esposibleresolverelproblema!
Formalmente,aunconjuntoordenadoyfinitodeinstruccionesquepermitenobtener,conbaseenunconjuntodeentradas,unconjuntodesalidasquerepresentanlasoluciónalproblema,lollamaremosalgoritmo.
Ahorasabemosloquerequerimosparasolucionarunproblemadeformaorganizada:susentradasysalidas,lasprecondicionesyposcondicionesdefinidasparaesosdatosyunalgoritmoquedescriba,apartirdeinstruccionesclarasyprecisas,pasoapasoloquesedebehacerparallegaraunasolución.Siqueremosdefinirunalgoritmoenunlenguajequecualquierpersonapuedaentenderdebemostenerencuentaciertasreglas.Estasreglasyloselementosqueconstituyenunalgoritmolosiremosconociendoconeltiempo,alolargodeestecurso.¡Comencemos!
2.1 Asignación
Unalgoritmosecomponedeunconjuntodeinstruccionesquedebenserrealizadasordenadamente,conelobjetivodedarsoluciónaunproblema.Laprimeraformaque
POLITÉCNICO GRANCOLOMBIANO EN ALIANZA CON WHITNEY INTERNATIONAL UNIVERSITY SYSTEM
AdrianNicolásMalaverBarrera 2
definiremosparaunainstruccióneslaasignación,quesebasaenasignar,comosunombrelodice,unvalorespecíficoaunavariable.Estevalorpuedeserunavariable,unaconstante,oengeneral,unaexpresión.Conlaasignaciónloquesepretendeesalmacenarunresultadoenunavariable.Cuandodefinamosasignaciones,loharemosdelasiguientemanera(Paraunadefiniciónmásformalconsultalalectura3deestasemana):<Variable>←<Expresión>
Veamosalgunosejemplosdeasignaciones:Tabla1.Ejemplosdeasignaciones
Asignación ¿Quépuederepresentar?V←15/2 Elcálculodeunavelocidad,basadaenvaloresdadosdedistanciaytiempo
A←π*R*R Eláreadeuncírculo
P←2*π*R Lalongituddeunacircunferencia
V←π*R*R*h Elvolumendeuncilindro
Alconstruirinstruccionesenformadeasignacionesdebemostenerencuentaquelasexpresionesinvolucradasesténestructuradascorrectamente.
Engeneral,unaexpresiónpuedeestarmalformadasi:
• Contieneerroresrelacionadosconlasintaxisoelordendelossímbolosusados.Porejemplo,laexpresión5+<4estámalformada,dadoquepararealizarcualquieradelasdosoperaciones,serequierendosoperandos.
• Contieneoperacionesquenotienensentidoonorespetanlasreglasmatemáticasimplicadas.Porejemplo5/(8–4*2)implicaquesehagaunadivisiónporcero,locualnotienevalidez.
• Contieneoperacionesquenosepuedenaplicaraltipodedatodelosoperandosimplicados.Porejemplo,noesposibleevaluar57Y85nilaexpresiónV+F*3.
Podemosentonces,definirlasinstruccionesdeunalgoritmoconbaseenunconjuntodeasignaciones.Veamosunejemplo:Sequierecalcularelvolumendeaguaquepuedeseralmacenadoen18vasoscilíndricos,dadoselradiodesubaseysualtura.
AdrianNicolásMalaverBarrera 3
Entonces,loprimeroquedebemoshacereselprocesodemodeladoquesebasaenlaidentificacióndeentradasysalidas.Podemosdecirquerequerimosdedosvariablesdeentrada,quesonlabaseylaalturadelvasoyobtendremosunasalidaqueeselvalordelvolumen.Luego,identificamoslaspreyposcondicionesquehablaríandelosvaloresconloscualestendríasentidosolucionarelproblema.Finalmente,pasamosadefinirelalgoritmoquenospermiteobtenerunasolución,quesefundamentaríaenelcálculodelvolumendeunodelosvasosysuposteriormultiplicaciónpor18.Unaveztengamosestainformaciónrequeridadebemosdocumentarlamejor.Entremásclaridadtengamosenladefinicióndelproblemaydelalgoritmo,mejoresymásprecisosseránlosresultadosobtenidos.
Unalgoritmobiendefinidopermiteque,dadounconjuntodedatosdeentradaquecumplelasprecondiciones,sesigueninstruccionesquepermitenhallarunconjuntodesalidasquedebencumplirlasposcondicionesdefinidas.
2.2 Estructuraformaldeunalgoritmo
Sijuntamoslosprocesosdemodelado,especificaciónyconstruccióndealgoritmos(conbaseenasignacionescomolohemosvisto)podemosdefinirunaformageneralparaescribirunalgoritmo.Veamos:
Tabla2.Estructuradeunalgoritmo
Algoritmo<Nombre del algoritmo> Unnombrequeindiqueloquepretendemoshacerconestealgoritmo
Entradas Variablesdeentrada
Pre:{…} Condicionesparalasvariablesdeentrada
Inicio Iniciodelalgoritmo Paso 1 Paso 2 . . . Paso n
Cadapasooinstruccióninvolucradaenlasolucióndelproblema
Fin Findelalgoritmo
Salidas Variablesdesalidas
Pos:{…} Condicionesquedeberáncumplirlassalida
AdrianNicolásMalaverBarrera 4
Yparaelejemplovistoantes,ladefiniciónpodríaserlasiguiente:
Tabla3.Ejemplosdealgoritmodeacuerdoconlaestructura
AlgoritmoVolumenDelCilindroEntradas radio, altura: RealPre:{radio>0 Y altura>0 }InicioVariables v: Real v ← π*radio*radio*altura volumen ← 18 * vFinSalidas volumen: RealPos:{volumen > 0}Cuando definimos algoritmos de esta forma, obtenemos lo que llamaremospseudocódigo, lenguaje que no es demasiado formal y está definido para describir deformasencilla,claraeindependientedeunlenguajedeprogramación,instruccionesquesedebenrealizarparaobtenerelresultadodeunproblema.Másadelanteveremosqueessencillopasardeestepseudocódigoallenguajedeprogramaciónenelquetrabajaremos.
2.2.1 Unejemplo
Muchasveceslosprocesosdemodeladoyespecificaciónrequierenuntrabajoadicionalparaidentificaryposteriormenteconstruirunalgoritmo.Veamosunejemploaúnmásinteresante:
Serequierecalculareláreadecadatriánguloconstruidoaltrazarlíneasdeunpuntodecoordenadas(x,y)alostresvértices{(0,0), (w,0) y (w,h)}deuntriánguloubicadoenelprimercuadrantedelplanocartesiano,comolomuestralagráfica.Elpunto(x,y)debeestardentrooenelbordedeltriángulo.
AdrianNicolásMalaverBarrera 5
Gráfica1.Informacióndelproblema
ModeladoEntradas:x, y, w, h: Real Dadoquerequerimoslainformacióndelascoordenadasdelpuntoydelosvaloresdewyhparaconocerlascoordenadasdelosvértices.
Salidas:a1,a2,a3: RealDadoqueelalgoritmodebecalculareláreadecadatriángulo.EspecificaciónPrecondiciones:
1. Queeltriánguloestéenelprimercuadrante
Paratalfin,debemosdefinirqueelpuntodecoordenadas(w,h)estéenelprimercuadrante;formalmente:{w>0 Y h>0}.Elpunto(0,0)sedescarta,dadoqueobtendríamosuntriángulodeáreacero.
2. Queelpuntodecoordenadas(x,y)estédentrodeltriángulo
Debemosdefinirprecondicionessimilaresalasdelpuntoanterior,peroesnecesariotenerencuentamásfactoresdadoquedebemoslimitarelpuntodentrodeunáreamáspequeña.Comencemosconx:{x >= 0 Y x <= w};paray,ademásdeverificarqueseencuentreenelintervalo[0,h]debemosverificarqueseencuentredebajoosobrelahipotenusadeltriángulo.Podemosdefinirestasprecondicioneshallandolaecuacióndelarectaquerepresentalahipotenusaparaconocerlaalturaquedeberíatenerlacoordenada,comolomuestralasiguientefigura:
AdrianNicolásMalaverBarrera 6
Gráfica2.Representacióndelacondiciónaverificar
Laecuacióngeneraldelarectaesy=mx+b,dondemeslapendientedelarectayequivaleah/w.Comob,elinterceptoconelejeverticalescero,podemosignorarla,ypodemosescribirloquenosinteresa:lacoordenadaydebesermayoroigualqueceroymenoroigualquelaalturadelarectaenelpuntox.Estoes:{y>=0 Y y<=(h/w)*x}.Simplementereescribimosmcomo(h/w).
Poscondiciones:
1. Elvalordecadaáreadebesermayorquecero,dadoquenotienesentidounáreanegativaycomowyhsonmayoresquecero,nodeberáserposibleobteneráreasnulas.Estoes:{a1>0 Y a2>0 Y a3>0}.
2. Lasumadelasáreasdebeserigualaláreatotaldeltriángulo.Estoes:{a1 + a2 + a3 = w*h/2},calculandoeláreadeltriángulocompletoconlafórmula.
Conlainformacióndefinida,podemosescribirelalgoritmodelasiguienteforma:
Tabla4.Algoritmodesolucióndelproblema
AlgoritmoÁreas
Entradas x,y,w,h: Real
Pre: {w>0 Y h>0 Y x>=0 Y x<=w Y y>=0 Y y<=(h/w)*x}Inicio a1←w*y/2 a2←h*(w-x)/2 a3←w*h/2-a1-a2
a1ya2secalculanconlafórmulageneral,a3secalculacomoladiferenciaentreeláreatotalyla
sumadelasáreaspreviamentecalculadas.
Fin
Salidas a1,a2,a3: Real
Pos:{a1>0 Y a2>0 Y a3>0 Y a1+a2+a3 = w*h/2}
Parafinalizar,verifiquemoselalgoritmoconalgunosvalores.
AdrianNicolásMalaverBarrera 7
Dadoslosvaloresdelasvariablesdeentradax=-15, y=18, w=30, h=24los
reemplazamosenlaexpresiónquedescribelasprecondicionesysilasentradassonválidas,laexpresióndebeserverdadera,enotrocaso,seráfalsa.Veamos:
Dado{w>0 Y h>0 Y x>=0 Y x<=w Y y>=0 Y y<=(h/w)*x},reemplazamos:30>0 Y 24>0 Y -15>0 Y -15<=30 Y 18>=0 Y 18<=(24/30)*-15 V Y V Y F Y V Y V Y 18<=-12 V Y V Y F Y V Y V Y V F Larespuestaesfalsadadoqueelvalordexesnegativo.Enestecasoesimportantenotarquelosvaloresdeentradadefinidos,correspondenaunproblemadistintoalquesepretendesolucionar,porlotantonotienesentidocalcularsusoluciónbajoelesquemadefinido.
Parax=10, y=5, w=-3, h=4Dado{w>0 Y h>0 Y x>=0 Y x<=w Y y>=0 Y y<=(h/w)*x},reemplazamos:-3>0 Y 4>0 Y 10>=0 Y 10<=-3 Y 5>=0 Y 5<=(4/-3)*10 F Y V Y V Y V Y V Y 5<=-13.3 F Y V Y V Y V Y V Y V F Larespuestaesfalsadadoqueelvalordewesnegativo.
Parax=1, y=4, w=8, h=5Dado{w>0 Y h>0 Y x>=0 Y x<=w Y y>=0 Y y<=(h/w)*x},reemplazamos:8>0 Y 5>0 Y 1>=0 Y 1<=8 Y 4>=0 Y 4<=(5/8)*1 V Y V Y V Y V Y V Y 4<=0.625 V Y V Y V Y V Y V Y F F Larespuestaesfalsadadoqueelvalordeelpunto(x,y),apesardecumplirlamayoríadelasprecondiciones,estáporencimadelahipotenusa.
Parax=5, y=3, w=10, h=8Dado{w>0 Y h>0 Y x>=0 Y x<=w Y y>=0 Y y<=(h/w)*x},reemplazamos:10>0 Y 8>0 Y 5>=0 Y 5<=10 Y 3>=0 Y 3<=(8/10)*5 V Y V Y V Y V Y V Y 3<=4 V Enestecasolarespuestaesverdaderaypodemosejecutarelalgoritmo.
AdrianNicolásMalaverBarrera 8
a1←w*y/2 a1←10*3/2
a1←15 a2←h*(w-x)/2
a2←8*(10-5)/2 a2←20
a3←w*h/2-a1-a2
a3←10*8/2–15-20 a3←5
Ahora,conestosvaloresseverificanlasposcondiciones:Dado{a1>0 Y a2>0 Y a3>0 Y a1+a2+a3 = w*h/2},reemplazamos: a1>0 Y a2>0 Y a3>0 Y a1+a2+a3 = w*h/2 15>0 Y 20>0 Y 5>0 Y 15+20+5 = 10*8/2 V Y V Y V Y 40 = 40 V Y V Y V Y V V Larespuestahalladaesválida.
EnresumenParalograrlaconstruccióndeunbuenalgoritmoesnecesariotenerencuentaladefinicióncorrectayclaradeentradasysalidas,ydelascondicionesquedefinenquedichosvaloressonválidos(precondicionesaplicadasalasentradasyposcondicionesaplicadasalassalidas).Dichascondicionesserepresentanmedianteexpresionesbooleanasquedeberánserverdaderasalreemplazarlosdatos.Elprimerelementoquenospermiteconstruiralgoritmoseslaasignación.Mediantesuusobuscamosasignarvalores(quepuedenserconstantes,variablesoengeneral,expresiones)avariablesespecíficas.
Paratenerencuenta:• Verificarenpapellasolucióndelalgoritmo“Áreas”paravariosconjuntosdevariables
deentrada.Verificargráficamentequelosvaloreshalladostengansentido.
• Verificarlaconstrucción,basándoseenlasgráficas,delasasignacionesquecalculaneláreadecadatriánguloindependiente.
• Sinnecesidaddetenerencuentalosvaloresdea1ya2,¿Cómopodríacalcularsea3?