324tp2015_1

324T.P.Lapso201511/11

UNIVERSIDADNACIONALABIERTAVICERRECTORADOACADMICOREAINGENIERA

TRABAJOPRCTICO:

ASIGNATURA:COMPUTACINII

CDIGO:324

FECHADEENTREGADELASESPECIFICACIONESALESTUDIANTE: Apartirdelaprimerasemanadeaplicacindepruebas,atravsdelasesordelaasignaturaensucentrolocal

FECHADEDEVOLUCINDELINFORMEPORELESTUDIANTE:AdjuntoalaPruebaIntegral25/07/2015

NOMBREDELESTUDIANTE:

CDULADEIDENTIDAD:

CORREOELECTRNICO:

TELEFONO:

CENTROLOCAL:

CARRERA:236

NMERODEORIGINALES:

FIRMADELESTUDIANTE:LAPSO:20151

UTILICEESTAMISMAPGINACOMOCARTULADESUTRABAJO

Especialista:NellyEscorchaIngenieradeSistemasEvaluador.SandraSnchez

324T.P.Lapso201512/11

RESULTADOSDECORRECCIN:OBJN 5 6 70:NL 1:L

ESPECIFICACIONESDELTRABAJOPRCTICO

Especificaciones:EstetrabajosebasarenelObjetivoNo.5delMduloIIylosobjetivos 6 y 7 correspondientes al Mdulo III. En l se evidenciar lashabilidades y destrezas adquiridas por el estudiante, al momento deimplementar algoritmos de ordenacin y bsqueda en Lenguajes deProgramacin, empleando la estructura de Grafos en la resolucin deproblemas.

MOD.II,UND.5,OBJ.5CRITERIODEDOMINIO1/1

1.LlamamoscaminoEuleriano,alcaminoquevisitatodaslasaristasslounavez.Sielcaminoformaunciclo,seledenominacicloEuleriano.SiunagrficatieneuncaminoEuleriano,sedicequelagrficaesEuleriana.SeconocenconestenombreenhonoraLeonhardEuler,quienfueelprimeroenestudiarlasaltratarderesolverelproblemadelossietepuentesdeKnigsberg.LaprimeracondicinnecesariaparaqueunagrficaseaEulerianaesqueseaconexa.El algoritmomsconocidoparaconstruir uncaminoocicloEulerianose leconocecomoalgoritmodeFleury.TeniendounagrficaEuleriana,tomamosunvrticecongradoimparparaempezarocualquierasinohayimpares.Paraescogerlaaristaatomar,seutilizacualquieraquenoseaunpuenteamenosquenosetengaotraopcin.Sepuederecordarqueunpuenteesunaaristaquealborrarlalagrficasevuelvenoconexa.Alaaristaquesetoma,seborra(osehacenoelegible). Serepiteesteprocedimientohastaquenoquedenaristas. A la grfica que se le quita las aristas se le conoce comogrficareducida.

Conestainformacin,sepuedeobservarelsiguientecaso:


324T.P.Lapso201513/11

Caso1:Dibujarungrafoqueindiquelascallesporlasquetienequepasaruncarteropararepartirelcorreoportodoslosedificiosdelascallesnumeradasdelmapa,verFig.1

Fig.N1CallesNumeradas


324T.P.Lapso201514/11

ConlosconceptosdadossobregrafosydatosdelCaso1,sepideunprogramaenlenguajedeprogramacinC++quepermita:

Transformar el recorrido en un grafo donde cada vrtice representa unrecorrido.

Queelcarterohagaelrecorridomseficiente,esdecir,nopasardosvecesporlamismaaristayregresaralpuntodecomienzo.

Imprimirlosgrficos.

CriteriodecorreccinSeconsideralogradoelobjetivosialmenossecumpleconlosiguiente: Entregadellistadodocumentadodelprograma,codificadoenC++,enforma

modularyestructurada.Enelencabezadodecadaprocedimiento,funcinoseccindeprogramaquelorequierayenladeclaracindelasestructurasdedatosse incluyeunbrevecomentarioacercadel proceso, mtodo odefinicindeestructura,segnseaelcaso.

