wneuper/isa: doc-src/isac/dmeindl/proposal.tex@ff503b021e6c

     1 \documentclass[12pt,a4paper]{article}

     2 \usepackage{a4}

     3 \usepackage[naustrian]{babel}

     4 \usepackage[latin1]{inputenc}

     5 \usepackage{calc}

     6 \usepackage{amsmath}

     7 \usepackage{epsfig}

     8 \usepackage{graphicx}

     9 \usepackage{xcolor}

    10 \usepackage{amsfonts}

    12 % Seitenräder einstellen und Höhe der Seitenzahlen

    13 \usepackage{geometry}

    14 \geometry{a4paper, left=2.5cm, right=2cm, top=3cm, bottom=2.8cm}

    15 \setlength{\footskip}{2cm}

    18 %Zähler definieren und Starwert setzen:

    19 \newcommand{\R}{\mathbb R}

    20 %\newcommand{\N}{\mathbb N}

    21 %\newcommand{\Q}{\mathbb Q}

    22 %\newcommand{\C}{\mathbb C}

    25 \newcounter{ctr}

    26 \setcounter{ctr}{0}

    28 \newcounter{Teubner}

    29 \newcounter{Klingenberg}

    30 \newcounter{T}

    31 \newcounter{Vo}

    32 \newcounter{Se}

    33 \newcounter{E}

    34 \newcounter{Bwl}

    35 \newcounter{Int}

    36 \newcounter{Prim}

    37 \newcounter{Z}

    38 \setcounter{Z}{0}

    39 \setcounter{Teubner}{1}

    40 \setcounter{Klingenberg}{2}

    41 \setcounter{T}{1}

    42 \setcounter{Vo}{7}

    43 \setcounter{Se}{2}

    44 \setcounter{E}{3}

    45 \setcounter{Bwl}{4}

    46 \setcounter{Int}{5}

    47 \setcounter{Prim}{6}

    48 %BSP

    49 \newenvironment{myBsp}{

    50   \begin{list}{\textbf{\textsc{Bsp:}}}{

    51     \setlength{\labelwidth}{8Pc}

    52     \setlength{\labelsep}{0.5Pc}

    53     \setlength{\rightmargin}{0Pc}

    54     \setlength{\leftmargin}{2Pc}

    55     \setlength{\parsep}{0ex plus 0.5ex}

    56     \setlength{\listparindent}{1em}

    57     \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}

    58     \setlength{\topsep}{0.5Pc}

    59   }}

    60   {\end{list}

    61 }

    64 %Lemma

    65 \newenvironment{myLemma}{

    66   \begin{list}{\textsc{\textbf{Lemma:\ \ \ }}}{

    67    \setlength{\labelsep}{-0.5Pc}

    68     \setlength{\leftmargin}{1Pc}

    69     \setlength{\parsep}{0ex plus 0.5ex}

    70     \setlength{\listparindent}{1em}

    71     \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}

    72     \setlength{\topsep}{0.5Pc}

    73   }}

    74   {\end{list}

    75 }

    76 %Korollar

    77 \newenvironment{myKorollar}{

    78   \begin{list}{\textsc{\textbf{Korollar: }}}{

    79     \setlength{\labelwidth}{8Pc}

    80     \setlength{\labelsep}{0.5Pc}

    81     \setlength{\rightmargin}{0Pc}

    82     \setlength{\leftmargin}{4Pc}

    83     \setlength{\parsep}{0ex plus 0.5ex}

    84     \setlength{\listparindent}{1em}

    85     \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}

    86     \setlength{\topsep}{0.5Pc}

    87   }}

    88   {\end{list}

    89 }

    91 %Theorem

    92 \newenvironment{myTheorem}{

    93   \begin{list}{\textsc{\textbf{Theorem: }}}{

    94     \setlength{\labelwidth}{8Pc}

    95     \setlength{\labelsep}{0.5Pc}

    96     \setlength{\rightmargin}{0Pc}

    97     \setlength{\leftmargin}{5Pc}

    98     \setlength{\parsep}{0ex plus 0.5ex}

    99     \setlength{\listparindent}{1em}

   100     \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}

   101     \setlength{\topsep}{0.5Pc}

   102   }}

   103   {\end{list}

   104 }

   107 %Proportion

   108 \newenvironment{myProp}{

   109   \begin{list}{\textsc{\textbf{Proportion: }}}{

   110     \setlength{\labelwidth}{8Pc}

   111     \setlength{\labelsep}{0.5Pc}

   112     \setlength{\rightmargin}{0Pc}

   113     \setlength{\leftmargin}{4Pc}

   114     \setlength{\parsep}{0ex plus 0.5ex}

   115     \setlength{\listparindent}{1em}

   116     \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}

   117     \setlength{\topsep}{0.5Pc}

   118   }}

   119   {\end{list}

   120 }

   122 %Farben

   124 \newcommand{\red}[1]{\textcolor[rgb]{0.7,0,0}{\bf #1}}

   125 \newcommand{\rd}[1]{\color{red}{#1}}

   126 \newcommand{\white}[1]{\textcolor[rgb]{1,0,0}{\bf #1}}

   127 \newcommand{\w}[1]{\color{white}{#1}}

   128 \newcommand{\g}[1]{\color{myColor}{#1}}

   130 \usepackage{color}

   131 \definecolor{myColor}{rgb}{0.9,0.9,0.9}% Wir definieren im RGB-Farbraum

   134 \newcommand{\myDef}[1]{\parbox{\columnwidth}{\addtocounter{ctr}{1}{\w .}\\[-0.2cm]\textbf{Definition\ \Nummer:}\\#1}}

   135 \newcommand{\mySatz}[2]{\colorbox{myColor}{\parbox{\columnwidth}{\addtocounter{ctr}{1}{\g .}\\[-0.2cm]\textbf{Satz\ \Nummer:}\ #1\\ #2}}}

   136 \newcommand{\myBeweis}[1]{\textit{\textbf{Beweis:}\\ #1}}

   137 \newcommand{\myAlg}[2]{\parbox{\columnwidth}{\addtocounter{ctr}{1}\textbf{Algorithmus\ \Nummer:}\ \ #1\\#2}}

   138 \newcommand{\myProg}[1]{\fbox{\parbox{\columnwidth}{#1}}}

   140 \newcommand{\add}[1]{\addtocounter{#1}{1}}

   141 \newcommand{\zahl}[1]{\setcounter{#1}{Z}}

   142 \newcommand{\Q}[2]{\parbox{\columnwidth}{$^{[\arabic{#1}/#2]}$ }}

   144 \newcommand{\Nummer}{\thesection.\arabic{ctr}}

   146 %---------- --------------------------------------------------- Beginn -----------------------------------------------------------------------

   148 \title{Greatest common divisor \\ for multi variable Polynomials}

   149 \author{By\\Diana Meindl\\meindl$_-$diana@yahoo.com}

   150 \date{}

   152 \begin{document}

   153 \maketitle

   154 {\w .}\\[12cm]

   155 \begin{center}

   156 Presented to \\

   157 A.Univ.Prof. Dipl.-Ing. Dr. Wolfgang Schreiner (RISC Insitute)\\

   158 and\\

   159 Dr. techn. Walther Neuper (Institut für Softwaretechnologie, TU Graz)

   160 \end{center}

   161 \newpage

   162 {\w .}\hspace{6.5cm}\textbf{Abstract}\\[0.5cm]

   163 Calculation with fractions is an important part of Computer-Algebra-Systems (CAS). Therefor you need algorithms for canceling fractions, respectively for the greatest common divisor (GCD).

   164 \section{Background}

   165 The ISAC-project is a research and development project at the Institute for Software Technology of the Graz University of Technology. It is an educational mathematics assistant, a single-stepping system for applied mathematics based on the computer theorem prover Isabelle. The special is an easy readable knowledge base including Isabelles HOL-theories and a transparently working knowledge interpreter (a generalization of 'single stepping' algebra systems).

   166 The background to both, development and research, is given by actual needs in math education as well as by fundamental questions about 'the mechanization of thinking' as an essential aspect in mathematics and in technology.

   167 The ISAC-system under construction comprises a tutoring-system and an authoring-system. The latter provides for adaption to various needs of individual users and educational institutions and for extensions to arbitrary fields of applied mathematics.

   169 \section{Goal of the thesis}

   170 \subsection{Current situation}

   171 At the time there is no good implementation for the problem of canceling fractions in Isac and or in Isabelle. But because canceling is important for calculating with fractions a new implementation is necessary.

   173 \subsection{Problem}

   174 The wish is to handle fractions in Isac not only in one variable also in more. So the goal of this thesis is to find, assess and evaluate the existing algorithms and methods for finding the GCD. This will be an functional program with the possibility to include it into Isabelle.

   175 \subsection{Expected results}

   176 Find good algorithms for the different problems, and find out which one will be the best for the special problem.\\

   177 The program should handling:

   178 \begin{itemize}

   179 \item[]real and rational coefficients. Maybe also imaginary coefficients.

   180 \item[]Multi variable polynomials canceling and adding, when they are in normal form.

   181 \end{itemize}

   182 For the program should be used a functional programing language with good commentaries. And it should be based on Isabelle and works correctly in Isac.

   183 \newpage

   185 \section{State of the art}

   186 Was ist vorhanden, was kann ich aus welchen Büchern für meine Arbeit verwenden

   187 Es gibt verschiedene CAS die bereits einen Algrotihmus implimentiert haben, wie haben die das gemacht, und welcher ist für mich am besten.

   189 \newpage

   190 \section{Thesis structure}

   191 The proposed table of contents of the thesis on the chapter level is as follows:

   192 \begin{enumerate}

   193 	\item Introduction (2-3 pages)

   194 	\item Computer Algebra Systems (CAS) (5 - 7 pages)\\

   195 	Which different CAS exists and whats the focus of them.

   196 	\item The \textit{ISAC}-Project (5 - 7 pages)\\

   197 	This chapter will describe the \textit{ISAC}-Project and the goals of the project.

   198 	\item Univariate Polynomials (15-20 pages)\\

   199 	This chapter will describe different Algorithms for univariate polynomials, with different coefficients.

   200 	\item Multivariate Polynomials (20-25 pages)\\

   201 	This chapter will describe different Algorithms for multivariate polynomials,  with different coefficients

   202 	\item Functional programing and SML(2-5 pages)\\

   203 	The basic idea of this programing languages.

   204 	\item Implementation in \textit{ISAC}-Project (15-20 pages)

   205 	\item Conclusion (2-3 pages)

   206 \end{enumerate}

   207 %\newpage

   209 \section{Time line}

   210 %Werd nie fertig.\\

   211 \begin{center}

   212 		\begin{tabular}{|l|l|l|}

   213 		\hline

   214 			 \textbf{Time}&\textbf{Thesis}&\textbf{Project}\\

   215 			 \hline

   216 			 & Functional programing & Learning the basics and the idea\\

   217 			 & & of functional programing\\

   218 			 \hline

   219 			 & Different CAS & Can they handle the problem \\

   220 			 & &and which algorithm do they use?\\ \hline

   221 			 & Univariate Polynomials & Implementation of the Algorithm\\

   222 			 & & for univariate Polynomials \\ \hline

   223 		   & Multivariate Polynomials &  Implementation of the Algorithm\\

   224 			 & & for multivariate Polynomials \\ \hline

   225 		   & The Isac-Project &\\ \hline

   226 		   & Conclusion and Introduction & Find good examples for testing\\

   227 			\hline

   228 		\end{tabular}

   229 	\end{center}

   231 \newpage

   233 \section{Bibliography}

   234 %mindestens 10

   235 \begin{enumerate}

   236  \item Bird/Wadler, \textit{Einführung in die funktionale Programmierung}, Carl Hanser and Prentice-Hall International, 1992

   237  \item Franz Winkler, \textit{Polynomial Algorithms in Computer Algebra}, Springer,1996

   238  \item %M. Mignotte, \textit{An inequality about factors of polynomial}

   239  \item %M. Mignotte, \textit{Some useful bounds}

   240  \item %W. S. Brown and J. F. Traub. \textit{On euclid's algorithm and the theory of subresultans}, Journal of the ACM (JACM), 1971

   241  \item %Bruno Buchberger, \textit{Algorhimic mathematics: Problem types, data types, algorithm types}, Lecture notes, RISC Jku A-4040 Linz, 1982

   243  \item %Tateaki Sasaki and Masayuki Suzuki, \textit{Thre new algorithms for multivariate polynomial GCD}, J. Symbolic Combutation, 1992

   244  \item

   245  \item

   246  \item

   247 \end{enumerate}

   249 \end{document}

author	Diana Meindl <meindl_diana@yahoo.com>
	Thu, 15 Sep 2011 13:03:21 +0200
branch	decompose-isar
changeset 42270	ff503b021e6c
parent 42266	eee328e06031
child 42273	3be1e95c4fbe
permissions	-rwxr-xr-x