-
Notifications
You must be signed in to change notification settings - Fork 5
/
Exemplo.tex
155 lines (107 loc) · 7.36 KB
/
Exemplo.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
\documentclass[graduacao,brazil]{ThesisPUC}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Rset}{\mathbb{R}}
\newcommand{\Zset}{\mathbb{Z}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\autor{Breno Calazans}
\autorR{Calazans, Breno}
\orientador{Gustavo Robichez de Carvalho}
\orientadorR{Carvalho, Gustavo Robichez de}
\titulo{Nome do seu projeto final}
\titulouk{Title of your project}
\subtitulo{Subt\'{i}tulo (opcional)}
\dia{07} \mes{Setembro} \ano{2014}
\cidade{Rio de Janeiro}
\CDD{510}
\departamento{Inform\'atica}
\programa{Sistemas de Informa\c{c}\~{o}es}
\centro{Centro T\'{e}cnico Cient\'{i}fico}
\universidade{Pontif\'{i}cia Universidade Cat\'{o}lica do Rio de Janeiro}
\uni{PUC--Rio}
\course{Sistemas de Informa\c{c}\~ao}
\diploma{Bacharel em Sistemas de Informa\c{c}\~ao}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Não precisa preencher se for um Projeto Final %
%
\banca{
\membrodabanca{Luis Carlos Pacheco R. Velho}{IMPA}
\membrodabanca{Jorge Stolfi}{UNICAMP}
\coordenador{Ney Augusto Dumont}
}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Não precisa preencher se for um Projeto Final %
%
\curriculo{%
Graduou--se em Engenharia na Ecole Polytechnique (Paris, Fran\c{c}a), cursando \'{A}lgebra e Inform\'{a}tica, assim como F\'{i}sica Te\'{o}rica. Especializou--se na Ecole Sup\'{e}rieure des T\'{e}l\'{e}communications (Paris, Fran\c{c}a) em Processamento de Sinais de Voz e Imagens, assim como Organiza\c{c}\~{a}o e Planejamento. Trabalhou junto com a empresa Inventel em sistemas de telecomunica\c{c}\~{o}es sem fil baseados na tecnologia BlueTooth. Desenvolveu junto com os seus orientadores durante o Mestrado ferramentas de topologia computacional.}%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\epigrafe{%
Lorem ipsum.
}
\epigrafeautor{Wassily Kandinsky}
\epigrafelivro{Regarde}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\agradecimentos{%
Aos meus orientadores Professores H\'{e}lio Lopes e Geovan Tavares pelo apoio, simpatia de sempre, e incentivo para a realiza\c{c}\~{a}o deste trabalho
Ao CNPq e \`{a} PUC--Rio, pelos aux\'{i}lios concedidos, sem os quais este trabalho n\~{a}o poderia ter sido realizado.
\`{A}s minhas av\'{o}s, que sofreram o mais pela saudade devida a minha expatria\c{c}\~{a}o. Aos meus pais, irm\~{a}s e fam\'{i}lia.
Aos meus colegas da PUC--Rio, quem me fizeram adorar esse lugar.
Aos professores Marcos da Silvera, Jean--Marie Nicolas e Anne Germa que me ofereceram a oportunidade desta coopera\c{c}\~{a}o.
Ao pessoal do departamento de Matem\'{a}tica para a ajuda de todos os dias, em particular \`{a} Ana Cristina, Creuza e ao Sinesio.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chaves{%
\chave{Teoria de Morse}%
\chave{Teoria de Forman}%
\chave{Topologia Computacional}%
\chave{Geometria Computacional}%
\chave{Modelagem Geom\'{e}trica}%
\chave{Matem\'{a}tica Discreta}%
}
\resumo{
A teoria de Morse \'{e} considerada uma ferramenta matem\'{a}tica importante em aplica\c{c}\~{o}es nas \'{a}reas de topologia computacional, computa\c{c}\~{a}o gr\'{a}fica e modelagem geom\'{e}trica. Ela foi inicialmente formulada para variedades diferenci\'{a}veis. Recentemente, Robin Forman desenvolveu uma vers\~{a}o dessa teoria para estruturas discretas, tais como complexos celulares. E isso permitiu que ela pudesse ser aplicada a outros tipos interessantes de objetos, em particular para malhas.
Uma vez que uma fun\c{c}\~{a}o de Morse \'{e} definida em uma variedade, informa\c{c}\~{o}es sobre sua topologia podem ser deduzidas atrav\'{e}s de seus elementos cr\'{i}ticos. O objetivo desse trabalho \'{e} apresentar um algoritmo para definir uma fun\c{c}\~{a}o de Morse discreta \'{o}tima para um complexo celular, onde obter o \'{o}timo significa construir uma fun\c{c}\~{a}o que possui o menor n\'{u}mero poss\'{i}vel de elementos cr\'{i}ticos. Aqui foi provado que esse problema \'{e} MAX--SNP dif\'{i}cil. Entretanto, tamb\'{e}m ser\'{a} proposto um algoritmo linear que, para o caso de variedades de dimens\~{a}o 2, \'{e} sempre \'{o}timo.
Tamb\'{e}m foram provados v\'{a}rios resultados sobre a pr\'{o}pria estrutura das fun\c{c}\~{o}es de Morse discretas. Em particular, uma representa\c{c}\~{a}o equivalente por hiperflorestas \'{e} apresentada. E atrav\'{e}s dessa representa\c{c}\~{a}o, foi desenvolvido um algoritmo para constru\c{c}\~{a}o de fun\c{c}\~{o}es de Morse discretas em complexos celulares com dimens\~{a}o arbitr\'{a}ria. Esse algoritmo \'{e} quadr\'{a}tico no tempo e, apesar de n\~{a}o se poder garantir o resultado \'{o}timo, d\'{a} respostas \'{o}timas na maioria dos casos pr\'{a}ticos.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chavesuk{
\chave{Morse Theory}%
\chave{Forman Theory}%
\chave{Computational Topology}%
\chave{Computational Geometry}%
\chave{Solid Modeling}%
\chave{Discrete Mathematics}%
}
\resumouk{%
Morse theory has been considered a powerful tool in its applications to computational topology, computer graphics and geometric modeling. It was originally formulated for smooth manifolds. Recently, Robin Forman formulated a version of this theory for discrete structures such as cell complexes. It opens up several categories of interesting objects (particularly meshes) to applications of Morse theory.
Once a Morse function has been defined on a manifold, then information about its topology can be deduced from its critical elements. The purpose of this work is to design an algorithm to define optimal discrete Morse functions on general cell complex, where optimality entails having the least number of critical elements. This problem is proven here to be MAX--SNP hard. However, we provide a linear algorithm that, for the case of 2--manifolds, always reaches optimality.
Moreover, we proved various results on the structure of a discrete Morse function. In particular, we provide an equivalent representation by hyperforests. From this point of view, we designed a construction of discrete Morse functions for general cell complexes of arbitrary finite dimension. The resulting algorithm is quadratic in time and, although not guaranteed to be optimal, gives optimal answers in most of the practical cases.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modotabelas{figtab} % nada, fig, tab ou figtab
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\input{Capitulos/Introducao}
\input{Capitulos/EstadoDaArte}
\input{Capitulos/PropostaEObjetivos}
\input{Capitulos/PlanoDeAcao}
\arial
\bibliography{Exemplo}
\normalfont
%\begin{thenotations}
% %------------------------------------------------------------------------------%
% \section*{Simplicial Complex}
% %------------------------------------------------------------------------------%
% %
% \noindent
% \begin{tabular}{ll}
% \mathbb{R} & conjunto dos n\'{u}meros reais \\
% \end{tabular}
%
%\end{thenotations}
%\printindex
%\appendix
%\chapter{Primeiro Ap\^{e}ndice}
%O primeiro ap\^{e}ndice deve vir ap\'{o}s as refer\^{e}ncias bibliogr\'{a}ficas. Depois que voc\^{e} colocar a diretiva ``{$\backslash$}apendix'', todos os %``{$\backslash$}chapter\{\}'' v\~{a}o gerar ap\^{e}ndices.
\end{document}