El programa corre sin restricciones. En general cada programa incluyemdulos que realizan o contribuyen a alcanzar lo solicitado en lasespecificaciones.

Incluyelasrespuestasenlasseccionessolicitadas.

MOD.III,UND.6,OBJ.6CRITERIODEDOMINIO1/1

2. El algoritmo de ordenacin Shell fue creado por Donald Shell, y sedenominaShellenhonorasuinventor.Elalgoritmoseparecealalgoritmodeordenacinporinsercin.Enel algoritmode insercin, cadaelementosecomparacon loselementoscontiguosdesu izquierdadeunoenuno,peroconelalgoritmodeShell lacomparacinsehaceconintervalosmayoresauno,lograndoconelloquelaordenacinseamsrpida.Generalmentesetomacomointervaloinicialndiv2,siendonlacantidaddeelementosdelalistaaordenar,luegosereducelosintervalosalamitadhastaqueelintervalollegueaseruno.Cuandolaordenacindelalistasehaceconunintervalode1elalgoritmosecomportacomoelalgoritmodeinsercin,peroconlaventajadequealtener


324T.P.Lapso201515/11

unalistacasiordenada,debidoalosordenamientosporintervalosanteriores,elordenamientoseharmsrpido.

a) TomandoencuentaestainformacinylasiguientelistadenmerosquerepresentanlascallesquedanaledificiodelaFig.1:7,3,10,1,9,8,4realizarunprogramaenC++queordenelosnmerosdemenoramayor(ascendentemente).

b) ImprimaelprimerrecorridoyelsegundorecorridoaplicandoelalgoritmoShellSort.

Criteriodecorreccin

Seconsideralogradoelobjetivosialmenossecumpleconlosiguiente: Entrega del listado documentadodel programa, codificado en C++, en

formamodularyestructurada.Enelencabezadodecadaprocedimiento,funcinoseccindeprogramaquelorequierayenladeclaracindelasestructurasdedatosseincluyeunbrevecomentarioacercadelproceso,mtodoodefinicindeestructura,segnseaelcaso.

Elprogramacorresinrestricciones.Engeneralcadaprograma incluyemdulos que realizan o contribuyen a alcanzar lo solicitado en lasespecificaciones.


MOD.III,UND.7,OBJ.7CRITERIODEDOMINIO1/1

3.DadalatablaNo.1quecontienenombresdeedificiosqueseencuentranenunamanzana.

TablaNo.1NombresdeEdificios

No Edifico1 Gmez2 Cubilln


324T.P.Lapso201516/11

3 Samuel4 Caminito5 Carache6 Atlntida7 SanJos8 CampoElas9 LaCeiba11 Mirandina12 MonteSacro

DesarrolleunprogramaenC++,queconstruyaunaestructuratipohashingodispersin,paraalmacenarlosnombresdelosedificiosporsuposicindadaenla tabla, enunarchivo tipo texto. El programasehar bajo lassiguientesconsideraciones:

Atravsdelarchivodetexto,extraigacadanombredeunedificioyubqueloenlaestructuramencionada.

Imprimaelnombredeledificioamedidaqueloinsertaenlaestructurayelnmerodelaceldaparaelloutiliceunafuncindehashing,

Funcin hashing:consisteenlasumadelasposicionesenelalfabetodelasletras (codificacin ASCII) que conforman el nombre del edificio. Como seindicaacontinuacin:

endondelieselcdigoASCIIdecadaletraqueformaelnombredeledificio,reselnmerodeentradasdelatabladehashingonmerodebucketsoslots.Enestecasoescojaunvalorder,elmejorserelqueproducemenornmerodesinnimos.Las tablasdeCodificacinASCII (tambin llamada asqui), sepresentanenlatablaNo.2.

Ejemplo:sisevaaconstruirlallaveparaunatablade200slots(de0a199),ysedeseainsertarelnombreTexas,deacuerdoaloscdigosASCII(vertablaASCII),laconstruccindelallaveserlasiguiente:


324T.P.Lapso201517/11

Valor=Cod(T)+Cod(e)+Cod(x)+Cod(a)+Cod(s)=84+113+120++97+115=1012

Valormodr=529mod199=131(restodeladivisinentera)

