Automatos_Lista_1.pdf

Automatos_Lista_1.tex

\documentclass{article}

\usepackage{lmodern}
\usepackage[]{algorithm2e}
\usepackage[T1]{fontenc}
\usepackage[portuguese]{babel}
\usepackage{mathtools}

\title{Lista 1 de Linguagens, Autômatos e Computabilidade}
\author{9410313 - Walter Perez Urcia}

\begin{document}

\maketitle

\section{Problema 1}
	\subsection{Declaração}
		Encontre o error na seguinte prova de que $2 = 1$. \\
		Considere a ecuação $a = b$. Multiplique ambos os lados por $a$ para obter $a^{2} = ab$. \\
		Subtraia $b^{2}$ de ambos os lados para obter $a^{2} -b^{2} = ab - b^{2}$. Agora fatore cada lado, $(a+b)(a-b) = b(a-b)$, e divida cada lado por $(a-b)$, para chegar em $a + b = b$.\\
		Finalmente, faça $a$ e $b$ iguais a 1, o que mostra que $2=1$.
	\subsection{Solução}
		Considerando o propriedade que se $ac = bc$, então se dividimos por $c$ a igualdade seguirá cumplindo-se ($a = b$). Esto é verdade para qualquer valor de $a$ e $b$, mas $c$ tem que ser diferente de $0$.
		Por tanto, o error da prova está em dividir a expressão $(a+b)(a-b) = b(a-b)$ por $a-b$ dado que se $a = b$, então $a - b = 0$ e então todo o que continua está errado.

\section{Problema 2}
	\subsection{Declaração}
		Encontre o error na seguinte prova de que todos os cavalos são da mesma cor.\\
		AFIRMAÇÃO: Em qualquer conjunto de $h$ cavalos, todos os cavalos são da mesma cor.\\
		PROVA: Por indução sobre $h$.\\
		\\
		\textbf{Base:} Para $h = 1$. Em qualquer conjunto contendo somente um cavalo, todos os cavalos claramente são da mesma cor.\\
		\\
		\textbf{Passo da Indução:} Para $k \geq 1$ assuma que a afirmação é verdadeira para $h = k$ e prove que ela é verdadeira para $h = k + 1$. Tome qualquer conjunto $H$ de $k + 1$ cavalos. Mostramos que todos os cavalos nesse conjunto são da mesma cor. Remova  um cavalo desse conjunto para obter o conjunto $H_1$ com apenas $k$ cavalos. Pela hipótese da indução, todos os cavalos em $H_1$ são da mesma cor. Agora reponha o cavalo removido e remova um diferente para obter o conjunto $H_2$. Pelo mesmo argumento, todos os cavalos em $H_2$ são da mesma cor. Conseqüentemente todos os cavalos em $H$ têm que ter a mesma cor, e a prova está completa.
	\subsection{Solução}
		O error está em que o passo da indução está errado porque por definição tem que que usar $P(k)$ para provar $P(k+1)$, donde $P(x)$ em este casso é que o conjunto de $x$ cavalos da mesma cor. O que está fazendo é usar $P(k+1)$ (como verdadeiro) e removendo um cavalo para probar que $P(k)$ também é verdadeiro.
\section{Problema 3}
	\subsection{Declaração}
		Demostre que o algoritmo recursivo do Merge-Sort cumpre o que promete: dados um vetor $X$ e índices $p$ e $r$, ordena as posições de $p$ a $r$ do vetor $X$. Sugestão: use indução em $r-p$.
	\subsection{Solução}
		Sendo a função Merge-Sort:\\
		\begin{algorithm}[H]
			Merge-Sort( $X , p , r$ )\\
				\If{$p < r$ :}{
					$q = ( p + r ) / 2$\\
					Merge-Sort( $X , p , q $)\\
					Merge-Sort( $X , q + 1 , r $)\\
					Merge( $X , p , q , r $)
				}
		\end{algorithm}
		AFIRMAÇÃO: Dado um vetor $X$ e índices $p$ e $r$, Merge-Sort ordena as posições de $p$ a $r$ do vetor $X$\\
		PROVA: Por indução sobre $l = r - p$.\\
		\\
		\textbf{Base:} Para $l = r - p = 0$. Qualquer vetor com um elemento está ordenado. Da mesma forma se pode fazer $p = r$ em a chamada a Merge-Sort com o que o programa não faria nada ($p$ não é menor que $r$) por já estar ordenado.\\
		\\
		\textbf{Passo da Indução:} Se asume que Merge-Sort ordena correctamente $k$ elementos. Então para $k+1$ elementos temos:\\
		A primeira chamada recursiva vai ter: $t_1 = q - p + 1 = ( k + 1 ) / 2$ elementos ordenados ($X[p...q]$).\\
		Da mesma forma, a segunda chamada recursiva vai ter: $t_2 = r - ( q + 1 ) + 1 = ( k + 1 ) / 2$ elementos ordenados ($X[{q+1}...r]$).\\
		Sabendo que a função Merge une corretamente os dois vetores em forma ordenada, vamos ter finalmente um vetor de $k + 1$ elementos ordenados ao final do execução de Merge-Sort.
\end{document}