Changeset 143

Legend:

Unmodified

Added

Removed

• docs/trunk/omega-test-slides/omega-test.tex

  r142	r143
  599	599
  600	600	\begin{frame}[fragile]
  601	\frametitle{F(削除) inal F (削除ここまで)low Chart}
  601	\frametitle{F(追記) (追記ここまで)low Chart}
  602	602	\biggraph{Omega-Flowchart-M1}
  603	603	\end{frame}
  …	…
  605	605	\subsection{Last Resort}
  606	606
  607
  608	%TODO explain what to do in the difficult case!
  609
  607	\begin{frame}[fragile]
  608	\frametitle{What do we know?}
  609	\begin{itemize}
  610	\item $b\alpha - a\beta \leq ab - a - b$
  611	\item $a\beta \leq b\alpha$
  612	\item If there is a solution:
  613	\begin{itemize}
  614	\item $a\beta \leq abx \leq b\alpha$
  615	\item $\therefore a\beta \leq abx \leq ab - a - b + a\beta$
  616	\end{itemize}
  617	\end{itemize}
  618	\end{frame}
  619
  620	\begin{frame}[fragile]
  621	\frametitle{Narrowing it down}
  622	\begin{center} \includegraphics[width=100mm]{Omega-Test-Number-Line-3.png} \end{center}
  623	\begin{itemize}
  624	\item Check all multiples of $a$ in the given region
  625	\item Consider the problem with each equality: $abx = a\beta + ac$ for integer $c$ such that: 0ドル \leq ac \leq ab - a - b$
  626	\begin{itemize}
  627	\item Computationally expensive!
  628	\item But rarely needed
  629	\end{itemize}
  630	\end{itemize}
  631	\end{frame}
  610	632
  611	633	\begin{frame}[fragile]
  …	…
  807	829	\section{Answers to Code}
  808	830
  831	(追記) %\begin{frame} (追記ここまで)
  832	(追記) %\frametitle{Relaying the Answers} (追記ここまで)
  833	(追記) %\begin{itemize} (追記ここまで)
  834	(追記) %\item We only stop when 0 or 1 variables remain in inequalities (追記ここまで)
  835	(追記) %\item If 0, all variables solved by equality (追記ここまで)
  836	(追記) %\end{frame} (追記ここまで)
  837	(追記) (追記ここまで)
  809	838	%Need an equality example with a step that has no unit coefficient:
  810	839
  …	…
  870	899	\end{frame}
  871	900
  872	%Adapting previous problem:
  873
  874	% 55 <= -19sigma <= 57
  875	% (Subst: z = -3sigma - 15)
  876	% -12sigma - 4z = 60 (=> -3sigma - z = 15), 40 <= z - 16sigma <= 42
  877	% (subst: 4sigma = -x + z - 1, therefore x = z - 4sigma - 1)
  878	% 3x - 7z = 57, 37 <= 4x - 3z <= 39
  879	% (subst: y = 5x + 3z)
  880	% 5x - y + 3z = 0, 18x - 3y + 2z = 57, 37 <= 14x - 2y + 3z <= 39
  881
  882	%TODO change the bounds above (37,39) so that more than one value of sigma will lie between them.
  883	%In the current problem, normalising sigma turns the problem into an equality (I think - check that too)
  884
  885	\begin{frame}<1-4> [fragile]
  886	\frametitle{A Worked Problem}
  887	\begin{tabular}{ll}
  888	Substitution & Equations \\ \hline
  889
  890	~ & $\begin{array}{rrrrcr}
  891	& 5x &- y + & 3z & = & 0 \\
  892	& 18x &- 3y + & 2z & = & 57 \\
  893	37 \leq & 14x &- 2y + &3z &\leq& 39 \end{array}$
  894
  895	\\ \hline
  896	\only<2->{
  897	$y = 5x + 3z$ &
  898	$\begin{array}{rrrcr}
  899	& 3x &- 7z &=& 57 \\
  900	37 \leq & 4x &- 3z &\leq& 39 \end{array}$}
  901
  902	\\ \hline
  903	\only<3->{
  904	$x = -4\sigma + z - 1$ &
  905	$\begin{array}{rrrcr}
  906	&-3\sigma &- z &=& 15 \\
  907	40 \leq &-16\sigma &+ z &\leq& 42 \end{array}$}
  908
  909	\\ \hline
  910	\only<4->{
  911	$z = -3\sigma - 15$ &
  912	55ドル \leq -19\sigma \leq 57$}
  913
  914	\end{tabular}
  915
  916	\only<4->{where $-19\sigma = \ldots$?}
  917
  918	\end{frame}
  919
  920	%TODO explain why we can't divide in these examples
  921
  922	\begin{frame}<1-4> [fragile]
  923	\frametitle{A Worked Problem}
  924	\begin{tabular}{ll}
  925	Rev Substitution & Rev Equations \\ \hline
  926
  927	& \only<4->{$-120 \leq 19z \leq -114$}
  928
  929
  930	\\ \hline
  931	\only<1>{$z = -3\sigma - 15$} \only<2->{3ドル\sigma = -z - 15$}
  932	& \only<1-2>{55ドル \leq -19\sigma \leq 57$} \only<3>{165ドル \leq -57\sigma \leq 171$}
  933
  934	\end{tabular}
  935
  936	\only<4>{Error message: Unsafe when $-120 \leq 19z \leq -114,ドル 3ドルx + z = -63$ and $y = 5x + 3z$. Good luck!}
  937
  938	%TODO need to understand the omega test a little better to know all possible ways to improve this
  939
  940	%TODO the error will be more complex if there are fewer equalities (one); mainly inequalities
  941
  942	%TODO If we only have a solution when there are 0 or 1 vars left, we can just set the 1 var
  943	%equal to its remaining bound and then use the equality-substitution method. Just need to
  944	%check this is possible for the exhaustive search method - I think so
  945
  946	\end{frame}
  947
  948
  949
  950	%TODO work through an example showing how to get the answer back to code (i.e. solution -> code)
  901	%TODO while we might end with 0-1 vars always, all but the last var will have
  902	%been projected away. So we may have a solution in sigma, with all the original
  903	%variables projected away. So we might need some cleverness to get the original
  904	%variables back after all; substitution into the bounds?
  951	905
  952	906	\section{Future Work}

Note: See TracChangeset for help on using the changeset viewer.