Porlotanto,lapalabraTexasseinsertarenunalistaasociadaalacelda(oslot)131.AcontinuacinsepresentanlastablasdecaracteresASCII.

Smbolo ValorASCII Smbolo ValorASCIIA 65 N 78B 66 O 79C 67 P 80D 68 Q 81E 69 R 82F 70 S 83G 71 T 84H 72 U 85I 73 V 86J 74 W 87K 75 X 88L 76 Y 89M 77 Z 90


324T.P.Lapso201518/11

a 97 n 110b 98 241c 99 o 111d 100 p 112e 101 q 113f 102 r 114g 103 s 115h 104 t 116i 105 u 117j 106 v 118k 107 w 119l 108 x 120m 109 y 121

z 122


324T.P.Lapso201519/11

TablaNo.1y2ASCII

Nota:Paradeterminarelordinalasociadoacadaletra(cdigoASCII),sepuedeemplearlafuncinord,lacualpertenecealconjuntodefuncionesestndaresdePascal.

ElaboreunprocedimientoenC++debsqueda,talque,dadoslosnombresdelosedificios,estossebusquenenlatabladehashing eimprimalaceldaalacualestasignada.

Criteriodecorreccin

Seconsideralogradoelobjetivosialmenossecumpleconlosiguiente: Entregadellistadodocumentadodelprograma,codificadoenC++,enforma

modularyestructurada.Enelencabezadodecadaprocedimiento,funcinoseccindeprogramaquelorequierayenladeclaracindelasestructurasdedatosse incluyeunbrevecomentarioacercadel proceso, mtodo odefinicindeestructura,segnseaelcaso.

El programa corre sin restricciones. En general cada programa incluyemdulos que realizan o contribuyen a alcanzar lo solicitado en lasespecificaciones.


InstruccionesgeneralessobreelTrabajoPrctico

Elestudiantedebeentregarlosiguiente:

Listado documentado del programa fuente. En el encabezado de cadaprocedimiento,funcinoseccindeprogramaquelorequiera,debeincluirunbrevecomentariodelprocesoqueserealizao delmtodoqueaplica.


324T.P.Lapso2015110/11

Igualmente esconvenientehacerloen ladefinicindelasestructurasdedatosyvariablesutilizadas.

Listadodelosresultados.

CD(DiscoCompacto)quecontengaelprogramafuente(.CPP)yelprogramaejecutable(.EXE),debidamenteidentificado.

Recomendaciones

Emplee nombres de variables, constantes, funciones y procedimientosalusivosaloquerepresentan.

Utiliceundiseomodularparalaresolucindelproblema.Estaestructuraaportar legibilidad y facilidad de comprensin, adems evitarredundanciasenlosprocesos.Evitevariablesglobalesenlasfuncionesyprocedimientos. Empleeparmetrosenlosmismos,determineculessonparmetrosvaloryculesparmetrosvariables.

Desarrollealgoritmoseficientes.

Elaboreprocedimientosdevalidacindeladataydedeteccindeerroresparaevitarinterrupcionesinesperadasenlaejecucindeltrabajo.

ElCDdebeestarlibredevirusydebeentregarseenunsobreconjuntamenteconellistadodeprogramayresultados.NousecintaengomadaparaadherirelCDyaquepodradaarlalminaprotectoradelmismo.


324T.P.Lapso2015111/11

El trabajo se entregar completo, adjunto a la prueba integral, con unaportadasimilaralapresentadaenlasespecificacionesdeestetrabajo.

FINDELASESPECIFICACIONESDELTP


NOTA: Los Trabajos Prcticos son estrictamente individuales y unaproduccininditadelestudiante,cualquierindicioquepongaendudasuoriginalidad,sermotivoparasuanulacin.Quedaadiscrecindelasesoroprofesorcorrector,solicitarunaverificacindelosobjetivoscontempladosen el mismo, nicamente en aquellos casos en los que se veacomprometidalaoriginalidaddelaautoradelpresentetrabajoprctico.

ESPECIFICACIONES DEL TRABAJO PRCTICOInstrucciones generales sobre el Trabajo Prctico

324tp2015_1

Documents