BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Departamento de Computación - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Departamento de Computación
X-ORIGINAL-URL:https://www.dc.uba.ar
X-WR-CALDESC:Eventos para Departamento de Computación
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Sao_Paulo
BEGIN:STANDARD
TZOFFSETFROM:-0300
TZOFFSETTO:-0300
TZNAME:-03
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Sao_Paulo:20241001T140000
DTEND;TZID=America/Sao_Paulo:20241001T160000
DTSTAMP:20260515T113918
CREATED:20240923T172823Z
LAST-MODIFIED:20240923T172823Z
UID:9437-1727791200-1727798400@www.dc.uba.ar
SUMMARY:Defensa Tesis Doctorado Pablo Terlisky
DESCRIPTION:Título: Representación numérica de modelos arco-circulares propios\nDirector: Dr. Francisco Soulignac\nJurados: Dr. Luerbio Faria\, Dra. Ana Ferreira Da Silva\, Dr. Luciano Grippo \nLink al evento: https://youtube.com/live/H4bl664rR_I?feature=share \nResumen: Un modelo arco-circular propio (PCA) es un par M=(C\,A) donde\nC es un círculo con un punto 0 y A es un conjunto de arcos de C donde\nningún arco contiene a otro. El modelo M es equivalente a otro modelo\nPCA M’ cuando los extremos de los arcos de M aparecen en el mismo\norden que aquellos de los arcos de M’ si se recorren sus círculos en\nsentido horario desde el 0. Si todos los arcos de M tienen longitud l\ny sus extremos están a distancia al menos 1\, entonces M es un modelo\n(|C|\,l)-CA. El problema de representación unitaria (Rep) pregunta si\nexiste un modelo (c\,l)-CA equivalente a un modelo PCA M dado\, para\nalgún c y l. \nEn esta Tesis abordamos Rep modelando cada instancia como un sistema\nde inecuaciones lineales R que tiene un digrafo toroidal S asociado.\nAsí\, derivamos un algoritmo certificante para resolver Rep más simple\nque los conocidos en la literatura. Además\, analizando la\nrepresentación toroidal de S\, demostramos que los vértices de la\nregión factible de R son enteros. Este resultado implica la\ntratabilidad computacional del problema de representación minimal\n(MinUCA)\, donde buscamos un modelo (c\,l)-CA equivalente a un modelo de\nentrada M que minimice c y l. Diseñamos un algoritmo que resuelve\nMinUCA en tiempo O(n^3) y espacio O(n^2). \nMás allá de MinUCA\, definimos el problema de representación mínima\n(IsoMinUCA)\, donde\, dado un modelo PCA M\, buscamos un modelo (c\,l)-CA\ncuyo grafo de intersección sea isomorfo al de M\, minimizando c y l.\nDemostramos que IsoMinUCA está bien definido y que es NP-Completo. \nFinalmente\, estudiamos k-Mult\, una generalización de Rep que consiste\nen determinar si un modelo PCA M es k-multiplicativo. Intuitivamente\,\ntenemos que encontrar un modelo (c\,l)-CA tal que al extender q veces\nla longitud de sus arcos se obtenga un modelo de la q-ésima potencia\nde M\, para todo q <= k.
URL:https://www.dc.uba.ar/event/defensa-tesis-doctorado-pablo-terlisky/
LOCATION:Sala 1604
CATEGORIES:Agenda
END:VEVENT
END:VCALENDAR