Curso de LaTeX - Atividade 1

 Olá, leitores! Estou fazendo um minicurso de LaTeX e vim compartilhar o código da primeira atividade do curso.

Nessa atividade, fiz um documento com 2 seções, em que expliquei sobre Recursividade e o Problema do Caixeiro Viajante, mostrando como resolver o problema com o algoritmo de Força Bruta. Esses foram assuntos que vi nos semestres anteriores (estou atualmente no 3º semestre). 

Utilizei o pacote minted para adicionar os códigos em Python com formatação, além do pacote de fórmulas matemáticas para mostrar a parte matemática por trás do código.  

\documentclass{article}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{amsmath, amsfonts, amssymb}
\usepackage{hyperref}
\usepackage{minted}

\title{Atividade nº1}
\author{Júlia Karolyne}
\date{\today}

\begin{document}

\maketitle

\section{Recursividade}
A recursividade é um conceito fundamental na ciência da computação e na matemática, que consiste na definição de uma função ou procedimento em termos de si mesmo. Em outras palavras, uma função recursiva é aquela que, ao ser executada, chama a si própria para resolver um problema menor do mesmo tipo.
\\\\
\noindent A ideia central da recursividade é a divisão de um problema complexo em subproblemas mais simples, que podem ser resolvidos de maneira semelhante até alcançar uma situação elementar chamada caso base. O caso base é essencial, pois garante que a função recursiva não entre em um ciclo infinito e que a execução possa terminar.
\\\\
\noindent Um exemplo clássico é o cálculo do fatorial de um número $n$:

\[
n! = \begin{cases}
1 & \text{se } n = 0 \text{ ou } n = 1 \\
n \cdot (n-1)! & \text{se } n > 1
\end{cases}
\]

De maneira análoga, podemos implementar em Python a forma recursiva do fatorial assim:

\begin{minted}{python}
    def fatorial(n):
        if n = 0 or n = 1:
            return 1
        else:
            return n*fatorial(n-1)
\end{minted}

\noindent A recursividade apresenta diversas vantagens, como a clareza e a elegância na definição de algoritmos para problemas naturalmente recursivos, como árvores, grafos, algoritmos de divisão e conquista (por exemplo, merge sort e quicksort) e estruturas hierárquicas.
\\\\
\noindent Entretanto, ela também possui desvantagens, como o uso maior de memória devido ao empilhamento das chamadas recursivas e, em alguns casos, menor eficiência em comparação com soluções iterativas.
\\\\
\noindent Assim, a recursividade pode ser usada em problema sofisticados, a exemplo do caixeiro viajante, no momento de montar as permutações.

\section{Problema do Caixeiro Viajante - Algoritmo de Força Bruta}

\subsection{Introdução do Problema}
O Problema do Caixeiro Viajante (PCV) consiste em determinar a rota de menor custo que permita visitar um conjunto de cidades, passando exatamente uma vez por cada uma delas, e retornando ao ponto de partida.
\\\\
\noindent Na classificação de problemas computacionais, o PCV é considerado NP-difícil, uma vez que não se conhece um algoritmo que o resolva em tempo polinomial. Tanto a busca pela melhor rota quanto a verificação de sua viabilidade apresentam, em geral, complexidade exponencial.
\\\\
\noindent Para resolver o problema, um dos algoritmos utilizados é o da força bruta. Nele, todas as rotas são formadas através da permutação $n!$, sendo $n$ o número de cidades,  e comparadas, a fim de garantir que a rota de menor custo seja a encontrada.
\\\\
\noindent Esse tipo de algoritmo é usado quando o valor de entrada é muito pequeno (por exemplo, menor que sete cidades), visto que por o número de permutações crescer exponencialmente, o tempo computacional também cresce, tornando inviável para um grande número de pontos.
\\\\
\noindent Além disso, outra razão para o seu uso é a garantia da exatidão, que em outros tipos de algoritmos, como os de natureza heurística, pode ficar comprometida.
\\\\
\noindent Esse problema pode ser formulado matematicamente, como

\[
f(x) = d(R, p_{1}) + \sum_{i=1}^{n-1} d(p_{i}, p_{i+1}) + d(p_{n}, R)
\]

sendo,

\begin{itemize}
    \item $R$ = cidade de partida e retorno
    \item $p_{1}, p_{2},...,  p_{n}$ = cidades visitadas
    \item $d(a, b)$ = distância entre as cidades a e b
\end{itemize}

e o objetivo do problema, encontrar a rota de menor custo:

\[
x = \arg \min_{x \in C} f(x)
\]

\subsection{Implementação}
Inicialmente, usamos a função $permutacoes$ para permutar os pontos (referente às casas que o caixeiro viajante passará), montando as rotas a terem suas distâncias calculadas.

\begin{minted}{python}
    def permutacoes(pontos):
        if len(pontos) == 0:
            return ['']
        resultado = []
        for c in pontos:
            restante = pontos.replace(c, '')
            for p in permutacoes(restante):
                resultado.append(c + p)
        return resultado
\end{minted}

\noindent Logo depois, temos a função que calcula a distância entre dois pontos adjacentes. Para fins de simplificação, usamos a distância de Manhattan, considerando que as ruas sejam apenas na vertical ou horizontal.

\begin{minted}{python}
    def dist_manhattan(tupleA, tupleB):
        dist = abs(tupleA[0] - tupleB[0]) + abs(tupleA[1] - tupleB[1])
        return dist
\end{minted}

\noindent A função a seguir calcula as distâncias do ponto de partida até os outros pontos, usando a função da distância de Manhattan. As rotas e suas respectivas distâncias são salvas em uma lista.

\begin{minted}{python}
    def calcular_distancias(loc_pontos, rotas):  
        distancias = []
        for rota in rotas:
            soma = 0
            for a, b in zip(rota, rota[1:]):
                soma += dist_manhattan(loc_pontos[a], loc_pontos[b])
            distancias.append((rota, soma))
        return distancias
\end{minted}

\noindent Finalmente, calculamos a melhor rota. É passado a lista de distâncias e para cada uma delas há a comparação com as rotas seguintes. A variável $menor\_dist$ é trocada sempre que houver uma rota melhor.

\begin{minted}{python}
    def melhor_rota(distancia):
        menor_dist = distancia[0][1]
        melhor = distancia[0][0]
        for rota, dist in distancia[1:]:
            if dist < menor_dist:
                melhor, menor_dist = rota, dist
        return melhor, menor_dist
\end{minted}

\end{document}

Para visualizar o resultado desse código, ou seja, o documento, acesse o link.