Apresentação da disciplina de Teoria de Grafos
Author
Esdras
License
Creative Commons CC BY 4.0
Abstract
Aula de Apresentação da disciplina de Teoria de Grafos da Universidade Federal de Goiás (UFG), Regional Jataí, semestre 2016.1.
Aula de Apresentação da disciplina de Teoria de Grafos da Universidade Federal de Goiás (UFG), Regional Jataí, semestre 2016.1.
\documentclass[xcolor=dvipsnames,table]{beamer}
\usepackage{latexsym}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{fancybox}
\usepackage{datetime}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{url}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{acronym}
\usepackage{array}
\newtheorem{definicao}{Definio}
\newcommand{\tab}{\hspace*{2em}}
\mode<presentation>
{
\definecolor{colortexto}{RGB}{0,0,0}
\setbeamertemplate{background canvas}[vertical shading][ bottom=white!10,top=white!10]
\setbeamercolor{normal text}{fg=colortexto}
\usetheme{Warsaw}
}
\title{Apresentação da disciplina}
\author{
Esdras Lins Bispo Jr. \\ \url{bispojr@ufg.br}
}
\institute{
Teoria de Grafos \\Bacharelado em Ciência da Computação}
\date{\textbf{23 de fevereiro de 2015} }
\logo{\includegraphics[width=1cm]{images/ufgJataiLogo.png}}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
\AtBeginSection{
\begin{frame}{Sumário}%[allowframebreaks]{Sumário}
\tableofcontents[currentsection]
%\tableofcontents[currentsection, hideothersubsections]
\end{frame}
}
\begin{frame}{Plano de Aula}
\tableofcontents
%\tableofcontents[hideallsubsections]
\end{frame}
\section{Sobre a Disciplina}
\subsection{Professor}
\begin{frame}{Professor}
\begin{columns}
\column{.4\textwidth}
\begin{center}
\includegraphics[height=.5\textheight]{images/esdras.png}
\end{center}
\column{.6 \textwidth}
\begin{block}{Formação}
\begin{center}
{\normalsize {\bf Bacharel} em Sistemas de Informação\\
{\bf Mestre} e {\bf Doutorando} em Representação Conhecimento (IA)}
\end{center}
\end{block}
\begin{block}{Quem?}
\begin{center}
{\bf Esdras Lins Bispo Junior} \\ Recife, Pernambuco.
\end{center}
\end{block}
\end{columns}
\end{frame}
\begin{frame}{Professor}
\begin{center}
\includegraphics[height=.65\textheight]{images/santa.png}
\end{center}
\end{frame}
\subsection{Informações Importantes}
\begin{frame}{Informações Importantes}
\begin{block}{Professor}
\begin{itemize}
\item Esdras Lins Bispo Jr.
\item \url{bispojr@ufg.br}
\item Sala 17B (Bloco dos Professores, em frente ao bebedouro)
\end{itemize}
\end{block}
\end{frame}
\begin{frame}{Informações Importantes}
\begin{block}{Disciplina}
\begin{itemize}
\item Teoria de Grafos
\item 09h30-11h10 (Segunda, LEC III)\\
15h30-17h10 (Quarta, LEC I)
\item Dúvidas: 09h30 - 11h10 (Terça)\\
{\color{red}[necessário confirmação comigo]}
\item \url{www.facebook.com/groups/tg.rej.2015.1/}
\end{itemize}
\end{block}
\end{frame}
\begin{frame}{Informações Importantes}
\begin{block}{Metodologia}
\begin{itemize}
\item Aulas expositivas;
\item Testes;
\item Provas;
\item Exercícios.
\end{itemize}
\end{block}
\end{frame}
\begin{frame}{Informações Importantes}
\begin{block}{Testes}
\begin{itemize}
\item Teste 1 $\Rightarrow$ 20\% da pontuação total (1 de abril);
\item Teste 2 $\Rightarrow$ 10\% da pontuação total (18 de maio).
\end{itemize}
\end{block}
\begin{block}{Provas}
\begin{itemize}
\item Prova 1 $\Rightarrow$ 40\% da pontuação total (22 de abril);
\item Prova 2 $\Rightarrow$ 30\% da pontuação total (03 de junho).
\end{itemize}
\end{block}
\begin{block}{Exercícios [Bônus]}
\begin{itemize}
\item Somatório dos exercícios $\Rightarrow$ 10\% da pontuação total.
\end{itemize}
\end{block}
\end{frame}
\begin{frame}{Informações Importantes}
\begin{block}{Avaliação}
O cálculo da média final será dada da seguinte forma:
\begin{itemize}
\item MF = MIN(10, PONT)
\end{itemize}
em que MIN representa o mínimo entre dois valores e PONT representa a pontuação total obtida em toda a disciplina.
\end{block} \pause
\begin{exampleblock}{Previsão de Término das Atividades}
22 de junho de 2015
\end{exampleblock}
\end{frame}
\begin{frame}{Informações Importantes}
\begin{block}{Reposições de Aula}
{\bf Dia:} Quarta-feira (15h30-17h10)
\end{block}
\begin{block}{Datas}
\begin{enumerate}
\item 19 de março;
\item 02 de abril;
\item 23 de abril;
\item 19 de maio;
\item 24 de maio;
\item 11 de junho.
\end{enumerate}
\end{block}
\end{frame}
% \begin{frame}{Informações Importantes}
% \begin{alertblock}{Não haverá aula}
% \begin{enumerate}
% \item 24 de março;
% \item 16 de abril;
% \item 21 de abril;
% \item 30 de abril;
% \item 05 de maio;
% \item 07 de maio;
% \item 23 de junho.
% \end{enumerate}
% \end{alertblock} \pause
% \begin{exampleblock}{Previsão de Término das Atividades}
% 30 de junho.
% \end{exampleblock}
% \end{frame}
\begin{frame}{Informações Importantes}
\begin{block}{Conteúdo do Curso}
\begin{enumerate}
\item Noções Básicas de Grafos;
\item Circuitos e Caminhos;
\item Subgrafos;
\item Grafos Conexos e Componentes;
\item Cortes e Pontes;
\end{enumerate}
\end{block}
\end{frame}
\begin{frame}{Informações Importantes}
\begin{block}{Conteúdo do Curso}
\begin{enumerate}
\item Árvores;
\item Isomorfismo;
\item Coloração;
\item Planaridade;
\item Outros Tópicos.
\end{enumerate}
\end{block}
\end{frame}
%------------------------------------------
\section{Pensamento}
\begin{frame}{Pensamento}
\begin{center}
\includegraphics[width=7cm]{images/pensamento.png}
\end{center}
\end{frame}
\begin{frame}{Pensamento}
\begin{columns}
\column{.4\textwidth}
\begin{center}
\includegraphics[height=.5\textheight]{images/euler.png}
\end{center}
\column{.6\textwidth}
\begin{block}{Frase}
\begin{center}
{\large Now I will have less distraction.}
\end{center}
\end{block}
\begin{block}{Quem?}
\begin{center}
{\bf Leonhard Euler (1707-83)} \\ Matemático e físico suíço.
\end{center}
\end{block}
\end{columns}
\end{frame}
%------------------------------------------
\section{O problema de Euler}
\begin{frame}[shrink]{O problema de Euler}
\begin{center}
\includegraphics[height=.6\textheight]{images/konigsberg.png}
\end{center} \pause
\begin{alertblock}{Sete pontes de Konigsberg} \pause
É possível cruzar as setes pontes sem passar \\
por duas vezes por nenhuma delas?
\end{alertblock}
\end{frame}
\begin{frame}[shrink]{O problema de Euler}
\begin{center}
\includegraphics[height=.6\textheight]{images/konigsberg2.png}
\end{center}
\begin{alertblock}{Sete pontes de Konigsberg}
É possível cruzar as setes pontes sem passar \\
por duas vezes por nenhuma delas?
\end{alertblock}
\end{frame}
\begin{frame}{O problema de Euler}
\begin{center}
\includegraphics[height=.6\textheight]{images/konigsberg3.png}
\end{center}
\begin{block}{Sete pontes de Konigsberg} \pause
Apresentado em 1736.
\end{block}
\end{frame}
\section{O problema de Guthrie}
\begin{frame}[shrink]{O problema de Guthrie}
\begin{center}
\includegraphics[height=.6\textheight]{images/mapa.png}
\end{center} \pause
\begin{alertblock}{Coloração de Mapas} \pause
É verdade que quatro cores são suficientes \\
para se colorar um mapa plano?
\end{alertblock}
\end{frame}
\begin{frame}[shrink]{O problema de Guthrie}
\begin{center}
\includegraphics[height=.6\textheight]{images/grafoColorido.png}
\end{center}
\begin{alertblock}{Coloração de Mapas}
É verdade que quatro cores são suficientes \\
para se colorar um mapa plano?
\end{alertblock}
\end{frame}
\begin{frame}{O problema de Guthrie}
\begin{center}
\includegraphics[height=.6\textheight]{images/grafoColorido2.png}
\end{center}
\begin{block}{Coloração de Mapas} \pause
Apresentado em 1852.
\end{block}
\end{frame}
\section{O problema do menor caminho}
\begin{frame}{O problema do menor caminho}
\begin{center}
\includegraphics[height=.6\textheight]{images/redes.png}
\end{center}
\begin{alertblock}{Menor Caminho} \pause
Qual é o roteamento de menor custo entre dois dispositivos?
\end{alertblock}
\end{frame}
\begin{frame}{O problema do menor caminho}
\begin{center}
\includegraphics[height=.6\textheight]{images/redesGrafo.png}
\end{center}
\begin{block}{Menor Caminho} \pause
Algoritmo de Dijkstra (proposto em 1852).
\end{block}
\end{frame}
\begin{frame}{O que existe em comum nos três problemas?} \pause
\begin{block}{Modelo} \pause
Um modelo é uma {\bf simplificação} da realidade. Um modelo abstrai algumas informações e se concentra em outras informações.
\end{block} \pause
\begin{block}{Bom modelo}
Um bom modelo é aquele que consegue descrever com maior proximidade as características essenciais do problema.
\end{block}
\end{frame}
\section{Noções Básicas de Grafos}
\begin{frame}{Noções Básicas de Grafos}
\begin{block}{$V^{(2)}$}
Para qualquer conjunto $V$, denotaremos por $V^{(2)}$ o conjunto de todos os pares não-ordenados de elementos distintos de $V$.
\end{block}
\pause
\begin{block}{Corolário 1}
Se $V$ tem $n$ elementos, então $V^{(2)}$ tem ${n \choose 2} := \frac{n(n-1)}{2}$ elementos.
\end{block}
\end{frame}
\begin{frame}{Noções Básicas de Grafos}
\begin{block}{Corolário 2}
Os elementos de $V^{(2)}$ serão identificados com os subconjuntos de $V$ que têm cardinalidade 2.
\end{block}
\pause
\begin{block}{Corolário 3}
Assim, cada elemento de $V^{(2)}$ terá a forma $\{ v,w \}$, sendo $v$ e $w$ dois elementos distintos de $V$.
\end{block}
\end{frame}
\begin{frame}{Desafios (0,5 pt)}
\begin{block}{Referência}
FEOFILOFF, P. {\bf Exercícios de Teoria dos Grafos}, \\
BCC, IME-USP, 2012. \\
\color{blue}{\url{http://www.ime.usp.br/~pf/grafos-exercicios/}}.
\end{block}
\begin{block}{Exercícios}
\begin{itemize}
\item E 1.1;
\item E 1.2.
\end{itemize}
\end{block}
\end{frame}
\begin{frame}
\titlepage
\end{frame}
\end{document}