meindl_diana@42263
|
1 |
\documentclass[12pt,a4paper]{article}
|
meindl_diana@42263
|
2 |
\usepackage{a4}
|
meindl_diana@42263
|
3 |
\usepackage[naustrian]{babel}
|
meindl_diana@42263
|
4 |
\usepackage[latin1]{inputenc}
|
meindl_diana@42263
|
5 |
\usepackage{calc}
|
meindl_diana@42263
|
6 |
\usepackage{amsmath}
|
meindl_diana@42263
|
7 |
\usepackage{epsfig}
|
meindl_diana@42263
|
8 |
\usepackage{graphicx}
|
meindl_diana@42263
|
9 |
\usepackage{xcolor}
|
meindl_diana@42263
|
10 |
\usepackage{amsfonts}
|
meindl_diana@42264
|
11 |
|
meindl_diana@42263
|
12 |
% Seitenräder einstellen und Höhe der Seitenzahlen
|
meindl_diana@42263
|
13 |
\usepackage{geometry}
|
meindl_diana@42263
|
14 |
\geometry{a4paper, left=2.5cm, right=2cm, top=3cm, bottom=2.8cm}
|
meindl_diana@42263
|
15 |
\setlength{\footskip}{2cm}
|
meindl_diana@42264
|
16 |
|
meindl_diana@42264
|
17 |
|
meindl_diana@42263
|
18 |
%Zähler definieren und Starwert setzen:
|
meindl_diana@42263
|
19 |
\newcommand{\R}{\mathbb R}
|
meindl_diana@42263
|
20 |
%\newcommand{\N}{\mathbb N}
|
meindl_diana@42263
|
21 |
%\newcommand{\Q}{\mathbb Q}
|
meindl_diana@42263
|
22 |
%\newcommand{\C}{\mathbb C}
|
meindl_diana@42263
|
23 |
|
meindl_diana@42263
|
24 |
|
meindl_diana@42263
|
25 |
\newcounter{ctr}
|
meindl_diana@42263
|
26 |
\setcounter{ctr}{0}
|
meindl_diana@42263
|
27 |
|
meindl_diana@42263
|
28 |
\newcounter{Teubner}
|
meindl_diana@42263
|
29 |
\newcounter{Klingenberg}
|
meindl_diana@42263
|
30 |
\newcounter{T}
|
meindl_diana@42263
|
31 |
\newcounter{Vo}
|
meindl_diana@42263
|
32 |
\newcounter{Se}
|
meindl_diana@42263
|
33 |
\newcounter{E}
|
meindl_diana@42263
|
34 |
\newcounter{Bwl}
|
meindl_diana@42263
|
35 |
\newcounter{Int}
|
meindl_diana@42263
|
36 |
\newcounter{Prim}
|
meindl_diana@42263
|
37 |
\newcounter{Z}
|
meindl_diana@42263
|
38 |
\setcounter{Z}{0}
|
meindl_diana@42263
|
39 |
\setcounter{Teubner}{1}
|
meindl_diana@42263
|
40 |
\setcounter{Klingenberg}{2}
|
meindl_diana@42263
|
41 |
\setcounter{T}{1}
|
meindl_diana@42263
|
42 |
\setcounter{Vo}{7}
|
meindl_diana@42263
|
43 |
\setcounter{Se}{2}
|
meindl_diana@42263
|
44 |
\setcounter{E}{3}
|
meindl_diana@42263
|
45 |
\setcounter{Bwl}{4}
|
meindl_diana@42263
|
46 |
\setcounter{Int}{5}
|
meindl_diana@42263
|
47 |
\setcounter{Prim}{6}
|
meindl_diana@42263
|
48 |
%BSP
|
meindl_diana@42263
|
49 |
\newenvironment{myBsp}{
|
meindl_diana@42263
|
50 |
\begin{list}{\textbf{\textsc{Bsp:}}}{
|
meindl_diana@42263
|
51 |
\setlength{\labelwidth}{8Pc}
|
meindl_diana@42263
|
52 |
\setlength{\labelsep}{0.5Pc}
|
meindl_diana@42263
|
53 |
\setlength{\rightmargin}{0Pc}
|
meindl_diana@42263
|
54 |
\setlength{\leftmargin}{2Pc}
|
meindl_diana@42263
|
55 |
\setlength{\parsep}{0ex plus 0.5ex}
|
meindl_diana@42263
|
56 |
\setlength{\listparindent}{1em}
|
meindl_diana@42263
|
57 |
\setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}
|
meindl_diana@42263
|
58 |
\setlength{\topsep}{0.5Pc}
|
meindl_diana@42263
|
59 |
}}
|
meindl_diana@42263
|
60 |
{\end{list}
|
meindl_diana@42263
|
61 |
}
|
meindl_diana@42263
|
62 |
|
meindl_diana@42263
|
63 |
|
meindl_diana@42263
|
64 |
%Lemma
|
meindl_diana@42263
|
65 |
\newenvironment{myLemma}{
|
meindl_diana@42263
|
66 |
\begin{list}{\textsc{\textbf{Lemma:\ \ \ }}}{
|
meindl_diana@42263
|
67 |
\setlength{\labelsep}{-0.5Pc}
|
meindl_diana@42263
|
68 |
\setlength{\leftmargin}{1Pc}
|
meindl_diana@42263
|
69 |
\setlength{\parsep}{0ex plus 0.5ex}
|
meindl_diana@42263
|
70 |
\setlength{\listparindent}{1em}
|
meindl_diana@42263
|
71 |
\setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}
|
meindl_diana@42263
|
72 |
\setlength{\topsep}{0.5Pc}
|
meindl_diana@42263
|
73 |
}}
|
meindl_diana@42263
|
74 |
{\end{list}
|
meindl_diana@42263
|
75 |
}
|
meindl_diana@42263
|
76 |
%Korollar
|
meindl_diana@42263
|
77 |
\newenvironment{myKorollar}{
|
meindl_diana@42263
|
78 |
\begin{list}{\textsc{\textbf{Korollar: }}}{
|
meindl_diana@42263
|
79 |
\setlength{\labelwidth}{8Pc}
|
meindl_diana@42263
|
80 |
\setlength{\labelsep}{0.5Pc}
|
meindl_diana@42263
|
81 |
\setlength{\rightmargin}{0Pc}
|
meindl_diana@42263
|
82 |
\setlength{\leftmargin}{4Pc}
|
meindl_diana@42263
|
83 |
\setlength{\parsep}{0ex plus 0.5ex}
|
meindl_diana@42263
|
84 |
\setlength{\listparindent}{1em}
|
meindl_diana@42263
|
85 |
\setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}
|
meindl_diana@42263
|
86 |
\setlength{\topsep}{0.5Pc}
|
meindl_diana@42263
|
87 |
}}
|
meindl_diana@42263
|
88 |
{\end{list}
|
meindl_diana@42263
|
89 |
}
|
meindl_diana@42263
|
90 |
|
meindl_diana@42263
|
91 |
%Theorem
|
meindl_diana@42263
|
92 |
\newenvironment{myTheorem}{
|
meindl_diana@42263
|
93 |
\begin{list}{\textsc{\textbf{Theorem: }}}{
|
meindl_diana@42263
|
94 |
\setlength{\labelwidth}{8Pc}
|
meindl_diana@42263
|
95 |
\setlength{\labelsep}{0.5Pc}
|
meindl_diana@42263
|
96 |
\setlength{\rightmargin}{0Pc}
|
meindl_diana@42263
|
97 |
\setlength{\leftmargin}{5Pc}
|
meindl_diana@42263
|
98 |
\setlength{\parsep}{0ex plus 0.5ex}
|
meindl_diana@42263
|
99 |
\setlength{\listparindent}{1em}
|
meindl_diana@42263
|
100 |
\setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}
|
meindl_diana@42263
|
101 |
\setlength{\topsep}{0.5Pc}
|
meindl_diana@42263
|
102 |
}}
|
meindl_diana@42263
|
103 |
{\end{list}
|
meindl_diana@42263
|
104 |
}
|
meindl_diana@42263
|
105 |
|
meindl_diana@42263
|
106 |
|
meindl_diana@42263
|
107 |
%Proportion
|
meindl_diana@42263
|
108 |
\newenvironment{myProp}{
|
meindl_diana@42263
|
109 |
\begin{list}{\textsc{\textbf{Proportion: }}}{
|
meindl_diana@42263
|
110 |
\setlength{\labelwidth}{8Pc}
|
meindl_diana@42263
|
111 |
\setlength{\labelsep}{0.5Pc}
|
meindl_diana@42263
|
112 |
\setlength{\rightmargin}{0Pc}
|
meindl_diana@42263
|
113 |
\setlength{\leftmargin}{4Pc}
|
meindl_diana@42263
|
114 |
\setlength{\parsep}{0ex plus 0.5ex}
|
meindl_diana@42263
|
115 |
\setlength{\listparindent}{1em}
|
meindl_diana@42263
|
116 |
\setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex}
|
meindl_diana@42263
|
117 |
\setlength{\topsep}{0.5Pc}
|
meindl_diana@42263
|
118 |
}}
|
meindl_diana@42263
|
119 |
{\end{list}
|
meindl_diana@42263
|
120 |
}
|
meindl_diana@42263
|
121 |
|
meindl_diana@42263
|
122 |
%Farben
|
meindl_diana@42263
|
123 |
|
meindl_diana@42263
|
124 |
\newcommand{\red}[1]{\textcolor[rgb]{0.7,0,0}{\bf #1}}
|
meindl_diana@42263
|
125 |
\newcommand{\rd}[1]{\color{red}{#1}}
|
meindl_diana@42263
|
126 |
\newcommand{\white}[1]{\textcolor[rgb]{1,0,0}{\bf #1}}
|
meindl_diana@42263
|
127 |
\newcommand{\w}[1]{\color{white}{#1}}
|
meindl_diana@42263
|
128 |
\newcommand{\g}[1]{\color{myColor}{#1}}
|
meindl_diana@42263
|
129 |
|
meindl_diana@42263
|
130 |
\usepackage{color}
|
meindl_diana@42263
|
131 |
\definecolor{myColor}{rgb}{0.9,0.9,0.9}% Wir definieren im RGB-Farbraum
|
meindl_diana@42263
|
132 |
|
meindl_diana@42263
|
133 |
|
meindl_diana@42263
|
134 |
\newcommand{\myDef}[1]{\parbox{\columnwidth}{\addtocounter{ctr}{1}{\w .}\\[-0.2cm]\textbf{Definition\ \Nummer:}\\#1}}
|
meindl_diana@42263
|
135 |
\newcommand{\mySatz}[2]{\colorbox{myColor}{\parbox{\columnwidth}{\addtocounter{ctr}{1}{\g .}\\[-0.2cm]\textbf{Satz\ \Nummer:}\ #1\\ #2}}}
|
meindl_diana@42263
|
136 |
\newcommand{\myBeweis}[1]{\textit{\textbf{Beweis:}\\ #1}}
|
meindl_diana@42263
|
137 |
\newcommand{\myAlg}[2]{\parbox{\columnwidth}{\addtocounter{ctr}{1}\textbf{Algorithmus\ \Nummer:}\ \ #1\\#2}}
|
meindl_diana@42263
|
138 |
\newcommand{\myProg}[1]{\fbox{\parbox{\columnwidth}{#1}}}
|
meindl_diana@42263
|
139 |
|
meindl_diana@42263
|
140 |
\newcommand{\add}[1]{\addtocounter{#1}{1}}
|
meindl_diana@42263
|
141 |
\newcommand{\zahl}[1]{\setcounter{#1}{Z}}
|
meindl_diana@42263
|
142 |
\newcommand{\Q}[2]{\parbox{\columnwidth}{$^{[\arabic{#1}/#2]}$ }}
|
meindl_diana@42263
|
143 |
|
meindl_diana@42263
|
144 |
\newcommand{\Nummer}{\thesection.\arabic{ctr}}
|
meindl_diana@42263
|
145 |
|
meindl_diana@42265
|
146 |
%---------- --------------------------------------------------- Beginn -----------------------------------------------------------------------
|
meindl_diana@42263
|
147 |
|
meindl_diana@42263
|
148 |
\title{Greates common divisor \\ for multivariable Polynomials}
|
meindl_diana@42263
|
149 |
\author{By\\Diana Meindl\\meindl$_-$diana@yahoo.com}
|
meindl_diana@42263
|
150 |
\date{}
|
meindl_diana@42263
|
151 |
|
meindl_diana@42263
|
152 |
\begin{document}
|
meindl_diana@42263
|
153 |
\maketitle
|
meindl_diana@42263
|
154 |
{\w .}\\[12cm]
|
meindl_diana@42263
|
155 |
\begin{center}
|
meindl_diana@42263
|
156 |
Presented to \\
|
meindl_diana@42263
|
157 |
A.Univ.Prof. Dipl.-Ing. Dr. Wolfgang Schreiner (RISC Insitute)\\
|
meindl_diana@42263
|
158 |
and\\
|
meindl_diana@42263
|
159 |
Dr. techn. Walther Neuper (Institut für Softwaretechnologie, TU Graz)
|
meindl_diana@42263
|
160 |
\end{center}
|
meindl_diana@42263
|
161 |
\newpage
|
meindl_diana@42234
|
162 |
{\w .}\hspace{6.5cm}\textbf{Abstact}\\[0.5cm]
|
meindl_diana@42263
|
163 |
Calculation with fractions is an importent part of Computer-Algebra-Systems (CAS). Therefor you need algorithms for canceling fractions, respectively for the greatest common divisor (GCD).
|
meindl_diana@42234
|
164 |
\section{Background}
|
meindl_diana@42266
|
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).
|
meindl_diana@42266
|
166 |
The background to both, development and research, is given by actual needs in math education as well as by foundamental questions about 'the mechanization of thinking' as an essential aspect in mathematics and in technology.
|
meindl_diana@42266
|
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.
|
meindl_diana@42263
|
168 |
|
meindl_diana@42234
|
169 |
\section{Goal of the thesis}
|
meindl_diana@42234
|
170 |
\subsection{Current situation}
|
meindl_diana@42266
|
171 |
At the time there is no good implimentation for the problem of canceling fractions in Isac and or in Isabelle. But because canceling is important for calculating with fractions a new implimentation is necessary.
|
meindl_diana@42266
|
172 |
|
meindl_diana@42234
|
173 |
\subsection{Problem}
|
meindl_diana@42266
|
174 |
The wish is to handle fractions in Isac not only in one variable also in more. So the goal of this thesis ist to find, assess and evaluate the existing algorithms and methods for finding the GCD. This will be an functional programm with the posibility to include it into Isabelle.
|
meindl_diana@42234
|
175 |
\subsection{Expected results}
|
meindl_diana@42266
|
176 |
Find good algorithms for the different problems, and find out which one will be the best for the special problem.\\
|
meindl_diana@42266
|
177 |
The program should handeling:
|
meindl_diana@42266
|
178 |
\begin{itemize}
|
meindl_diana@42266
|
179 |
\item[]real and rational coefficients. Maybe also imaginary coefficients.
|
meindl_diana@42266
|
180 |
\item[]Mulivariable polynomials canceling and adding, when they are in normalform.
|
meindl_diana@42266
|
181 |
\end{itemize}
|
meindl_diana@42266
|
182 |
For the program should be used a functional programming language with good commentaries. And it should be based on Isabelle and works correctly in Isac.
|
meindl_diana@42266
|
183 |
\newpage
|
meindl_diana@42234
|
184 |
|
meindl_diana@42234
|
185 |
\section{State of the art}
|
meindl_diana@42263
|
186 |
Was ist vorhanden, was kann ich aus welchen Büchern für meine Arbeit verwenden
|
meindl_diana@42263
|
187 |
Es gibt verschiedene CAS die bereits einen Algrotihmus implimentiert haben, wie haben die das gemacht, und welcher ist für mich am besten.
|
meindl_diana@42234
|
188 |
|
meindl_diana@42266
|
189 |
\newpage
|
meindl_diana@42234
|
190 |
\section{Thesis structure}
|
meindl_diana@42266
|
191 |
The proposed table of contents of the thesis on the chapter level is as follows:
|
meindl_diana@42234
|
192 |
\begin{enumerate}
|
meindl_diana@42263
|
193 |
\item Introduction (2-3 pages)
|
meindl_diana@42266
|
194 |
\item Computer Algebra Systems (CAS) (5 - 7 pages)\\
|
meindl_diana@42266
|
195 |
Which different CAS exists and whats the foucus of them.
|
meindl_diana@42263
|
196 |
\item The \textit{ISAC}-Project (5 - 7 pages)\\
|
meindl_diana@42263
|
197 |
This chapter will describe the \textit{ISAC}-Project and the goals of the project.
|
meindl_diana@42234
|
198 |
\item Univariate Polynomials (15-20 pages)\\
|
meindl_diana@42263
|
199 |
This chapter will describe different Algorithms for univariate polynomials, with different coefficients.
|
meindl_diana@42234
|
200 |
\item Multivariate Polynomials (20-25 pages)\\
|
meindl_diana@42263
|
201 |
This chapter will describe different Algorithms for multivariate polynomials, with different coefficients
|
meindl_diana@42263
|
202 |
\item Functional programming and SML(2-5 pages)\\
|
meindl_diana@42263
|
203 |
The basic idea of this programming languages.
|
meindl_diana@42263
|
204 |
\item Implimentation in \textit{ISAC}-Project (15-20 pages)
|
meindl_diana@42263
|
205 |
\item Conclusion (2-3 pages)
|
meindl_diana@42234
|
206 |
\end{enumerate}
|
meindl_diana@42234
|
207 |
%\newpage
|
meindl_diana@42234
|
208 |
|
meindl_diana@42234
|
209 |
\section{Timeline}
|
meindl_diana@42234
|
210 |
%Werd nie fertig.\\
|
meindl_diana@42234
|
211 |
\begin{center}
|
meindl_diana@42234
|
212 |
\begin{tabular}{|l|l|l|}
|
meindl_diana@42234
|
213 |
\hline
|
meindl_diana@42234
|
214 |
\textbf{Time}&\textbf{Thesis}&\textbf{Project}\\
|
meindl_diana@42263
|
215 |
\hline
|
meindl_diana@42266
|
216 |
& Functional programming & Learning the basics and the idea\\
|
meindl_diana@42266
|
217 |
& & of funcional programming\\
|
meindl_diana@42263
|
218 |
\hline
|
meindl_diana@42266
|
219 |
& Different CAS & Can they handle the problem \\
|
meindl_diana@42266
|
220 |
& &and which algorithm do they use?\\ \hline
|
meindl_diana@42263
|
221 |
& Univariate Polynomials & Implimentation of the Algorithm\\
|
meindl_diana@42263
|
222 |
& & for univariate Polynomials \\ \hline
|
meindl_diana@42266
|
223 |
& Multivariate Polynomials & Implimentation of the Algorithm\\
|
meindl_diana@42266
|
224 |
& & for multivariate Polynomials \\ \hline
|
meindl_diana@42266
|
225 |
& The Isac-Project &\\ \hline
|
meindl_diana@42266
|
226 |
& Conclusion and Introduction & Find good examples for testing\\
|
meindl_diana@42234
|
227 |
\hline
|
meindl_diana@42234
|
228 |
\end{tabular}
|
meindl_diana@42234
|
229 |
\end{center}
|
meindl_diana@42266
|
230 |
|
meindl_diana@42266
|
231 |
\newpage
|
meindl_diana@42234
|
232 |
|
meindl_diana@42234
|
233 |
\section{Bibliography}
|
meindl_diana@42266
|
234 |
%mindestens 10
|
meindl_diana@42234
|
235 |
\begin{enumerate}
|
meindl_diana@42266
|
236 |
\item Bird/Wadler, \textit{Einführung in die funktionale Programmierung}, Carl Hanser and Prentice-Hall International, 1992
|
meindl_diana@42263
|
237 |
\item Franz Winkler, \textit{Polynomial Algorithms in Computer Algebra}, Springer,1996
|
meindl_diana@42266
|
238 |
\item %M. Mignotte, \textit{An inequality about factors of polynomial}
|
meindl_diana@42266
|
239 |
\item %M. Mignotte, \textit{Some useful bounds}
|
meindl_diana@42266
|
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
|
meindl_diana@42266
|
241 |
\item %Bruno Buchberger, \textit{Algorhimic mathematics: Problem types, data types, algorithm types}, Lecture notes, RISC Jku A-4040 Linz, 1982
|
meindl_diana@42266
|
242 |
|
meindl_diana@42266
|
243 |
\item %Tateaki Sasaki and Masayuki Suzuki, \textit{Thre new algorithms for multivariate polynomial GCD}, J. Symbolic Combutation, 1992
|
meindl_diana@42234
|
244 |
\item
|
meindl_diana@42234
|
245 |
\item
|
meindl_diana@42234
|
246 |
\item
|
meindl_diana@42263
|
247 |
\end{enumerate}
|
meindl_diana@42263
|
248 |
|
meindl_diana@42263
|
249 |
\end{document} |