Federal University of Pelotas thesis and dissertation (texufpel)

This work (the "texufpel" document class and its supporting files)
is distributed under the LaTeX Project Public License (LPPL), version 1.3c.

Copyright 2026 Marilton Sanchotene de Aguiar

This work has the LPPL maintenance status `maintained'.
The Current Maintainer of this work is Marilton Sanchotene de Aguiar.

This work consists of the file texufpel.cls.

The full text of the LPPL version 1.3c follows below. The latest version
of this license is always available at latex-project.org

================================================================

The LaTeX Project Public License
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

LPPL Version 1.3c  2008-05-04

Copyright 1999 2002-2008 LaTeX3 Project
    Everyone is allowed to distribute verbatim copies of this
    license document, but modification of it is not allowed.


PREAMBLE
========

The LaTeX Project Public License (LPPL) is the primary license under
which the LaTeX kernel and the base LaTeX packages are distributed.

You may use this license for any work of which you hold the copyright
and which you wish to distribute.  This license may be particularly
suitable if your work is TeX-related (such as a LaTeX package), but 
it is written in such a way that you can use it even if your work is 
unrelated to TeX.

The section `WHETHER AND HOW TO DISTRIBUTE WORKS UNDER THIS LICENSE',
below, gives instructions, examples, and recommendations for authors
who are considering distributing their works under this license.

This license gives conditions under which a work may be distributed
and modified, as well as conditions under which modified versions of
that work may be distributed.

We, the LaTeX3 Project, believe that the conditions below give you
the freedom to make and distribute modified versions of your work
that conform with whatever technical specifications you wish while
maintaining the availability, integrity, and reliability of
that work.  If you do not see how to achieve your goal while
meeting these conditions, then read the document `cfgguide.tex'
and `modguide.tex' in the base LaTeX distribution for suggestions.


DEFINITIONS
===========

In this license document the following terms are used:

   `Work'
    Any work being distributed under this License.
    
   `Derived Work'
    Any work that under any applicable law is derived from the Work.

   `Modification' 
    Any procedure that produces a Derived Work under any applicable
    law -- for example, the production of a file containing an
    original file associated with the Work or a significant portion of
    such a file, either verbatim or with modifications and/or
    translated into another language.

   `Modify'
    To apply any procedure that produces a Derived Work under any
    applicable law.
    
   `Distribution'
    Making copies of the Work available from one person to another, in
    whole or in part.  Distribution includes (but is not limited to)
    making any electronic components of the Work accessible by
    file transfer protocols such as FTP or HTTP or by shared file
    systems such as Sun's Network File System (NFS).

   `Compiled Work'
    A version of the Work that has been processed into a form where it
    is directly usable on a computer system.  This processing may
    include using installation facilities provided by the Work,
    transformations of the Work, copying of components of the Work, or
    other activities.  Note that modification of any installation
    facilities provided by the Work constitutes modification of the Work.

   `Current Maintainer'
    A person or persons nominated as such within the Work.  If there is
    no such explicit nomination then it is the `Copyright Holder' under
    any applicable law.

   `Base Interpreter' 
    A program or process that is normally needed for running or
    interpreting a part or the whole of the Work.    

    A Base Interpreter may depend on external components but these
    are not considered part of the Base Interpreter provided that each
    external component clearly identifies itself whenever it is used
    interactively.  Unless explicitly specified when applying the
    license to the Work, the only applicable Base Interpreter is a
    `LaTeX-Format' or in the case of files belonging to the 
    `LaTeX-format' a program implementing the `TeX language'.



CONDITIONS ON DISTRIBUTION AND MODIFICATION
===========================================

1.  Activities other than distribution and/or modification of the Work
are not covered by this license; they are outside its scope.  In
particular, the act of running the Work is not restricted and no
requirements are made concerning any offers of support for the Work.

2.  You may distribute a complete, unmodified copy of the Work as you
received it.  Distribution of only part of the Work is considered
modification of the Work, and no right to distribute such a Derived
Work may be assumed under the terms of this clause.

3.  You may distribute a Compiled Work that has been generated from a
complete, unmodified copy of the Work as distributed under Clause 2
above, as long as that Compiled Work is distributed in such a way that
the recipients may install the Compiled Work on their system exactly
as it would have been installed if they generated a Compiled Work
directly from the Work.

4.  If you are the Current Maintainer of the Work, you may, without
restriction, modify the Work, thus creating a Derived Work.  You may
also distribute the Derived Work without restriction, including
Compiled Works generated from the Derived Work.  Derived Works
distributed in this manner by the Current Maintainer are considered to
be updated versions of the Work.

5.  If you are not the Current Maintainer of the Work, you may modify
your copy of the Work, thus creating a Derived Work based on the Work,
and compile this Derived Work, thus creating a Compiled Work based on
the Derived Work.

6.  If you are not the Current Maintainer of the Work, you may
distribute a Derived Work provided the following conditions are met
for every component of the Work unless that component clearly states
in the copyright notice that it is exempt from that condition.  Only
the Current Maintainer is allowed to add such statements of exemption 
to a component of the Work. 

  a. If a component of this Derived Work can be a direct replacement
     for a component of the Work when that component is used with the
     Base Interpreter, then, wherever this component of the Work
     identifies itself to the user when used interactively with that
     Base Interpreter, the replacement component of this Derived Work
     clearly and unambiguously identifies itself as a modified version
     of this component to the user when used interactively with that
     Base Interpreter.
     
  b. Every component of the Derived Work contains prominent notices
     detailing the nature of the changes to that component, or a
     prominent reference to another file that is distributed as part
     of the Derived Work and that contains a complete and accurate log
     of the changes.
  
  c. No information in the Derived Work implies that any persons,
     including (but not limited to) the authors of the original version
     of the Work, provide any support, including (but not limited to)
     the reporting and handling of errors, to recipients of the
     Derived Work unless those persons have stated explicitly that
     they do provide such support for the Derived Work.

  d. You distribute at least one of the following with the Derived Work:

       1. A complete, unmodified copy of the Work; 
          if your distribution of a modified component is made by
          offering access to copy the modified component from a
          designated place, then offering equivalent access to copy
          the Work from the same or some similar place meets this
          condition, even though third parties are not compelled to
          copy the Work along with the modified component;

       2. Information that is sufficient to obtain a complete,
          unmodified copy of the Work.

7.  If you are not the Current Maintainer of the Work, you may
distribute a Compiled Work generated from a Derived Work, as long as
the Derived Work is distributed to all recipients of the Compiled
Work, and as long as the conditions of Clause 6, above, are met with
regard to the Derived Work.

8.  The conditions above are not intended to prohibit, and hence do not
apply to, the modification, by any method, of any component so that it
becomes identical to an updated version of that component of the Work as
it is distributed by the Current Maintainer under Clause 4, above.

9.  Distribution of the Work or any Derived Work in an alternative
format, where the Work or that Derived Work (in whole or in part) is
then produced by applying some process to that format, does not relax or
nullify any sections of this license as they pertain to the results of
applying that process.
     
10. a. A Derived Work may be distributed under a different license
       provided that license itself honors the conditions listed in
       Clause 6 above, in regard to the Work, though it does not have
       to honor the rest of the conditions in this license.
      
    b. If a Derived Work is distributed under a different license, that
       Derived Work must provide sufficient documentation as part of
       itself to allow each recipient of that Derived Work to honor the 
       restrictions in Clause 6 above, concerning changes from the Work.

11. This license places no restrictions on works that are unrelated to
the Work, nor does this license place any restrictions on aggregating
such works with the Work by any means.

12.  Nothing in this license is intended to, or may be used to, prevent
complete compliance by all parties with all applicable laws.


NO WARRANTY
===========

There is no warranty for the Work.  Except when otherwise stated in
writing, the Copyright Holder provides the Work `as is', without
warranty of any kind, either expressed or implied, including, but not
limited to, the implied warranties of merchantability and fitness for a
particular purpose.  The entire risk as to the quality and performance
of the Work is with you.  Should the Work prove defective, you assume
the cost of all necessary servicing, repair, or correction.

In no event unless required by applicable law or agreed to in writing
will The Copyright Holder, or any author named in the components of the
Work, or any other party who may distribute and/or modify the Work as
permitted above, be liable to you for damages, including any general,
special, incidental or consequential damages arising out of any use of
the Work or out of inability to use the Work (including, but not limited
to, loss of data, data being rendered inaccurate, or losses sustained by
anyone as a result of any failure of the Work to operate with any other
programs), even if the Copyright Holder or said author or said other
party has been advised of the possibility of such damages.


MAINTENANCE OF THE WORK
=======================

The Work has the status `author-maintained' if the Copyright Holder
explicitly and prominently states near the primary copyright notice in
the Work that the Work can only be maintained by the Copyright Holder
or simply that it is `author-maintained'.

The Work has the status `maintained' if there is a Current Maintainer
who has indicated in the Work that they are willing to receive error
reports for the Work (for example, by supplying a valid e-mail
address). It is not required for the Current Maintainer to acknowledge
or act upon these error reports.

The Work changes from status `maintained' to `unmaintained' if there
is no Current Maintainer, or the person stated to be Current
Maintainer of the work cannot be reached through the indicated means
of communication for a period of six months, and there are no other
significant signs of active maintenance.

You can become the Current Maintainer of the Work by agreement with
any existing Current Maintainer to take over this role.

If the Work is unmaintained, you can become the Current Maintainer of
the Work through the following steps:

 1.  Make a reasonable attempt to trace the Current Maintainer (and
     the Copyright Holder, if the two differ) through the means of
     an Internet or similar search.

 2.  If this search is successful, then enquire whether the Work
     is still maintained.

  a. If it is being maintained, then ask the Current Maintainer
     to update their communication data within one month.
     
  b. If the search is unsuccessful or no action to resume active
     maintenance is taken by the Current Maintainer, then announce
     within the pertinent community your intention to take over
     maintenance.  (If the Work is a LaTeX work, this could be
     done, for example, by posting to comp.text.tex.)

 3a. If the Current Maintainer is reachable and agrees to pass
     maintenance of the Work to you, then this takes effect
     immediately upon announcement.
     
  b. If the Current Maintainer is not reachable and the Copyright
     Holder agrees that maintenance of the Work be passed to you,
     then this takes effect immediately upon announcement.  
    
 4.  If you make an `intention announcement' as described in 2b. above
     and after three months your intention is challenged neither by
     the Current Maintainer nor by the Copyright Holder nor by other
     people, then you may arrange for the Work to be changed so as
     to name you as the (new) Current Maintainer.
     
 5.  If the previously unreachable Current Maintainer becomes
     reachable once more within three months of a change completed
     under the terms of 3b) or 4), then that Current Maintainer must
     become or remain the Current Maintainer upon request provided
     they then update their communication data within one month.

A change in the Current Maintainer does not, of itself, alter the fact
that the Work is distributed under the LPPL license.

If you become the Current Maintainer of the Work, you should
immediately provide, within the Work, a prominent and unambiguous
statement of your status as Current Maintainer.  You should also
announce your new status to the same pertinent community as
in 2b) above.


WHETHER AND HOW TO DISTRIBUTE WORKS UNDER THIS LICENSE
======================================================

This section contains important instructions, examples, and
recommendations for authors who are considering distributing their
works under this license.  These authors are addressed as `you' in
this section.

Choosing This License or Another License
----------------------------------------

If for any part of your work you want or need to use *distribution*
conditions that differ significantly from those in this license, then
do not refer to this license anywhere in your work but, instead,
distribute your work under a different license.  You may use the text
of this license as a model for your own license, but your license
should not refer to the LPPL or otherwise give the impression that
your work is distributed under the LPPL.

The document `modguide.tex' in the base LaTeX distribution explains
the motivation behind the conditions of this license.  It explains,
for example, why distributing LaTeX under the GNU General Public
License (GPL) was considered inappropriate.  Even if your work is
unrelated to LaTeX, the discussion in `modguide.tex' may still be
relevant, and authors intending to distribute their works under any
license are encouraged to read it.

A Recommendation on Modification Without Distribution
-----------------------------------------------------

It is wise never to modify a component of the Work, even for your own
personal use, without also meeting the above conditions for
distributing the modified component.  While you might intend that such
modifications will never be distributed, often this will happen by
accident -- you may forget that you have modified that component; or
it may not occur to you when allowing others to access the modified
version that you are thus distributing it and violating the conditions
of this license in ways that could have legal implications and, worse,
cause problems for the community.  It is therefore usually in your
best interest to keep your copy of the Work identical with the public
one.  Many works provide ways to control the behavior of that work
without altering any of its licensed components.

How to Use This License
-----------------------

To use this license, place in each of the components of your work both
an explicit copyright notice including your name and the year the work
was authored and/or last substantially modified.  Include also a
statement that the distribution and/or modification of that
component is constrained by the conditions in this license.

