<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\usepackage{epsf}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}


\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}}  \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 3091 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 330 - Programação Inteira - MAC 5780 }
\end{center}

\begin{center}
{\bf Segundo semestre de 2002}
\end{center}

\begin{center}
{\large  Lista de Exercício 2}

\vspace{0.3cm}
\end{center}

\begin{enumerate}

\item Considere o problema de encontrar um emparelhamento de custo máximo 
em um grafo bipartido. 
\begin{itemize} 
\item Escreva um problema de programação inteira que modela o problema (como feito
em sala de aula). 
\item Mostre que a matriz de incidência de um grafo bipartido é totalmente
unimodular. 
\item Use a relaxação linear para encontrar um emparelhamento de custo máximo
no grafo abaixo 
$$ \epsffile{l2f1.eps} $$ 
\end{itemize} 

\item Uma matriz $B$ apenas com $0$ e $1$ tem a \textbf{propriedade dos 1s
consecutivos} se para cada coluna $j$, $b_{ij} = b_{i'j} = 1$ com $i &lt; i'$
implica que $b_{lj} = 1$ para todo $i &lt; l &lt; i'$.  

Uma condição suficiente mais geral para que uma matriz seja totalmente
unimodular é: a matriz $A$ é TU se
\begin{itemize} 
\item $a_{ij} \in \{0, -1, +1\}$ para todo $i,j$. 
\item para todo subconjunto $M$ de linhas, existe uma partição $(M_1, M_2)$ de
$M$ tal que cada coluna $j$ satisfaz
\[ | \sum_{i \in M_1} a_{ij} - \sum_{i \in M_2} a_{ij} | \leq 1. \]
\end{itemize} 
Use a condição acima para mostrar que uma matriz com a propriedade dos 1s
consecutivos é TU. 

\item Considere um grafo $G=(V,E)$ com custos $c_e \ge 0$ nas arestas e um
subconjunto $Z \subseteq V$ de vértices terminais. 
\begin{itemize} 
\item Formule como um problema de programação inteira o problema de encontrar
uma árvore de $G$ que conecta todos os terminais (os não-terminais não
precisam ser necessariamente conectados) e tenha custo mínimo. 
\item Formule o algoritmo guloso para resolver o problema. Mostre através de
um contra-exemplo que este algoritmo não encontra sempre a solução ótima. 
\end{itemize}

\item Sabemos que para multiplicar uma matriz $A_{m\times n}$ por uma matriz
$B_{n\times p}$
o algoritmo mais simples calcula  $mnp$ multiplicações. Considere 
agora que desejamos
calcular várias multiplicações de matrizes: 
\[ M^1_{m_0\times m_1} * M^2_{m_1\times m_2} * \dots * M^n_{m_{n-1}\times m_n} \]
Como o produto de matrizes é associativo, podemos fazer este cálculo de várias
formas, resultando em um número diferente de multiplicações necessárias para
calcular a matriz produto. 

Exemplo: Suponha que queremos calcular o produto das matrizes
\[ M^1_{1000 \times 3} * M^2_{3 \times 50} * M^3_{50 \times 2} \]
Se fizermos, $(M^1 * M^2) * M^3$ teremos $250000$ multiplicações. Se fizermos
$M^1 * (M^2 * M^3)$, teremos $6300$ multiplicações. 

Faça um programa baseado em programação dinâmica que recebe o número $n$ de
matrizes a serem multiplicadas, as dimensões destas matrizes ($n+1$ valores
inteiros) e devolve o número mínimo de multiplicações que devem ser feitas
para calcular o produto.  
 
\end{enumerate}

\end{document}

</pre></body></html>