TP matematica discreta granado peralta

  • Published on
    24-Dec-2015

  • View
    107

  • Download
    15

DESCRIPTION

Trabajos practicos . Materia matematicas discreta catedra susana granado peralta

Transcript

*ld(ofrNt0o,Fl , lU=(oltlIMATEMATICA DISCRETAATICA KlFP1CENTRO deESTUDIANTES deINGENIERIATECNOTOGICAUTN.BUNIVERSIDAD TECNOLOGICA NACIONALFACULTAD REGIONAL BUENOS AIRES?//?t2,rrtilagwrn@Jfz,-,%abrtz/gaau*z qgo,zal &tatn& -{i2,Ingeniela en Sistenws ile InfurmacinMATEUTTTCE DISCRETACTSDRA CRANADO PERAITAAO eorro1o5172l28J34251fIFFFiIJI,It -IttI'iIiIiIIiiIt!rrrri.INDICETpicoProgramaTrabajo Prctico no rTrabajo Frctieo no zTrabajo Prctico no 3Trabajo Prctieo no 4Trabajo Prctieo no 5Trabajo Prctico no 6Trabajo Prctico no 7Trabajo Prctico no 8Trabajo Prctico no 9i'Fk-1h,n"'rg12Teao@am'Jtrdona/%aru*n/fu uona/gKlra&-{i/er'Departamento Ingenieria en Sistemas de InformacinASil@TATURA:DEPAXTAMENTO ING EN SIST DEINFORMACiONARf,"TBr.oQtlEMODALIDAD:HOR-A,S SEM.: 6.horas'HOnAS/AO: qobrasHORASRELOJNTVEL: lao DEDICTADO:2011q* as"g+ UformtcrOndlfrrturo'Ingenieio,"' .,.;';' : "Et pido desarrollo ile las actuales computadoras, con su inmensa capacidad de clculo, con$ enorme rapidez, versatilidad, potencia de representacin grfica, posibidades para lamodelizacin sin pasar por la forrrulacin matemtica de corte clsico,... ha abierto multudde campos diversos, con origen no ya en ia fisica sino en ohas muchas ciencias tales como laeconoma, las ciencias de Ia organizacin, biologa,... cuyos problemas resultaban opacos' enparte por las enormes mrsas de informacin que haba que tratar hasta llegar a dar con lasintuiciones matemticas valiosas que pudieran conducir a procesos de resolucin de losdificiles problemas propuestos en estos campos.Por otra parte, el aceuto en los algoriros discretos, usados en las ciencias de la computacin,en la informtica, as como en la modelizacin de diversos fenmenos, ha dado lugar a u:rfaslado de nfasis eu la matemca actual hacia la matemtica discreta. Ciertas porciones deella son suficientemente elementales como para poder formar parte con xito de un progrrmainicial de matemtica.Para un profesional en sistemas de informacin, que precise una fomacin que le permitadesarrollar investigaciones en la Informtica aplicada le es muy impoftante domina lostemas bsicos y avanzados de la Matemtica Discreta Hay temas fundamentales parr uningeniero en sistemas tales como lgica, lgebra de Boole, mquinas de estados finitos ygrafos, mtodos de demostracin, sistemas de numeracin y relaciones de recurrencia (i.e.eqaciones en diferencias) que no pueden ignorar-Por todo lo orpuesto se hace imprescindible que los alumnos conozcan y manejencorrectamente los conceptos basicos de la Matemtica Discreta y que comprendan que sonnecesarios para conseguir soluciones rigurosas a problemas de muy diversas reas queencontrarn en asignaturas posteriores del plan de Estudios. De igual forma se pretende queD?//r/?rtdaTer:zofo r:n,Jfubngaal/fa@grbna/&rttpt'.{/?},Departamento Ingeniera en Sistemas de Informacindichos alumnos desarrollen una cepacidad de resolucin de problemas en la que tengaimportancia el anlisis previo a su propia resolucin.' t : r t lr dplicar mtodos inductivos, deductivos y recursivos en la resolucin de situacionesproblemticas y demostraciones matemticas.. Comprender los conceptos y procedimientos necesarios para resolver relaciones derecurreneia.. Aplicar propiedades y funciones definidas en los nmeros enteros y enteros nonegativos.o Caracterizar distintas estructuras algebraicas, enfatizando las que sean finitas y laslgebras de Boole.. Aplicar propiedades de grafos, grafos y rboles en la resolucin de situacionesproblemticas.,6 horas catedra de acuerdo a lo establecido en el plan de estudios.c-oi ryl$#{ffi.l!ryqq ii:,.',:i,,.,,;,,,,,,'t:. Igca proposicional Clasica y de predicados de Primer Orden.. Teoa de Nmeros.. Induecin Matemtica' Relacionesderecurrencia. EsfructurasAlgebraicas FinitasyAgebras de Boole.. Grafos dgrafosyrbolescot ,iit i!,,, ;,r,,': ,,t ,;. :.,i,. ;,,,,,,'.,,:,;i',Unidad l: CIcrrlo proposicional y crlculo de predicadosProposiciones. Conectivos. Equivalencias lgicas. Le,ves de la lgica. Tautologas yeon[adicciones. Cuanficadores. Implicaciones y derilaciones tgicas. Componentessintcticos del elculo de predicados. Variables libres y ligadas. Lgica de primer orden:sintaxis, semntica, reglas de inferencias, sistemas deductivos.Logros oedaggicos: Conocer la formalidad del lenguaje matemtico y laesfuctura de ios razonamientos bien formados%osrvidgrro&hz'JVArztzJgazl/tu qgfural gut ?n' tkt'Departamento Ingeniera en Sistemas de InformacinIffidtr: Teoa de ConfuntosOqtsmm y subconjuntos. Is operaciones y sus propiedades. Producto cartesiano yff-*. Relaciones, matrices y dgrafos. Propiedades de las relaciones. Relaciones detfeleneia y particiones. Relaciones de orden, elementos notables y diagrama de Hasse.Loeros pedagsicos: Manejarhenamientas importantes para resolvercuestionei afines a }a asignatura con la computadora y conocer lafundamentacin de las bases de datos relacionales'Eridad III: Teora de NmerosDivisbilidad. Algoritmo de ta visin. Mximo comn sor y mnimo comn multiplo-Torema fundamental de Ia aitrntica. Congruencias. Ecuacin lineal de congruencias.Tenrena cle Fermat.Logros oedaggicos: Conocer las bases matemticas de las herramientasutilizadas frecuentemente en teora de la informacinUridad fV: Induccin y RecursividadConjuntos inductivos y Principio de induccin matemca. Definiciones recursivas'F"elaciones de resurrencia lineales homogneas con coefieientes constantes con races simplesy reales, complejas y simples, reales mltiples. Relaciones de recurrencia lineales nobomogneasLog.oe pedaegicos: Reconocer y resolver ecuaciones recursivas aplicandometodologas especficas o un usando un proceso iterativo y que adems seacapaz de validar su resultado usando induecin matemca'Uniitad V: Eslructuras Algebraicas Finitasoperaciones ceradas. Propiedades. Definicin y ejemplos de grupos. subgrupos. Gruposcclicos. Isomorfismo de grupos. co-clases y subgrupo normal. Teorema de Lagrange' Grupocociente.Iogros pedaggicos: Couocer la estructura de grupo y aplicarla paradisear cdigos de deteccin de errores en cdigo en bloque (cgos degrupo)EidadVt i{Igebras de BooleRetcrlo: definicin y ejenplos. Principio de Dualidad. Isomorfismos. lgebras de Boolehebras de Boole finitas. Maxitrminos y mini$rminos' Formas cannicas' Redes dempuertas.lIt?lnaxnzg"zro@za'Jnatua/gazlh qglbra/ &E to& -{?8'Departamento Ingeniera en sistemas de InformacinLoo.os pedaggicos: Conocer la estructura matemtica del lgebra denoot. p pod* uplicarla a problemas concretos y diferenciarla del modelomatemitico de gruPo'Unidad VII: Grafos, Dgrafos y,{rbolesGrafo: definicin formal ! oociones elementales. Matrices de adlncencia y de incidencia'Subgrafos. Caminos y cicls de Euler. Caminos y ciclos de Hamilton. Isomorfismo de grafos'Gafos dirigidos: definicin formal y nocionei elementales. Matrices de adyacencia y deineidencia. caminos y ciclos de Euler. caminos y ciclos de Hamilton ' catactenTacin de losarboles. Arboles dirigidos y no dirigidos. boles con ra2. Recorrido ile rboles'I . .ogrospedaeqicos:Usargrafos,dgrafosyarbolesparamodelarProbiemas concretos'Unidad VIII: Lenguajes, Gramticas y AutmatasOperaciones con palabias. Operaciones con lenguajes. Clausuas de Kleene y Positiva de unlenguaje. Gramticas: definicin formal, obtencin de palabras y clasificacin' Lenguajesregulares y autmatas nitos-Lorros pedaegicos: se pretende dar una introduccin al tema Lenguajes,gr"-d"* y autmatas que pmfun?t* en la asignatura Sintaxis yemantica clel Lenguaje con el objeto de relaciona muchos de los temasdesarrollados durante el cuatrimesfe en un tema especfico de la carrera'EqiEMctAol-is-'":;.;,,:,'i:;:;,"|riiN considera el aprendizaje como eonstmccin no se puede aceptar una separacin arbitrariaentre teora y prctica: la propuesla es acercarse a los problemas integrando la teoa con laprctica como forma de gineracin de conocimientos y vinculanclo al alumno de una formams interesante y ugr"bi. con la disciplina, utilizando nuevas tecnologas y distintasestrategias didcticas segn la unidad'En las clases, que sernLrico- prcticas se inducir al alumno a participar activamente ; seponclra especial nfasis en formar al estudiante como ln investigador en el tratamiento decada uno de los temas abordados inducindolos a formular, probar y modelizar'Con eferencia a las demostraciones de propiedades slo se harn las que por su aporte a laformacin se consideren pertinentes, otras, "propiedades menores", que generalmentt"p"t."u" en la gua de Trabajos Prcticos, las harn los alumnos con Ia ayuda del doeente; eltodos los casos se priorizar el conocimiento y manejo de las hiptesis al hecho de poderdemostrar algo que tiene dos inconvenientes: por un lado est en todos los libros y por el otrtla estutlian de memoria.se Ie dar especial importancia al desarrollo de la capacidad crear'a' que a lo largo de Iicarrera y en su profesin le permir ser sensible a los cambios del contexto cuficonsecuencia es logfar soluciones especficas adaptadas a cada circunstancia'I Il ;It-!q--?//r(t?rdaTezzo@an,Jtrt'orrz/gaaaegkbn&rrlroe.{i/%'Departamento Ingeniera en Sistemas de Inforrnacinr{ertinte el anlisis de datos para el uso de propiedades se facilitar una actitud decryr'o;bacin sistemca de la validez de los supuestos sobre los cuales se basanafirmaciones.Se dacionarn cada una de las unidades temcas con otras asignaturas con el objetivo defmecer una actitud interdisciplinaria en el batamiento de los problemas.Ccncretando, esta propuesta apunta a la combinacin integrada de conocimientos,habiliclades y actitudes eonducentes a un desempeo adecuado y oporfuno en diversoscotrtextos.roiu:6, ,;::;ir,,;;::iiif,:;;iii.;,:.,::,,'.iii.,.;.1,;.'.,,',,,i,';;:,::;|.i-i!'la ecahcin de los Conocimientos adquiridos es contiua y se formaliza de la siguienteforma:a) Entrega y defensa de un Trabajo Prctico integrador con problemas (no ejercicios) aresolver en grupo y defensa individual que inciuye todos los temas del programa.b) Aprobacin del 75o de parciales correspondientes a cada una de las unidades adesrrrollar ( evaiuacin de proceso)c) La aprobacin de un Parcial integrador que abarca todos los temas de la materia, quesgunla normava puede ser recuperado dos vecesd) Si ha crrmplimentado las instancias anteriores est en condiciones de rendir el exmenfinal que est dirigido y prioriza (como durante toda la cursada)Ia formacin de un cuerpo deconocimientos)Algo para tener en cuenta es que todos los documentos escritos entregados por el alumno seles corrigen y entregan para que puedan eonsultar acerca de sus errores'rfii,, ii,:.,.,;i,,,r.;i-;-:,r:lrii,i';:.i',Se armar equipos integrados por un mnimo de cuatro alumnos y un mximo de seis losc$ales propondriin y evarn adelante una idea-proyecto de carcter tcnico-*minisativo relacionado con la carrera dento del rea de su inters. A partir de la idea,csostruirn en forma gradual cada pieza clave mediante la utilizacin de los procesosnecssgrios aprendidos en el transcurso de Ia asignatura-Sbograa obligatoriaL Dorronsoro, J. .,Hernandez,E. ; tgg6; Nmeros, grupos v anill6s,; Addison WesleySkaenalzd{ernnfotam'gaa/tuggrbna/&ftttut{i/?,Departamento Ingeniera en Sistemas de Informacin2. Granado Peralta, S.; zoog; Matemtica Discreta; Etorial CEIT3. Isasi; Martinez & Borrajo; 1997; Lengaajes, Gramticas y Autmatas :un enfoqueprctico ;Addison Wesley4. Johnsonbaugb, R; 2oo5; Matemtias Discretas; Prentice Hall.S. Ross, IC,Wright,R; r99o; Matemticas Discretas ; Prentice HaIlBibliografr a eomplementariaGrassmann,W. ; Tremblal', J ; tggS ; Matemtica Discreta y lgica, Prence HallKolnan Busbl', Ross; rg96;Discrete Mathematical Structures ; Prentice HallLiu, C. L; tggS Elementos de Matemticas Discretas;. Mc.Graw HillScheinerman, E. ; zool; Matemticas Discretas, Math;Trembla J.Manohar, R; 1996; Matemticas discretas con apiicaciones a lasciencias de la computacin; CECSA1.2.3.4.5.iTU.T.N.F.R.B--DNPENTTTTNNTO DE INGENIERA EN SISTEMAS DE INFORMACINMArEMTrcA DrscRgrA - crgune cnNoo pERAlrAAozouTRABAJO PRAC'TI@N" TCalculo proposicional y crilculo de predicadosr.r Sabiendo que p = "Marcos es un beb", g= "Marcos es feliz' escribir las siguientesafirmaciones en forma simblicaa) Marcos no es un beb o es felizb) Marcos es un beb y es felizc) Marcos es beb o es felizd) Si Marcos es beb entonces es feiize) Marcos es feliz si y slo es beb.r.z Idencar las proposiciones simples y expresar simblicamentea) Mateo es alto y Marcos es pequeo y gil.b) Six es un nmero menor que g y y es menor que z entonces x es menor que z.c) Si no mal, Carlos conduca un auto colorado y deportivo y estabaacompaado por una mujer rubia.d) La inflacin ceder si y slo si se reduce el gasto pblico.e) Habr un brindis slo si no llueve.r.3 Construir en cada caso la tabla de verdad, -indica si se trat de u tautologa,eonngencia o contradiccin e identificar loy'enunc,radqslquiyalentg )a) (p^(p=+q))=+qb) (p=+q)U.T.N.F.R.B.A,-DEPARTAIVIENTo DE INGEIERA EN SISTEMAS DE INFORMACINMATEMT4JTICA DISCRETA - CATEDRA GRANADO PERALTAAOzouTRABAJOPRflICIONO TClculo proposicional y clculo de predicadosLS Para cada una de las siguientes proposiciones se pide negarlas y simplificarlas(p.rq)=+q(pv- g) ^ l(- p v q) v ( - (- p v - r)) n ql[ - (prq)nr]v -qp v- e, , [ (p ^ q) " (p v- g) n (-P n q)](p.r(s^ e))v(-qns)[ [ [ (p " q) n r ] v [(p ^r ) n- r ] l v- ql=sConsiderar el siguiente enunciado: "Si estudio Matemtica Discreta, entoncesaprobar el finaf. Se pide escribirla en lenguaje simbco y dar los enunciadosrcproco, inverso (contrario) y contrarreeproco en forma coloquial ]'simblicamente.Para la proposicin' si un polgono es un tiingulo entonces la suma de sus ngulosinteriores es 18o", se pide:Escbirla simblicamenteDar su valor de verdadEscribir la reeproca, la contrarrecproca y la contrariaDar el valor de verdad en cada casor.8 Probar que las siguientes proposiciones son tautologasa) ((p r q) ,. - p) =q (silogismo disyuntivo)b) (p"(p=+q))=q (modusponens)c) p= (pv q) ( leyde acin)d) ( p " q) =p ( ley de simplificacin)e) ((p ?e) n (q+r)) = (p=rr) (silogismo hipottico o implicacin lgica)f) ((p ==rq) ^- q) 3 -p ( modustollens)r.9 Para cada uno de Ios siguientes casos indicar las reglas de inferencia que se usron:a) Si Pedro descubre que el auto est chocado, se pondr fuioso. Se que Pedro estal tanto de que el auto est chocado. Por lo tanto Pedro se pondr furioso.b) Sabemos que Mario comprara un Ford o un Corsa. Mario no compr el Corsa. PorIo tanto Maio comPr el Fordc) Si yo Io hice, estoy arrepentida, si no lo hice tambin estoy arrepentida. Por lotanto estoy arrePentida1.1o Dar la validez de los siguientes razonamientosa) t$ =r) n (- p+9) z' (q >s)l = (-r =s)b) [[(- pv - e) = (r >s)] . (r:+t) r. -tl +pa)b)c)d)e)f)t.6L.7a)b)c)d)U.T.N.F.R.B.A.-DEPARTAMENTO DE INGENIERA EN SISTEMAS DE INFORMACINMAIEMATTCA DISCREIA - CAIEDRA GRANADO PENALTA. AozouTRABAJO PRAC,IICONO 1Calculo proposicionaly calculo de predicadosc) [p ^ (p " q) n[q+ (r +s)] n (t +r)l = (- sv - t)r.uConsiderar las siguientes proposiciones abierlas:l (x):xS+;U(x):x+2esimpar;r(x):x)o, def inidas sobre el eonjunto Z, de losnmeros enteros. Se pide dar, justificando, su valor de verdad:. / \ . - f / \ \ ' l / \ [ / \ . | '1 r / \ / \ ]alp(o);b)o(-+);c)-r(z) ;d) [n(z)^q(-3) l=+ r(z)p)=x: [n(x)n-q(x)] ; f )vx: l r (xJ^ q(xJlr.:.2 Considerar, sobre el conjunto de ios nmeros enteros, las siguientes proposicionesabiertas:P(x): x" -V+ 1o = oq(x):x2-2x-3=6r (x): xU.T.N.F.R.B.A--DEPARTAMENTIO DE INGENETA EN SSTEIS T IXF(IIITCTIMATEIIATICA DISCREIA - CATEIITA G3AXlrU) IEIETAoeorrTRABAJO PRCTIOO 'O TCIculo proposicional y clcrlo de predicadcs(x): x es un cuadadot(x): x es un ringuloDar el valo de verdad de las siguientes proposiciones:v x[a(x)v t (x) ]v x[ i (x)=e(x)] t x[ t (x)n p(") ]v x[a(x)=+"(x)] ;v x[(a(x)n t (x))U.T.N.F.R.B.A..DEPARTAMENTO DE INGENTERA EN SISTEMAS DE INFORMACINMATETUATICA DISCNETA - CATEOT,E CNANADO PENALTAAo orTRABA'O PRACTICCI NO ZTeora de Conjuutos1. ls conjuntos ] sus operacionesr.r Considerar los conjuntos A = {a,ia},b}vn = {a,{l},U}e indicar, justificando, elvalor de verdad de los siguientes enunciados:a)a e A,b)a e B,c){a}e dd){a} e B,e)a g A"f)a c B,g){a}: A"h){a} s B,i){b}e A, j)tb} e n,k){{b}} a,t ' t1{{b}} = e,m){{a}} c e,n) {{a}} e B,o){a, {a}} s A,n){a, {a}} e nr.z iCules de las siguientes proposiciones son verdaderas?a)aea;b)slz;c)ag{s};a e{a,a};db e{o,a};03A /b c Ar.3 Para cada uno de los siguientes enunciados determinar si son verdaderos o falsos;demuestre si es verdadera y presente un contraejemplo si es falso.a) AnB gAcAuBb) B gAU.T.N.F.R.B.A..I}EPARTAMENTO DE INGENIBfA Et STTI/TA E T'IMATEIII.JIICA DISICRETA - CXE)IA GI.|XTN' E]Tf,EororrTm"m'd) A: (-o;6),8=(9; +a:,)e) A: (-o;6),8=[6; +e)0 A: {-*;6),8=[-6; +ca)r.6 Sea A un conjunto, llamamos conjunto potencia o conjuuto de parbs de A y loindicamos P(A) al siguiente conjunto:r(a){xx s e}a)calcular y / o enpresar el conjunto de Partes para cada uno de los siguientes czrs(E:A= {-L 2, 3}, A = {(a; b), (c; d)}, A= A,A = (-3; zf, A= {r, {r, z}}b) Probar que para dos conjuntos Ay B se verifica que:1.P(A)nP(B)=r(enn);z.r(.r ,)uP(B)g n(a u n)r.7 Sea U un conjunto universal y sea I un conjunto de ndices, paracadai . I , seaB, g!Demostrarquesi Ag U sever i f ica,on[-" , ' |= U(^nBi) .l ie l I ie l 'Enunciar y demostrar la expresin dual.z. Pro.ducto Cartesianoz.t Probar o refutar el valor de verdad de cada una de las siguientes proposicionessabiendo que A, B, C g Ua) e*(Buc) = ( , t , .s)u(e"c)b) (ene).c : (A"c)n(e"c)c) (n"n)-(e, .e) : (e-n).(n-n)d) (eue).(eun) e (e 'n)u(n'a)e) A"(B-c):(e, .n)-(e"c)z.z Mostra que, para cualquier conjunto A, in u) ' A : ({r} , ,rr) u {{t} . n)2.3 Para un conjunto finito A de cardinal z, se pide:a) Expticitan la'l,lr1e)lvl* (o')lb) Contestar las mismas cuestiones para el conjunto vacoc) Contestar las misms cuestiones para un conjunto finito A de cadinal n-2.4 SeandB dos conjuntos , probar o refutar cada una de las siguientes afirmaciones:u'T'N.F.n-B--DEP4FTAlfENro DE TNGENTERfa EN srsrEMAs DE INFoRMAcTNMATEMATICA DISCRETA -- cATEDn, cneNo_p}nrreANO orrTRABA.'OPRCTIOONO ZTeora de Coniuntosa)AxB =eA=QvB=Ab)AxB=BxArB}, Ro ={ {x;y) lx2 + y2 , = segn correspondaa) | Ax B 1. . . . . . . . . . . . . i BxAlb) Si R=AxBentonceslRl . . . . . lRr ia)b)c)d)U.T.N.F.N.B.A.-DEPARTAMENTO DE INGENIERIA EN SISTEMAS DE INFORMACINMAtrMAficA DIscREra - crr,pn cnNoo pERALTAAozouW""mffffil"'c) Si"RgAxBentonces I R1.... . . .1 O Id) Si RgAx B entonces lAx B | .......1R Ie) Si& ScAxBentonces I Rn S 1. . .1 Rlf) siR-cAxBentonces lnl . . lfe"B)-Rl4. Manejo Maqlia] de Retaoo4.r Considerar los conjuntos,A={*e N/xf e}VU={xZ/- tIU.T.N.F.R-B-A--DEPARTAMENT0 DE INGENIEnA EN sIsTEMAs DE INFoRMAcTNMArEMArrca Drscnsre _- cArBDn c*Nenri-RALTAANOzoilTRABA'O PR..CTTCO NO 2Teora de ConiuntosSe pide:a) I relacin S por enumeracinb) fs matrices de la relaciones recproca y complementaria5 Relacionesl'Dgrafos5.1 En el conjunto A : {ab,c"d}se definen las relacionesn : {(a; a), (a; b), (a; a), (b; u), (u; a), (u; c), (c; u), (a; c)}s = {(e a ) , (u; b), (c; c), (c: a ) , (c; o), (u; a), (u ' ")}Se pide:a) El dgrafo para cada relacinb) Los dgrafospara las relaciones R nS,R USc) Los dgrafos paralas relaciones n -S.3- n-l5-z Dado el conjunto A = {r, b, e, 4 e} y la relacin R: A -+ A cuyo dgrafo es:Se pide:a) R por extensin y su matriz Mnb) R.ysu dgrafoc) [ ysu matizd) (F)', M,:-, IeldgrafoiRi-i , s.g Para los conjuutos A = {r,2,3,4},8 = {t,4,g,7,n},C = {r,5,ro,rz.15} yhs relaeionesR g A xB,S ! B xC definidaspor:aRb U.T.N.F.N.B.A..DEPARTAMENTO DE INCq\IERA EN SISTEMAS DE INFORMACINMATEMAIIcA DISCRETA _. CATEDn,A c.t*"-S?iH"o*,Teora deC,onjuntos[orolt l5.4sea M* =f r r rJ hmatrizdelarelacinRdefinidaen A:{au.c}.Describir laslolojmatrices de Rn, R* y de R* Prooiedades de las Relacionesu't *Sjtfl las propiedades de la relacin R, dada por su matriz Ma denida en el conjuntornorcado en cacla casoa)A = {r ,2,3,4,S},M* =Sobre el conjunto A : {a, b, c, d} dar un ejemplo de:Una relacin reflexiva y simtrica pero no transivaUna relacin reflexiva y transitiva pero no simtricaUna relacin simtrica y transitiva pero no reflexivaUna relacin simtrica y antisimtricaDa condiciones para las qu una reracin no es reflexiva, no es simtrica, no estransiva, no es ansimtrica.Eshldiar las-propiedades de cada una de las siguientes relaciones definidas en elconjunto indicado en cada caso:R _ Nz,aRb U.T.N.F.R.B.A.-DEPARTAMENTO DE INGENIAA EN SISTEMAS DE INFORMACINMATEMTrcA DTScRETA - crnne cnroo pERAr.'TA,"""-S?i&coNozTeora de Conjuntosd) R -c p (e)' P (A),x,Y, z E IeZ esfijo, XRY U'T'N'F R-B'A'-DEPARTAMENTO DE rNGErrERlA EN srsTEltlAs DE rNFoRMAcrNMarEMLrrca rscnsrA _ cArDRA-ci psRALTAITABA'O PNACTICONO 2Teora de Coniuntos7.2 Sea f : A --r g rn firncin,la relacin aRb ++ f(a) = f(b) se llama relacin asociada a f.Sepide:a)probar que es unarelacin de equivalenciab)da las clases de equivalencia para la siguiente funcin real F : R - R[x-r ,s iU.T.N.F.R.B.A.DEPARTAMENTO DE INGENIERA EN SISTEMAS DE INFORMACINMATEMATTcA DrscREfa - crgox,e cnxeo PERALTAAoaorrH"?"'mff.I"'c){{n : n2 > 11 }, {n : nz < rr }}d){{n:n>o},{n:nU.T.N.F.R.B.I-DEPARTAMENTo DE INGENTER,fA EN SISTEI}IAS DE INFONMACINMATI :&{.TICADISCRETA-CAIEDRAGRANADOPI'IGA-. TAAozouTRABAIO PRACTI@NO T. TeoradeConjuntosDe los siguientes subconjuntos {1, 2, 4},{3,4},{t,2,3},{5,2,3},{5, +}.de A, indicarcuales son cadenasy cuales no.B.3Sea el conjunto A={a, b, c, d, e, f, g}eon el orden dado por el diagrama de Hasse, dartodas las cadenas que contengil , d menos, tes elementos.8.4Sobre N2 se define la reiacin (x;y)S(z;t)U.T.N.F.R-B-&-DEPARTAMENTO DE INGENTER.A EN SISTEMAS DE INFORMACINMATEIVIATICA DISCRETA _ CATEDRA GRANADO PERALTAAo zorrTY"?:Js"Tff,T""c) Si R es un orden en A entonces R' es un orden en Ad) Si un conjunto A est parcialmente ordenado por R entonees ningn subconjunto novaco de A esta totalmente ordenado por Re) Si R es una relacin de orden y S una relacin de equivalencia definida en el mismoconjunto A entonces R nS es una relacin de orden8.9 Para el conjunto ordenado del ejercicio 8.3, se pidea) Hallar maximalesy minimalesb) paraB= {c,d,f}, g = {a,b}, = {lu} y g= {c,d}darcotassuperiores einferioresc) Repetir las cuestiones anteriores pero con el orden recprocod) Indicar en cada uno de los casos anteriores si ha,v mximoy / o mnimoB.roPara={(o;o),(r :o)(z;o)(3;o),(o;r) , ( r ; r ) , (z;r) , fs;r) , (o;z) , (s;z) , (uz),(z;z)}ordenado por (x;y)S(z;t) + v 1 z Ay < t. Se pide:a) El diagrama de Hasseb) Las cotas superiores, inferiores' supremo, mximo, nfimo y mnimo paraB = {(r; r), (r; z), (e; r) }S.rrConsiderar el conjunto A C (n;S),e = {x e lR / x2 > +e}e incar si est acotado, sicorresponde dar mximo y / mnimo'8.rz Hallar, si es posible, el eonjunto de maximales, minimales' mximo y mnimo paracada una de los siguientes casos. Justificara) (r(e):e)b) (,1 )c) (N-{r} ' l )8.rg Hatla el conjunto de maximales, minimales, cotas superiores, cotas inferiores,indicar si hay m.ximoy I o mnimo para B en cada uno de los siguientes casos:a) En el conjunto N, de los nmeros naturales, ordenado por la relacin "divide a",considerar B =Dn = {x e N, xln}b) En el conjunto N, de los nmeros naturales, ordenado por la relacin "divide ao,considerar B ={2, 3,4,5,.....,198, r99, zoo}c) En el conjunto A={t2,g,g,4,8,16,25,g2,64,27,8t} ordenado por: a Rb U.T.N.F.R.B.&.DEFARTAMENTIo DE INGENIERfA EN SISTEMAS DE INFORMACINM TEMATICA DISCRETA - CTEDRA GRANADO PERALTAAozorrT"#"ff*ffi,#=a) Si existen, las cotas superiores e inferiores,b) Elementos maximales y minimales,c) Mximo, mnimo, supremo e nfimo de S.S.r5Probar o refutar con un contraejemploa) Todo conjunto ordenado tiene al menos un elemento minimal.b) Si A es un conjunto ordenado y a +B gA , entonces ninguna cota( superior y / o inferior) pertenecen a Bc) SiAes un conjuntoordenado y o +B qA yc es cota superiorde B en (A;R) entonces c escota inferior de B en (A; R -')d) Si A est totalmente ordenado y M es el conjunto de maximaies (minimales)entonceslMl=r.8.16 Sea Aunconjunto,sealAl=oyt*M*la matriz de la relacin & de orden,ilefinida sobre d se pide:a) Indicar la forma de reconocer un elemento maximal(minimal) usando la matrb) Indicar la forma de reconocer el elemento mximo o mnimo usando la matrizt6a)b)e)d)e)D: "U.T.N.F.R-B-A-.DEPARTAMENTO DE INGENIERfA EN SISTEMAS DE TNFonMAcINM.{TEMATICA DTSCRETA - CATEDRA GR.ANADO PERAI'TAAO rorrTRABA.TO PRACTICONO 3Teora de Nmerosr'r Indicar cuales de las siguientes proposiciones son verdaderas, justificar.Todo nmero enteo que es divisible por 4lo es porr6Todo nmero entero que es divisible por 9 lo es por gTodo nmero entero que es divisible por 6lo es por 2 o por 3Si un nmero entero no es divisible por 6 no es divisible por 3 ni por zTodo nmero entero que no es divisible por 6 no lo es pox 2 o por gHa-v nmeros naturales menores que too que son r'isibles por S J por gr.z Considerar el clnjunto Z, de los nmeros enteros y para las proposiciones que se dan acontinuacin, se pide demostra las verdaderas y dar uniontrae;ernplo si son faisas.a) Sia+o=a lab) Sia;o,^.neN=a lanc) Sia+o-a I l " l " l " l I ad) Siao^a lb+c+a lbrra lce) Sia;o,c+o, a lb+a.c I b.c0 Sia+o,alb.u.T.N.F.R-B--DEIaRTAMENIo DE qycENrERfA rl bibrnrvrs DE rNFoRMAcrNa . . r urmarrcADrscR-Era-ffamnne cneteoo PERAL,TA ;*"t-ffi|+co*s '.Teoa de Nmerosr.8 Demostrar las siguientes propiedades:a) a ez,b ez+(a,b)= ( l" l , l D = (b,a)b) a eZ,b eZ,c ez + (a,(b,c)) = (1a,U, . )c) a = o,(a,b)= lal - : q:U.T.N.F.R*B*L-DEPARTAMENTO DE INGEMERfA EN SISTEMAS DE INFORMACINMATEMATICA DISCRETA - CATEDRA GRANADO PERAI'TAAoorrTRABAJO PRaCarCON"STeora deNmerosL13 Dar los valores de n que hacen verdadera cada una de las proposiciones que se dan aconnuacina) S=+(n)b) S=-+ (n)c) r=o(n)d) 9=-9(n)e) lzz49Q)r.r4 Probar las siguientes propiedadesa) a=a(n)b) a: b (n) +b = a(n)c) a=b (n) nb =c(n)=a= c(n)d) a=o(n)U.T.N.F.R-B-A--DEPARIIMENTO DE INCENIERfA EN STSTEMAS DE INFORMACINMATEMATTCA.DTSSRETA - crn cnNmo PERATTAAogouTRABAJO PRAC'IICOi}{" 3 -' .Teora de NmerosSe pide calcular:a) q(r)=rb) e(z) = 1c) q(g)={ xeN / xU.T.N.F.R.B.A-DTPERTMTWTO DE INGEI{TEN,A EN SISIEMAS DE INFORMACINMATErATrcA DTSCRETA - crson cnNno PERALTAAozou'ffi:;t#tr'S,L1. InduccinIt Indicar, justificando, cules de los siguientes conjuntos son inductivosa) A=[-z; +oo)b) {-r, o} u(r, +oo)c) {x eZ / - 6 =x< r}u {xeZ / x>t}d) { r , 2,3, 5,6,7} w(7; +a)e)Qr.z Para cada uno de los siguientes casos indicar si harv alguna hiptesis del principiode induccin matemca que no se verifica.")p(") :n < z;b)p(n) ' " r 'e N;c)p(n) =zn+ 1< n2;d)p(") :3n' > ro;f lp(n):znln+tr.g Probar, usando induccin matemtica, si los siguientes enunciados son r'Iidos:n z r i" l i f 5 l =o-5"- '- f , \6/ " 6nu) f i tz i ' )=r-(n-r)zni= l t / r2c) r+23 +33 +43 +. . .+n3 = o- (o*rJ4, ,9. 3n(n+l)o) )_r = ---;-i=r zn^tre) t3 i - '= -^- tn- st / . ,2 I a \I ) L3. \2r-7) = n.(4n- - 1)i=r. . - -1-* 1 - =3- 1o'2 ' -1 92-1 (n+r)2-r 4 z(n+r) z(n+z)2nhlf x =2n(2n+r)r - li )VneN,ncn2j)Sike R,k ) o,n N,entonces(r+k)o > I + n.k, i# i.it$n e N,[r,n] = {xeN / *s"}v(e),.*1. sin= ev ln,l : tqlerl : rprobaque l,,t,'A"l = le'l'l"1z. Demostrar gue: lA, * A" x A, x.".""' x e"[ = le,l'le"l'letl""""'le"|U.T.N.F.R-B.A-DrpnruNtoDEINGENIERIAENsIsIEMsDEtr.[FoRMActNarE,rrcA orscnsre - caTEDRA GnANADo PERALTAAozournno PncrrooNo4: Ioduccin Y Recursividadk)Si o > l,n N,n ) 2 entoncesq" - r>n'(o - r)l) sea n un nmero natural o cero, probar que si A es un conjunto con n elementosentonces P(A) tiene cardinal znn) Sea una familia de conjuntos, se Pide:m) siA*,A2,..................,An, B son conjuntos' Entonces mt n: rlr(4u e)r.4 usando induccin matemtica probar la validez de las siguientes proposroonesVneN,6.7n-2.3na) VneN, n3- n es divisible Por 3b) Vn N,nz + 3n + r es imParc) VneN, zn + (-r) s+l es divisible por 3d) Vn e N u {o!,3o -7o - z es divisible por 8e) Vn e N,6.7n - z-3n es divisible por 40 Vn N,ton + 3.4o*t + 5 es divisible por 9g) Yn N,x2n - yto "s divisible por x*.yz. Sucesionesz.r Hallar una expresin general para cada uno de los siguientes casos:a) 1r-1, 1,-1, 1,-1, ...b) r, g, 6, 10, 15,...c) L, 4, t6,64,256,.--d) S,8, rL,14,L7,..,e) S, 15, 45, 135, ..-..z.z Hallar paa cada caso la o'presin general en forma no restrrsivaa) a1 = 1i n = n-r * 2, Sin >1b)a1 = 2iAn=On-r*2n-1, s in>1c) a1 = O; an = an-t * (n -f), Si n > Zd) ao - o;at= V2;dn = r l ? n -2: s in> ee) a1 = 3i rn = n-r * 3n, si n >fU.T.N.F.R.B.A.-DEPARTAMENTIO DE INGENERfA EN SISTEMAS DE INFORMACINMATEMATICA DISCRSTA - CATEDRA GRANAD.O PERAIJTAAoouTRABA.O PATCTIOON" Indu cci y Recrusivi dad2.3 Para cada uua de las siguientes relaciones de recurrencia dar el orden, indicar si es,homognea, si sus coeficientes son constantes, si es lineal.a)ao = -2an-rrb)an = 2fr?-.tc)o = 2nan-3 * an-r, d)ao = 8n-" - 6an-, + ot * s,e)flo = (nlogz)aro - 6(""-r)", f)ao = -2&n-r+ n, g) aR +n(n - 1) =n!z. Definir las siguientes sucesiones mediante una relacin de recurencia y clasicarlaa) S,= o; U 3; 6; ro; 15;-...........b) S,= r ;g;4;7; r r ; rB;c) Su= 1;3;7; i5;3r;d)54=1;-g;9; -27;8r;e) Su= 2;3;5; B; ' " ; . . . . . . . . . . . . . .0 So= 2; 4;8; t6; . . . . . . . . .2.5 Dar la solucin general y Ia solucin particular para las conciones iniciales dadasen da uno de los siguientes casos&)an =.an-, +8an-.rao = 1ral = ob)ao=6ao-r ,ao=2c)ao = 7an_r -1oa_2,2o = $,fl, = 2d)a, = -8do-, - 16an-2,ao = 2rat = -:roe)ao - 48o-r- 4a-2,ao = z,at = of)ar, = 3ao-, - 2an-z,ao = L,r, = 2g)ao = 8n- - ?n-e +ao_" -?n_rrao = 1 = agrar = 2 = ?42.6 Probar, usando induccin los resultados del ejercicio 2.52.7 Resolver cada una de las siguientes cuesonesa) Encontrar una relacin de recunencia lineal, homognea con coeficientes constantes, conuna condicin inieial, que determine la siguiente sucesin y verifica usando induccin.'S"=3;6; tz;24;b) Encontrar la solucin general de la recureneia : t n+z - 3 an+r = o. Probar lo obtenidousando induecin.c) Paa la siguienterelacin de recurrencia:2 r = 12 r n-r - 22r n-z + 12 r n-3 se pide:la solucin general y una solucin particular para las condiciones iniciales:r=Oia2=-1ya3=L23U.T.N.F.R.B.A.DEPARTAMENTO DE INGENIERIA EN SISTEMAS DE INFORMACINMATEMJ,TICA I}ISCRSTA - CA]IEDN/i GNANADO PERALTA*4""r#iffi"oNo+,, Induccin y Recrrsividadd) Sabiendo e 11 = -1 y r, = 2, son los ceros de la ecuacin caracterstica de una relacin derecunencia lineal y homognea eon coeficientes constarxtes, se pide denir la relacin ydar Ia solucin particular si ao = 1! 8r = -2 son las mndiciones iniciales.e) Silasolucindeunarelacinderecurreneiaes ar, =i(r)' -r(-r)",tr )o,sepide4reconstruirla indicando las condiciones iniciales y clasificarla.Relaciones recurrencia con races complejasObservacin: cuando los ceros de la ecuacin caracterstica son nmeros complejos, parahallar la solucin general debemos usar la frmula que nos brinda el Teorema de MoilretIa expresin polar de un nmero complejo es z= x + y i= r (cosg + i seng)El teorema de Moirre se usa para calcular la potencia ensima de un nmero complejo ytiene la siguiente o'.presin:z= rn (cos ng + i sen ng) ( que puede probarse usando induccin ).En el caso qlre tengamos que resolver una ecuacin de reeurrenbia donde las races de laecuacin caracterstica sean complejas, slo hallaremos, en este curso, la solucin generalya que para calcular las soluciones particulares es necesario poner enjuego saberes previosque Dotenemos.Ejemplo para a = 2 an-r - 2a-2El polinomio caracterstico es p(x)= x2 -27(. + 2Is ceros de la ecuacin caracterstica sorl 11 = 1 * i, rz= 1 -iI solucin general s : A(r + i)n + B( r -i)".2.8 Dala solucin general de las siguientes relaciones de recurrencia?) a = -o-,b) a= -4an-zC) an = n-r* n-z' Se uliza para calcular las races de un nmero complejo24U.T.N.F.R.B.A--DEPARTAMENTO DE INGEIERfA EN SISTEMAS DE INFORMACINMATEMATICA DISCRETA - CIEDRA GRANADO PERALTAAOzouTRABA'O PRCTTCO NO Induccin v RecursividadRelaciones recurrencia lineal no homogneaLlamamos relacin de recurrencia lineal no homogneas de orden k, con coeficientesconstante, a una eriipresin de la forma siguiente:a= k1a-1 + kern-z +...+ kr n-r CoIl n > r (I)donde Vi=o,k, los ki son nmeros realesn>k,neNan=f(n)Si f(n)= o eshomogneaAlgunos ejemplos:a) an = 2an-r + 3( 2n)b) an+2an-r=n2-n-1c) in-2.n- l*n-z=3iCmo se resuelven?r) Dada (I) ( que es la ecuacin de recurrencia que se quiere resolver), llamamosrelacin de recurrencia homoenea asociada a (I) a la Siguiente:O= kr?n-r + kzfln-z +...+ kr n-r CoIl Ir ) r (II)z) Aceptamos, sin demostrar,la siguiente propiedad:Cualquier solucin (an) de (I), para determinadas cond.iciones iniciales puede escribirseoomo:=p*hnhn es la solucin de homognea asociadaIln es nna solucin particular de (t)3) Para hallar ia solucin parlicular de (I) , no hay una regla general, sino unconjunto de pautas4) Algunos ejemplos:a) an-3on-r=2en este caso f(n) es nna constante, no depende de n, se puede probar con = d25U.T.N.F of rcngmnfeEN sIsrEMAs or nvronrvrcrNrcr, - o(TEDRA GRANADo PERALTArxer.a.ro rnerrco r" 4Induccin y Recursividadse sustituye en la ecuacin y se obtiene:A - e A =2, de donde A= -1 , por lo tantO la solucin particular buscada s 8n=-1slo resta busca la solucin de la homognea asociadab) ao*r- n= D, az =1 n)2 (I)La homognea asociada S n +r- =O, de donde 3n +1= a cula solucin eSK{r)nIa solucin padcular se puede pensar como un polinomio de grado r, digamosA n + B, siendo B soluein de la homognea, por ser una constante de dondeconviene multiplicar (A n + B) por la fienor potencia de n que asegUre la noexistencia de constantes (en este caso n)Queda &n= An2 + Bn , (I) se escribe &D +t= .n + nSe reemplaza y queda:A(n +r)z + B( n+r)= A n2 + Bn +n , operando y comparando los coecientes delas potencia semejantes queda:Para n2: A=A,Paran: eA +B= B+rPara eltrmino independiente: A +B = o= I, B=;i4La solucin particular es:r - l& = i!. +t-JD-I solucin de lahomognea asociada es k. I solucin que sebusca es:t - lan= fu2 +(f)n + cUsando las condieiones iniciales queda que c debe ser o y por lo tantoun = F= *(?"c) Si la ecuacin s ?= 3 an -r + 5( 3n) se puede proponer pn= A3oComo la solucin de la homognea asociada s k3o, reemplazando se llega auna contadiecin y por lo tanto se modifica por pn= An3o y queda 5n3r comosolucin particular quedando como solucin general: an = k3t+ 5r3n, donde elvalor de k se obtiene aplicando las eonciones iniciales.z6U.T.N.F,R-BJ"-DEPARTAMENTO DE INGENIERA EN SISTEMAS DE INFONMACINMATEMATICA DISCREIA _ CTEDRA GRANADO PEN,ATTA'Ao:ou, TRABA'OPNACTIOOT{O4Indu ccin y Rectrsidadnngnt t naturalrnr reald) La siguiente tabla nos ayrda para encontrar la forma de la solucin particular enalgutros casos determinadosSolucin particularconstanteAn+BAn2+Bn+CPolinomio completo de grado tArn2.9 Resolver cada una de las siguientes recurrenciasa) an = 4an+ - 3(4n)b) an*2&-1 =2c) an - 2-1 = 3n41.a)b)c)d)e)0s)A=N, a+b=2a.bA=2, a*b = a+2bA=P(B), a*b=abA = R, a*b = 2a+b-3c,c > a-bA=& "*=la.blA = N, a* b = {min {a'b}si min {a'b} s +" t max{a,bi en otro casoI ( r r - r ' l \Io=] l l I l ,u,u .z l r l , **y=*.yt l lD al I t\ \LJJ/(e= {a, la\,{u},{a,u}}r),r* y = (xt,r)- (* ^v)(a = n - {o} " Rf ),(x;y) * (";t) = (x.z;y.z + t}u.T.N.F.n-B-A-DEpARTAMENTo DE INcENTERfa EN srsrEMAs DE vFoRMAcINMATEMATTca orscng:r"lr - crrpn GRI$ADo PERATTAAoorrTRABAIo rrulc'rrcoxo5Estmchrras Al gebraicas FinitasJustificando, indicar cuales de las siguientes operaciones binarias son cerradas en el conjuntodado en cada caso:Con referencia al ejercicio anterior, cuando correspond4 estudiar ias propiedades y Ia existenciade elementos caacterscosAnalizar si los siguientes prres de operaciones se snibuyen mutuamentea * b = a + b, a o b = a. ben el conjunto R de los nmeros realesa *b =a+ b, a a b = aben el conjunto R delos nmeiosrealesa,rb= (a,b),a o b = [a,bJ enelconjuntoN delosnmerosnaturalesa * b = X nY, a o b = X uY enA = {@,{a,b},{c},{a, b, c}}a *b = XnY, a c b = XvYen P(A), V AConsiderar A = {a, b} y el conjunto e = {f: A -+ Ai. En AA se dene f*g = I t f I (x)Vx e A . Se pide dar la tabla para la operacin *.Estudiar las propiedades y hallar elelemento neutro. Indicar los elementos que tienen simtrico'Para el conjunto A = {e,4, 8, 16, 3z} y hs operaeiones binarias y cerradasa* b = (ab)Va. b = [a,b]donde(a,b)denotaelmximocomnvisorentre ayb,y[a, b] el mnimo comn mlplo.Se pide : a)Estudiar en cada caso las propiedades, b) la existenciade elementos caactesticos, c)indicar si se distribuyen mutunmente d)Justificar cada afirmacin.Indicar, justificando, cu'les de los siguientes pares alcanzan la estructura de grupo, cualesson semigmpos y en todos los casos analizar la conmutatidah)i)3.a)b)c)d)e)4.5.6.c)fnr) .a*=u'b-3- \ ' / ' 2 gd)(R-{o}f) ,a*b=+" l le=f[ ' o l . , ) \' t tL rJ ' =zJ{ ) 'x* Y = rY0(A = {a,{u},{b},{a,b}} '* ) ,* * y = (x- v)u(v- *)s)(e = n - {o} x R;*),(x;y) * (" ; t ) = ( :u;o)7. Sea G = {a, b, g d} V (C;* on grupo.Se pide determinar los elementos que faltan en la tablade la operacin *8.SeaX+Z,demostrarque(A'={f :S+S/fesbiyect iva};") ,dondef *S=f le(") ] ,vxeS t ieneestrustura de gnrpo. iQu pasa si las funciones son inyectivas?9. Aplir el resultado anterior aI conjunto finito = {a,b, c} .ro. Sean (C, ;., ) v (C" f , ) dos grupos con neutro e1Y e.r respectivamente. Probar que(G, " G";*),(*;y)* (r; t) = (x * tziy * zt)es un grupo, e incar las condieiones para gue seaabeano.rr. Aplicar el resultado del ejercicio anterior a(e = {o,r};*, ),tz. Demostra:( r = {o,r ,z} f") ,012r20201a) Si (G; *)es un semigrupo con neubo e, el conjunto G' = Inv (G) = {x e G / x' e G}29u.T.N.F.RB-a-DEpARTAMENTo DE INGENTEnIa n sr^srgues DE trifFoRMAcrNMArEMirrcA DtscR%3f?RA cR.eNADo PERALTATRABAIoPRTCTTCON" 5Estructuras Algebraicas Finitases un 8rupo.b) si (G;*)es un grupo entonces(G;')donde x' y : y* x es un grupoc) Si (G;*)esun grupo con neutro , X.y e G entonces (* * y)' = y'* x'd) (C;*)es un grupo abeliano o (x " y)' = x'* y'e) Si (G; *) es un grupo con neutro e; dados a, b probar que existen x, -v tales quea * x = b,y * a = b.v que esos elementos son nicosf) Si (G;*) esungrupo conneutroe,probar: a*c = b*c=a= b,c*a= c"b +a= bg) Si (G;*) esungrupoconneutroedondeparaeadaelementox, x*x:e entoncesGesungrupo abeano13. Reso)ver, si es posible, las ecuaeiones en el conjunto dado con Ia operacin indicada encada casoa)(Z; . ) ,2.x= zb)(r;z)* (";y) = (o;r) en el grupo del ejercicio no rrc) (t ; Z) + (*; y) = (z; l)en (N2; *) , N es el conjunto de los nmeros naturalesd) zx + 1 = -g n R con la mulplicacin usual14. Se sabe que en todo grupo, el elemento neutro es su propio simtrico. Probar que si(C;-) o un grupo y lCl es par, entonces hay, por lo menos, otro elemento de G quees su propio simtrico15. Sea (Cf ) u" grupo con neutlo e, sea H c G. Demostrar que H es un subgrupo de G si ysolamente si :H+ @,a e H,b e H entoncesa* b' e H16. Responder cada una de las siguientes cuestiones:a) Para el grupo (e = {4,{a}, [ t ] , {a,u}} f ) ,**y = (xu'y)-(xny).probar si H = {a, {.^\), T = {4, {a, b}}, P = {{b}, {"}} son subgruposb) sea s = {a,b,c} v el grupo(A = {f s -+ s / f es biyectiva} ;*),f * g = f [g (x)], vx .Probar si H = {f'f"},T = {q,fo,fu} son subgrupos' Considerar:3ou.r.N.r,.ng;;pARTAMENTo DE n{GENrERfa EN srsreuAs DE nFoRMAcrN- {l:,, r"ruonrr*"Xmffi;cRr{Ar}spERALrA' ' 'Esurturas Algebraicas Finitasf, = {(a;a),(b;b),(c; ' : - )} , f , = {(a;b),(b;c),(c;a)}, f , = {(a;c),(b;b),(c;a)},f* = {(a;a),(b;e),(c;b)} , fu = {(a;b),(b;a),(c;c)} , fu = {(a;c) , (b;a),(c;b)}c) para el grupo (2.*),probar que H = nZ = {x eZ,x = Lz,n,z e Z,nesfijo} es subgrupo17. Sea (G) un grupo y sean ] H, K subgrupos. Demostrar o refutar cada una de la-s siguientesafirmaciones:a,H n K es un subgrupo de (G;-)b)H u, K esun subgrupo de (C;*)c)H - Kes un subgrupo de (G;*)dIHAK es un subgrupo de (G;*)18. Considerar el conjuntoA = {(o;o),(o;r),(r;o),(r;r)}yla operacin * dadapor:- . . f ( "*c;b+d)si a+c< r ,b+d U.T.N.F.R.B-A.DNPITUENTO DE INGENIERfA EN SISTEMAS DE INFORMACINMArEIVATICA DISCR.ETA - CATI,ON CNIOO PERALTAAozouT.RABA'O PRr(CTIOO N" 5Estructuras Algebraicas Finitaszo. Hallar el subgrupo generado por el elemento dado en cada uno de los siguientes casos:") (i),(c = {r,-r,i,-i} ; .)b) ((" ;b) , ( ;c) , (c;a) )en s,c) (c) en (Cf) con la operacin definida por la siguiente tabla : abcdefabbccddeeffacddeeffaabbceffaabbccddezr. Sabiendo que para el grupo de los restos mduio n,los generadores son:Gen Zo {[t] (t.n = 1,1 < k < n - r], se pide da los generadores para n = t8 y n primo.ze. Dar la red de subgrupos para el grupo simtrico 53, para el grupo de los restos mduio 8, mduio5 y mdulo rz y el grupo del ejercicio no 1829. Un grupo G ene subgrupos H y K Encontrar todos los posibles rdenes de HtrKpara cada uno de los siguientes casos:a) lHl= 16, lKl= 2sb) lHl = lKl= 7c) lHl=3, lKl =Sd) Si lGl= z4 yl H l= 4,icules son los posibles rdenes para el cardinal de K?24. Halla las clases laterales determinada^s por cada subgrupo en el grupo dado en cada caso.Indicar, adems cuIes son subgrupos normalesa((o;o))en el grupo del ejercicio rrb) Para los subgrupos del grupo del ejercicio nol8/U^ ^\ ) \c)Parael srupoi { l ' l f ,a,c,de R};+ ly el subgupo S= {f : : ) ," . *}' \ t \ " d l ' ' ' ) ' ) ' [ \c o/ ' )d) Para el grupo (2,"1),n = (o)e) Para el grupo (z,u- {o};e); H = {;,;,;,;}25. Sea (G;*)un grupo y sea el conjunto Ze = {x e G / x* a = a * x, Va G} . Probar que es nnsubgrupo de G e indicar si es normal. Justificar cada afirmacin.26. Sean (Cl)"" grupo y H un subgrupo probar:32u.r.N.F.B-"ffHoffiHffi*Hfl"m|hffi '"AozouTRABA'O PRCTICO NO 5Estructuras Algebraicas Finitasa) si lcl= n,Hessubgupoae(cr)vlul= luotoo""s H es normal \ t - | | 2b) si lcl = u, E[ es subsrupo de (Gf ) ento"""r ful / lcfz7.Sea (c;-) ungrupoy (tr),.* unafamiliadesubgruposde (c)-Nssstssnjuntodelosnmeros naturales, probar qo" . H, es un subgrupo del grupo dado. Si todos losr=1subgrupos fueran normales, se pid.e demostrar que la interseccin es un subgrupo normal.Justifi car cada afi rmacin.zB. Probar si las siguientes funciones son homomorfismos de grupos, si corresponde dar ncleo eimagenalr,lzri)- (2, i) t([x]) = s - xb)f :{z;+} * (sz;+) / f (x) = pc)r : (n- {o} ' ) * (R - {o} ; . ) / r (x) = lx l29. Hallar todos los isomorfismos entre los grupos (zo;i)l (zu - {o} O)3o. Indicar, justificando, si el grupo simtrico So es isomor{o al grupo de los restos mdulo z4lz^;+) r l3r. Probarquelatuncin f :(R;+)-(M"(n);.)/r(*)=l:::1- ]""" lesunhomomorfismode'' ' l senx cosx Igrupos. Clasificarlo.32. Considerar el subgrupo multiplicavo de C (nmeros complejos), (i) = {i,-i,r,-r}y el grupo losrestos mdulo 4. Se pide probar que son isomorfos.33. Sea f : G, + G"un isomorfismo de grupos, probar que la funcin inversa ff' : G" -+ Giestambin un isomorfismo34. HaIIar el ndice que cada subgrupo deterrnina en el grupo simtrico S. y en el grupo de los restosmdulo 12. Dar, cuando corregponda el grupo cociente.35.Responder, justificando adecuadamente si los siguientes enunciados son verdaderos o falsos:a) En un grupo cada elemento tiene un nico simtricob) Un grupo puede tener mas de un neutroc) Puede haber un grupo donde falle la propiedad cancelatilad) Todo conjunto de nmeros que es grupo bajo la suma lo es respecto de la multiplicacine) Todo subconjunto de un grupo es un subgrupo bajo la operacin inducida0 El gupo simtrico Sn ene n elementosu'r'"''*Bfi mfffi mHt"m*ffi '"TR.BAro Pncrroo N3 5Esrncturas Algebraicas Finitasg) Todo grupo cclico es abelianoh) Todo grupo abeliano es celicor) Todo zubgrupo de un grupo abeliano es abeliano ynormalt Si un subgrupo de un grupo G es abeliano, el grupo G es abelianok) Todo grupo factor de un grupo infinito es infinitol) Ia composicin de homomorfismos de grupos es un homomorfismo de gruposm) Todos los grupos del mismo orden son isomorfosU'TJr.F-R-B-A--DEPARTAMENTI0 DE rNGENrEnfa EN srsTEltAs DE INFoRltAcrNMATEMIJTcI' "tr.."i"#f; u cnoo-plnrr ;.--.- --- -rnnuo pngnco r"oAgebras de BooleRedes1' Indicar, justicando, cules de los siguientes conjuntos ordenados estituye una redbde0oz. Considera el conjunto ordenado(A = {t,2,g,4,5,6,7,g,9,ro};U.T.N.F.R.B-A--DEPARTAI}ENTO DE INGENIERA EN SISTEMAS DE INFONMACINMATEVATICA DISCRETA - CATEDRA GRANAD.O PENALTAAoeorrTRA.BAJO PRACTICO NOlgebras de Boole5. Cousidera en conjunto A = {a, b, c, d, e, f g } y las operaciones dadas por las tablasabcdefg abcdefSabdfoDacdeacccdeagbcdebgccdecgdddgdgeegeegbcdefggggcgEabdfoafaLafafbbbbfbabcccfcabcdcfdabccefef f f f f f fabcdefESe pide dibujar el diagrama de Hasse, y probar si (lu v; a)es una red6. Sea A = {a-b,c,d,p,m}, completar la siguiente tabla y definir la operacin dual, demodo de obtener una red.abcdmabdmPbddPPdapbpcpdppT. Sobre un conjunto finito d considerar una red con primer elemento p y ultimoelemento u, e indicar los elementos neutro y absorbente para cada una de lasoperaciones. Justificar en cada caso.8. iCules de las siguieDtes son redes distribuvas?a) Dzo, a v b = mcm { a, b }= [ a, b ]; a b = mcm { a, b }= ( a, b )b)A= P (B) conB = {x, ,v,z} y a vb = aubi anb = a nbc)a36U.TJiIJI.B.A--I}EPAXTAUENTO DE INGENIERA EN SISIEMAS DE INFOXMACINUATtrIIC DISCTEIA - CTEDRA GRANADO PERAXTAAozouTRABA'O PNACTICO NO,{lgebras de Booleg. Sean(lsU.T.N.F.R.B.A--DEPARTAIENTO DE INGENIERA EN SISTEMAS DE INFORMACINMATEMTICA DTSCNETA - CAIEDRA GRANADO PENALTAAozo11TR.ATA.'O PNACTICONOAlgebras de Booleb e =f (C), C = {r,z;g} y B = {x e P(L)}, L es el conjunto de tomos de P (C)lgebra de Boole - Funciones booleanasProbar que (e = {1,23,4}yn) , donde las operaciones estn definidas por ias tablas quese dan a connuacin, alcanza la estructura de lgebra de Boole:7234 ^e+723422223232422412411121374113431L4z. Indicar, justificndo, cuIes de los siguientes conjuntos con las operaciones dadas encada caso alcanzan la estmctura de lgebra de Boole.a)(Dovn), avb = [a,b] ,a r ,b = (a,b),n = pr.ps.ps. . . .pu conpi +p,si i * jb) (Do;n),a v b = [a,b],a 5 = (a,b)c)(Ay),dondelel=19d) Si A es un conjunto, {r(a)vn)3. Anelizr la validez de las siguientes propiedades en un lgebra de Boole B, con neutoOgVlt para las operaciones v, n respectivamente, dar un contraejemplo si son falsasa) va,Vb,a = b (" " b)" (a" U) = o"b)vavb,(a nb)v (a " U)= ac) Va, Vb,(a n b) = r, 6d) va,vb,vsu " ( l ^.) = ; ; (b ' ")e)Va,Vb,ab)f(x, ;x, ;xr) = I ( t , n x,) , , (x" r . . x.) t xs] n x"c)f(x, :xr) = * , n [* . ' r ( r , ^( , . , " ; r ) ) ]U.T.NJT.B.L-DEPARTAJWENTO DE INGE{IERA EN SISTEMAS DE INFONMACINMAIEMJTICA DIS.CRSIA - CAIE.DRA GRANADO PERALTAr*o*-#..?ffi"o*"uAgebras d.e Boolec) 3 sub algebras distintas de la triviald) Identificar los tomos y establecer definir un isomorfismo ente (nrorv;n)f el conjuntode partes de los tomose) iCuntos isomorfismos se pueden definir? d,euntas funciones biyectivas no sonisomorfismos?S. Para cada una de las siguientes expresiones booleanas dar la funcin booleana quedeterminan.a) F,'(xr; xri xg) = Xr V (x" n x3 )b) E"(x'; xzi xJ = (xr v x") n (xr v xs)c )Ee( xr; xzi xg ) = ( x1 n xs ) v ( x, x" ) v ( x2 n x' n x. )6. Simpfieara)f (x, ;x" ;x,)= * , ' [ ( t " . . )n (" , . , * . " \ ) ]7. Expresar las siguientes funciones booleanas en forma cannica en minitrminos(forma normal disyuntiva) y en forma cannica en maxitrminos (forma normalconjuntiva)a) f (x, ;x";x, ) = [ " (r.] )b) f(x';x";xs) = x1 V (x, v x3)c)f(x, ;x. ;xr)= *" "( . , " \ )cl) f (x';xr;xJ = (xr v x" ) n (x' v xg)e) f (x'; x2) = (x' v x2) n (x' a xr)8. Cada una de las siguientes tablas definen fuciones booleanas. Se pide:a) Las formas cannicas en minitrminos y ma;iitrminos en cada caso.b) La forma cannica en ma;ritrminos para h(x) = f(x; y; z) ng(x; y; z)c) la forma cannica en minitrminos para t(x) = t y; z) vg(x;y; z)x v z f. (x;y; z) g(x; y; z)1 1 I 1 o1 I o 1 o1 o I o oI o o o o39o 1 1 o 1o 1 o o 1o o 1 o 1o o o 1 oU.T.N.F.R.B^--DEPRTAUNNTO DE INGENIENfA EN SISTEMAS DE INFORMACINMATEMATICA DIS,CREIA _ CAIEDNA GRANADO PERALTAAo zorrTRABA'O PRACTICO NO6Agebras de Booleg. Disear una red de compuertas con entradas x, y que produzca salidas a, b, c en lassiguientes condi ciones :- a=1,b=C=O,SiX)y- b-c=O,a=1,six =y- C=a=1,b=O,SiX(y10' Un examen consta de 4 preguntas. Is respuestas correctas son la ro es Verdadera,la zo es Falsa, la 30 es Verdadera y la 40 es Falsa. Constrir una funcin booleanaque analice cada examen y distinga los aprobados de los reprobados. Se consideraaprobado con tres o ms respuestas correctas.u. Se quiere consEuir una alarma para un automvil a travs de un sistema decompuerlas de modo tal que la alarma suene si: Si el motor est funcionando valguna de ias puerLas se encuentre abierta. El motor est sin funcionar, las lucencendidas y algunas de las ventanas est abierta El motor est funcionando y elcinturn de seguridad se encuentra desabroehado. Se pide disear eI sistema y darsu forrna normal disyunwre. Carlos gan un bono de $6Zoo en un superniercado y el dinero se efectivizar sloen el caso de utilizar la mayor candad posible, no repetir productos y elegirlos dela lista que se da a continuacin. se pide disea oo" ,ud de compuelas queotplicite la situacin.TELE\IISOR $3zooDVD $nooNOTEBOOK $4sooNETBOOK s23oODescrib, concompuertasuna funcin booleana, cada uno de los siguientes agramas de13.40U.T.N.F.R.B*A--DEPARTAMENTO DE INGENIERfA EN SISTEMAS DE INFORMACINMATEMrrcA DTScRETA - crgon' cnNoo PERALTAAozouTRABA.'o PRAgnCON"6Algebras de Boole---------------_ \\t l-----l-----7-.ff--E)F)4tU.T.N.F.N.B.DEPARTAMENTO DE INGENIERfA EN SISTEMAS DE TNFORMACNMATEM..TICA DISCRETA - CATEDNA GRANAIX) PERALTArn#rifficor*" zGrafos, Digrafos, r{bolesGrafosr. Dibujar el grafo G = ({r,2,3, 4,s,6\da,a2,a3,a4,a5,a6,a7}ro)dado pora, larararaoauaoa,p(a,)l{s,z} {s,t} {+l {s,s} lo,qi {o,r}{z,r}z. Para cada uno de los siguientes grafos, dar explcitamente la funcin de incidencia l' a1-u. I u" /a lu,| ,z'ul IaY )c\Juonn4----1\. l'\l\ .P\^g. Dar para cada uno de los grafos de los ejercicios anteriores ejemplos de vrticesadyacentes, lazos, aristas ad,vacentes y paralelas y en cada caso las matrices deadyacencia e incidencia.4. Para el grafo C = (v,p ) eula matriz de adyacencia es M" , dada por:101o101()1101o10111Se pide:a) El agrama del grafob) I matr de incidenciac) El subgafo que se obtiene suprimiendo el subconjunto de los vrtices cu,vos elementosseanlos de mayorymenor grado.M"=1()1011101oooo10ooo42U.T.N.F.LB.A.DEPARTAITfENTO DE INGENIER'A EN SSTEMAS DE INFORMACINMATEMTICA DISCRETA _ CA' TEDRA GRANADO PERALTAAozorrTRABAJO PnriCTrCONo 7Grafos, Digrafos, Arbolesd) El subgrafo que se obtiene suprimiendo las aristas que inciden en pol lo menos unvrtice de grado par.S. Dibujar el grafo G = (v; ,q ,p i cuya matriz de incidencia es M, , dada por:[orroloIlo I o o I 1M,: lo o r 1 o Ilo o o o o 0Ll 00ooo6. Establecer una relacindiagrama del grafo.. '1; lIr lI0lIolentre la matriz de incidencia y las caractersticas delT. Resolver cada una de las siguientes cuestiones:a) Identificar los caminos simples de maJ'or y menor longitud para el grafo delejercicio rb) Indicar el camino elemental de mayor longitud para el grafo i) del ejercicio zc) Mostrar un camino finito y cerrado para el grafo ii) del ejercicio zd) Dar los caminos simples y elementales para los grafos de los ejercicios r y ze) Idenficar los grafos conexos de los ejercicios 1, 2, 4,58. Considera el siguiente grafo:Resolver cada una de las siguientes qrestiones:a) Caminos simples entre aY g43U'T.N.F.RB.DEPARTAJ}ENToDEINGENIERAENsIsTEMAsDEINFoRMACINMATiii&tncatls"*okmRA GRANADo PERAITA"'ff#f'#trHil"'b) Menor nmero de aristas que es neeesario suprimir para interrumpir el caminoentre b y dc) i ,Hayalgncaminocerradoentrecycdemaneraquepasesolamenterrnavezpor cada uno de los vrtices restantes?d) if,s posible partir del vrrice c, pasar por todos los vrtices y no regresar al c?e) i, se puede comenzar por un vrtice recolTer torls las aristas exastamente unavez?( se permite pasar mas de una vez por los vrtices y no es necesario volver alvrtice del que Parti)9. Dar el grado de cad"a vrtice de los grafos de los ejercicios 8 y rro. Si G = (V; A;u.TJa|-t.lErIDEraIt rlE INGqIIERA EN STSTEMAS DE INFORMACINaOzorrTTABAJOPB,gnCoNoTGrafos, grafos, t{rbolesr8. Demosrar o rfucon rm connaejemplo:a) Si G = (r'I,;g)esuugrcompleto"oolvl= n, entonce'lol=9b) En todo grafr & dos e mas vrtices debe haber dos vrtices del mismo gradoc) Todo subgrafo de un grafo bipartito es bipanito19. Si es posible daun camino y / o un ciclo de Euler para los siguiente, *o,'a) Grafo bipartito comPleto K a4b) Grafo del ejercicio 820' Para los grafos bipartito completo Km'n Y completo Kn' Dar condiciones sobre my n para el primero de los grafos y sobre n para eI segUndo pala que existancaminos de Euler. Caracterizar, adems en ambos casos la matriz de adyacenciazr. sea G = (v;A;p) un grafo con un nmero par (zn) de vrtices y matriz deadyacencia:f-e clMIS DJSe sabe que B, C, D son matrices cuadradas de orden n Responder,jusficando,cada una de las siguientes cuestiones:a) Si C es la maEiz nula, ies conexo?b) Si B=D, es bipartito comPleto?c) Si G es conexo y la suma de los vrtices es 2n-2, ies un fubol?zz. Cules de los siguientes grafos tienen caminos y / o ciclos de Hamilton23. Si es posible da un camino y / o un eiclo de Hamilton para los siguientes casos:a) Ks,K4 d'influ,ve quen seaparo impar?b) &,g,L*Kr,, iinfluye que n' m sean ambos pares o ambos impares' o uno pary el otro impar?15U.T.N.F.R-B.DEPARTAMENTO DE INGENIENfA EN SISTEMAS DE INFORMACINMATEMTIQ\ DISCRETA - CTEDRA GRA{ADO PERALTAAo zorrTRABAJO PRACTICONO "Grafos, Dgrafos, r4bolesz4.Paralas siguientes armaciones se pide, demostrarlas si son verdaderas y e>ribirun contraejemplo si son falsasa) En un grafo mmpleto K,r, n > 3. el nmero de aristas es lel = n (n - 3) + nb)Para un grafo bipartito completo G = Krn.n , el cardinal de las aristas es n.m y el de losr'rtices m+nc) Todo subgrafo de un grafo bipartito completo es bipartito eompletod) Si G = (Vg q) es un grafo no conexo con k componentes conexa.s y lfrl = n, lAl = m.Entonces,n S m+k25. Indicar si los siguientes pares de grafos son isomorfos, si corresponde exhibir elisomorfismo26. Demostrar o refuta:a) Grafos isomorfos tienen igual nmero de vrtices y aristasb) f : (q;A,;o.) -+ (v,;A";o, ) es un isomorfismo d.e grafos, v e \ entonces el gradode v es el mismo que el grado de f(v)c) Existen grafos no isomorfos con eI mismo nmero de vrtices y aristasd) Si G y T son dos grafos isomorfos y T tiene un cido de Euler entonces todos losvrtices cle G tiene grado par.e) Si G, =(\;A,;g,) yG, =(V;Ar;gr) son isomorfosexisteunordenconvenienteenVlMa(&)=\{a(Ge)a)b)+6u.T.N.F.R.B.DEPAI$AMENToDEINGENIERIAENsIsTEMAsDEINFoIMACIN-- MAffitrc orscnr - cAnoRA cR'aNl)o PER'ALTAtlnlo rncrtco N" zGrafos, Dgrafos, rbolesDgrafos1. Para el dgrafo G = (V;AS) ' cuyo diagrama se da a continuacin:v5'Resolver cada una cle ias siguientes cuestiones:a) Denicin formalbi Buclesc) Aristas paraielas,v antiparalelasd) Vrtices.v aristas adYacentesei Matriz de adYacenciag Matriz de incidenciag) Pozos Y fuentestr C*Ao positivo, negavo, neto y total para cada vrticeZ. Siete ciudades A, B, C, D, E, F, G estan conectadas por nn sistema de autopistas, de laforma que se da'a continuacin:(t) !-zzva de A a C Pasando Por B(z) I-Sg va de C a D, pasa por B y sigue hacia FtB) I-q+va de D Por E hacia A(+) I-SS va de F a B Pasando Por GG) I-66 va de G a D.Considerando que las ciudades son los vrtices ile un dgrafo y las autopistas las aristas,se pide:a) Modelizar ia situacin usando un dgrafob) Darlos caminos simples entre GyD"i Indicar el menor o*"ro de tramos de autopista que se pueden cerTar de modo queel paso entre B y D quede intemrmpidod) Justificar si es posible salir de -c y t"gr"t* a c pasando por todas las otras ciudadessolameute unaveze) Incar si es posible'esmenzar en alguna ciudad y ajar por todas las autopistaspasando por cada,una de ellas solamente una vez(se pude visitar una ciudad mas de unavez y no es necesaio regresar a la ciudad de la que se parti)?717U.T.N.F.R-B.A.DEPARTAI}ENTO DE INGENIERIA EN SISTEMAS DE INFORMACINMATEMATTcA DrscRErlBgl?RA cRAI\ADo pERAL'raffif'#ffK':,g. Hay cuatro tipos brsicos de sangre A, B, AB y o. El tipo o puede donar sangre a loscuatro tipos, Ay B pueden dona aAB lo mismo que a su propio tipo pero el po AB slopuede donar aAB. Dibujar un grafo dirigido que muestre esa informacin.4. Sea G = [V; A;6) un dgrafo, en el conjunto de vrtices V se define la siguiente relacin vRw eov = wv existe un camino de v a w vexisteun camino de wav"Probar que la relacin R es de equivalencia.rboles1. Para el grafo G=(y; A; q ) ,con lV = 5 dibujar todos los arboles no isomorfos.2. sean G, = (V, A, ;e, ) y Gz = (v" l\2 ;e" ) dos rboles donde i Az l= 26 Y[Vrl = zlAzl. Deterrninar: l\'11, V"lV ltl.3. Sea G : (V*t;p) un grafo conexo que tiene 29 aristas, 7 vrtices de grado t, 3 de grado 2,Z de grado 3 y n vrtices de grado a determinar para satisfacer, si es posible, cada una delas siguientes situaciones:a) G seaun arbolb) G no tlebe ser rbo]4. Probar que un arbol con n vrtices ene (n - r) aristasS. Sea T uu bol con rz vrtices que tiene 3 vrtices de grado 3, r vrtice de grado z. Se pidedarla sucesin de gados de los vrtices' 6. Seaungrafo G=(VA;q) ,conexo,sinciclosyconnvrt ices,entonces IS(")=z(n-r)vIV7. Sea G = (Vlug) un grafo conexo, probar que es un rbol si y solamente si toda arista es unpuente.8. Sea G = (\r;A;g) un bosque con n vrtices y k componentes. Deducir y demostrar unaerpresin que calcule el nmero de aristas.g. Despues de equetar los vrtices que no lo estn en el agrama I que representa un rbol ,se pide responder cada una de las siguientes preguntas:a) iCules de los vrtices son hojas?b) iQu vrtice es la raz?c) Qu vrtice es el padre de g?il) d,Qu vrtices son los descendientes de fle) iCules son los hermanos de d?f) Cul es el nmero de nivel del vrtice j?+8ElltI-f-LrElatfalrElvo DE TNGENTERa EN srsTEMAs DE rNFoRMAcrN- IAXflIICADISCnETA_CATEDnCeb-r-rxr,rAo zorrTRABAJO PRCTICO NO ZGrafos, Dgrafos, bolesg,) Qrevtrces enen el nivel 3 ?h) ftl es la altura del rbol?i) iEs u bol balanceado?j) iEs m- ario, para algn m?k) Es regular?l) Es pleno?m) Dar los subarboles con raz en f, b 'd. Caracterizarlos.diagrama (I)10. Para el rrbol del ejercicio anterior establecer rrn orden para los hijos del mismo padre.u. rndicar, al menos un par de arboles isomorfos entre los siguientes:+! -r^->, +#-^rz. Considerar el siguiente rbol, etiquetarlo v recorerlo, si es posible, en orden prwio, ordensimtico y orden posterior. . / \/ \faaa4913.14,15.U.T.N.F.N-B3.DEPARTAMENM DE INGENIERA EN SISTEMAS DE INFORMACINMATEMATICA DISCRETA - CTEDN,A GRANADO PER.{I,'TAAo orrTRABA.'O rnaCrrCO rrr" 7Grafos, Dgrafos, rbolesIa siguienteetpresin:xy+31ry-gt-xy * "rndadaennotacinnotuor**".r . , r .pide recuperar el rbol, escribirla en notacin infija usual y simplificarlaIa siguiente expresin: ((Z-a) /S) * ((a + b)tg) est dada en notacin infija uzual, se piderecuperar el rbol, escribiria en notacin poiaca 1'en notacin polaca inversaIa siguiente expresin: (a + b-c) I (d * es) esta dada en notacin infija usual , se piderecuperar el rbol, escribirla en notacin polaca y polaca inversa16. Dar un ejemplo de arbol binario, con por lo menos 3 vrtices en el que:a) Los reeonidos en orden previo y orden simtrico sean el mismob) l.os recorridos en orden posterior y orden simtico sea los mismos17. Indicar si los siguientes enunciados son verdaderos. Justificar Ia siguiente erpresin dada en notacin polaca inversa no puede ser expresada ennotacin infija usual ab + cd*ef /-+a *b) El recorrido de un rbol en orden simtrico alcanzapara definir una operacin aritrncaU.TJ{J @rral E SFrrxrs rtE llfutrst'rrE.rc --Gffi^ GIANAIX} PER^LTArfu-orrr|DsltcrraoN"8r -Er+=, ganticas, autmatasIcnguajes1. Parataspalabrasl{r = 1oo1, \r2 = o, w3 = 2deV" siendo y = {o,r} se pide:w1w2, lw1rrrg, w3wr, wrRwz, ( wrRwz )R, (*g*rR)R, (w1t'2w3)R, (w1w3Rw2R)Rz. Considerar el alfabeto y = {ab.c}y dar, por enumeracin:a) Todaslas paiabras de longitud < rb) Todas las paiabras de longitud < zc) Todas las palabras de longitud < 33. Darla longitud de cada una de las palabras del ejercicio r4. probar que si Ves un alfabeto, el conjunto V* de todas las palabras que se puedenescribir con las letras de V es un semigrupo, bajo la concatenacin y caracterizarlo.5. Probar, usando induccin matemtica que si Ves un alfabeto, w e V',n e N u {O}entonces long(wo ) = t.loog*6. Paral=321{deV*,conV={o,r.2,3,4},sepidedar: long(wto), to"g( l* to)toT. Para los lenguajes L, = {ab.ba},L" = {UaU},r, = ttr},L+ = , deV',siendoV = {a,b1t se pide:L,L,,L rL 3,L, L4, L4L3, (L't " )*, {{, {r,f , Lo u Lsr, L, n L5,,, I{ u LoB. Probar que si V es un alfabeto, el conjunto P (V*) de todos los lenguajes de V*es unsemigrupo, bajo la concatenacin y caracterizarlog. Considerar eI alfabeto y={o,r} y los lenguajes Lr={Ot,tr,o} y Lz= {ro,r}, se pide:a) Calcular L, x L" yLrLreindicar, en cada caso, eI cardinalbi Dar un ejemplo donde ll,rl=l.ll.rlll."lro. Descrbir L|L',L1I y(L1L2)" sirr. Se sabe que paratodolenguaje Irz. Proba o refuta :a){I}= {l}- = {rfLr={1},L"={o}l,eL:*, icuandotreL*?51U.T.N.F.R-B*&-DEPART4MEMO DE INGENIERA EN SISTEMAS DE INFORMACTNMATEMAncA nrscnrrSSflpnl' GRANADo PERALTATR,ABAIO PRJ{CTICO N" 8Lenguajes, gramticas, autmatasb) Si V es un lenguaje, V+ = V* -{ 2 }13. Calcular las clausuras positiva y de Kleene del lenguaje vacoGramticas1. Para lagramtica 6 = (vo;\t f;s)dondevo = {a,b,s},v, = {o,r,a}-vlasproducciones de P estn dadas por: s -+ ab, a + 01 | oar, b -+ z I bz'Se pide dar por lo menos 4 palabras del lenguaje que Senera y las derivaciones paraencontrar las palabras aL222, ooo111222e. Considerar la gramtica G =( { e, u, t, v, f h{ i, *, *, (,), h P; e) donde lasproduecionesde Pestndadaspor: e ) u, u ) t /u+t,v ) f /v ' r f , f ) i /(e) . Dar cinco palabras del ienguaje que genera'g. Halla una gramca que genere cada uno de los siguientes lenguajes:a) = {oen conn>e}b) l= {omlD2m,tr2o,m>1}c) I= {ont2n,n>1}i t ) Lo= {(or)nol ,n>o}4. Considerar la gramtica G = ({x, y, z, t} do, r} P;x) y clasificarla de acuerdo con lasreglas gramaticales que se dan en cad'a caso:x--+zyt , t+o l1,oy-)1, 1y+ a,oz-+ 1 '12-+o l1x +zt" zt-+tY, Y-+L, z-+ax+zylyz, z+1, y-+ox-+ly l tuy-+o,z-+ol1Para las expresiones regulares sobre el alfabeto V ={o,t} , que se dan aen cada caso dar cinco*connuacint o1*o;o*t*;(or)-;o* v 01* ;(o t' r)o- ;(o-r- )palabras y el lenguaje regular asociado6. Mostrar si las siguientes gramticas son equivalentes:Gr= ({a, b, ch{o,rhP; a)a -+ co; co -+ rbr; 1c -+ obo; b -+L I o ; c --+LGz = ({a, b, ch{o,rhP; a)a+rb; b->t / rc loc,c-+1a)b)c).1)5.52L-.T*\[JT N [ {In|S T,]Tu|TO D fTGEiIBfA E]t[ SISTEMAS DE INFORI{ACINil,JrTffi.{T\ D|aMELI' - CTEDBA GRANA.DO PERAL'TA.l$o zorrTr.ABJuo plctlcox" 8T en8qies, gramtics, autmatase = i{a- b}:io.:.}:p: a)a --+ rbt, u; b --+r I oAutmatas1. Dibujar el diagrama de transicin y dar ia definicin formal para cada uno delos siguientes diaglamas de transiciones:a es estado iniciala, b son estados finaleso12a es estado iniciaic es estado finalo es estado iniciala)b)a)b)abcabcbcac a bc)o12Jo1r {o, z}3131r es estado finalDado el agrama de transiciones dar explcitamente la funcin de transiciones y ladefinicin formaltrac)U.T.N.F.R-B.A.-DNPENTITEXTO DE INGENTERfA EN SISTEMA.S DE INFORMACINMATE&(TICA DISCRETA _ CATEDRA GRANADO PERALTArn.r.S?ifficox"e'' " -' ' knguajes, gramticas, autmatas3. Con referencia al ejercicio anterior y mediante la observacin del dgrafo dar ellenguaje que reconoce cada autmata. Justificar usado las reglas.4. Ciasificar los autmatas de los ejercicios anteriores en determinsticos, nodeterminsticos y completos.5. Considerar el alfabeto 1r= {o,r}y disear un AF. que responda cada una de lassiguientes situacionesAcepte un lenguaje no finito cu1'as paiabras tengan un nmero impar de cerosAcepte solo las siguientes palabras ooq 1oo; ooo; 111Acepte un lenguajes no finito cuyas palabras tengan un nmero impar de letrasDisea un autmata finito determinstico que reconozca el lenguaje = (ab., aba)* v a* , y dar el diagrama de transiciones.Sea el autmata finito M = ({p,q}da,u}fu {o})donde la funcin 6 se define por latabla de transiciones:a)b)c)6.n6l a bt[e,=]-61-q | @ {p,q}Se pide indicar,justificando, si ias palabras azb, ba, b2a pertenecen al lenguajereconocido por el autmata8. Disear un autmata finito que reconozca un lenguaje no finito, sobre V = {o,r}cuyas palabras tengan un nmero par de ceros j un nmero impar de unos9. Definir una gramtica regular que genere el lenguaje I= {aa,bb, ab, ba} y dar elAutmata finito que lo reconoceI5+

Recommended

View more >