Here is an example of such a notice and statement:

  %% pig.dtx
  %% Copyright 2008 M. Y. Name
  %
  % This work may be distributed and/or modified under the
  % conditions of the LaTeX Project Public License, either version 1.3
  % of this license or (at your option) any later version.
  % The latest version of this license is in
  %   https://www.latex-project.org/lppl.txt
  % and version 1.3c or later is part of all distributions of LaTeX
  % version 2008 or later.
  %
  % This work has the LPPL maintenance status `maintained'.
  % 
  % The Current Maintainer of this work is M. Y. Name.
  %
  % This work consists of the files pig.dtx and pig.ins
  % and the derived file pig.sty.

Given such a notice and statement in a file, the conditions
given in this license document would apply, with the `Work' referring
to the three files `pig.dtx', `pig.ins', and `pig.sty' (the last being
generated from `pig.dtx' using `pig.ins'), the `Base Interpreter'
referring to any `LaTeX-Format', and both `Copyright Holder' and
`Current Maintainer' referring to the person `M. Y. Name'.

If you do not want the Maintenance section of LPPL to apply to your
Work, change `maintained' above into `author-maintained'.  
However, we recommend that you use `maintained', as the Maintenance
section was added in order to ensure that your Work remains useful to
the community even when you can no longer maintain and support it
yourself.

Derived Works That Are Not Replacements
---------------------------------------

Several clauses of the LPPL specify means to provide reliability and
stability for the user community. They therefore concern themselves
with the case that a Derived Work is intended to be used as a
(compatible or incompatible) replacement of the original Work. If
this is not the case (e.g., if a few lines of code are reused for a
completely different task), then clauses 6b and 6d shall not apply.


Important Recommendations
-------------------------

 Defining What Constitutes the Work

   The LPPL requires that distributions of the Work contain all the
   files of the Work.  It is therefore important that you provide a
   way for the licensee to determine which files constitute the Work.
   This could, for example, be achieved by explicitly listing all the
   files of the Work near the copyright notice of each file or by
   using a line such as:

    % This work consists of all files listed in manifest.txt.
   
   in that place.  In the absence of an unequivocal list it might be
   impossible for the licensee to determine what is considered by you
   to comprise the Work and, in such a case, the licensee would be
   entitled to make reasonable conjectures as to which files comprise
   the Work.

43 KB — too long to show here. It arrives with the project.

%==============================================================================
% bibliografia.bib -- base de exemplo da classe texufpel
%
% Mostra como cadastrar os tipos de documento mais citados em trabalhos de
% Computação, usando clássicos da área. Cada entrada traz, acima, um
% comentário dizendo quando usar aquele tipo. O estilo abnt.bst formata as
% referências conforme o Manual de normas UFPel para trabalhos acadêmicos
% (2023); as páginas citadas nos comentários são as do Manual.
%
% Convenções
% - Chaves de citação: Sobrenome:Ano:Sigla (sigla = iniciais do título).
% - Autores: "Sobrenome, Prenomes". Partículas no fim dos prenomes ficam em
%   minúsculas ("Cruz, Tamara Meneghetti da") e não são abreviadas.
% - Entidades (pessoa jurídica) entre chaves duplas e com iniciais
%   maiúsculas: author = {{Associação Brasileira de Normas Técnicas}}. A lista
%   de referências põe o nome em maiúsculas; a citação no texto o mantém como
%   está escrito (Manual, p. 27 e 62).
% - Acentos podem ser digitados em UTF-8. O BibTeX, porém, ordena por bytes:
%   "Ávila" iria para depois do Z, e "Associação" para depois de
%   "Association". Quando o acento afetar a ordem, escreva a letra como
%   comando, como na entrada ABNT:2018:NBR6023:
%       author = {{\'A}vila, Maria}
% - Meses: as macros jan, feb, ..., dec geram as abreviaturas em inglês do
%   Anexo A do Manual (p. 79). Para publicação em português, escreva o mês
%   como texto: month = {abr.}. O mês segue o idioma da publicação (p. 33).
% - Edição: só a partir da 2ª (p. 18). Número ("4") vira "4. ed."; texto no
%   idioma do documento é transcrito ("2nd" -> "2nd ed.", p. 28-29).
% - Documentos online: url e urldate (data de acesso, já no formato
%   "8 nov. 2026"). DOI sem o prefixo https://doi.org/ (o estilo acrescenta).
% - Campos extras deste estilo:
%     titleaddon  responsabilidade após o título (Orientador, Tradução etc.)
%     editortype  tipo de participação do editor: org., coord., comp., ed.
%     eventtitle, eventnumber, eventyear, venue   dados de eventos
% - "% VERIFICAR": dado que não foi possível confirmar na fonte e por isso
%   ficou de fora da entrada.
%
% Dados conferidos em novembro de 2026 nas fontes indicadas em cada entrada.
%==============================================================================


%------------------------------------------------------------------------------
% Tipo article -- artigo de periódico (revista científica). Título do periódico em
% negrito; local, volume, número, páginas e data (Manual, p. 46-47). Sem local
% conhecido, o estilo escreve [s. l.].
%------------------------------------------------------------------------------

% Fonte: DOI 10.1112/plms/s2-42.1.230. Escrito e apresentado em 1936, mas o
% registro do periódico data a publicação de 1937 (s2-42, 1936-1937).
@article{Turing:1937:OCN,
  author  = {Turing, Alan Mathison},
  title   = {On computable numbers, with an application to the {Entscheidungsproblem}},
  journal = {Proceedings of the London Mathematical Society},
  volume  = {s2-42},
  number  = {1},
  pages   = {230--265},
  year    = {1937},
  doi     = {10.1112/plms/s2-42.1.230}
}

% Fonte: Oxford Academic, Mind, v. LIX, n. 236, out. 1950.
@article{Turing:1950:CMI,
  author  = {Turing, Alan Mathison},
  title   = {Computing machinery and intelligence},
  journal = {Mind},
  volume  = {59},
  number  = {236},
  pages   = {433--460},
  month   = oct,
  year    = {1950},
  doi     = {10.1093/mind/LIX.236.433}
}

% Fonte: Bell System Technical Journal, parte 1 (julho de 1948). A parte 2
% saiu no v. 27, n. 4, p. 623-656, em outubro de 1948.
@article{Shannon:1948:MTC,
  author  = {Shannon, Claude Elwood},
  title   = {A mathematical theory of communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  number  = {3},
  pages   = {379--423},
  month   = jul,
  year    = {1948},
  doi     = {10.1002/j.1538-7305.1948.tb01338.x}
}

% Fonte: Springer, Numerische Mathematik, v. 1, dez. 1959.
@article{Dijkstra:1959:NTP,
  author  = {Dijkstra, Edsger Wybe},
  title   = {A note on two problems in connexion with graphs},
  journal = {Numerische Mathematik},
  volume  = {1},
  pages   = {269--271},
  month   = dec,
  year    = {1959},
  doi     = {10.1007/BF01386390}
}

% Carta ao editor (seção de um periódico, Manual, p. 46). O título publicado
% inclui o nome da seção. Fonte: DOI 10.1145/362929.362947.
@article{Dijkstra:1968:GTS,
  author  = {Dijkstra, Edsger Wybe},
  title   = {Letters to the editor: go to statement considered harmful},
  journal = {Communications of the ACM},
  volume  = {11},
  number  = {3},
  pages   = {147--148},
  year    = {1968},
  doi     = {10.1145/362929.362947}
}

% Artigo em páginas não contínuas. Fonte: Communications of the ACM, v. 12,
% n. 10, out. 1969; DOI 10.1145/363235.363259.
@article{Hoare:1969:ABC,
  author  = {Hoare, Charles Antony Richard},
  title   = {An axiomatic basis for computer programming},
  journal = {Communications of the ACM},
  volume  = {12},
  number  = {10},
  pages   = {576--580, 583},
  month   = oct,
  year    = {1969},
  doi     = {10.1145/363235.363259}
}

% Fonte: Communications of the ACM, v. 13, n. 6, jun. 1970.
@article{Codd:1970:RMD,
  author  = {Codd, Edgar Frank},
  title   = {A relational model of data for large shared data banks},
  journal = {Communications of the ACM},
  volume  = {13},
  number  = {6},
  pages   = {377--387},
  month   = jun,
  year    = {1970},
  doi     = {10.1145/362384.362685}
}

% Fonte: Microsoft Research (página do autor) e DOI 10.1145/359545.359563.
@article{Lamport:1978:TCO,
  author  = {Lamport, Leslie},
  title   = {Time, clocks, and the ordering of events in a distributed system},
  journal = {Communications of the ACM},
  volume  = {21},
  number  = {7},
  pages   = {558--565},
  month   = jul,
  year    = {1978},
  doi     = {10.1145/359545.359563}
}

% Fonte: RePEc/IDEAS (registro do periódico), Management Science, v. 6,
% n. 1, out. 1959. O registro traz só as iniciais dos prenomes.
@article{Dantzig:1959:TDP,
  author  = {Dantzig, G. B. and Ramser, J. H.},
  title   = {The truck dispatching problem},
  journal = {Management Science},
  volume  = {6},
  number  = {1},
  pages   = {80--91},
  month   = oct,
  year    = {1959},
  doi     = {10.1287/mnsc.6.1.80}
}

% Fonte: RePEc/IDEAS (registro do periódico), Operations Research, v. 35,
% n. 2, abr. 1987.
@article{Solomon:1987:AVR,
  author  = {Solomon, Marius M.},
  title   = {Algorithms for the vehicle routing and scheduling problems with time window constraints},
  journal = {Operations Research},
  volume  = {35},
  number  = {2},
  pages   = {254--265},
  month   = apr,
  year    = {1987},
  doi     = {10.1287/opre.35.2.254}
}


%------------------------------------------------------------------------------
% Tipo mastersthesis -- dissertação de mestrado e trabalho de conclusão de curso
% (TCC). O campo type traz o tipo, o grau e o curso; school traz a unidade e
% a universidade; year é o ano de depósito e de defesa (Manual, p. 41-44).
% Orientador e coorientador vão em titleaddon.
%------------------------------------------------------------------------------

% TCC da UFPel. Dados do exemplo de elementos complementares do Manual
% (p. 42).
@mastersthesis{Cruz:2015:FCS,
  author     = {Cruz, Tamara Meneghetti da},
  title      = {Uma ferramenta computacional para a simulação da dispersão de poluentes na atmosfera},
  titleaddon = {Orientadora: Daniela Buske. Coorientador: Marilton Sanchotene de Aguiar},
  year       = {2015},
  pages      = {65},
  type       = {Trabalho de Conclusão de Curso (Bacharelado em Engenharia de Computação)},
  school     = {Centro de Desenvolvimento Tecnológico, Universidade Federal de Pelotas},
  address    = {Pelotas}
}

% Trabalho estrangeiro: o tipo é transcrito no idioma do documento.
% Fonte: DSpace do MIT (handle 1721.1/11173): "Thesis (M.S.)--Massachusetts
% Institute of Technology, Dept. of Electrical Engineering, 1940". Escrita em
% 1937; o registro do MIT data o trabalho de 1940.
% VERIFICAR: número de folhas (o registro não informa).
@mastersthesis{Shannon:1940:SAR,
  author     = {Shannon, Claude Elwood},
  title      = {A symbolic analysis of relay and switching circuits},
  titleaddon = {Orientador: Frank L. Hitchcock},
  year       = {1940},
  type       = {Thesis (M.S.)},
  school     = {Department of Electrical Engineering, Massachusetts Institute of Technology},
  address    = {Cambridge, MA},
  url        = {https://dspace.mit.edu/handle/1721.1/11173},
  urldate    = {8 nov. 2026}
}


%------------------------------------------------------------------------------
% Tipo phdthesis -- tese de doutorado. Mesmos campos da dissertação.
%------------------------------------------------------------------------------

% Fonte: Wikipedia, "Systems of Logic Based on Ordinals" (tese de doutorado
% em Princeton, 1938, orientada por Alonzo Church).
% VERIFICAR: número de folhas.
@phdthesis{Turing:1938:SLO,
  author     = {Turing, Alan Mathison},
  title      = {Systems of logic based on ordinals},
  titleaddon = {Orientador: Alonzo Church},
  year       = {1938},
  type       = {Thesis (Ph.D.)},
  school     = {Princeton University},
  address    = {Princeton}
}


%------------------------------------------------------------------------------
% Tipo techreport -- relatório técnico, nota técnica, RFC. A instituição faz o
% papel de editora; type e number identificam a série do relatório.
%------------------------------------------------------------------------------

% Fonte: Internet Archive (cópia da Smithsonian Libraries): Philadelphia,
% Moore School of Electrical Engineering, University of Pennsylvania, 1945.
% VERIFICAR: número do contrato (W-670-ORD-4926) e número de páginas; as
% fontes consultadas não confirmam esses dados.
@techreport{vonNeumann:1945:FDR,
  author      = {von Neumann, John},
  title       = {First draft of a report on the {EDVAC}},
  institution = {Moore School of Electrical Engineering, University of Pennsylvania},
  address     = {Philadelphia},
  year        = {1945}
}

% RFC: relatório técnico da série Request for Comments. O número vai junto
% com o nome da série, em type.
% Fonte: RFC Editor (info/rfc791): J. Postel, set. 1981, DOI 10.17487/RFC791.
@techreport{Postel:1981:IP,
  author      = {Postel, Jon},
  title       = {Internet protocol},
  institution = {RFC Editor},
  type        = {Request for Comments 791},
  year        = {1981},
  doi         = {10.17487/RFC791},
  url         = {https://www.rfc-editor.org/info/rfc791},
  urldate     = {8 nov. 2026}
}


%------------------------------------------------------------------------------
% Tipo book -- livro (monografia no todo): autor, título, edição, local, editora,
% ano (Manual, p. 41-43). Elementos complementares: páginas (pages),
% série e volume (series, volume).
%------------------------------------------------------------------------------

% Obra póstuma editada e completada por outra pessoa: a entrada é pelo autor e
% a responsabilidade do editor vai em titleaddon (Manual, p. 26).
% Fonte: catálogo TUAT: Urbana, University of Illinois Press, 1966, xix, 388 p.
@book{vonNeumann:1966:TSR,
  author     = {von Neumann, John},
  title      = {Theory of self-reproducing automata},
  titleaddon = {Edited and completed by Arthur W. Burks},
  address    = {Urbana},
  publisher  = {University of Illinois Press},
  year       = {1966},
  pages      = {xix, 388}
}

% Obra em vários volumes, citando um deles, com edição (Manual, p. 35-36).
% Fonte: página do autor (Stanford): Reading, Massachusetts, Addison-Wesley,
% 1997, xx+650 p.
@book{Knuth:1997:ACP,
  author    = {Knuth, Donald Ervin},
  title     = {The art of computer programming: fundamental algorithms},
  volume    = {1},
  edition   = {3},
  address   = {Reading, MA},
  publisher = {Addison-Wesley},
  year      = {1997},
  pages     = {xx, 650}
}

% Quatro ou mais autores: a lista mostra o primeiro seguido de et al.
% (Manual, p. 25). Fonte: Wikipedia, "Introduction to Algorithms" (4. ed.,
% MIT Press, 2022, 1312 p.). Local da MIT Press: Cambridge, MA (página de
% rosto de outras obras da editora).
@book{Cormen:2022:IA,
  author    = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
  title     = {Introduction to algorithms},
  edition   = {4},
  address   = {Cambridge, MA},
  publisher = {MIT Press},
  year      = {2022},
  pages     = {1312}
}

% Livro com subtítulo (só o título fica em negrito, Manual, p. 28).
% Fonte: catálogo NIFS: Reading, Mass., Addison-Wesley, c1975, xi, 195 p.
@book{Brooks:1975:MMM,
  author    = {Brooks, Frederick Phillips},
  title     = {The mythical man-month: essays on software engineering},
  address   = {Reading, MA},
  publisher = {Addison-Wesley},
  year      = {1975},
  pages     = {xi, 195}
}

% Dois autores e um colaborador indicado após o título (Manual, p. 26).
% Fonte: página de rosto da 2. ed.: The MIT Press, Cambridge, Massachusetts,
% 1996, "with Julie Sussman".
@book{Abelson:1996:SIC,
  author     = {Abelson, Harold and Sussman, Gerald Jay},
  title      = {Structure and interpretation of computer programs},
  titleaddon = {With Julie Sussman},
  edition    = {2},
  address    = {Cambridge, MA},
  publisher  = {MIT Press},
  year       = {1996}
}

% Livro de uma série numerada (Manual, p. 37-38).
% Fonte: CiNii: Philadelphia, SIAM, 1979, xi, 190 p. (SIAM studies in applied
% mathematics, 2).
@book{Moore:1979:MAI,
  author    = {Moore, Ramon E.},
  title     = {Methods and applications of interval analysis},
  address   = {Philadelphia},
  publisher = {Society for Industrial and Applied Mathematics},
  year      = {1979},
  pages     = {xi, 190},
  series    = {SIAM Studies in Applied Mathematics},
  volume    = {2}
}


%------------------------------------------------------------------------------
% Tipo inbook -- parte (capítulo) de livro do mesmo autor. Se chapter traz o título
% da parte, o estilo gera "Parte. In: AUTOR. Livro" (Manual, p. 44-45); se traz
% só um número, gera "cap. N".
%------------------------------------------------------------------------------

% Fonte: InformIT (sumário: Chapter 2, Information Structures).
% VERIFICAR: páginas inicial e final do capítulo.
@inbook{Knuth:1997:IS,
  author    = {Knuth, Donald Ervin},
  chapter   = {Information structures},
  title     = {The art of computer programming: fundamental algorithms},
  volume    = {1},
  edition   = {3},
  address   = {Reading, MA},
  publisher = {Addison-Wesley},
  year      = {1997}
}


%------------------------------------------------------------------------------
% Tipo incollection -- capítulo de livro organizado por outra pessoa: "In:
% ORGANIZADOR (org.). Título do livro" (Manual, p. 44-45). Use editortype
% para org., coord., comp.; o padrão é ed.
%------------------------------------------------------------------------------

% Duas editoras em locais diferentes, separadas por ponto e vírgula
% (Manual, p. 30). Fonte: Wellcome Collection: Cerebral mechanisms in
% behavior: the Hixon Symposium, ed. Lloyd A. Jeffress, New York: John Wiley;
% London: Chapman & Hall, 1951.
% VERIFICAR: páginas do capítulo no livro.
@incollection{vonNeumann:1951:GLT,
  author     = {von Neumann, John},
  title      = {The general and logical theory of automata},
  editor     = {Jeffress, Lloyd A.},
  editortype = {ed.},
  booktitle  = {Cerebral mechanisms in behavior: the {Hixon} Symposium},
  address    = {New York},
  publisher  = {John Wiley; London: Chapman \& Hall},
  year       = {1951}
}


%------------------------------------------------------------------------------
% Tipo inproceedings -- trabalho publicado em anais de evento (Manual, p. 50-51):
% "In: NOME DO EVENTO, número., ano, local. Anais [...]. Local: Editora, ano."
% Use eventtitle, eventnumber e venue (cidade do evento); type traz Anais
% (padrão), Anais eletrônicos, Proceedings etc.; address e publisher são os
% dados da publicação.
%------------------------------------------------------------------------------

% Fonte: Wikipedia, "Cook-Levin theorem" (Proceedings of the Third Annual
% ACM Symposium on Theory of Computing, p. 151-158, DOI) e bibtex.github.io
% (STOC 1971, Shaker Heights, Ohio).
@inproceedings{Cook:1971:CTP,
  author      = {Cook, Stephen A.},
  title       = {The complexity of theorem-proving procedures},
  eventtitle  = {Annual ACM Symposium on Theory of Computing},
  eventnumber = {3},
  venue       = {Shaker Heights},
  type        = {Proceedings},
  address     = {New York},
  publisher   = {ACM},
  year        = {1971},
  pages       = {151--158},
  doi         = {10.1145/800157.805047}
}


%------------------------------------------------------------------------------
% Tipo proceedings -- anais do evento no todo (Manual, p. 48-49). Mesmos campos
% de evento, sem autor.
%------------------------------------------------------------------------------

@proceedings{ACM:1971:STOC,
  eventtitle  = {Annual ACM Symposium on Theory of Computing},
  eventnumber = {3},
  venue       = {Shaker Heights},
  type        = {Proceedings},
  address     = {New York},
  publisher   = {ACM},
  year        = {1971}
}


%------------------------------------------------------------------------------
% Tipo manual -- normas técnicas, manuais, guias e documentos de entidades
% (pessoa jurídica como autor, Manual, p. 27).
%------------------------------------------------------------------------------

% Os acentos de "Associação" estão escritos como comandos para que a entrada
% seja ordenada antes de "Association" (o BibTeX ordena por bytes).
% Fonte: referências do Manual UFPel (p. 111).
@manual{ABNT:2018:NBR6023,
  author    = {{Associa{\c{c}}{\~a}o Brasileira de Normas T{\'e}cnicas}},
  title     = {{ABNT NBR} 6023: informação e documentação: referências: elaboração},
  edition   = {2},
  address   = {Rio de Janeiro},
  publisher = {ABNT},
  year      = {2018},
  pages     = {74}
}


%------------------------------------------------------------------------------
% Tipo booklet -- folheto ou documento curto sem editora comercial. O abnt.bst o
% formata como misc. Sem local conhecido, o estilo escreve [S. l.].
%------------------------------------------------------------------------------

% Oito organizadores: a lista mostra o primeiro seguido de et al.
% Fonte: seção "Como citar" do próprio documento (SBC, 2017, 153 p.,
% ISBN 978-85-7669-424-3).
% VERIFICAR: local de publicação (o documento não informa).
@booklet{Zorzo:2017:RFC,
  author    = {Zorzo, Avelino Francisco and Nunes, Daltro and Matos, Ecivaldo and Steinmacher, Igor and Leite, Jair and Araujo, Renata Mendes and Correia, Ronaldo and Martins, Simone},
  title     = {Referenciais de formação para os cursos de graduação em computação},
  publisher = {Sociedade Brasileira de Computação},
  year      = {2017},
  pages     = {153}
}


%------------------------------------------------------------------------------
% Tipo unpublished -- documento não publicado formalmente (manuscrito, nota
% interna). O abnt.bst o formata como misc; descreva o documento em
% howpublished.
%------------------------------------------------------------------------------

% Fonte: E. W. Dijkstra Archive (UT Austin), EWD 1036, Austin, 2 dez. 1988.
@unpublished{Dijkstra:1988:CRT,
  author       = {Dijkstra, Edsger Wybe},
  title        = {On the cruelty of really teaching computing science},
  year         = {1988},
  howpublished = {Manuscrito (EWD 1036)},
  url          = {https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1036.html},
  urldate      = {8 nov. 2026}
}


%------------------------------------------------------------------------------
% Tipo misc -- tudo o que não se encaixa nos tipos acima. O abnt.bst não define
% os tipos online, software, dataset nem tipos para legislação: use o tipo misc com
% howpublished para a descrição física ("Programa de computador",
% "Conjunto de dados", "Preprint"). Online, inclua url e urldate (Manual,
% p. 39 e 61).
%------------------------------------------------------------------------------

% Preprint do arXiv (8 autores: et al. na lista). Fonte: arXiv:1706.03762
% (v1 de 12 jun. 2017).
@misc{Vaswani:2017:AIA,
  author       = {Vaswani, Ashish and Shazeer, Noam and Parmar, Niki and Uszkoreit, Jakob and Jones, Llion and Gomez, Aidan N. and Kaiser, Lukasz and Polosukhin, Illia},
  title        = {Attention is all you need},
  year         = {2017},
  howpublished = {Preprint arXiv:1706.03762},
  doi          = {10.48550/arXiv.1706.03762},
  url          = {https://arxiv.org/abs/1706.03762},
  urldate      = {8 nov. 2026}
}

% Página da web de uma entidade. Página sem data: ano entre colchetes
% (Manual, p. 32), protegido por chaves duplas. Fonte: awards.acm.org/turing.
@misc{ACM:2026:TA,
  author       = {{Association for Computing Machinery}},
  title        = {About {ACM A.M. Turing Award}},
  year         = {{[2026]}},
  url          = {https://awards.acm.org/turing},
  urldate      = {8 nov. 2026}
}

% Programa de computador ou repositório de código (Manual, p. 61).
@misc{Aguiar:2026:TEX,
  author       = {Aguiar, Marilton Sanchotene de},
  title        = {texufpel: formatação de documentos {LaTeX} da {UFPel}},
  year         = {2026},
  howpublished = {Classe LaTeX},
  url          = {https://github.com/notcc/texufpel},
  urldate      = {8 nov. 2026}
}

% Legislação (Manual, p. 53-55): jurisdição em maiúsculas como autor,
% epígrafe e ementa no título. Dados do exemplo do Manual (p. 54).
@misc{Brasil:2015:LBI,
  author       = {{Brasil}},
  title        = {Lei nº 13.146, de 6 de julho de 2015. Institui a Lei brasileira de inclusão da pessoa com deficiência (Estatuto da pessoa com deficiência)},
  address      = {Brasília},
  publisher    = {Presidência da República},
  year         = {2015},
  url          = {http://www.planalto.gov.br/ccivil_03/_Ato2015-2018/2015/Lei/L13146.htm},
  urldate      = {30 ago. 2023}
}

% Conjunto de dados. Fonte: UCI Machine Learning Repository (citação
% sugerida: Fisher, R. (1936). Iris [Dataset]; DOI 10.24432/C56C76).
@misc{Fisher:1936:IRI,
  author       = {Fisher, R. A.},
  title        = {Iris},
  publisher    = {UCI Machine Learning Repository},
  year         = {1936},
  howpublished = {Conjunto de dados},
  doi          = {10.24432/C56C76}
}

%==============================================================================
% Exemplo de Proposta de Dissertação com a classe texufpel
%
% A proposta tem o mesmo tema do exemplo de dissertação
% (dissertação/exemplo-diss.tex): é o projeto que, depois de executado,
% resultaria naquele trabalho. Troque os dados do preâmbulo (os comentários
% "ALTERE" indicam o que mudar) e o texto dos capítulos.
%
% Compilação (a partir da pasta raiz do repositório):
%   pdflatex dissertação/exemplo-diss-proposta
%   bibtex   exemplo-diss-proposta
%   pdflatex dissertação/exemplo-diss-proposta
%   pdflatex dissertação/exemplo-diss-proposta
%
% As páginas citadas nos comentários são as do Manual de normas UFPel para
% trabalhos acadêmicos (2023).
%==============================================================================

% Opção diss-proposta: a proposta não é depositada na biblioteca, por isso a
% classe não gera capa (a opção capa é ignorada) nem a referência do trabalho
% acima do resumo. A antiga opção nocipinfo não é mais necessária aqui: a
% classe já a aplica às propostas.
\documentclass[diss-proposta]{texufpel}

%------------------------------------------------------------------------------
% Dados institucionais. ALTERE para o seu programa.
% Unidade feminina (Faculdade, Escola): \unidade[a]{...}.
%------------------------------------------------------------------------------
\unidade{Centro de Desenvolvimento Tecnológico}
\programa{Programa de Pós-Graduação em Computação}
\curso{Ciência da Computação}

%------------------------------------------------------------------------------
% Dados do trabalho. ALTERE.
% Os nomes abaixo são de grandes nomes da Computação e servem só de exemplo.
% Substitua pelos nomes da sua orientação.
%------------------------------------------------------------------------------
\title{Roteamento da coleta seletiva em grafos dirigidos: um estudo de caso em Pelotas}

\author{Lovelace}{Ada}                          % ALTERE: autor(a)
\advisor[Prof.ª~Dr.ª]{Liskov}{Barbara}          % ALTERE: orientador(a)
\coadvisor[Prof.~Dr.]{Dijkstra}{Edsger W.}      % ALTERE: coorientador(a), opcional

% Palavras-chave: iniciais minúsculas (exceto nomes próprios), separadas por
% ponto e vírgula, a última terminada em ponto (Manual, p. 15).
\keyword{algoritmo de Dijkstra;}
\keyword{caminho mínimo;}
\keyword{coleta seletiva;}
\keyword{grafos dirigidos.}

\begin{document}

% Orientadora: troque o rótulo da folha de rosto.
\renewcommand{\advisorname}{Orientadora}

\maketitle   % folha de rosto (sem capa, por ser proposta)
\sloppy      % evita linhas que ultrapassam a margem direita

%------------------------------------------------------------------------------
% Resumo (no máximo uma página): problema, objetivo e contribuição esperada.
%------------------------------------------------------------------------------
\begin{abstract}
A coleta seletiva de Pelotas segue rotas definidas pela experiência das
equipes, sem apoio de ferramentas de otimização. Em bairros com muitas ruas de
mão única, a ordem em que o caminhão visita os pontos de coleta pode aumentar
a distância rodada por dia. Esta proposta de dissertação trata o problema como
um problema de caminho mínimo em grafos dirigidos, em que o sentido das ruas é
representado pela direção das arestas. A malha viária de quatro setores de
coleta será modelada dessa forma, e o algoritmo de Dijkstra calculará a menor
rota entre a garagem e a cooperativa de reciclagem, passando pelos pontos de
cada setor. O objetivo principal é verificar se as rotas calculadas são mais
curtas do que as rotas praticadas hoje e medir quanto do ganho se deve à
representação correta das ruas de mão única. A contribuição esperada é um
protótipo em Python, aplicado aos quatro setores, e uma comparação, setor a
setor, entre as rotas calculadas e as atuais.
\end{abstract}

%==============================================================================
\chapter{Motivação}
% Entre uma e duas páginas.
%==============================================================================

O problema do caminho mínimo acompanha a Computação desde o fim da década de
1950. A nota de três páginas em que \citet{Dijkstra:1959:NTP} apresentou seu
algoritmo resolve o caso de origem única com pesos não negativos, e outras
soluções da mesma época, como a de Bellman, tratam pesos negativos
\citep{Cormen:2022:IA}. Hoje esses algoritmos estão em sistemas de navegação,
no roteamento de redes de computadores e em boa parte dos problemas de
logística \citep{Knuth:1997:ACP,Cormen:2022:IA}.

A coleta seletiva é um desses problemas. O caminhão parte da garagem, passa
pelos pontos de coleta e leva o material até a cooperativa de reciclagem; cada
quilômetro a mais é combustível, tempo da equipe e desgaste do veículo. Em
Pelotas, como em muitas cidades de porte médio, as rotas são definidas pela
experiência de quem dirige. Isso funciona em traçados simples, mas tende a
gerar desvios no centro histórico, onde boa parte das ruas é de mão única.

É justamente a mão única que motiva esta dissertação. Um modelo em que as ruas
são arestas sem direção calcula rotas que o caminhão não pode seguir, e a
economia que ele promete é, em parte, ilusória. Representar a malha como um
grafo dirigido corrige isso, mas também muda o resultado esperado: é possível
que a rota mínima real seja bem mais longa do que a calculada no modelo
simplificado. Medir essa diferença é a principal contribuição acadêmica do
trabalho.

O tema também se liga a outros trabalhos da Universidade Federal de Pelotas que usam a Computação para
apoiar decisões ambientais da cidade, como o de \citet{Cruz:2015:FCS}, sobre a
simulação da dispersão de poluentes na atmosfera.

%==============================================================================
\chapter{Objetivos e Resultados}
% Entre uma e três páginas.
%==============================================================================

O objetivo geral é verificar se o algoritmo de Dijkstra, aplicado a um modelo
em grafo dirigido da malha viária, reduz a distância percorrida nas rotas de
coleta seletiva de Pelotas.

Os objetivos específicos são:

\begin{enumerate}
  \item modelar a malha viária de quatro setores de coleta como grafos
        ponderados e dirigidos, com o sentido de cada rua;
  \item implementar o algoritmo de Dijkstra e validá-lo em grafos pequenos,
        com resultado conhecido;
  \item calcular as rotas mínimas de cada setor nos modelos dirigido e não
        dirigido;
  \item comparar as rotas calculadas com as rotas praticadas pela equipe de
        coleta.
\end{enumerate}

Os resultados esperados são:

\begin{enumerate}
  \item um protótipo em Python, de código aberto, que recebe o grafo de um
        setor e devolve a rota mínima;
  \item os grafos dos quatro setores, conferidos com a equipe de coleta;
  \item uma comparação, setor a setor, entre as rotas praticadas e as
        calculadas nos dois modelos;
  \item a submissão de ao menos um artigo a evento da área.
\end{enumerate}

As listas acima usam alíneas, como pede o Manual (p. 71): o texto que as
antecede termina em dois pontos, cada alínea termina em ponto e vírgula e a
última, em ponto.

%==============================================================================
\chapter{Metodologia}
% Entre uma e três páginas.
%==============================================================================

O trabalho será desenvolvido em quatro etapas, uma para cada objetivo
específico.

Na primeira, os setores serão escolhidos com a equipe de coleta, de modo a
incluir traçados diferentes: o centro, com quarteirões regulares e muitas ruas
de mão única, e bairros com loteamentos mais recentes. Cada setor será
modelado como um grafo, com a garagem, os pontos de coleta e a cooperativa como
vértices e os trechos de rua como arestas, com a distância em quilômetros como
peso. Trechos de mão dupla terão duas arestas, uma em cada sentido; trechos de
mão única, uma só.

Na segunda etapa, o algoritmo de Dijkstra será implementado em Python, com a
fila de prioridade do módulo \texttt{heapq}, seguindo a descrição de
\citet{Cormen:2022:IA}. A implementação será validada em grafos pequenos, com
distâncias mínimas calculadas à mão.

Na terceira, o protótipo calculará a rota mínima de cada setor duas vezes: no
modelo dirigido e em uma versão do mesmo grafo que ignora o sentido das ruas.
Na quarta, as rotas calculadas serão comparadas com as rotas praticadas,
informadas pela equipe de coleta, pela distância total percorrida.

%==============================================================================
\chapter{Cronograma}
% Atividades em doze meses, incluindo seminário de andamento, entrega e
% apresentação da dissertação.
%==============================================================================

As atividades previstas são:

\begin{enumerate}
  \item revisão da literatura sobre caminho mínimo e roteamento;
  \item levantamento dos setores e das rotas praticadas, com a equipe de
        coleta;
  \item modelagem dos grafos dirigidos dos setores;
  \item implementação e validação do algoritmo de Dijkstra;
  \item cálculo das rotas nos dois modelos e comparação com as rotas
        praticadas;
  \item escrita da dissertação;
  \item seminário de andamento;
  \item submissão de artigo a evento da área;
  \item entrega da dissertação à banca;
  \item apresentação da dissertação (defesa).
\end{enumerate}

A Tabela~\ref{tab:cronograma} distribui as atividades ao longo de 2026,
identificadas pela letra da alínea.

% Cronograma em tabela: uma coluna para a atividade (a letra da alínea) e uma
% para cada mês, com os meses abreviados conforme o Anexo A do Manual (p. 79).
\begin{table}[htbp]
  \caption{Cronograma de atividades em 2026}
  \label{tab:cronograma}
  \centering
  \setlength{\tabcolsep}{4pt}
  \begin{tabular}{l*{12}{c}}
    \hline
    Atividade & jan. & fev. & mar. & abr. & maio & jun. & jul. & ago. & set. & out. & nov. & dez. \\
    \hline
    a) & X & X & X &   &   &   &   &   &   &   &   &   \\
    b) &   & X & X & X &   &   &   &   &   &   &   &   \\
    c) &   &   &   & X & X &   &   &   &   &   &   &   \\
    d) &   &   &   &   & X & X & X &   &   &   &   &   \\
    e) &   &   &   &   &   &   &   & X & X &   &   &   \\
    f) &   &   & X & X & X & X & X & X & X & X & X &   \\
    g) &   &   &   &   &   &   & X &   &   &   &   &   \\
    h) &   &   &   &   &   &   &   &   &   & X &   &   \\
    i) &   &   &   &   &   &   &   &   &   &   & X &   \\
    j) &   &   &   &   &   &   &   &   &   &   &   & X \\
    \hline
  \end{tabular}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{table}

%------------------------------------------------------------------------------
% Referências: estilo abnt.bst e base bibliografia.bib, na raiz. Só as obras
% citadas no texto entram na lista.
%------------------------------------------------------------------------------
\bibliographystyle{abnt}
\bibliography{bibliografia}

%------------------------------------------------------------------------------
% Assinaturas da proponente e da orientadora.
%------------------------------------------------------------------------------
\chapter*{Assinaturas}

\vspace{2cm}

\begin{center}
\rule{8cm}{.3mm}

Ada Lovelace\\               % ALTERE
Proponente
\end{center}

\vspace{3cm}

\begin{center}
\rule{8cm}{.3mm}

Prof.ª Dr.ª Barbara Liskov\\  % ALTERE
Orientadora
\end{center}

\end{document}

%==============================================================================
% Exemplo de Dissertação de mestrado com a classe texufpel
%
% Adaptação do exemplo de TCC (tcc/exemplo-tcc.tex) para dissertação. O texto
% de cada seção explica o recurso que aparece nela. As diferenças em relação
% ao TCC estão marcadas com "DISSERTAÇÃO" nos comentários: opção diss,
% programa de pós-graduação, orientadora, lista de símbolos e errata.
% Para começar o seu trabalho, copie este arquivo, troque os dados do
% preâmbulo (os comentários "ALTERE" indicam o que mudar) e substitua o texto
% dos capítulos.
%
% Compilação (a partir da pasta raiz do repositório, onde estão a classe, o
% estilo abnt.bst, o bibliografia.bib e a pasta imagens/):
%   pdflatex dissertação/exemplo-diss
%   bibtex   exemplo-diss
%   pdflatex dissertação/exemplo-diss
%   pdflatex dissertação/exemplo-diss
% principal.
%
% As páginas citadas nos comentários são as do Manual de normas UFPel para
% trabalhos acadêmicos (2023).
%==============================================================================

% Opções da classe:
%   diss  dissertação de mestrado (DISSERTAÇÃO; use tcc, tese, eq,
%         diss-proposta... para os outros tipos)
%   capa  gera a capa (obrigatória no trabalho depositado, Manual, p. 12)
\documentclass[diss,capa]{texufpel}

%------------------------------------------------------------------------------
% Pacotes usados neste exemplo. Nenhum é obrigatório: carregue só o que o seu
% trabalho usar. A classe já carrega graphicx, hyperref, natbib e caption.
%------------------------------------------------------------------------------
\usepackage{amsmath}        % equações alinhadas (align) e \eqref
\usepackage{algpseudocode}  % pseudocódigo (ambiente algorithmic)
\usepackage{listings}       % listagens de código-fonte
\usepackage{pdfcomment}     % \pdftooltip: dica com o significado da sigla

% Referência completa em nota de rodapé (\footcite). O Manual adota o sistema
% autor-data (p. 62); use este recurso só se o curso pedir.
\usepackage{bibentry}
\nobibliography*
\newcommand{\footcite}[1]{\footnote{\bibentry{#1}}}

% Palavras do pseudocódigo em português
\algrenewcommand\algorithmicrequire{\textbf{Entrada:}}
\algrenewcommand\algorithmicensure{\textbf{Saída:}}
\algrenewcommand\algorithmicfor{\textbf{para}}
\algrenewcommand\algorithmicforall{\textbf{para cada}}
\algrenewcommand\algorithmicdo{\textbf{faça}}
\algrenewcommand\algorithmicwhile{\textbf{enquanto}}
\algrenewcommand\algorithmicif{\textbf{se}}
\algrenewcommand\algorithmicthen{\textbf{então}}
\algrenewcommand\algorithmicend{\textbf{fim}}
\algrenewcommand\algorithmicreturn{\textbf{retorne}}

% Aparência das listagens de código: fonte monoespaçada pequena, linhas
% numeradas e acentos aceitos nos comentários.
\lstset{
  basicstyle=\ttfamily\footnotesize,
  numbers=left, numberstyle=\tiny, numbersep=6pt,
  frame=single, columns=fullflexible, keepspaces=true,
  breaklines=true, showstringspaces=false, tabsize=2,
  literate={á}{{\'a}}1 {é}{{\'e}}1 {í}{{\'i}}1 {ó}{{\'o}}1 {ú}{{\'u}}1
           {â}{{\^a}}1 {ê}{{\^e}}1 {ô}{{\^o}}1 {ã}{{\~a}}1 {õ}{{\~o}}1
           {ç}{{\c{c}}}1 {à}{{\`a}}1 {Á}{{\'A}}1 {É}{{\'E}}1 {Ç}{{\c{C}}}1
}

%------------------------------------------------------------------------------
% Dados institucionais. ALTERE para o seu programa.
% DISSERTAÇÃO: em vez de \nomecurso e \titulocurso, informe o \programa.
% \curso é a área do título: "Mestre em Ciência da Computação".
% Se a unidade for feminina (Faculdade, Escola), use \unidade[a]{...}: a
% folha de rosto passa a dizer "do Programa ... da Faculdade" (Manual, p. 85).
%------------------------------------------------------------------------------
\unidade{Centro de Desenvolvimento Tecnológico}
\programa{Programa de Pós-Graduação em Computação}
\curso{Ciência da Computação}

% Versões em inglês, usadas na referência do abstract
\unidadeeng{Technology Development Center}
\programaeng{Graduate Program in Computing}
\cursoeng{Computer Science}

%------------------------------------------------------------------------------
% Dados do trabalho. ALTERE.
% \author{Sobrenome}{Prenomes}: o sobrenome vai em maiúsculas na referência
% do trabalho, no resumo e no abstract.
% \advisor[título]{Sobrenome}{Prenomes}, e o mesmo para \coadvisor.
%
% Os nomes abaixo são de grandes nomes da Computação e servem só de exemplo.
% Substitua pelos nomes da sua orientação e da sua banca.
%------------------------------------------------------------------------------
\title{Roteamento da coleta seletiva em grafos dirigidos: um estudo de caso em Pelotas}

\author{Lovelace}{Ada}                          % ALTERE: autor(a)
\advisor[Prof.ª~Dr.ª]{Liskov}{Barbara}          % ALTERE: orientador(a)
\coadvisor[Prof.~Dr.]{Dijkstra}{Edsger W.}      % ALTERE: coorientador(a), opcional

% Palavras-chave: iniciais minúsculas (exceto nomes próprios), separadas por
% ponto e vírgula, a última terminada em ponto (Manual, p. 15). Até 10.
\keyword{algoritmo de Dijkstra;}
\keyword{caminho mínimo;}
\keyword{coleta seletiva;}
\keyword{grafos;}
\keyword{logística urbana.}

\keywordeng{Dijkstra's algorithm;}
\keywordeng{shortest path;}
\keywordeng{selective waste collection;}
\keywordeng{graphs;}
\keywordeng{urban logistics.}

\begin{document}

% Orientadora ou coorientadora: troque o rótulo. Com mais de uma pessoa,
% troque também o plural (\advisorsname, \coadvisorsname).
% DISSERTAÇÃO: aqui a orientação é de uma professora.
\renewcommand{\advisorname}{Orientadora}
% \renewcommand{\coadvisorname}{Coorientadora}

\maketitle   % capa e folha de rosto

% Ficha catalográfica: sem argumento, gera uma página provisória. Quando a
% biblioteca enviar a ficha em PDF, use \fichacatalografica[ficha.pdf]
% (Manual, p. 12).
\fichacatalografica

% Errata (opcional; Manual, p. 13 e 87): vai logo após a folha de rosto e só
% existe se o trabalho já impresso tiver erros a corrigir. Cada linha traz a
% folha, a linha, o texto errado e o texto correto. Descomente para usar.
% DISSERTAÇÃO: o ambiente vale para qualquer tipo de trabalho.
% \begin{errata}
% 16 & 10 & Dijsktra & Dijkstra \\
% \end{errata}

%------------------------------------------------------------------------------
% Folha de aprovação (Manual, p. 13 e 89). O argumento é a data da defesa.
% ALTERE os nomes, a titulação e a instituição de cada membro da banca.
%------------------------------------------------------------------------------
\begin{aprovacao}{15 de dezembro de 2026}
\noindent Prof.ª Dr.ª Barbara Liskov (Orientadora)\\
Doutora em Ciência da Computação pela Stanford University\\[1cm]

\noindent Prof. Dr. Donald E. Knuth\\
Doutor em Matemática pelo California Institute of Technology\\[1cm]

\noindent Prof.ª Dr.ª Grace Hopper\\
Doutora em Matemática pela Yale University
\end{aprovacao}

% Elementos opcionais: dedicatória, agradecimentos e epígrafe
\begin{dedicatoria}
Às equipes de coleta seletiva, que percorrem a cidade todos os dias.
\end{dedicatoria}

\begin{agradecimentos}
À professora Barbara Liskov, pela orientação paciente e pelas perguntas que
me obrigaram a reescrever o capítulo de metodologia três vezes.

Ao professor Edsger W. Dijkstra, pela coorientação e pela ajuda com o
protótipo.

Aos colegas do programa, que testaram as primeiras versões das rotas.
\end{agradecimentos}

% A epígrafe é uma citação com indicação de autoria (Manual, p. 14). A obra
% citada entra nas referências.
\begin{epigrafe}
I propose to consider the question, ‘Can machines think?’\\
\hspace*{\fill}\citep[p.~433]{Turing:1950:CMI}
\end{epigrafe}

%------------------------------------------------------------------------------
% Resumo: de 150 a 500 palavras, parágrafo único, voz ativa, terceira pessoa
% do singular, sem citações nem siglas (Manual, p. 14). A referência do
% trabalho, acima do texto, é gerada pela classe.
%------------------------------------------------------------------------------
\begin{abstract}
A coleta seletiva em cidades de porte médio costuma seguir rotas definidas
pela experiência das equipes, sem apoio de ferramentas de otimização. Esta
dissertação investiga se algoritmos clássicos de caminho mínimo podem reduzir a
distância percorrida pelos caminhões de coleta em Pelotas, no Rio Grande do
Sul. A malha viária de quatro setores de coleta foi modelada como um grafo
ponderado e dirigido, para representar o sentido das ruas, em que os vértices representam pontos de coleta, a garagem e a
cooperativa de reciclagem, e o peso de cada aresta corresponde à distância
em quilômetros. Sobre esse modelo, aplicou-se o algoritmo de Dijkstra,
implementado em Python, para calcular a menor rota entre a garagem e a
cooperativa passando pelos pontos de cada setor. As rotas obtidas foram
comparadas com as rotas praticadas pela equipe de coleta. Nos quatro setores,
as rotas calculadas foram mais curtas, com redução média de 13,5\% na
distância percorrida, e a maior economia ocorreu no setor com mais
cruzamentos de mão única. A dissertação mostra que um algoritmo conhecido desde
1959, de implementação simples, já oferece ganho mensurável na logística da
coleta, desde que o grafo represente com fidelidade o sentido das vias. Como
limitação, o modelo considera apenas a distância e ignora o tempo de parada
em cada ponto, o que fica como sugestão para trabalhos futuros.
\end{abstract}

% Abstract: tradução do resumo; o argumento é o título em inglês.
\begin{englishabstract}{Routing selective waste collection on directed graphs: a case study in Pelotas}
Selective waste collection in medium-sized cities usually follows routes set
by the crews' experience, without the support of optimization tools. This
dissertation investigates whether classical shortest path algorithms can reduce the
distance covered by collection trucks in Pelotas, in the state of Rio Grande
do Sul, Brazil. The road network of four collection sectors was modeled as a
weighted directed graph, to represent the direction of the streets, in
which vertices represent collection points, the garage and
the recycling cooperative, and the weight of each edge is the distance in
kilometers. On this model, Dijkstra's algorithm, implemented in Python, was
applied to compute the shortest route between the garage and the cooperative
through the points of each sector. The resulting routes were compared with
the routes currently used by the collection crew. In all four sectors, the
computed routes were shorter, with an average reduction of 13.5\% in the
distance covered, and the largest saving occurred in the sector with the most
one-way intersections. The dissertation shows that an algorithm known since 1959,
simple to implement, already yields a measurable gain in collection
logistics, as long as the graph faithfully represents the direction of the
streets. As a limitation, the model considers only distance and ignores the
stopping time at each point, which is left as a suggestion for future work.
\end{englishabstract}

% Listas: entram depois do abstract e antes do sumário, nesta ordem.
\listoffigures
\listofquadros   % quadros numerados como Figura, em lista própria (Manual, p. 16)
\listoftables

% Lista de abreviaturas e siglas, em ordem alfabética (Manual, p. 18).
% O argumento é a sigla mais longa, para alinhar a coluna dos significados.
\begin{listofabbrv}{UFPel}
  \item[IBGE]  Instituto Brasileiro de Geografia e Estatística
  \item[SBC]   Sociedade Brasileira de Computação
  \item[TCC]   Trabalho de Conclusão de Curso
  \item[UFPel] Universidade Federal de Pelotas
\end{listofabbrv}

% DISSERTAÇÃO: lista de símbolos (Manual, p. 19), na ordem em que aparecem no
% texto. O argumento é o símbolo mais largo, para alinhar os significados.
% Símbolos com colchetes vão entre chaves: \item[{$d[v]$}].
\begin{listofsymbols}{$\delta(s, v)$}
  \item[$G$]            grafo
  \item[$V$]            conjunto de vértices
  \item[$E$]            conjunto de arestas
  \item[$w$]            função de peso das arestas
  \item[$p$]            caminho
  \item[$\delta(s, v)$] distância mínima de $s$ até $v$
  \item[{$d[v]$}]       estimativa da distância até $v$
  \item[{$\pi[v]$}]     predecessor de $v$ no caminho mínimo
\end{listofsymbols}

\tableofcontents

%==============================================================================
\chapter{Introdução}
\label{cap:introducao}
%==============================================================================

A coleta seletiva de Pelotas atende bairros com traçados bem diferentes: o
centro histórico tem quarteirões regulares e muitas ruas de mão única, enquanto
os bairros mais novos crescem em loteamentos com poucas ligações entre si.
Em ambos os casos, a ordem em que o caminhão visita os pontos de coleta define
quantos quilômetros ele roda por dia. Este trabalho trata esse problema como
um problema de caminho mínimo em grafos e testa o algoritmo de
\citet{Dijkstra:1959:NTP} sobre dados de quatro setores de coleta.

Este documento também é o exemplo de dissertação da classe
\texttt{texufpel}, adaptado do exemplo de Trabalho de Conclusão de Curso
(\pdftooltip{TCC}{Trabalho de Conclusão de Curso}). Cada seção usa um
recurso da classe e explica, no próprio texto, como ele foi feito. Os elementos que aparecem antes
desta página (capa, folha de rosto, ficha catalográfica, folha de aprovação,
dedicatória, agradecimentos, epígrafe, resumo, abstract, listas e sumário)
seguem a ordem do Manual de normas da Universidade Federal de Pelotas
(\pdftooltip{UFPel}{Universidade Federal de Pelotas}) e são gerados pelos comandos do
preâmbulo e pelos ambientes do início do arquivo \texttt{exemplo-diss.tex}.

Siglas são escritas por extenso na primeira vez em que aparecem, com a sigla
entre parênteses, e entram na lista de abreviaturas e siglas (Manual, p. 18).
No parágrafo anterior, a sigla foi escrita com
\verb|\pdftooltip{TCC}{Trabalho de...}|, do pacote \texttt{pdfcomment}, que
mostra o significado quando o leitor passa o mouse sobre ela no PDF. É um recurso de leitura na tela e não substitui a escrita por extenso
na primeira ocorrência.

\section{O que muda em relação ao TCC}

Para transformar o exemplo de TCC nesta dissertação, bastou trocar a opção
da classe de \texttt{tcc} para \texttt{diss} e informar o programa de
pós-graduação com \verb|\programa|. A classe ajusta sozinha a natureza do
trabalho na folha de rosto (``Dissertação apresentada ao Programa de
Pós-Graduação em Computação...''), o texto da folha de aprovação e o tipo de
trabalho na referência do resumo, ``Dissertação (Mestrado em Ciência da
Computação)'' (Manual, p. 85, 89 e 94).

Como a orientação é de uma professora, o preâmbulo redefine o comando
\verb|\advisorname|, que passa a valer ``Orientadora''. O exemplo também traz a
lista de símbolos, que reúne os símbolos das equações do
Capítulo~\ref{cap:fundamentacao} na ordem em que aparecem (Manual, p. 19), e
um modelo de errata, comentado no arquivo, para o caso de o trabalho já
impresso precisar de correções.

\section{Objetivos}
\label{sec:objetivos}

O objetivo geral é verificar se o algoritmo de Dijkstra reduz a distância
percorrida nas rotas de coleta seletiva de Pelotas. Os objetivos específicos
são:

\begin{enumerate}
  \item modelar a malha viária de quatro setores de coleta como um grafo
        ponderado e dirigido;
  \item implementar o algoritmo de Dijkstra e validá-lo em um grafo pequeno;
  \item comparar as rotas calculadas com as rotas praticadas pela equipe:
  \begin{enumerate}
    \item pela distância total percorrida;
    \item pela quantidade de conversões à esquerda.
  \end{enumerate}
\end{enumerate}

A lista acima segue as regras de alíneas do Manual (p. 71): o texto que a
antecede termina em dois pontos, cada alínea começa com letra minúscula e
termina em ponto e vírgula, e a última termina em ponto. A classe formata o
primeiro nível do ambiente \texttt{enumerate} como alíneas, com a), b), c), e o
segundo nível como subalíneas, com travessão. A pontuação fica por conta de
quem escreve.

\section{Organização do texto}

O Capítulo~\ref{cap:fundamentacao} apresenta os conceitos de grafos e o
algoritmo de Dijkstra e mostra as formas de citação. O
Capítulo~\ref{cap:metodologia} descreve como os dados foram obtidos e como o
protótipo foi construído, com exemplos de figura, quadro e listagem de código.
O Capítulo~\ref{cap:resultados} traz os resultados em tabela e mostra a
numeração das seções até o quinto nível. O Capítulo~\ref{cap:consideracoes}
encerra o trabalho. Os números dos capítulos neste parágrafo foram gerados com
\verb|\label| e \verb|\ref|: se um capítulo mudar de lugar, as referências
cruzadas se atualizam na próxima compilação.

%==============================================================================
\chapter{Fundamentação teórica}
\label{cap:fundamentacao}
%==============================================================================

\section{Citações}
\label{sec:citacoes}

Este capítulo usa as formas de citação do Manual (p. 62-67). Todas seguem o
sistema autor-data e são feitas com dois comandos do pacote \texttt{natbib}:

\begin{lstlisting}[language={[LaTeX]TeX}, numbers=none]
\cite{Codd:1970:RMD}     % (Codd, 1970)    citação entre parênteses
\citet{Codd:1970:RMD}    % Codd (1970)     autor como parte da frase
\cite[p.~380]{Codd:1970:RMD}   % (Codd, 1970, p. 380)
\end{lstlisting}

A citação indireta reproduz a ideia do autor com outras palavras. O modelo
relacional, por exemplo, propõe que os dados sejam vistos como relações
matemáticas, independentes da forma como estão armazenados
\citep{Codd:1970:RMD}. Quando o autor faz parte da frase, o ano vem entre
parênteses logo depois do nome: \citet{Lamport:1978:TCO} mostrou que, em um
sistema distribuído, a ordem dos eventos pode ser definida sem relógio
global.

Várias obras na mesma citação ficam separadas por ponto e vírgula, de
preferência em ordem alfabética \citep{Hoare:1969:ABC,Lamport:1978:TCO}.
Obras do mesmo autor em anos diferentes aparecem com os anos separados por
vírgula, como em \citet{Turing:1937:OCN,Turing:1950:CMI}. Com quatro ou mais
autores, a citação usa o primeiro seguido de et al. \citep{Cormen:2022:IA}.

A citação direta curta, de até três linhas, fica entre aspas no corpo do
texto, com a página. Para a Sociedade Brasileira de Computação
(\pdftooltip{SBC}{Sociedade Brasileira de Computação}), ``Os cientistas da
computação são responsáveis pela pesquisa e desenvolvimento em Computação''
\citep[p.~30]{Zorzo:2017:RFC}.

A citação direta longa, com mais de três linhas, usa o ambiente
\texttt{quote}. A classe aplica o recuo de 4~cm, a letra tamanho 10 e o espaço
simples que o Manual pede (p. 63). O trecho abaixo foi traduzido de um
documento em inglês, e por isso a chamada termina com ``tradução nossa''
(Manual, p. 66):

\begin{quote}
O protocolo internet é limitado, por definição, às funções necessárias para
entregar um pacote de bits (um datagrama internet) de uma origem a um destino
por meio de um sistema de redes interconectadas. Não há mecanismos para
aumentar a confiabilidade dos dados de ponta a ponta, nem para controle de
fluxo, sequenciamento ou outros serviços comuns em protocolos entre
hospedeiros. O protocolo internet pode tirar proveito dos serviços de suas
redes de suporte para oferecer vários tipos e níveis de serviço
\citep[p.~1, tradução nossa]{Postel:1981:IP}.
\end{quote}

A citação de citação usa a expressão apud. Na lista de referências entra só a
obra consultada (Manual, p. 65). Uma das origens do algoritmo de Bellman-Ford é um
trabalho de 1958 sobre roteamento, que não consultamos diretamente:
\apud{Bellman}{1958}{Cormen:2022:IA} trata do caminho mínimo em grafos que
admitem pesos negativos. Entre parênteses, a mesma citação fica
\apudp{Bellman}{1958}{Cormen:2022:IA}. Os comandos \verb|\apud| e
\verb|\apudp| são da classe; o autor e o ano da obra original são escritos à
mão para que ela não vá para as referências.

Se o curso pedir a referência completa em nota de rodapé, use o comando
\verb|\footcite|, definido no preâmbulo deste arquivo. Ele coloca a referência
no pé da página\footcite{Postel:1981:IP}, e a obra continua na lista de
referências.

\section{Grafos e caminhos mínimos}
\label{sec:grafos}

Um grafo ponderado é um par $G = (V, E)$, em que $V$ é o conjunto de vértices
e $E$ o conjunto de arestas, com uma função de peso $w$ que associa a cada
aresta um número real não negativo \citep{Cormen:2022:IA}. O custo de um
caminho $p = \langle v_0, v_1, \dots, v_k \rangle$ é a soma dos pesos de suas
arestas:
\begin{equation}
  w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i).
  \label{eq:custo}
\end{equation}

A distância mínima $\delta(s, v)$ entre dois vértices é o menor custo entre
todos os caminhos que os ligam. O algoritmo de Dijkstra mantém uma estimativa
$d[v]$ dessa distância e a melhora por um passo chamado relaxamento, que
testa se passar por $u$ encurta o caminho até $v$:
\begin{align}
  \delta(s, v) &= \min \{\, w(p) : p \text{ é um caminho de } s \text{ até } v \,\},
  \label{eq:delta}\\
  d[v] &\leftarrow \min \{\, d[v],\; d[u] + w(u, v) \,\}.
  \label{eq:relax}
\end{align}

As equações são numeradas com algarismos arábicos entre parênteses, alinhados
à direita (Manual, p. 76). A Equação~\eqref{eq:custo} foi escrita com o
ambiente \texttt{equation}; as Equações~\eqref{eq:delta} e~\eqref{eq:relax},
com \texttt{align}, que alinha as linhas pelo símbolo marcado com \verb|&|.
Para citar uma equação, use \verb|\eqref{rótulo}|.

\section{O algoritmo de Dijkstra}
\label{sec:dijkstra}

O algoritmo resolve o problema do caminho mínimo de origem única quando todos
os pesos são não negativos \citep{Dijkstra:1959:NTP}. A cada passo, ele retira
da fila de prioridade o vértice com a menor estimativa de distância e relaxa
as arestas que saem dele, como mostra a Figura~\ref{fig:dijkstra}.

\begin{figure}[htbp]
  \caption{Pseudocódigo do algoritmo de Dijkstra}
  \label{fig:dijkstra}
  \begin{algorithmic}[1]
    \Require grafo $G = (V, E)$, pesos $w$ não negativos, origem $s$
    \Ensure distâncias $d[v]$ e predecessores $\pi[v]$ para todo $v \in V$
    \ForAll{$v \in V$}
      \State $d[v] \gets \infty$; \quad $\pi[v] \gets \text{nulo}$
    \EndFor
    \State $d[s] \gets 0$
    \State $Q \gets V$ \Comment{fila de prioridade pela chave $d$}
    \While{$Q \neq \emptyset$}
      \State $u \gets$ vértice de $Q$ com menor $d[u]$; remova $u$ de $Q$
      \ForAll{$v$ adjacente a $u$}
        \If{$d[v] > d[u] + w(u, v)$}
          \State $d[v] \gets d[u] + w(u, v)$; \quad $\pi[v] \gets u$
        \EndIf
      \EndFor
    \EndWhile
    \State \Return $d, \pi$
  \end{algorithmic}
  \caption*{Fonte: Adaptado de \citet{Cormen:2022:IA}.}
\end{figure}

O Manual chama de Figura toda ilustração, inclusive esquemas e algoritmos
(p. 16). Por isso o pseudocódigo está dentro de um ambiente \texttt{figure},
com a legenda em cima e a fonte embaixo, e aparece na lista de figuras. O
pseudocódigo foi escrito com o ambiente \texttt{algorithmic}, do pacote
\texttt{algpseudocode}; as palavras-chave em português estão definidas no
preâmbulo deste arquivo.

\section{Outros algoritmos de caminho mínimo}
\label{sec:outros}

Há outros algoritmos para o mesmo problema, cada um com suas restrições. A
Figura~\ref{qua:algoritmos} compara três deles.

\begin{quadro}[htbp]
  \caption{Comparação entre algoritmos de caminho mínimo}
  \label{qua:algoritmos}
  \centering
  \begin{tabular}{|p{2.8cm}|p{2.6cm}|p{4.4cm}|p{4.2cm}|}
    \hline
    \textbf{Algoritmo} & \textbf{Problema} & \textbf{Pesos negativos} & \textbf{Tempo} \\ \hline
    Dijkstra       & origem única       & não aceita & $O((V + E) \log V)$ com heap binário \\ \hline
    Bellman-Ford   & origem única       & aceita e detecta ciclos negativos & $O(VE)$ \\ \hline
    Floyd-Warshall & todos os pares     & aceita, sem ciclos negativos & $\Theta(V^3)$ \\ \hline
  \end{tabular}
  \caption*{Fonte: Elaborado pela autora (2026), com base em \citet{Cormen:2022:IA}.}
\end{quadro}

Um quadro organiza informações textuais e tem as bordas fechadas, ao
contrário da tabela, que apresenta dados numéricos. O Manual não usa o nome
``Quadro'' na legenda: todo quadro é uma Figura, mas pode ter lista própria
quando houver muitos (p. 16). O ambiente \texttt{quadro} da classe faz
exatamente isso: numera junto com as figuras e manda o item para a Lista de
Quadros, gerada por \verb|\listofquadros|.

\section{Trabalhos relacionados}

Na própria UFPel, \citet{Cruz:2015:FCS} desenvolveu uma ferramenta
computacional para simular a dispersão de poluentes na atmosfera, um exemplo
de como a Computação apoia decisões ambientais da cidade. Este trabalho segue
a mesma linha, aplicada à logística da coleta.

%==============================================================================
\chapter{Metodologia}
\label{cap:metodologia}
%==============================================================================

\section{Modelagem da malha viária}

Cada setor de coleta foi modelado como um grafo: os vértices são a garagem
(D), os pontos de coleta (P1 a P4) e a cooperativa de reciclagem (C); as
arestas são os trechos de rua entre eles, com a distância em quilômetros.
Nos trechos de mão única, a aresta tem um só sentido. Os
trajetos foram conferidos com a equipe de coleta\footnote{Informação fornecida
pela equipe de coleta do setor 1 em conversa com a autora, em agosto de 2026
(informação verbal). Exemplo fictício de nota de referência para dados não
publicados (Manual, p. 69).}. A Figura~\ref{fig:grafo} mostra o grafo de um
dos setores, com a rota mínima em destaque.

\begin{figure}[htbp]
  \caption{Grafo de um setor de coleta, com a rota mínima de D até C em destaque}
  \label{fig:grafo}
  \centering
  \includegraphics[width=0.75\textwidth]{imagens/grafo-coleta.pdf}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{figure}

A figura foi inserida com o código abaixo. A legenda vem antes da imagem,
porque o Manual pede a identificação na parte superior, com o número, um
travessão e o título sem ponto final (p. 16). Abaixo da imagem vai a fonte,
obrigatória mesmo quando a figura é da própria autora (p. 17). A classe deixa
a legenda e a fonte em tamanho 10 e espaço simples.

\begin{lstlisting}[language={[LaTeX]TeX}, numbers=none]
\begin{figure}[htbp]
  \caption{Grafo de um setor de coleta, com a rota mínima de D até C em destaque}
  \label{fig:grafo}
  \centering
  \includegraphics[width=0.75\textwidth]{imagens/grafo-coleta.pdf}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{figure}
\end{lstlisting}

O caminho da imagem é relativo à pasta onde o documento é compilado, que é a
raiz do repositório. Se a figura vier de outra obra, a fonte traz a citação,
por exemplo \verb|\caption*{Fonte: \citet{Cormen:2022:IA}.}|, e a obra entra nas
referências (Manual, p. 17).

\section{Implementação}

O protótipo foi escrito em Python, com a fila de prioridade do módulo
\texttt{heapq}. A Figura~\ref{fig:codigo} mostra a função principal, aplicada
ao grafo da Figura~\ref{fig:grafo}. Ao ser executada, ela imprime a distância
13 e o caminho D, P2, P1, P3, P4, C.

\begin{figure}[htbp]
  \caption{Implementação do algoritmo de Dijkstra em Python}
  \label{fig:codigo}
\begin{lstlisting}[language=Python]
import heapq

def dijkstra(grafo, origem):
    dist = {v: float("inf") for v in grafo}
    anterior = {v: None for v in grafo}
    dist[origem] = 0
    fila = [(0, origem)]
    while fila:
        d_u, u = heapq.heappop(fila)
        if d_u > dist[u]:
            continue  # entrada antiga da fila
        for v, peso in grafo[u].items():
            if dist[u] + peso < dist[v]:
                dist[v] = dist[u] + peso
                anterior[v] = u
                heapq.heappush(fila, (dist[v], v))
    return dist, anterior

grafo = {
    "D":  {"P1": 4, "P2": 2},
    "P1": {"D": 4, "P2": 1, "P3": 5},
    "P2": {"D": 2, "P1": 1, "P3": 8, "P4": 10},
    "P3": {"P1": 5, "P2": 8, "P4": 2, "C": 6},
    "P4": {"P2": 10, "P3": 2, "C": 3},
    "C":  {"P3": 6, "P4": 3},
}
dist, anterior = dijkstra(grafo, "D")
caminho, v = [], "C"
while v is not None:
    caminho.append(v)
    v = anterior[v]
print(dist["C"], caminho[::-1])  # 13 ['D', 'P2', 'P1', 'P3', 'P4', 'C']
\end{lstlisting}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{figure}

A listagem foi feita com o ambiente \texttt{lstlisting}, do pacote
\texttt{listings}, dentro de um ambiente \texttt{figure}: assim como o
pseudocódigo, o código-fonte é uma ilustração e recebe o nome de Figura. O
estilo das listagens (fonte, numeração de linhas, moldura e acentos) está no
comando \verb|\lstset| do preâmbulo.

\section{Uso de inteligência artificial}

Na elaboração deste trabalho, utilizou-se a ferramenta de inteligência
artificial generativa [nome e versão da ferramenta], entre [mês/ano] e
[mês/ano], exclusivamente para [finalidades, por exemplo: revisão ortográfica
e tradução do resumo para a língua inglesa]. A ferramenta não foi utilizada
para gerar dados, análises, interpretações ou conclusões. Todo o conteúdo
sugerido foi revisado, editado e validado pela autora, que assume integral
responsabilidade pelo texto final, pela exatidão das informações e pela
autoria intelectual do trabalho.

O parágrafo acima é o modelo de declaração da pasta \texttt{instruções/} do
repositório. Se usar uma ferramenta desse tipo, preencha os trechos entre
colchetes; se não usar, apague a seção.

%==============================================================================
\chapter{Resultados}
\label{cap:resultados}
%==============================================================================

A Tabela~\ref{tab:resultados} compara a distância das rotas praticadas com a
das rotas calculadas nos quatro setores.

\begin{table}[htbp]
  \caption{Distância percorrida por setor, em quilômetros}
  \label{tab:resultados}
  \centering
  \begin{tabular}{lrrr}
    \hline
    Setor & Rota praticada & Rota calculada & Redução (\%) \\
    \hline
    1 -- Centro      & 18,6 & 15,2 & 18,3 \\
    2 -- Fragata     & 22,4 & 19,8 & 11,6 \\
    3 -- Três Vendas & 25,1 & 22,0 & 12,4 \\
    4 -- Areal       & 20,3 & 17,9 & 11,8 \\
    \hline
    Média            & 21,6 & 18,7 & 13,5 \\
    \hline
  \end{tabular}
  \caption*{Fonte: Elaborada pela autora (2026), com dados fictícios para fins de exemplo.}
\end{table}

A tabela segue a padronização do Instituto Brasileiro de Geografia e
Estatística (\pdftooltip{IBGE}{Instituto Brasileiro de Geografia e Estatística}),
indicada pelo Manual (p. 17): traços
horizontais no cabeçalho e no fim, sem traços verticais e sem fechar as
laterais. O título vai em cima e a fonte embaixo, como nas figuras. Valores
numéricos ficam alinhados à direita (\texttt{r} na especificação das
colunas).

\section{Análise por setor}

O setor 1 teve a maior redução. É o setor com mais ruas de mão única, e a rota
praticada fazia retornos longos que o algoritmo evitou.

\subsection{Setores com traçado regular}

Esta é uma seção terciária. A classe numera as seções até o quinto nível,
como pede o Manual (p. 70), e todas aparecem no sumário em negrito.

\subsubsection{Setor 1 -- Centro}

Esta é uma seção quaternária, criada com \verb|\subsubsection|.

\paragraph{Trecho entre a garagem e o primeiro ponto}

Esta é uma seção quinária, criada com \verb|\paragraph|. Não use níveis abaixo
deste: o Manual limita a numeração progressiva à seção quinária.

%==============================================================================
\chapter{Considerações finais}
\label{cap:consideracoes}
%==============================================================================

O algoritmo de Dijkstra reduziu a distância percorrida nos quatro setores
estudados, com redução média de 13,5\% (Tabela~\ref{tab:resultados}). O ganho
foi maior onde as ruas de mão única tornam a rota intuitiva mais longa. O modelo ainda
ignora o tempo de parada em cada ponto e as janelas de horário, que ficam como
trabalho futuro, com variações do problema de roteamento de veículos.

Os apêndices trazem material produzido pela autora: o Apêndice~\ref{apx:dados}
lista os dados do grafo, e o Apêndice~\ref{apx:referencias} mostra como
cadastrar cada tipo de referência. O Anexo~\ref{anx:meses} reproduz material de
outra autoria.

%------------------------------------------------------------------------------
% Referências: estilo abnt.bst e base bibliografia.bib, ambos na raiz.
%------------------------------------------------------------------------------
\bibliographystyle{abnt}
\bibliography{bibliografia}

%------------------------------------------------------------------------------
% Apêndices: material elaborado pela própria autora (Manual, p. 23).
% \apendices cria a folha de abertura; cada \chapter vira "Apêndice A – ...".
%------------------------------------------------------------------------------
\apendices

\chapter{Dados do grafo de exemplo}
\label{apx:dados}

O grafo da Figura~\ref{fig:grafo} tem seis vértices e nove arestas. Os pesos
são as distâncias em quilômetros usadas no código da
Figura~\ref{fig:codigo}: D--P1, 4; D--P2, 2; P1--P2, 1; P1--P3, 5; P2--P3, 8;
P2--P4, 10; P3--P4, 2; P3--C, 6; P4--C, 3. As distâncias mínimas a partir de
D, calculadas pelo algoritmo, são: P2, 2; P1, 3; P3, 8; P4, 10; C, 13.

Apêndices e anexos são numerados com letras e citados no texto pelo nome
seguido da letra, como Apêndice~\ref{apx:referencias} (Manual, p. 23).

\chapter{Exemplos de referências por tipo de documento}
\label{apx:referencias}

Este apêndice cita todas as entradas do arquivo \texttt{bibliografia.bib},
para que a lista de referências deste exemplo mostre como o estilo
\texttt{abnt.bst} formata cada tipo. O arquivo traz, acima de cada entrada, um
comentário explicando quando usar aquele tipo.

Artigos de periódico usam o tipo \texttt{article}:
\citet{Turing:1937:OCN}, \citet{Turing:1950:CMI}, \citet{Shannon:1948:MTC},
\citet{Dijkstra:1959:NTP}, \citet{Dijkstra:1968:GTS}, \citet{Hoare:1969:ABC},
\citet{Codd:1970:RMD}, \citet{Lamport:1978:TCO},
\citet{Dantzig:1959:TDP} e \citet{Solomon:1987:AVR}.

Trabalhos acadêmicos usam \texttt{mastersthesis}, para TCC e dissertação, como
\citet{Cruz:2015:FCS} e \citet{Shannon:1940:SAR}, e \texttt{phdthesis}, para
tese, como \citet{Turing:1938:SLO}. Relatórios técnicos usam
\texttt{techreport}: \citet{vonNeumann:1945:FDR} e \citet{Postel:1981:IP}.

Livros usam \texttt{book}: \citet{vonNeumann:1966:TSR},
\citet{Knuth:1997:ACP}, \citet{Cormen:2022:IA}, \citet{Brooks:1975:MMM},
\citet{Abelson:1996:SIC} e \citet{Moore:1979:MAI}. Um capítulo de livro do
mesmo autor usa \texttt{inbook} \citep{Knuth:1997:IS}; um capítulo de livro
organizado por outra pessoa, \texttt{incollection}
\citep{vonNeumann:1951:GLT}.

Trabalhos publicados em anais de eventos usam \texttt{inproceedings}
\citep{Cook:1971:CTP}; os anais no todo, \texttt{proceedings}
\citep{ACM:1971:STOC}. Normas técnicas usam \texttt{manual}
\citep{ABNT:2018:NBR6023}. Folhetos usam \texttt{booklet}
\citep{Zorzo:2017:RFC}, e documentos não publicados, \texttt{unpublished}
\citep{Dijkstra:1988:CRT}.

Os demais documentos usam \texttt{misc}: preprint
\citep{Vaswani:2017:AIA}, página da web \citep{ACM:2026:TA}, programa de
computador \citep{Aguiar:2026:TEX}, legislação \citep{Brasil:2015:LBI} e
conjunto de dados \citep{Fisher:1936:IRI}.

%------------------------------------------------------------------------------
% Anexos: material de outra autoria (Manual, p. 23-24).
%------------------------------------------------------------------------------
\anexos

\chapter{Abreviatura dos meses em português}
\label{anx:meses}

\begin{table}[htbp]
  \caption{Abreviatura dos meses em português}
  \centering
  \begin{tabular}{llll}
    \hline
    Mês & Abreviatura & Mês & Abreviatura \\
    \hline
    janeiro   & jan.  & julho    & jul. \\
    fevereiro & fev.  & agosto   & ago. \\
    março     & mar.  & setembro & set. \\
    abril     & abr.  & outubro  & out. \\
    maio      & maio  & novembro & nov. \\
    junho     & jun.  & dezembro & dez. \\
    \hline
  \end{tabular}
  \caption*{Fonte: \citet{ABNT:2018:NBR6023}.}
\end{table}

\end{document}

\mode<presentation>

\definecolor{UFPelAzul}{RGB}{0,65,140}
\definecolor{UFPelAzulCiano}{RGB}{180,220,240}
\definecolor{UFPelLaranja}{RGB}{245,165,0}
\definecolor{UFPelVermelho}{RGB}{190,15,15}
\definecolor{UFPelAmarelo}{RGB}{250,210,0}
\definecolor{UFPelVerde}{RGB}{190,210,0}

% Normal text
\setbeamercolor{normal text}{fg=black}

% First page
\setbeamercolor*{title}{fg=black,bg=gray}
\setbeamercolor*{author}{fg=black,bg=gray}
\setbeamercolor*{date}{fg=black,bg=gray}

% Generic frames header and footer
\setbeamercolor{titlelike}{fg=black}
\setbeamercolor*{frametitle}{fg=white}
\setbeamercolor*{framesubtitle}{fg=white}
\setbeamercolor*{title in head/foot}{fg=UFPelAzul}
\setbeamercolor*{author in head/foot}{fg=UFPelAzul}

%Blocks
\setbeamercolor{block title}{bg=UFPelAmarelo!40,fg=black}
\setbeamercolor{block title alerted}{bg=UFPelVermelho!40,fg=black}
\setbeamercolor{block title example}{bg=UFPelVerde!40,fg=black}
\setbeamercolor{block body}{bg=UFPelAmarelo!10,fg=black}
\setbeamercolor{block body alerted}{bg=UFPelVermelho!10,fg=black}
\setbeamercolor{block body example}{bg=UFPelVerde!10,fg=black}

% Lists
\setbeamercolor*{item}{fg=UFPelAzul}

% Quotation and quote
\setbeamercolor*{quotation}{fg=black,bg=UFPelAzul!5}

% Verse
\setbeamercolor*{verse}{fg=black,bg=UFPelAzul!5}

% Abstract
\setbeamercolor*{abstract}{fg=black,bg=UFPelAzul!5}

% Table of contents 
\setbeamercolor*{structure}{fg=black}

% Bibliography
\setbeamercolor*{bibliography entry title}{fg=black}
\setbeamercolor*{bibliography entry author}{fg=black}
\setbeamercolor*{bibliography entry location}{fg=black!50}
\setbeamercolor*{bibliography entry note}{fg=black!50}


\mode
<all>

\usepackage[T1]{fontenc}

% Font sizes
\setbeamerfont{title}{size=\Huge}
\setbeamerfont{frametitle}{size=\Large}
\setbeamerfont{framesubtitle}{size=\normalsize}
\setbeamerfont{title in head/foot}{size=\footnotesize}
\setbeamerfont{author in head/foot}{size=\footnotesize}

\setbeamerfont*{bibliography entry author}{series=\bfseries}
\setbeamerfont*{bibliography entry title}{series=\bfseries}
\setbeamerfont*{description item}{series=\bfseries}

%capa
\mode<presentation>

\setbeamertemplate{sections/subsections in toc}[circle]
\setbeamertemplate{items}[circle]
\usebeamercolor[fg]{normal text}

\setbeamertemplate{background}{
\begin{tikzpicture}
  
\ifnum\thepage>1\relax%
% background for pages > 1 
	\fill[white,opacity=1] (0,0) rectangle(\the\paperwidth,\the\paperheight);

   \node[inner sep=0pt] (logo) at (3,4.75){\includegraphics[width=6cm]{graphics/UFPelLogo}};

\else 
  % background for the title page
  \useasboundingbox (0,0) rectangle(\the\paperwidth,\the\paperheight);

  % background logo
  \node[inner sep=0pt] (logo) at (3,4.75){\includegraphics[width=6cm]{graphics/UFPelLogo}};

  % line between institute and author
  \fill[color=UFPelAzul] (0,5.95) rectangle(1,6);  
  \fill[color=UFPelLaranja] (1,5.95) rectangle(1.15,6);  
  \fill[color=UFPelAzul] (1.15,5.95) rectangle(\the\paperwidth,6);  

\fi
% in debug mode, show the grid
\ifdefined\DEBUG
	\draw[help lines,xstep=1,ystep=1,gray] (current page.south west) grid (current page.north east);
\fi
\end{tikzpicture}
}

% Title page
\defbeamertemplate*{title page}{ufpel}[1][]
{
\centering
\begin{textblock*}{\the\paperwidth}(0cm,1cm)
	{\usebeamercolor[fg]{title}\usebeamerfont{title}\inserttitle}
\end{textblock*}
\begin{textblock*}{\the\paperwidth}(0cm,3.5cm)
	{\usebeamercolor[fg]{author}\usebeamerfont{author}\insertauthor}
\end{textblock*}
\begin{textblock*}{\the\paperwidth}(0cm,5cm)
	{\usebeamercolor[fg]{author}\usebeamerfont{author}\insertinstitute}
\end{textblock*}
\begin{textblock*}{\the\paperwidth}(0cm,8cm)
	{\usebeamercolor[fg]{author}\usebeamerfont{author}\insertdate}
\end{textblock*}
}

\mode
<all>

\mode<presentation>

% Frame title
\defbeamertemplate*{frametitle}{ufpel}[1][]
{

\begin{tikzpicture}
\useasboundingbox (0,-0.05) rectangle(\the\paperwidth,0.95);

% Three-colored line
 \fill[color=UFPelAzul] (-1,0) rectangle(0,1);
 \fill[color=UFPelLaranja] (0,0) rectangle(0.15,1);
 \fill[color=UFPelAzul] (0.15,0) rectangle(\the\paperwidth,1);
 
 % Logo in the orange box
 \node[inner sep=0pt] (logo) at (-0.5,0.5){\includegraphics[width=0.85cm]{graphics/UFPelLogoBranco}};
\end{tikzpicture}

% If we don't have a subtitle, put the title
% at the center of the header
\ifx\insertframesubtitle\@empty

  \begin{textblock*}{15cm}(1.5cm,0.3cm)
  {\usebeamercolor[fg]{frametitle}\usebeamerfont{frametitle}\insertframetitle}
  \end{textblock*}

\else
% If we have both title and subtitle, stack them
  \begin{textblock*}{15cm}(1.5cm,0.1cm)
  {\usebeamercolor[fg]{frametitle}\usebeamerfont{frametitle}\insertframetitle}
  \end{textblock*}

  \begin{textblock*}{15cm}(1.5cm,0.6cm)
  {\usebeamercolor[fg]{framesubtitle}\usebeamerfont{framesubtitle}\insertframesubtitle}
  \end{textblock*}

\fi

}

% Frame footer
\setbeamertemplate{footline}
{
\ifnum\thepage>1
\begin{tikzpicture}
\useasboundingbox (0,0) rectangle(\the\paperwidth,1);

% Three-colored line
\fill[color=UFPelAzul] (0,1.25) rectangle(1,1.3);
\fill[color=UFPelLaranja] (1,1.25) rectangle(1.15,1.3);
\fill[color=UFPelAzul] (1.15,1.25) rectangle(\the\paperwidth,1.3);

\end{tikzpicture}

%paperwidth = 455 points

\begin{textblock*}{28pt}(0cm,8.65cm)
\centering{\usebeamercolor[fg]{title in head/foot}\usebeamerfont{title in head/foot}\insertframenumber/\inserttotalframenumber}
\end{textblock*}

\begin{textblock*}{114pt}(1.15cm,8.65cm)
\centering{\usebeamercolor[fg]{author in head/foot}\usebeamerfont{author in head/foot}\insertshortauthor}
\end{textblock*}

\begin{textblock*}{313pt}(5.15cm,8.65cm) %\dimexpr\the\paperwidth-7.8cm
\centering{\usebeamercolor[fg]{title in head/foot}\usebeamerfont{title in head/foot}\insertshorttitle}
\end{textblock*}

\fi % \ifnum\thepage>1
}

\mode<all>

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%										%%%%%
%%%%%				~WARNING~				%%%%%
%%%%%										%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Please note that including the option [usenames,dvipsnames] 
% is MANDATORY when declaring the document class due to
% compatibility issues between the packaged tikz and xcolor.
% So, to use this theme, you MUST write
% \documentclass[usenames,dvipsnames]{beamer}
% as first command of your main presentation file.

\mode<presentation>

% comment/uncomment this line to enable/disable debug mode
%\newcommand*{\DEBUG}{}

% Requirement
\RequirePackage{xcolor}	% colors
\RequirePackage{tikz}	% drawing 
\RequirePackage{soul} 	% text highlighting

% in debug mode, show the boxes around the text
\ifdefined\DEBUG
\usepackage[absolute,overlay,showboxes]{textpos}
\else
\usepackage[absolute,overlay]{textpos}
\fi

% Settings
\useinnertheme{ufpel}
\useoutertheme{ufpel}
\usecolortheme{ufpel}
\usefonttheme{ufpel}

% Remove navigation symbols
\setbeamertemplate{navigation symbols}{}
% Squared blocks
\setbeamertemplate{blocks}[rounded=false] 

% Table of contents (outline) styling
\setbeamertemplate{section in toc}[ball numbered]
\setbeamertemplate{subsection in toc}[subsections numbered]

% Bibliography styling
\setbeamertemplate{bibliography item}[text]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%										%%%%%
%%%%%			~BONUS COMMANDS~			%%%%%
%%%%%										%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% See the provided main.tex template for a tutorial
% on how to use \framecard and \framepic.

%%%%%										%%%%%
%%%%%	~Frame with huge centered text~		%%%%%
%%%%%										%%%%%
\newcommand{\framecard}[2][UFPelLaranja]{
    {\setbeamercolor{background canvas}{bg=#1}%
      \begin{frame}[plain]%
        \vfill%
        \begin{center}%
          {\color{white}\Huge\textbf{%
            {#2}%
          }}%
        \end{center}%
        \vfill%
      \end{frame}%
  }
}

%%%%%										%%%%%
%%%%%	~Frame with background image~		%%%%%
%%%%%										%%%%%
\newcommand{\framepic}[3][1]{
  {
    \usebackgroundtemplate{%
    \tikz[overlay,remember picture] \node[opacity=#1, at=(current page.center)] {
      \includegraphics[height=\paperheight]{#2}};
    }
    \begin{frame}[plain]
      \huge{#3}
    \end{frame}
  }
}

%%%%%										%%%%%
%%%%%	~Marker for text highlighting ~		%%%%%
%%%%%										%%%%%

% beamer/soul compatibility fix
\makeatletter
\newcommand\SoulColor{%
  \let\set@color\beamerorig@set@color
  \let\reset@color\beamerorig@reset@color}
\makeatother

\newcommand{\marker}[2][UFPelLaranja]{{\SoulColor\sethlcolor{#1}\hl{#2}}}

\mode<all>

\documentclass[aspectratio=169]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usetheme{ufpel}

%Mais informações sobre fontes

\usepackage{fontspec}
\setmainfont[Mapping=tex-text]{Fira Sans Compressed Regular}
\setmonofont[Mapping=tex-text,Scale=.8]{Fira Code Regular}
\let\sfdefault\rmdefault

\newcommand{\pdfnewline}{\texorpdfstring{\newline}{ }} 

%------------------------------------------------------------
%This block of code defines the information to appear in the
%Title page
\title[About Beamer] %optional
{About the Beamer class in presentation making}

\author[Arthur, Doe] % (optional)
{A.~B.~Arthur\inst{1} \and J.~Doe\inst{2}}

\institute[VFU] % (optional)
{
  \inst{1} Faculty of Physics\\
  Very Famous University
  \and
  \inst{2} Faculty of Chemistry\\
  Very Famous University
}

\date[VLC 2014] % (optional)
{Very Large Conference, April 2014}

\logo{\includegraphics[height=1.5cm]{graphics/cc.jpg}\\[.2cm]}

%End of title page configuration block
%------------------------------------------------------------



%------------------------------------------------------------
%The next block of commands puts the table of contents at the 
%beginning of each section and highlights the current section:

\AtBeginSection[]
{
  \begin{frame}
    \frametitle{Table of Contents}
    \tableofcontents[currentsection]
  \end{frame}
}
%------------------------------------------------------------


\begin{document}

%The next statement creates the title page.
\frame{\titlepage}


%---------------------------------------------------------
%This block of code is for the table of contents after
%the title page
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents
\end{frame}
%---------------------------------------------------------


\section{First section}

%---------------------------------------------------------
%Changing visivility of the text
\begin{frame}
\frametitle{Sample frame title}
This is a text in second frame. For the sake of showing an example.

\begin{itemize}
    \item<1-> Text visible on slide 1
    \item<2-> Text visible on slide 2
    \item<3> Text visible on slides 3
    \item<4-> Text visible on slide 4
\end{itemize}
\end{frame}

%---------------------------------------------------------


%---------------------------------------------------------
%Example of the \pause command
\begin{frame}
In this slide \pause

the text will be partially visible \pause

And finally everything will be there
\end{frame}
%---------------------------------------------------------

\section{Second section}

%---------------------------------------------------------
%Highlighting text
\begin{frame}
\frametitle{Sample frame title}

In this slide, some important text will be
\alert{highlighted} because it's important.
Please, don't abuse it.

\begin{block}{Remark}
Sample text
\end{block}

\begin{alertblock}{Important theorem}
Sample text in red box
\end{alertblock}

\begin{examples}
Sample text in green box. The title of the block is ``Examples".
\end{examples}
\end{frame}
%---------------------------------------------------------


%---------------------------------------------------------
%Two columns
\begin{frame}
\frametitle{Two-column slide}

\begin{columns}

\column{0.5\textwidth}
This is a text in first column.
$$E=mc^2$$
\begin{itemize}
\item First item
\item Second item
\end{itemize}

\column{0.5\textwidth}
This text will be in the second column
and on a second tought this is a nice looking
layout in some cases.
\end{columns}
\end{frame}
%---------------------------------------------------------


\end{document}

% Fonte da figura imagens/grafo-coleta.pdf, usada no exemplo de TCC.
% Para regerar o PDF (a partir da pasta imagens/):
%   pdflatex grafo-coleta.tex
\documentclass[tikz,border=4pt]{standalone}
\usepackage[T1]{fontenc}
\usepackage{helvet}
\renewcommand{\familydefault}{\sfdefault}
\usetikzlibrary{positioning}

\begin{document}
\begin{tikzpicture}[
    ponto/.style={circle, draw, thick, minimum size=10mm, font=\small\bfseries},
    via/.style={draw, gray!70},
    rota/.style={draw, line width=2.2pt},
    peso/.style={font=\footnotesize, fill=white, inner sep=1.5pt}
  ]
  \node[ponto] (D)  at (0,0)     {D};
  \node[ponto] (P2) at (2.6,-1.6) {P2};
  \node[ponto] (P1) at (2.6,1.6)  {P1};
  \node[ponto] (P3) at (5.6,1.6)  {P3};
  \node[ponto] (P4) at (5.6,-1.6) {P4};
  \node[ponto] (C)  at (8.2,0)    {C};

  % vias que não fazem parte da rota mínima
  \draw[via] (D)  -- node[peso] {4}  (P1);
  \draw[via] (P2) -- node[peso, pos=0.3] {8}  (P3);
  \draw[via] (P2) -- node[peso] {10} (P4);
  \draw[via] (P3) -- node[peso] {6}  (C);

  % rota mínima de D até C: D-P2-P1-P3-P4-C (13 km)
  \draw[rota] (D)  -- node[peso] {2} (P2);
  \draw[rota] (P2) -- node[peso] {1} (P1);
  \draw[rota] (P1) -- node[peso] {5} (P3);
  \draw[rota] (P3) -- node[peso] {2} (P4);
  \draw[rota] (P4) -- node[peso] {3} (C);
\end{tikzpicture}
\end{document}

43 KB — too long to show here. It arrives with the project.

%==============================================================================
% Exemplo de Proposta de Trabalho de Conclusão de Curso com a classe texufpel
%
% A proposta tem o mesmo tema do exemplo de TCC (tcc/exemplo-tcc.tex): é o
% projeto que, depois de executado, resultaria naquele trabalho. Troque os
% dados do preâmbulo (os comentários "ALTERE" indicam o que mudar) e o texto
% dos capítulos.
%
% Compilação (a partir da pasta raiz do repositório):
%   pdflatex tcc/exemplo-tcc-proposta
%   bibtex   exemplo-tcc-proposta
%   pdflatex tcc/exemplo-tcc-proposta
%   pdflatex tcc/exemplo-tcc-proposta
%
% As páginas citadas nos comentários são as do Manual de normas UFPel para
% trabalhos acadêmicos (2023).
%==============================================================================

% Opção tcc-proposta: a proposta não é depositada na biblioteca, por isso a
% classe não gera capa (a opção capa é ignorada), nem referência do trabalho
% no resumo, e não há ficha catalográfica nem folha de aprovação.
\documentclass[tcc-proposta]{texufpel}

%------------------------------------------------------------------------------
% Dados institucionais. ALTERE para o seu curso.
% Unidade feminina (Faculdade, Escola): \unidade[a]{...}.
%------------------------------------------------------------------------------
\unidade{Centro de Desenvolvimento Tecnológico}
\curso{Ciência da Computação}
\nomecurso{Bacharelado em Ciência da Computação}
\titulocurso{Bacharel em Ciência da Computação}

%------------------------------------------------------------------------------
% Dados do trabalho. ALTERE.
% Os nomes abaixo são de grandes nomes da Computação e servem só de exemplo.
% Substitua pelos nomes da sua orientação.
%------------------------------------------------------------------------------
\title{Rotas de coleta seletiva com algoritmos de caminho mínimo: um estudo de caso em Pelotas}

\author{Lovelace}{Ada}                          % ALTERE: autor(a)
\advisor[Prof.~Dr.]{Dijkstra}{Edsger W.}        % ALTERE: orientador(a)
\coadvisor[Prof.ª~Dr.ª]{Hopper}{Grace}          % ALTERE: coorientador(a), opcional

\begin{document}

% Orientadora ou coorientadora: troque o rótulo da folha de rosto.
% \renewcommand{\advisorname}{Orientadora}
\renewcommand{\coadvisorname}{Coorientadora}

\maketitle   % folha de rosto (sem capa, por ser proposta)
\sloppy      % evita linhas que ultrapassam a margem direita

%==============================================================================
\chapter{Dados de Identificação}
%==============================================================================

\section{Nome do Projeto}
Rotas de coleta seletiva com algoritmos de caminho mínimo: um estudo de caso em
Pelotas.

\section{Local de Realização}
Centro de Desenvolvimento Tecnológico, Universidade Federal de Pelotas (UFPel).

\section{Responsável pelo Projeto}
Ada Lovelace

[email protected] % ALTERE: seu e-mail

\section{Professor Orientador}
Prof. Dr. Edsger W. Dijkstra

\section{Professora Coorientadora}
% Sem coorientação, apague esta seção.
Prof.ª Dr.ª Grace Hopper

%==============================================================================
\chapter{Sumário Executivo}
% No máximo uma página.
%==============================================================================

A coleta seletiva de Pelotas segue rotas definidas pela experiência das
equipes, sem apoio de ferramentas de otimização. Em bairros com muitas ruas de
mão única, a ordem em que o caminhão visita os pontos de coleta pode aumentar
bastante a distância rodada por dia. Este projeto propõe tratar o problema
como um problema de caminho mínimo em grafos: a malha viária de cada setor de
coleta será modelada como um grafo ponderado, e o algoritmo de
\citet{Dijkstra:1959:NTP} calculará a menor rota entre a garagem e a
cooperativa de reciclagem, passando pelos pontos do setor.

O objetivo principal é verificar se as rotas calculadas são mais curtas do que
as rotas praticadas hoje. A contribuição esperada é um protótipo em Python,
aplicado a quatro setores da cidade, e uma comparação, setor a setor, entre a
distância das rotas calculadas e a das rotas atuais. Se o ganho se confirmar,
o protótipo pode servir de ponto de partida para uma ferramenta de apoio ao
planejamento da coleta.

%==============================================================================
\chapter{Histórico e Justificativa}
% No mínimo uma página.
%==============================================================================

O problema do caminho mínimo é um dos mais antigos da teoria dos grafos
aplicada à computação. Em 1959, Dijkstra publicou, em uma nota de três
páginas, o algoritmo que leva seu nome, para encontrar o menor caminho entre
dois vértices de um grafo com arestas de comprimento conhecido
\citep{Dijkstra:1959:NTP}. No mesmo período surgiram outras soluções, como a
de Bellman, que admite pesos negativos \citep{Cormen:2022:IA}. Desde então, o
algoritmo de Dijkstra é tema obrigatório dos livros de algoritmos e base de
sistemas de navegação e de roteamento em redes de computadores
\citep{Knuth:1997:ACP,Cormen:2022:IA}.

A coleta seletiva é um caso em que esse problema aparece de forma direta. O
caminhão parte da garagem, passa por pontos de coleta e leva o material até a
cooperativa de reciclagem. Cada quilômetro a mais na rota é combustível,
tempo da equipe e desgaste do veículo. Em cidades de porte médio, como
Pelotas, é comum que as rotas sejam definidas pela experiência de quem
dirige, o que funciona bem em traçados simples, mas tende a gerar desvios em
áreas com muitas ruas de mão única, como o centro histórico.

A justificativa do projeto é, portanto, prática. Um algoritmo conhecido, de
implementação simples e de custo computacional baixo, pode indicar rotas
melhores sem exigir equipamentos nem programas comerciais. O trabalho também
tem valor acadêmico para o curso: aplica conteúdos das disciplinas de
estruturas de dados e de algoritmos a um problema real da cidade, na mesma
linha de outros trabalhos da UFPel que usam a Computação para apoiar decisões
ambientais, como o de \citet{Cruz:2015:FCS}.

O que distingue esta proposta de um uso direto de aplicativos de navegação é
o foco na coleta: os pontos de coleta, a garagem e a cooperativa são vértices
fixos, e a comparação será feita com as rotas que a equipe já usa. Assim, o
resultado mede o ganho real que uma ferramenta desse tipo traria para o
serviço.

%==============================================================================
\chapter{Objetivos e Metas}
%==============================================================================

O objetivo geral é verificar se o algoritmo de Dijkstra reduz a distância
percorrida nas rotas de coleta seletiva de Pelotas.

Os objetivos específicos são:

\begin{enumerate}
  \item modelar a malha viária de quatro setores de coleta como grafos
        ponderados;
  \item implementar o algoritmo de Dijkstra e validá-lo em um grafo pequeno,
        com resultado conhecido;
  \item calcular as rotas mínimas de cada setor;
  \item comparar as rotas calculadas com as rotas praticadas pela equipe de
        coleta.
\end{enumerate}

As metas, que permitem acompanhar a execução do projeto, são:

\begin{enumerate}
  \item ter os grafos dos quatro setores conferidos com a equipe de coleta até
        maio;
  \item ter o protótipo validado até julho, junto com a entrega da monografia
        intermediária;
  \item ter a comparação dos quatro setores concluída até setembro.
\end{enumerate}

Os objetivos são resultados do trabalho, e não atividades: as atividades que
levam a cada um deles estão no Capítulo~\ref{cap:atividades}. As duas listas
acima usam alíneas, como pede o Manual (p. 71): o texto que as antecede termina
em dois pontos, cada alínea termina em ponto e vírgula e a última, em ponto.

%==============================================================================
\chapter{Metodologia}
%==============================================================================

O projeto será desenvolvido em quatro etapas, uma para cada objetivo
específico.

Na primeira, os setores de coleta serão escolhidos com a equipe responsável,
procurando incluir traçados diferentes: o centro, com quarteirões regulares e
muitas ruas de mão única, e bairros com loteamentos mais recentes. Para cada
setor, a malha viária será modelada como um grafo ponderado, com a garagem, os
pontos de coleta e a cooperativa como vértices e os trechos de rua como
arestas, com a distância em quilômetros como peso. O sentido das vias será
representado por arestas dirigidas.

Na segunda etapa, o algoritmo de Dijkstra será implementado em Python, com a
fila de prioridade do módulo \texttt{heapq}, seguindo a descrição de
\citet{Cormen:2022:IA}. A implementação será validada em um grafo pequeno,
cujas distâncias mínimas podem ser calculadas à mão.

Na terceira, o protótipo calculará a rota mínima de cada setor. Na quarta, as
rotas calculadas serão comparadas com as rotas praticadas, informadas pela
equipe de coleta, pela distância total percorrida em cada setor.

%==============================================================================
\chapter{Plano de Atividades e Cronograma}
\label{cap:atividades}
% Para um ano.
%==============================================================================

As atividades previstas são:

\begin{enumerate}
  \item revisão da literatura sobre caminho mínimo e roteamento;
  \item levantamento dos setores e das rotas praticadas, com a equipe de
        coleta;
  \item modelagem dos grafos dos setores;
  \item implementação e validação do algoritmo de Dijkstra;
  \item cálculo das rotas e comparação com as rotas praticadas;
  \item escrita da monografia;
  \item entrega da monografia intermediária;
  \item entrega da monografia final;
  \item apresentação final (banca);
  \item submissão de artigo a evento de iniciação científica (opcional).
\end{enumerate}

A Tabela~\ref{tab:cronograma} distribui as atividades ao longo de 2026,
identificadas pela letra da alínea. As
atividades de escrita, entrega e apresentação da monografia são obrigatórias,
e os meses de entrega e da banca seguem o calendário definido pelo professor
responsável pelo Trabalho de Conclusão de Curso.

% Cronograma em tabela: uma coluna para a atividade e uma para cada mês.
% A coluna da atividade usa só a letra da alínea da lista acima, para caber
% na página.
% Os meses vão abreviados conforme o Anexo A do Manual (p. 79).
\begin{table}[htbp]
  \caption{Cronograma de atividades em 2026}
  \label{tab:cronograma}
  \centering
  \setlength{\tabcolsep}{4pt}
  \begin{tabular}{l*{12}{c}}
    \hline
    Atividade & jan. & fev. & mar. & abr. & maio & jun. & jul. & ago. & set. & out. & nov. & dez. \\
    \hline
    a) & X & X & X &   &   &   &   &   &   &   &   &   \\
    b) &   & X & X & X &   &   &   &   &   &   &   &   \\
    c) &   &   &   & X & X &   &   &   &   &   &   &   \\
    d) &   &   &   &   & X & X & X &   &   &   &   &   \\
    e) &   &   &   &   &   &   &   & X & X &   &   &   \\
    f) &   &   & X & X & X & X & X & X & X & X & X &   \\
    g) &   &   &   &   &   &   & X &   &   &   &   &   \\
    h) &   &   &   &   &   &   &   &   &   &   & X &   \\
    i) &   &   &   &   &   &   &   &   &   &   &   & X \\
    j) &  &   &   &   &   &   &   &   &   & X &   &   \\
    \hline
  \end{tabular}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{table}

A tabela segue o padrão do Instituto Brasileiro de Geografia e Estatística
indicado pelo Manual (p. 17): título em cima, fonte embaixo, traços
horizontais no cabeçalho e no fim, sem traços verticais. A especificação
\verb|l*{12}{c}| cria uma coluna à esquerda e doze colunas centralizadas, uma
por mês.

%------------------------------------------------------------------------------
% Bibliografia: estilo abnt.bst e base bibliografia.bib, na raiz. Só as obras
% citadas no texto entram na lista. O título da seção segue o Manual, que usa
% a expressão "Referências" (p. 21).
%------------------------------------------------------------------------------
\bibliographystyle{abnt}
\bibliography{bibliografia}

%------------------------------------------------------------------------------
% Assinaturas da proponente e do orientador.
%------------------------------------------------------------------------------
\chapter*{Assinaturas}

\vspace{2cm}

\begin{center}
\rule{8cm}{.3mm}

Ada Lovelace\\          % ALTERE
Proponente
\end{center}

\vspace{3cm}

\begin{center}
\rule{8cm}{.3mm}

Prof. Dr. Edsger W. Dijkstra\\   % ALTERE
Orientador
\end{center}

\end{document}

%==============================================================================
% Exemplo de Trabalho de Conclusão de Curso (TCC) com a classe texufpel
%
% Este arquivo é ao mesmo tempo um TCC fictício e um manual de uso da classe:
% o texto de cada seção explica o recurso que aparece nela. Para começar o seu
% trabalho, copie este arquivo, troque os dados do preâmbulo (os comentários
% "ALTERE" indicam o que mudar) e substitua o texto dos capítulos.
%
% Compilação (a partir da pasta raiz do repositório, onde estão a classe, o
% estilo abnt.bst, o bibliografia.bib e a pasta imagens/):
%   pdflatex tcc/exemplo-tcc
%   bibtex   exemplo-tcc
%   pdflatex tcc/exemplo-tcc
%   pdflatex tcc/exemplo-tcc
%
% As páginas citadas nos comentários são as do Manual de normas UFPel para
% trabalhos acadêmicos (2023).
%==============================================================================

% Opções da classe:
%   tcc   trabalho de conclusão de curso (use diss, tese, eq, tcc-proposta...
%         para os outros tipos)
%   capa  gera a capa (obrigatória no trabalho depositado, Manual, p. 12)
\documentclass[tcc,capa]{texufpel}

%------------------------------------------------------------------------------
% Pacotes usados neste exemplo. Nenhum é obrigatório: carregue só o que o seu
% trabalho usar. A classe já carrega graphicx, hyperref, natbib e caption.
%------------------------------------------------------------------------------
\usepackage{amsmath}        % equações alinhadas (align) e \eqref
\usepackage{algpseudocode}  % pseudocódigo (ambiente algorithmic)
\usepackage{listings}       % listagens de código-fonte
\usepackage{pdfcomment}     % \pdftooltip: dica com o significado da sigla

% Referência completa em nota de rodapé (\footcite). O Manual adota o sistema
% autor-data (p. 62); use este recurso só se o curso pedir.
\usepackage{bibentry}
\nobibliography*
\newcommand{\footcite}[1]{\footnote{\bibentry{#1}}}

% Palavras do pseudocódigo em português
\algrenewcommand\algorithmicrequire{\textbf{Entrada:}}
\algrenewcommand\algorithmicensure{\textbf{Saída:}}
\algrenewcommand\algorithmicfor{\textbf{para}}
\algrenewcommand\algorithmicforall{\textbf{para cada}}
\algrenewcommand\algorithmicdo{\textbf{faça}}
\algrenewcommand\algorithmicwhile{\textbf{enquanto}}
\algrenewcommand\algorithmicif{\textbf{se}}
\algrenewcommand\algorithmicthen{\textbf{então}}
\algrenewcommand\algorithmicend{\textbf{fim}}
\algrenewcommand\algorithmicreturn{\textbf{retorne}}

% Aparência das listagens de código: fonte monoespaçada pequena, linhas
% numeradas e acentos aceitos nos comentários.
\lstset{
  basicstyle=\ttfamily\footnotesize,
  numbers=left, numberstyle=\tiny, numbersep=6pt,
  frame=single, columns=fullflexible, keepspaces=true,
  breaklines=true, showstringspaces=false, tabsize=2,
  literate={á}{{\'a}}1 {é}{{\'e}}1 {í}{{\'i}}1 {ó}{{\'o}}1 {ú}{{\'u}}1
           {â}{{\^a}}1 {ê}{{\^e}}1 {ô}{{\^o}}1 {ã}{{\~a}}1 {õ}{{\~o}}1
           {ç}{{\c{c}}}1 {à}{{\`a}}1 {Á}{{\'A}}1 {É}{{\'E}}1 {Ç}{{\c{C}}}1
}

%------------------------------------------------------------------------------
% Dados institucionais. ALTERE para o seu curso.
% Se a unidade for feminina (Faculdade, Escola), use \unidade[a]{...}: a
% folha de rosto passa a dizer "apresentado à Faculdade" (Manual, p. 86).
%------------------------------------------------------------------------------
\unidade{Centro de Desenvolvimento Tecnológico}
\curso{Ciência da Computação}
\nomecurso{Bacharelado em Ciência da Computação}
\titulocurso{Bacharel em Ciência da Computação}

% Versões em inglês, usadas na referência do abstract. Com a opção english
% (trabalho escrito em inglês), também na capa, na folha de rosto e na folha
% de aprovação; \titulocursoeng é o título obtido, em inglês.
\unidadeeng{Technology Development Center}
\cursoeng{Computer Science}
\nomecursoeng{Bachelor's Degree in Computer Science}
\titulocursoeng{Bachelor of Computer Science}

%------------------------------------------------------------------------------
% Dados do trabalho. ALTERE.
% \author{Sobrenome}{Prenomes}: o sobrenome vai em maiúsculas na referência
% do trabalho, no resumo e no abstract.
% \advisor[título]{Sobrenome}{Prenomes}, e o mesmo para \coadvisor.
%
% Os nomes abaixo são de grandes nomes da Computação e servem só de exemplo.
% Substitua pelos nomes da sua orientação e da sua banca.
%------------------------------------------------------------------------------
\title{Rotas de coleta seletiva com algoritmos de caminho mínimo: um estudo de caso em Pelotas}

\author{Lovelace}{Ada}                          % ALTERE: autor(a)
\advisor[Prof.~Dr.]{Dijkstra}{Edsger W.}        % ALTERE: orientador(a)
\coadvisor[Prof.ª~Dr.ª]{Hopper}{Grace}          % ALTERE: coorientador(a), opcional

% Palavras-chave: iniciais minúsculas (exceto nomes próprios), separadas por
% ponto e vírgula, a última terminada em ponto (Manual, p. 15). Até 10.
\keyword{algoritmo de Dijkstra;}
\keyword{caminho mínimo;}
\keyword{coleta seletiva;}
\keyword{grafos;}
\keyword{logística urbana.}

\keywordeng{Dijkstra's algorithm;}
\keywordeng{shortest path;}
\keywordeng{selective waste collection;}
\keywordeng{graphs;}
\keywordeng{urban logistics.}

\begin{document}

% Orientadora ou coorientadora: troque o rótulo. Com mais de uma pessoa,
% troque também o plural (\advisorsname, \coadvisorsname).
% \renewcommand{\advisorname}{Orientadora}
\renewcommand{\coadvisorname}{Coorientadora}

\maketitle   % capa e folha de rosto

% Ficha catalográfica: sem argumento, gera uma página provisória. Quando a
% biblioteca enviar a ficha em PDF, use \fichacatalografica[ficha.pdf]
% (Manual, p. 12).
\fichacatalografica

%------------------------------------------------------------------------------
% Folha de aprovação (Manual, p. 13 e 90). O argumento é a data da defesa.
% ALTERE os nomes, a titulação e a instituição de cada membro da banca.
%------------------------------------------------------------------------------
\begin{aprovacao}{15 de dezembro de 2026}
\noindent Prof. Dr. Edsger W. Dijkstra (Orientador)\\
Doutor pela Universidade de Amsterdã\\[1cm]

\noindent Prof. Dr. Donald E. Knuth\\
Doutor em Matemática pelo California Institute of Technology\\[1cm]

\noindent Prof.ª Dr.ª Barbara Liskov\\
Doutora em Ciência da Computação pela Stanford University
\end{aprovacao}

% Elementos opcionais: dedicatória, agradecimentos e epígrafe
\begin{dedicatoria}
Às equipes de coleta seletiva, que percorrem a cidade todos os dias.
\end{dedicatoria}

\begin{agradecimentos}
Ao professor Edsger W. Dijkstra, pela orientação paciente e pelas perguntas
que me obrigaram a reescrever o capítulo de metodologia três vezes.

À professora Grace Hopper, pela coorientação e pela ajuda com o protótipo.

Aos colegas do curso, que testaram as primeiras versões das rotas.
\end{agradecimentos}

% A epígrafe é uma citação com indicação de autoria (Manual, p. 14). A obra
% citada entra nas referências.
\begin{epigrafe}
I propose to consider the question, ‘Can machines think?’\\
\hspace*{\fill}\citep[p.~433]{Turing:1950:CMI}
\end{epigrafe}

%------------------------------------------------------------------------------
% Resumo: de 150 a 500 palavras, parágrafo único, voz ativa, terceira pessoa
% do singular, sem citações nem siglas (Manual, p. 14). A referência do
% trabalho, acima do texto, é gerada pela classe.
%------------------------------------------------------------------------------
\begin{abstract}
A coleta seletiva em cidades de porte médio costuma seguir rotas definidas
pela experiência das equipes, sem apoio de ferramentas de otimização. Este
trabalho investiga se algoritmos clássicos de caminho mínimo podem reduzir a
distância percorrida pelos caminhões de coleta em Pelotas, no Rio Grande do
Sul. A malha viária de quatro setores de coleta foi modelada como um grafo
ponderado, em que os vértices representam pontos de coleta, a garagem e a
cooperativa de reciclagem, e o peso de cada aresta corresponde à distância
em quilômetros. Sobre esse modelo, aplicou-se o algoritmo de Dijkstra,
implementado em Python, para calcular a menor rota entre a garagem e a
cooperativa passando pelos pontos de cada setor. As rotas obtidas foram
comparadas com as rotas praticadas pela equipe de coleta. Nos quatro setores,
as rotas calculadas foram mais curtas, com redução média de 13,5\% na
distância percorrida, e a maior economia ocorreu no setor com mais
cruzamentos de mão única. O estudo mostra que um algoritmo conhecido desde
1959, de implementação simples, já oferece ganho mensurável na logística da
coleta, desde que o grafo represente com fidelidade o sentido das vias. Como
limitação, o modelo considera apenas a distância e ignora o tempo de parada
em cada ponto, o que fica como sugestão para trabalhos futuros.
\end{abstract}

% Abstract: tradução do resumo; o argumento é o título em inglês.
\begin{englishabstract}{Selective waste collection routes with shortest path algorithms: a case study in Pelotas}
Selective waste collection in medium-sized cities usually follows routes set
by the crews' experience, without the support of optimization tools. This
work investigates whether classical shortest path algorithms can reduce the
distance covered by collection trucks in Pelotas, in the state of Rio Grande
do Sul, Brazil. The road network of four collection sectors was modeled as a
weighted graph, in which vertices represent collection points, the garage and
the recycling cooperative, and the weight of each edge is the distance in
kilometers. On this model, Dijkstra's algorithm, implemented in Python, was
applied to compute the shortest route between the garage and the cooperative
through the points of each sector. The resulting routes were compared with
the routes currently used by the collection crew. In all four sectors, the
computed routes were shorter, with an average reduction of 13.5\% in the
distance covered, and the largest saving occurred in the sector with the most
one-way intersections. The study shows that an algorithm known since 1959,
simple to implement, already yields a measurable gain in collection
logistics, as long as the graph faithfully represents the direction of the
streets. As a limitation, the model considers only distance and ignores the
stopping time at each point, which is left as a suggestion for future work.
\end{englishabstract}

% Listas: entram depois do abstract e antes do sumário, nesta ordem.
\listoffigures
\listofquadros   % quadros numerados como Figura, em lista própria (Manual, p. 16)
\listoftables

% Lista de abreviaturas e siglas, em ordem alfabética (Manual, p. 18).
% O argumento é a sigla mais longa, para alinhar a coluna dos significados.
\begin{listofabbrv}{UFPel}
  \item[IBGE]  Instituto Brasileiro de Geografia e Estatística
  \item[SBC]   Sociedade Brasileira de Computação
  \item[TCC]   Trabalho de Conclusão de Curso
  \item[UFPel] Universidade Federal de Pelotas
\end{listofabbrv}

\tableofcontents

%==============================================================================
\chapter{Introdução}
\label{cap:introducao}
%==============================================================================

A coleta seletiva de Pelotas atende bairros com traçados bem diferentes: o
centro histórico tem quarteirões regulares e muitas ruas de mão única, enquanto
os bairros mais novos crescem em loteamentos com poucas ligações entre si.
Em ambos os casos, a ordem em que o caminhão visita os pontos de coleta define
quantos quilômetros ele roda por dia. Este trabalho trata esse problema como
um problema de caminho mínimo em grafos e testa o algoritmo de
\citet{Dijkstra:1959:NTP} sobre dados de quatro setores de coleta.

Este documento também é o exemplo de Trabalho de Conclusão de Curso
(\pdftooltip{TCC}{Trabalho de Conclusão de Curso}) da classe
\texttt{texufpel}. Cada seção usa um recurso da classe e
explica, no próprio texto, como ele foi feito. Os elementos que aparecem antes
desta página (capa, folha de rosto, ficha catalográfica, folha de aprovação,
dedicatória, agradecimentos, epígrafe, resumo, abstract, listas e sumário)
seguem a ordem do Manual de normas da Universidade Federal de Pelotas
(\pdftooltip{UFPel}{Universidade Federal de Pelotas}) e são gerados pelos comandos do
preâmbulo e pelos ambientes do início do arquivo \texttt{exemplo-tcc.tex}.

Siglas são escritas por extenso na primeira vez em que aparecem, com a sigla
entre parênteses, e entram na lista de abreviaturas e siglas (Manual, p. 18).
No parágrafo anterior, a sigla foi escrita com
\verb|\pdftooltip{TCC}{Trabalho de...}|, do pacote \texttt{pdfcomment}, que
mostra o significado quando o leitor passa o mouse sobre ela no PDF. É um recurso de leitura na tela e não substitui a escrita por extenso
na primeira ocorrência.

\section{Objetivos}
\label{sec:objetivos}

O objetivo geral é verificar se o algoritmo de Dijkstra reduz a distância
percorrida nas rotas de coleta seletiva de Pelotas. Os objetivos específicos
são:

\begin{enumerate}
  \item modelar a malha viária de quatro setores de coleta como um grafo
        ponderado;
  \item implementar o algoritmo de Dijkstra e validá-lo em um grafo pequeno;
  \item comparar as rotas calculadas com as rotas praticadas pela equipe:
  \begin{enumerate}
    \item pela distância total percorrida;
    \item pela quantidade de conversões à esquerda.
  \end{enumerate}
\end{enumerate}

A lista acima segue as regras de alíneas do Manual (p. 71): o texto que a
antecede termina em dois pontos, cada alínea começa com letra minúscula e
termina em ponto e vírgula, e a última termina em ponto. A classe formata o
primeiro nível do ambiente \texttt{enumerate} como alíneas, com a), b), c), e o
segundo nível como subalíneas, com travessão. A pontuação fica por conta de
quem escreve.

\section{Organização do texto}

O Capítulo~\ref{cap:fundamentacao} apresenta os conceitos de grafos e o
algoritmo de Dijkstra e mostra as formas de citação. O
Capítulo~\ref{cap:metodologia} descreve como os dados foram obtidos e como o
protótipo foi construído, com exemplos de figura, quadro e listagem de código.
O Capítulo~\ref{cap:resultados} traz os resultados em tabela e mostra a
numeração das seções até o quinto nível. O Capítulo~\ref{cap:consideracoes}
encerra o trabalho. Os números dos capítulos neste parágrafo foram gerados com
\verb|\label| e \verb|\ref|: se um capítulo mudar de lugar, as referências
cruzadas se atualizam na próxima compilação.

%==============================================================================
\chapter{Fundamentação teórica}
\label{cap:fundamentacao}
%==============================================================================

\section{Citações}
\label{sec:citacoes}

Este capítulo usa as formas de citação do Manual (p. 62-67). Todas seguem o
sistema autor-data e são feitas com dois comandos do pacote \texttt{natbib}:

\begin{lstlisting}[language={[LaTeX]TeX}, numbers=none]
\cite{Codd:1970:RMD}     % (Codd, 1970)    citação entre parênteses
\citet{Codd:1970:RMD}    % Codd (1970)     autor como parte da frase
\cite[p.~380]{Codd:1970:RMD}   % (Codd, 1970, p. 380)
\end{lstlisting}

A citação indireta reproduz a ideia do autor com outras palavras. O modelo
relacional, por exemplo, propõe que os dados sejam vistos como relações
matemáticas, independentes da forma como estão armazenados
\citep{Codd:1970:RMD}. Quando o autor faz parte da frase, o ano vem entre
parênteses logo depois do nome: \citet{Lamport:1978:TCO} mostrou que, em um
sistema distribuído, a ordem dos eventos pode ser definida sem relógio
global.

Várias obras na mesma citação ficam separadas por ponto e vírgula, de
preferência em ordem alfabética \citep{Hoare:1969:ABC,Lamport:1978:TCO}.
Obras do mesmo autor em anos diferentes aparecem com os anos separados por
vírgula, como em \citet{Turing:1937:OCN,Turing:1950:CMI}. Com quatro ou mais
autores, a citação usa o primeiro seguido de et al. \citep{Cormen:2022:IA}.

A citação direta curta, de até três linhas, fica entre aspas no corpo do
texto, com a página. Para a Sociedade Brasileira de Computação
(\pdftooltip{SBC}{Sociedade Brasileira de Computação}), ``Os cientistas da
computação são responsáveis pela pesquisa e desenvolvimento em Computação''
\citep[p.~30]{Zorzo:2017:RFC}.

A citação direta longa, com mais de três linhas, usa o ambiente
\texttt{quote}. A classe aplica o recuo de 4~cm, a letra tamanho 10 e o espaço
simples que o Manual pede (p. 63). O trecho abaixo foi traduzido de um
documento em inglês, e por isso a chamada termina com ``tradução nossa''
(Manual, p. 66):

\begin{quote}
O protocolo internet é limitado, por definição, às funções necessárias para
entregar um pacote de bits (um datagrama internet) de uma origem a um destino
por meio de um sistema de redes interconectadas. Não há mecanismos para
aumentar a confiabilidade dos dados de ponta a ponta, nem para controle de
fluxo, sequenciamento ou outros serviços comuns em protocolos entre
hospedeiros. O protocolo internet pode tirar proveito dos serviços de suas
redes de suporte para oferecer vários tipos e níveis de serviço
\citep[p.~1, tradução nossa]{Postel:1981:IP}.
\end{quote}

A citação de citação usa a expressão apud. Na lista de referências entra só a
obra consultada (Manual, p. 65). Uma das origens do algoritmo de Bellman-Ford é um
trabalho de 1958 sobre roteamento, que não consultamos diretamente:
\apud{Bellman}{1958}{Cormen:2022:IA} trata do caminho mínimo em grafos que
admitem pesos negativos. Entre parênteses, a mesma citação fica
\apudp{Bellman}{1958}{Cormen:2022:IA}. Os comandos \verb|\apud| e
\verb|\apudp| são da classe; o autor e o ano da obra original são escritos à
mão para que ela não vá para as referências.

Se o curso pedir a referência completa em nota de rodapé, use o comando
\verb|\footcite|, definido no preâmbulo deste arquivo. Ele coloca a referência
no pé da página\footcite{Postel:1981:IP}, e a obra continua na lista de
referências.

\section{Grafos e caminhos mínimos}
\label{sec:grafos}

Um grafo ponderado é um par $G = (V, E)$, em que $V$ é o conjunto de vértices
e $E$ o conjunto de arestas, com uma função de peso $w$ que associa a cada
aresta um número real não negativo \citep{Cormen:2022:IA}. O custo de um
caminho $p = \langle v_0, v_1, \dots, v_k \rangle$ é a soma dos pesos de suas
arestas:
\begin{equation}
  w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i).
  \label{eq:custo}
\end{equation}

A distância mínima $\delta(s, v)$ entre dois vértices é o menor custo entre
todos os caminhos que os ligam. O algoritmo de Dijkstra mantém uma estimativa
$d[v]$ dessa distância e a melhora por um passo chamado relaxamento, que
testa se passar por $u$ encurta o caminho até $v$:
\begin{align}
  \delta(s, v) &= \min \{\, w(p) : p \text{ é um caminho de } s \text{ até } v \,\},
  \label{eq:delta}\\
  d[v] &\leftarrow \min \{\, d[v],\; d[u] + w(u, v) \,\}.
  \label{eq:relax}
\end{align}

As equações são numeradas com algarismos arábicos entre parênteses, alinhados
à direita (Manual, p. 76). A Equação~\eqref{eq:custo} foi escrita com o
ambiente \texttt{equation}; as Equações~\eqref{eq:delta} e~\eqref{eq:relax},
com \texttt{align}, que alinha as linhas pelo símbolo marcado com \verb|&|.
Para citar uma equação, use \verb|\eqref{rótulo}|.

\section{O algoritmo de Dijkstra}
\label{sec:dijkstra}

O algoritmo resolve o problema do caminho mínimo de origem única quando todos
os pesos são não negativos \citep{Dijkstra:1959:NTP}. A cada passo, ele retira
da fila de prioridade o vértice com a menor estimativa de distância e relaxa
as arestas que saem dele, como mostra a Figura~\ref{fig:dijkstra}.

\begin{figure}[htbp]
  \caption{Pseudocódigo do algoritmo de Dijkstra}
  \label{fig:dijkstra}
  \begin{algorithmic}[1]
    \Require grafo $G = (V, E)$, pesos $w$ não negativos, origem $s$
    \Ensure distâncias $d[v]$ e predecessores $\pi[v]$ para todo $v \in V$
    \ForAll{$v \in V$}
      \State $d[v] \gets \infty$; \quad $\pi[v] \gets \text{nulo}$
    \EndFor
    \State $d[s] \gets 0$
    \State $Q \gets V$ \Comment{fila de prioridade pela chave $d$}
    \While{$Q \neq \emptyset$}
      \State $u \gets$ vértice de $Q$ com menor $d[u]$; remova $u$ de $Q$
      \ForAll{$v$ adjacente a $u$}
        \If{$d[v] > d[u] + w(u, v)$}
          \State $d[v] \gets d[u] + w(u, v)$; \quad $\pi[v] \gets u$
        \EndIf
      \EndFor
    \EndWhile
    \State \Return $d, \pi$
  \end{algorithmic}
  \caption*{Fonte: Adaptado de \citet{Cormen:2022:IA}.}
\end{figure}

O Manual chama de Figura toda ilustração, inclusive esquemas e algoritmos
(p. 16). Por isso o pseudocódigo está dentro de um ambiente \texttt{figure},
com a legenda em cima e a fonte embaixo, e aparece na lista de figuras. O
pseudocódigo foi escrito com o ambiente \texttt{algorithmic}, do pacote
\texttt{algpseudocode}; as palavras-chave em português estão definidas no
preâmbulo deste arquivo.

\section{Outros algoritmos de caminho mínimo}
\label{sec:outros}

Há outros algoritmos para o mesmo problema, cada um com suas restrições. A
Figura~\ref{qua:algoritmos} compara três deles.

\begin{quadro}[htbp]
  \caption{Comparação entre algoritmos de caminho mínimo}
  \label{qua:algoritmos}
  \centering
  \begin{tabular}{|p{2.8cm}|p{2.6cm}|p{4.4cm}|p{4.2cm}|}
    \hline
    \textbf{Algoritmo} & \textbf{Problema} & \textbf{Pesos negativos} & \textbf{Tempo} \\ \hline
    Dijkstra       & origem única       & não aceita & $O((V + E) \log V)$ com heap binário \\ \hline
    Bellman-Ford   & origem única       & aceita e detecta ciclos negativos & $O(VE)$ \\ \hline
    Floyd-Warshall & todos os pares     & aceita, sem ciclos negativos & $\Theta(V^3)$ \\ \hline
  \end{tabular}
  \caption*{Fonte: Elaborado pela autora (2026), com base em \citet{Cormen:2022:IA}.}
\end{quadro}

Um quadro organiza informações textuais e tem as bordas fechadas, ao
contrário da tabela, que apresenta dados numéricos. O Manual não usa o nome
``Quadro'' na legenda: todo quadro é uma Figura, mas pode ter lista própria
quando houver muitos (p. 16). O ambiente \texttt{quadro} da classe faz
exatamente isso: numera junto com as figuras e manda o item para a Lista de
Quadros, gerada por \verb|\listofquadros|.

\section{Trabalhos relacionados}

Na própria UFPel, \citet{Cruz:2015:FCS} desenvolveu uma ferramenta
computacional para simular a dispersão de poluentes na atmosfera, um exemplo
de como a Computação apoia decisões ambientais da cidade. Este trabalho segue
a mesma linha, aplicada à logística da coleta.

%==============================================================================
\chapter{Metodologia}
\label{cap:metodologia}
%==============================================================================

\section{Modelagem da malha viária}

Cada setor de coleta foi modelado como um grafo: os vértices são a garagem
(D), os pontos de coleta (P1 a P4) e a cooperativa de reciclagem (C); as
arestas são os trechos de rua entre eles, com a distância em quilômetros. Os
trajetos foram conferidos com a equipe de coleta\footnote{Informação fornecida
pela equipe de coleta do setor 1 em conversa com a autora, em agosto de 2026
(informação verbal). Exemplo fictício de nota de referência para dados não
publicados (Manual, p. 69).}. A Figura~\ref{fig:grafo} mostra o grafo de um
dos setores, com a rota mínima em destaque.

\begin{figure}[htbp]
  \caption{Grafo de um setor de coleta, com a rota mínima de D até C em destaque}
  \label{fig:grafo}
  \centering
  \includegraphics[width=0.75\textwidth]{imagens/grafo-coleta.pdf}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{figure}

A figura foi inserida com o código abaixo. A legenda vem antes da imagem,
porque o Manual pede a identificação na parte superior, com o número, um
travessão e o título sem ponto final (p. 16). Abaixo da imagem vai a fonte,
obrigatória mesmo quando a figura é da própria autora (p. 17). A classe deixa
a legenda e a fonte em tamanho 10 e espaço simples.

\begin{lstlisting}[language={[LaTeX]TeX}, numbers=none]
\begin{figure}[htbp]
  \caption{Grafo de um setor de coleta, com a rota mínima de D até C em destaque}
  \label{fig:grafo}
  \centering
  \includegraphics[width=0.75\textwidth]{imagens/grafo-coleta.pdf}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{figure}
\end{lstlisting}

O caminho da imagem é relativo à pasta onde o documento é compilado, que é a
raiz do repositório. Se a figura vier de outra obra, a fonte traz a citação,
por exemplo \verb|\caption*{Fonte: \citet{Cormen:2022:IA}.}|, e a obra entra nas
referências (Manual, p. 17).

\section{Implementação}

O protótipo foi escrito em Python, com a fila de prioridade do módulo
\texttt{heapq}. A Figura~\ref{fig:codigo} mostra a função principal, aplicada
ao grafo da Figura~\ref{fig:grafo}. Ao ser executada, ela imprime a distância
13 e o caminho D, P2, P1, P3, P4, C.

\begin{figure}[htbp]
  \caption{Implementação do algoritmo de Dijkstra em Python}
  \label{fig:codigo}
\begin{lstlisting}[language=Python]
import heapq

def dijkstra(grafo, origem):
    dist = {v: float("inf") for v in grafo}
    anterior = {v: None for v in grafo}
    dist[origem] = 0
    fila = [(0, origem)]
    while fila:
        d_u, u = heapq.heappop(fila)
        if d_u > dist[u]:
            continue  # entrada antiga da fila
        for v, peso in grafo[u].items():
            if dist[u] + peso < dist[v]:
                dist[v] = dist[u] + peso
                anterior[v] = u
                heapq.heappush(fila, (dist[v], v))
    return dist, anterior

grafo = {
    "D":  {"P1": 4, "P2": 2},
    "P1": {"D": 4, "P2": 1, "P3": 5},
    "P2": {"D": 2, "P1": 1, "P3": 8, "P4": 10},
    "P3": {"P1": 5, "P2": 8, "P4": 2, "C": 6},
    "P4": {"P2": 10, "P3": 2, "C": 3},
    "C":  {"P3": 6, "P4": 3},
}
dist, anterior = dijkstra(grafo, "D")
caminho, v = [], "C"
while v is not None:
    caminho.append(v)
    v = anterior[v]
print(dist["C"], caminho[::-1])  # 13 ['D', 'P2', 'P1', 'P3', 'P4', 'C']
\end{lstlisting}
  \caption*{Fonte: Elaborada pela autora (2026).}
\end{figure}

A listagem foi feita com o ambiente \texttt{lstlisting}, do pacote
\texttt{listings}, dentro de um ambiente \texttt{figure}: assim como o
pseudocódigo, o código-fonte é uma ilustração e recebe o nome de Figura. O
estilo das listagens (fonte, numeração de linhas, moldura e acentos) está no
comando \verb|\lstset| do preâmbulo.

\section{Uso de inteligência artificial}

Na elaboração deste trabalho, utilizou-se a ferramenta de inteligência
artificial generativa [nome e versão da ferramenta], entre [mês/ano] e
[mês/ano], exclusivamente para [finalidades, por exemplo: revisão ortográfica
e tradução do resumo para a língua inglesa]. A ferramenta não foi utilizada
para gerar dados, análises, interpretações ou conclusões. Todo o conteúdo
sugerido foi revisado, editado e validado pela autora, que assume integral
responsabilidade pelo texto final, pela exatidão das informações e pela
autoria intelectual do trabalho.

O parágrafo acima é o modelo de declaração da pasta \texttt{instruções/} do
repositório. Se usar uma ferramenta desse tipo, preencha os trechos entre
colchetes; se não usar, apague a seção.

%==============================================================================
\chapter{Resultados}
\label{cap:resultados}
%==============================================================================

A Tabela~\ref{tab:resultados} compara a distância das rotas praticadas com a
das rotas calculadas nos quatro setores.

\begin{table}[htbp]
  \caption{Distância percorrida por setor, em quilômetros}
  \label{tab:resultados}
  \centering
  \begin{tabular}{lrrr}
    \hline
    Setor & Rota praticada & Rota calculada & Redução (\%) \\
    \hline
    1 -- Centro      & 18,6 & 15,2 & 18,3 \\
    2 -- Fragata     & 22,4 & 19,8 & 11,6 \\
    3 -- Três Vendas & 25,1 & 22,0 & 12,4 \\
    4 -- Areal       & 20,3 & 17,9 & 11,8 \\
    \hline
    Média            & 21,6 & 18,7 & 13,5 \\
    \hline
  \end{tabular}
  \caption*{Fonte: Elaborada pela autora (2026), com dados fictícios para fins de exemplo.}
\end{table}

A tabela segue a padronização do Instituto Brasileiro de Geografia e
Estatística (\pdftooltip{IBGE}{Instituto Brasileiro de Geografia e Estatística}),
indicada pelo Manual (p. 17): traços
horizontais no cabeçalho e no fim, sem traços verticais e sem fechar as
laterais. O título vai em cima e a fonte embaixo, como nas figuras. Valores
numéricos ficam alinhados à direita (\texttt{r} na especificação das
colunas).

\section{Análise por setor}

O setor 1 teve a maior redução. É o setor com mais ruas de mão única, e a rota
praticada fazia retornos longos que o algoritmo evitou.

\subsection{Setores com traçado regular}

Esta é uma seção terciária. A classe numera as seções até o quinto nível,
como pede o Manual (p. 70), e todas aparecem no sumário em negrito.

\subsubsection{Setor 1 -- Centro}

Esta é uma seção quaternária, criada com \verb|\subsubsection|.

\paragraph{Trecho entre a garagem e o primeiro ponto}

Esta é uma seção quinária, criada com \verb|\paragraph|. Não use níveis abaixo
deste: o Manual limita a numeração progressiva à seção quinária.

%==============================================================================
\chapter{Considerações finais}
\label{cap:consideracoes}
%==============================================================================

O algoritmo de Dijkstra reduziu a distância percorrida nos quatro setores
estudados, com redução média de 13,5\% (Tabela~\ref{tab:resultados}). O ganho
foi maior onde as ruas de mão única tornam a rota intuitiva mais longa. O
modelo ainda ignora o tempo de parada em cada ponto e as restrições de
horário, que podem ser tratados em trabalhos futuros com variações do problema
de roteamento de veículos.

Os apêndices trazem material produzido pela autora: o Apêndice~\ref{apx:dados}
lista os dados do grafo, e o Apêndice~\ref{apx:referencias} mostra como
cadastrar cada tipo de referência. O Anexo~\ref{anx:meses} reproduz material de
outra autoria.

%------------------------------------------------------------------------------
% Referências: estilo abnt.bst e base bibliografia.bib, ambos na raiz.
%------------------------------------------------------------------------------
\bibliographystyle{abnt}
\bibliography{bibliografia}

%------------------------------------------------------------------------------
% Apêndices: material elaborado pela própria autora (Manual, p. 23).
% \apendices cria a folha de abertura; cada \chapter vira "Apêndice A – ...".
%------------------------------------------------------------------------------
\apendices

\chapter{Dados do grafo de exemplo}
\label{apx:dados}

O grafo da Figura~\ref{fig:grafo} tem seis vértices e nove arestas. Os pesos
são as distâncias em quilômetros usadas no código da
Figura~\ref{fig:codigo}: D--P1, 4; D--P2, 2; P1--P2, 1; P1--P3, 5; P2--P3, 8;
P2--P4, 10; P3--P4, 2; P3--C, 6; P4--C, 3. As distâncias mínimas a partir de
D, calculadas pelo algoritmo, são: P2, 2; P1, 3; P3, 8; P4, 10; C, 13.

Apêndices e anexos são numerados com letras e citados no texto pelo nome
seguido da letra, como Apêndice~\ref{apx:referencias} (Manual, p. 23).

\chapter{Exemplos de referências por tipo de documento}
\label{apx:referencias}

Este apêndice cita todas as entradas do arquivo \texttt{bibliografia.bib},
para que a lista de referências deste exemplo mostre como o estilo
\texttt{abnt.bst} formata cada tipo. O arquivo traz, acima de cada entrada, um
comentário explicando quando usar aquele tipo.

Artigos de periódico usam o tipo \texttt{article}:
\citet{Turing:1937:OCN}, \citet{Turing:1950:CMI}, \citet{Shannon:1948:MTC},
\citet{Dijkstra:1959:NTP}, \citet{Dijkstra:1968:GTS}, \citet{Hoare:1969:ABC},
\citet{Codd:1970:RMD}, \citet{Lamport:1978:TCO},
\citet{Dantzig:1959:TDP} e \citet{Solomon:1987:AVR}.

Trabalhos acadêmicos usam \texttt{mastersthesis}, para TCC e dissertação, como
\citet{Cruz:2015:FCS} e \citet{Shannon:1940:SAR}, e \texttt{phdthesis}, para
tese, como \citet{Turing:1938:SLO}. Relatórios técnicos usam
\texttt{techreport}: \citet{vonNeumann:1945:FDR} e \citet{Postel:1981:IP}.

Livros usam \texttt{book}: \citet{vonNeumann:1966:TSR},
\citet{Knuth:1997:ACP}, \citet{Cormen:2022:IA}, \citet{Brooks:1975:MMM},
\citet{Abelson:1996:SIC} e \citet{Moore:1979:MAI}. Um capítulo de livro do
mesmo autor usa \texttt{inbook} \citep{Knuth:1997:IS}; um capítulo de livro
organizado por outra pessoa, \texttt{incollection}
\citep{vonNeumann:1951:GLT}.

Trabalhos publicados em anais de eventos usam \texttt{inproceedings}
\citep{Cook:1971:CTP}; os anais no todo, \texttt{proceedings}
\citep{ACM:1971:STOC}. Normas técnicas usam \texttt{manual}
\citep{ABNT:2018:NBR6023}. Folhetos usam \texttt{booklet}
\citep{Zorzo:2017:RFC}, e documentos não publicados, \texttt{unpublished}
\citep{Dijkstra:1988:CRT}.

Os demais documentos usam \texttt{misc}: preprint
\citep{Vaswani:2017:AIA}, página da web \citep{ACM:2026:TA}, programa de
computador \citep{Aguiar:2026:TEX}, legislação \citep{Brasil:2015:LBI} e
conjunto de dados \citep{Fisher:1936:IRI}.

%------------------------------------------------------------------------------
% Anexos: material de outra autoria (Manual, p. 23-24).
%------------------------------------------------------------------------------
\anexos

\chapter{Abreviatura dos meses em português}
\label{anx:meses}

\begin{table}[htbp]
  \caption{Abreviatura dos meses em português}
  \centering
  \begin{tabular}{llll}
    \hline
    Mês & Abreviatura & Mês & Abreviatura \\
    \hline
    janeiro   & jan.  & julho    & jul. \\
    fevereiro & fev.  & agosto   & ago. \\
    março     & mar.  & setembro & set. \\
    abril     & abr.  & outubro  & out. \\
    maio      & maio  & novembro & nov. \\
    junho     & jun.  & dezembro & dez. \\
    \hline
  \end{tabular}
  \caption*{Fonte: \citet{ABNT:2018:NBR6023}.}
\end{table}

\end{document}

42 KB — too long to show here. It arrives with the project.

53 KB — too long to show here. It arrives with the project.

%==============================================================================
% Exemplo de Trabalho Individual com a classe texufpel
%
% O tema é o mesmo do exemplo de exame de qualificação
% (qualificação/exemplo-qualificacao.tex): o roteamento da coleta seletiva de
% Pelotas com janelas de tempo. Aqui ele aparece como trabalho individual de
% doutorado, uma revisão da base teórica feita antes da qualificação. O texto
% de cada seção explica o recurso que aparece nela. As particularidades do
% trabalho individual estão marcadas com "TRABALHO INDIVIDUAL" nos
% comentários.
% Para começar o seu trabalho, copie este arquivo, troque os dados do
% preâmbulo (os comentários "ALTERE" indicam o que mudar) e substitua o texto
% dos capítulos.
%
% Compilação (a partir da pasta raiz do repositório, onde estão a classe, o
% estilo abnt.bst, o bibliografia.bib e a pasta imagens/):
%   pdflatex trabalho-individual/exemplo-ti
%   bibtex   exemplo-ti
%   pdflatex trabalho-individual/exemplo-ti
%   pdflatex trabalho-individual/exemplo-ti
% principal.
%
% As páginas citadas nos comentários são as do Manual de normas UFPel para
% trabalhos acadêmicos (2023).
%==============================================================================

% Opções da classe:
%   tid  trabalho individual de doutorado; use ti para o de mestrado
% TRABALHO INDIVIDUAL: o trabalho não é depositado na biblioteca. A classe
% não gera capa (a opção capa é ignorada) nem a referência do trabalho acima
% do resumo e do abstract.
\documentclass[tid]{texufpel}

%------------------------------------------------------------------------------
% Pacotes usados neste exemplo. Nenhum é obrigatório: carregue só o que o seu
% trabalho usar. A classe já carrega graphicx, hyperref, natbib e caption.
%------------------------------------------------------------------------------
\usepackage{amsmath}        % equações alinhadas (align) e \eqref
\usepackage{pdfcomment}     % \pdftooltip: dica com o significado da sigla
\usepackage{array}          % colunas alinhadas à esquerda no quadro (L{...})

% Coluna de largura fixa com texto alinhado à esquerda, sem os espaços largos
% que a justificação cria em colunas estreitas.
\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}

%------------------------------------------------------------------------------
% Dados institucionais. ALTERE para o seu programa.
% \curso é a área do título: "Doutor em Ciência da Computação".
% Se a unidade for feminina (Faculdade, Escola), use \unidade[a]{...}.
%------------------------------------------------------------------------------
\unidade{Centro de Desenvolvimento Tecnológico}
\programa{Programa de Pós-Graduação em Computação}
\curso{Ciência da Computação}

%------------------------------------------------------------------------------
% Dados do trabalho. ALTERE.
% Os nomes abaixo são de grandes nomes da Computação e servem só de exemplo.
% Substitua pelos nomes da sua orientação.
%------------------------------------------------------------------------------
\title{Roteamento de veículos com janelas de tempo: fundamentos para a coleta seletiva urbana}

\author{Lovelace}{Ada}                          % ALTERE: autor(a)
\advisor[Prof.ª~Dr.ª]{Liskov}{Barbara}          % ALTERE: orientador(a)
\coadvisor[Prof.~Dr.]{Dijkstra}{Edsger W.}      % ALTERE: coorientador(a), opcional

% Ano da folha de rosto. Sem este comando, a classe usa o ano em que o
% documento é compilado. ALTERE.
\date{novembro}{2027}

% Palavras-chave: iniciais minúsculas (exceto nomes próprios), separadas por
% ponto e vírgula, a última terminada em ponto (Manual, p. 15).
\keyword{coleta seletiva;}
\keyword{heurísticas;}
\keyword{janelas de tempo;}
\keyword{problema de roteamento de veículos.}

\keywordeng{selective waste collection;}
\keywordeng{heuristics;}
\keywordeng{time windows;}
\keywordeng{vehicle routing problem.}

\begin{document}

% Orientadora ou coorientadora: troque o rótulo.
\renewcommand{\advisorname}{Orientadora}

\maketitle   % folha de rosto (sem capa, por ser trabalho individual)

% TRABALHO INDIVIDUAL: sem ficha catalográfica, errata e folha de aprovação,
% que pertencem ao trabalho depositado e avaliado por banca. Dedicatória,
% agradecimentos e epígrafe são opcionais; este exemplo não os usa.

%------------------------------------------------------------------------------
% Resumo: de 150 a 500 palavras, parágrafo único, voz ativa, terceira pessoa
% do singular, sem citações nem siglas (Manual, p. 14).
%------------------------------------------------------------------------------
\begin{abstract}
A coleta seletiva em cidades de porte médio costuma seguir rotas definidas
pela experiência das equipes, sem considerar o horário em que cada ponto pode
ser atendido. Este trabalho individual reúne a base teórica para tratar esse
problema como um problema de roteamento de veículos com janelas de tempo, tema
da tese em andamento. O texto parte do problema do caminho mínimo e do
algoritmo de Dijkstra, que calcula as distâncias sobre a malha viária, e chega
ao problema de roteamento de veículos, em que várias rotas saem de um depósito
e atendem um conjunto de clientes. Na variante com janelas de tempo, cada
cliente só pode ser atendido dentro de um intervalo, e o veículo espera quando
chega antes da abertura. Os métodos de solução foram organizados em quatro
grupos: formulações exatas, heurísticas de construção, busca local e
meta-heurísticas. Para cada grupo, o trabalho descreve o que o método garante
e onde encontra limites. A comparação indica que, para os setores de coleta de
Pelotas, com poucas dezenas de pontos, uma heurística de inserção seguida de
busca local é um ponto de partida razoável, e que a formulação exata serve para
medir a qualidade das rotas nos setores menores. O trabalho termina com a lista
de dados que precisam ser levantados com a equipe de coleta antes da etapa
experimental da tese.
\end{abstract}

% Abstract: tradução do resumo; o argumento é o título em inglês.
\begin{englishabstract}{Vehicle routing with time windows: foundations for urban selective waste collection}
Selective waste collection in medium-sized cities usually follows routes set
by the crews' experience, without considering the time at which each point
can be served. This individual study gathers the theoretical background to
treat this problem as a vehicle routing problem with time windows, the topic
of the ongoing doctoral thesis. The text starts from the shortest path
problem and Dijkstra's algorithm, which computes distances on the road
network, and moves on to the vehicle routing problem, in which several routes
leave a depot and serve a set of customers. In the time window variant, each
customer can only be served within an interval, and the vehicle waits when it
arrives before the window opens. Solution methods were organized into four
groups: exact formulations, construction heuristics, local search and
metaheuristics. For each group, the study describes what the method
guarantees and where it reaches its limits. The comparison indicates that,
for the collection sectors of Pelotas, with a few dozen points, an insertion
heuristic followed by local search is a reasonable starting point, and that
the exact formulation is useful to measure route quality in the smaller
sectors. The study ends with the list of data that must be gathered with the
collection crew before the experimental stage of the thesis.
\end{englishabstract}

% Listas: entram depois do abstract e antes do sumário.
\listoffigures
\listofquadros   % quadros numerados como Figura, em lista própria (Manual, p. 16)

% Lista de abreviaturas e siglas, em ordem alfabética (Manual, p. 18).
\begin{listofabbrv}{VRPTW}
  \item[UFPel] Universidade Federal de Pelotas
  \item[VRPTW] \textit{Vehicle Routing Problem with Time Windows}
\end{listofabbrv}

\tableofcontents

%==============================================================================
\chapter{Introdução}
\label{cap:introducao}
%==============================================================================

O caminhão da coleta seletiva de Pelotas sai da garagem, passa pelos pontos
de coleta e leva o material até a cooperativa de reciclagem. A ordem desses
pontos é decidida por quem dirige, e duas restrições pesam nessa escolha: o
sentido das ruas e o horário de cada ponto. O comércio do centro põe os
resíduos na calçada no fim do expediente, e as escolas só podem ser atendidas
fora do horário de aula.

Escolher rotas com essas restrições é o problema de roteamento de veículos
com janelas de tempo (\pdftooltip{VRPTW}{Vehicle Routing Problem with Time
Windows}, do inglês \textit{Vehicle Routing Problem with Time Windows}). Este
trabalho individual reúne o que a tese precisa saber sobre ele antes de
começar os experimentos: de onde o problema vem, como é formulado e que
métodos o resolvem.

\section{O trabalho individual na classe}

Este documento também é o exemplo de trabalho individual da classe
\texttt{texufpel}. A opção \texttt{tid} indica o trabalho de doutorado; para
o de mestrado, use \texttt{ti}. O trabalho individual não é depositado na
biblioteca da Universidade Federal de Pelotas
(\pdftooltip{UFPel}{Universidade Federal de Pelotas}), e por isso a classe
não gera capa nem coloca a referência do trabalho acima do resumo e do
abstract. A folha de rosto traz a natureza do trabalho (``Trabalho Individual
apresentado ao Programa de Pós-Graduação em Computação...'') e a orientação.
O arquivo também não tem ficha catalográfica nem folha de aprovação.

\section{Objetivos}

O objetivo deste trabalho é organizar a base teórica da tese. Os objetivos
específicos são:

\begin{enumerate}
  \item descrever o problema do caminho mínimo e o problema de roteamento de
        veículos, com e sem janelas de tempo;
  \item classificar os métodos de solução quanto ao que garantem e ao tempo
        que exigem;
  \item listar os dados de que a tese vai precisar para aplicar esses
        métodos à coleta seletiva.
\end{enumerate}

A lista segue as regras de alíneas do Manual (p. 71): o texto que a antecede
termina em dois pontos, cada alínea termina em ponto e vírgula e a última, em
ponto.

\section{Organização do texto}

O Capítulo~\ref{cap:problemas} apresenta os problemas de caminho mínimo e de
roteamento de veículos. O Capítulo~\ref{cap:metodos} compara os métodos de
solução. O Capítulo~\ref{cap:aplicacao} mostra como esses conceitos se
aplicam à coleta seletiva, e o Capítulo~\ref{cap:consideracoes} encerra o
trabalho.

%==============================================================================
\chapter{Problemas de roteamento}
\label{cap:problemas}
%==============================================================================

\section{Caminho mínimo}

Um grafo ponderado é um par $G = (V, E)$, em que $V$ é o conjunto de vértices
e $E$ o conjunto de arestas, com uma função de peso $w$ que associa a cada
aresta um número real não negativo \citep{Cormen:2022:IA}. O problema do
caminho mínimo pede o caminho de menor custo entre dois vértices. Quando os
pesos são não negativos, o algoritmo de \citet{Dijkstra:1959:NTP} resolve o
problema a partir de uma origem para todos os outros vértices. No roteamento,
ele serve para calcular a distância entre cada par de pontos sobre a malha
viária, respeitando o sentido das ruas.

\section{Roteamento de veículos}

\citet{Dantzig:1959:TDP} formularam o problema de roteamento de veículos para
planejar a entrega de combustível a postos a partir de um terminal. Em vez de
um caminho entre dois vértices, procura-se um conjunto de rotas que saem do
depósito, atendem todos os clientes e voltam, com o menor custo total. O
problema generaliza o do caixeiro-viajante e é NP-difícil, classificação que
remonta à teoria da NP-completude iniciada por \citet{Cook:1971:CTP}.

As duas chamadas acima mostram a regra de citação com mais de um autor. Com
os nomes na frase, os sobrenomes são ligados por ``e'', como em
\citet{Dantzig:1959:TDP}; dentro dos parênteses, por ponto e vírgula
\citep{Dantzig:1959:TDP}. Os comandos são os mesmos de sempre,
\verb|\citet| e \verb|\citep|: o estilo \texttt{abnt.bst} e a classe
escolhem o separador.

\section{Janelas de tempo}
\label{sec:janelas}

Na variante com janelas de tempo, cada cliente $i$ só pode ser atendido
dentro de um intervalo $[a_i, b_i]$ e exige um tempo de serviço $s_i$. Se o
veículo chega antes de $a_i$, espera. Sendo $\tau_{ij}$ o tempo de viagem de
$i$ até $j$, o atendimento em $j$ começa no instante dado pela
Equação~\eqref{eq:inicio}, e a rota só é viável se a
Equação~\eqref{eq:janela} valer para todos os clientes:
\begin{align}
  t_j &= \max \{\, a_j,\; t_i + s_i + \tau_{ij} \,\},
  \label{eq:inicio}\\
  t_j &\le b_j.
  \label{eq:janela}
\end{align}

As equações são numeradas com algarismos arábicos entre parênteses, alinhados
à direita (Manual, p. 76), e citadas com \verb|\eqref|. A variante com
janelas de tempo ganhou um conjunto de instâncias de teste e as primeiras
heurísticas de construção no trabalho de \citet{Solomon:1987:AVR}.

%==============================================================================
\chapter{Métodos de solução}
\label{cap:metodos}
%==============================================================================

Os métodos para o problema com janelas de tempo podem ser organizados em
quatro grupos. A Figura~\ref{qua:metodos} resume o que cada um garante e onde
encontra limites.

\begin{quadro}[htbp]
  \caption{Grupos de métodos para o roteamento com janelas de tempo}
  \label{qua:metodos}
  \centering
  \begin{tabular}{|L{3.3cm}|L{3.8cm}|L{3.9cm}|L{3.2cm}|}
    \hline
    \textbf{Grupo} & \textbf{O que garante} & \textbf{Limite} & \textbf{Exemplo} \\ \hline
    Formulação exata & solução ótima & tempo cresce rápido com o número de clientes & programa linear inteiro \\ \hline
    Heurística de construção & rota viável em pouco tempo & nenhuma garantia de qualidade & inserção \\ \hline
    Busca local & melhora uma solução existente & pode parar em um ótimo local & troca de dois clientes \\ \hline
    Meta-heurística & escapa de ótimos locais & exige ajuste de parâmetros & busca tabu \\ \hline
  \end{tabular}
  \caption*{Fonte: Elaborado pela autora (2027).}
\end{quadro}

O quadro foi feito com o ambiente \texttt{quadro} da classe. Como o Manual
chama de Figura toda ilustração (p. 16), o quadro é numerado junto com as
figuras e vai para a Lista de Quadros, gerada por \verb|\listofquadros|. As
colunas usam o tipo \texttt{L}, definido no preâmbulo, que alinha o texto à
esquerda e evita os espaços largos da justificação em colunas estreitas.

\section{Formulações exatas}

O problema pode ser escrito como programa linear inteiro, com variáveis que
indicam se o veículo vai de um cliente a outro e restrições que impõem as
janelas. Um resolvedor encontra a solução ótima, mas o tempo cresce rápido
com o número de clientes. Na tese, a formulação exata tem um papel de
referência: medir a distância entre as rotas das heurísticas e o ótimo nos
setores pequenos.

\section{Heurísticas de construção}

A heurística de inserção de \citet{Solomon:1987:AVR} acrescenta um cliente
por vez, na posição de menor custo que mantém a rota viável. É rápida e só
põe um cliente onde as janelas continuam respeitadas, mas não diz quão longe
as rotas obtidas estão do ótimo.

\section{Busca local e meta-heurísticas}

A busca local parte de uma solução e testa pequenas alterações, como trocar
dois clientes de posição, mantendo as que reduzem o custo sem violar as
janelas. Ela para quando nenhuma alteração ajuda, o que pode acontecer longe
do ótimo. As meta-heurísticas, como a busca tabu, aceitam pioras temporárias
para sair desses pontos, ao custo de mais parâmetros a ajustar.

%==============================================================================
\chapter{Aplicação à coleta seletiva}
\label{cap:aplicacao}
%==============================================================================

Na coleta seletiva, o depósito é a garagem, os clientes são os pontos de
coleta e o destino final é a cooperativa. A Figura~\ref{fig:grafo} mostra um
setor pequeno modelado como grafo, com a rota mínima entre a garagem (D) e a
cooperativa (C) em destaque.

\begin{figure}[htbp]
  \caption{Grafo de um setor de coleta, com a rota mínima de D até C em destaque}
  \label{fig:grafo}
  \centering
  \includegraphics[width=0.75\textwidth]{imagens/grafo-coleta.pdf}
  \caption*{Fonte: Elaborada pela autora (2027).}
\end{figure}

A legenda vem acima da figura, com número, travessão e título, e a fonte vem
abaixo, mesmo quando a figura é da própria autora (Manual, p. 16-17).

Para aplicar os métodos do Capítulo~\ref{cap:metodos}, a tese vai precisar
dos seguintes dados de cada setor:

\begin{enumerate}
  \item a malha viária, com o comprimento e o sentido de cada trecho de rua;
  \item a localização dos pontos de coleta, da garagem e da cooperativa;
  \item para cada ponto:
  \begin{enumerate}
    \item a janela de atendimento, $[a_i, b_i]$;
    \item o tempo de serviço, $s_i$;
  \end{enumerate}
  \item as rotas praticadas hoje, para comparação.
\end{enumerate}

A lista tem subalíneas, que a classe marca com travessão (Manual, p. 71).

%==============================================================================
\chapter{Considerações finais}
\label{cap:consideracoes}
%==============================================================================

A revisão mostrou que a coleta seletiva com horários de atendimento cabe no
problema de roteamento de veículos com janelas de tempo, e que o algoritmo de
Dijkstra continua útil como primeira etapa, no cálculo das distâncias. Para
setores com poucas dezenas de pontos, uma heurística de inserção seguida de
busca local parece o ponto de partida mais simples, com a formulação exata
como referência nos setores menores. O próximo passo é levantar os dados do
Capítulo~\ref{cap:aplicacao} com a equipe de coleta.

%------------------------------------------------------------------------------
% Referências: estilo abnt.bst e base bibliografia.bib, ambos na raiz. Só as
% obras citadas no texto entram na lista.
%------------------------------------------------------------------------------
\bibliographystyle{abnt}
\bibliography{bibliografia}

%------------------------------------------------------------------------------
% Apêndices: material elaborado pela própria autora (Manual, p. 23).
% Anexos (\anexos) seguem a mesma lógica, para material de outra autoria; veja
% o exemplo de dissertação.
%------------------------------------------------------------------------------
\apendices

\chapter{Dados do grafo de exemplo}
\label{apx:dados}

O grafo da Figura~\ref{fig:grafo} tem seis vértices e nove arestas, com as
distâncias em quilômetros: D--P1, 4; D--P2, 2; P1--P2, 1; P1--P3, 5; P2--P3,
8; P2--P4, 10; P3--P4, 2; P3--C, 6; P4--C, 3. A rota mínima de D até C passa
por P2, P1, P3 e P4 e tem 13~km.

\end{document}