|
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} |
|
11 %\usepackage{graphs} |
|
12 %\usepackage[all,dvips,arc,curve,color,frame]{xy} |
|
13 %% Declaring a new color for use in a XY graph. |
|
14 %\newxyColor{pink}{1.0 0.4 0.5}{rgb}{} |
|
15 % Eigene Nummerierung |
|
16 % Seitenräder einstellen und Höhe der Seitenzahlen |
|
17 \usepackage{geometry} |
|
18 \geometry{a4paper, left=2.5cm, right=2cm, top=3cm, bottom=2.8cm} |
|
19 \setlength{\footskip}{2cm} |
|
20 %Zähler definieren und Starwert setzen: |
|
21 |
|
22 \newcommand{\R}{\mathbb R} |
|
23 %\newcommand{\N}{\mathbb N} |
|
24 %\newcommand{\Q}{\mathbb Q} |
|
25 %\newcommand{\C}{\mathbb C} |
|
26 |
|
27 |
|
28 \newcounter{ctr} |
|
29 \setcounter{ctr}{0} |
|
30 |
|
31 \newcounter{Teubner} |
|
32 \newcounter{Klingenberg} |
|
33 \newcounter{T} |
|
34 \newcounter{Vo} |
|
35 \newcounter{Se} |
|
36 \newcounter{E} |
|
37 \newcounter{Bwl} |
|
38 \newcounter{Int} |
|
39 \newcounter{Prim} |
|
40 \newcounter{Z} |
|
41 \setcounter{Z}{0} |
|
42 \setcounter{Teubner}{1} |
|
43 \setcounter{Klingenberg}{2} |
|
44 \setcounter{T}{1} |
|
45 \setcounter{Vo}{7} |
|
46 \setcounter{Se}{2} |
|
47 \setcounter{E}{3} |
|
48 \setcounter{Bwl}{4} |
|
49 \setcounter{Int}{5} |
|
50 \setcounter{Prim}{6} |
|
51 %BSP |
|
52 \newenvironment{myBsp}{ |
|
53 \begin{list}{\textbf{\textsc{Bsp:}}}{ |
|
54 \setlength{\labelwidth}{8Pc} |
|
55 \setlength{\labelsep}{0.5Pc} |
|
56 \setlength{\rightmargin}{0Pc} |
|
57 \setlength{\leftmargin}{2Pc} |
|
58 \setlength{\parsep}{0ex plus 0.5ex} |
|
59 \setlength{\listparindent}{1em} |
|
60 \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex} |
|
61 \setlength{\topsep}{0.5Pc} |
|
62 }} |
|
63 {\end{list} |
|
64 } |
|
65 |
|
66 |
|
67 %Lemma |
|
68 \newenvironment{myLemma}{ |
|
69 \begin{list}{\textsc{\textbf{Lemma:\ \ \ }}}{ |
|
70 \setlength{\labelsep}{-0.5Pc} |
|
71 \setlength{\leftmargin}{1Pc} |
|
72 \setlength{\parsep}{0ex plus 0.5ex} |
|
73 \setlength{\listparindent}{1em} |
|
74 \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex} |
|
75 \setlength{\topsep}{0.5Pc} |
|
76 }} |
|
77 {\end{list} |
|
78 } |
|
79 %Korollar |
|
80 \newenvironment{myKorollar}{ |
|
81 \begin{list}{\textsc{\textbf{Korollar: }}}{ |
|
82 \setlength{\labelwidth}{8Pc} |
|
83 \setlength{\labelsep}{0.5Pc} |
|
84 \setlength{\rightmargin}{0Pc} |
|
85 \setlength{\leftmargin}{4Pc} |
|
86 \setlength{\parsep}{0ex plus 0.5ex} |
|
87 \setlength{\listparindent}{1em} |
|
88 \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex} |
|
89 \setlength{\topsep}{0.5Pc} |
|
90 }} |
|
91 {\end{list} |
|
92 } |
|
93 |
|
94 %Theorem |
|
95 \newenvironment{myTheorem}{ |
|
96 \begin{list}{\textsc{\textbf{Theorem: }}}{ |
|
97 \setlength{\labelwidth}{8Pc} |
|
98 \setlength{\labelsep}{0.5Pc} |
|
99 \setlength{\rightmargin}{0Pc} |
|
100 \setlength{\leftmargin}{5Pc} |
|
101 \setlength{\parsep}{0ex plus 0.5ex} |
|
102 \setlength{\listparindent}{1em} |
|
103 \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex} |
|
104 \setlength{\topsep}{0.5Pc} |
|
105 }} |
|
106 {\end{list} |
|
107 } |
|
108 |
|
109 |
|
110 %Proportion |
|
111 \newenvironment{myProp}{ |
|
112 \begin{list}{\textsc{\textbf{Proportion: }}}{ |
|
113 \setlength{\labelwidth}{8Pc} |
|
114 \setlength{\labelsep}{0.5Pc} |
|
115 \setlength{\rightmargin}{0Pc} |
|
116 \setlength{\leftmargin}{4Pc} |
|
117 \setlength{\parsep}{0ex plus 0.5ex} |
|
118 \setlength{\listparindent}{1em} |
|
119 \setlength{\itemsep}{1ex plus 0.5ex minus 0.2ex} |
|
120 \setlength{\topsep}{0.5Pc} |
|
121 }} |
|
122 {\end{list} |
|
123 } |
|
124 |
|
125 %Farben |
|
126 |
|
127 \newcommand{\red}[1]{\textcolor[rgb]{0.7,0,0}{\bf #1}} |
|
128 \newcommand{\rd}[1]{\color{red}{#1}} |
|
129 \newcommand{\white}[1]{\textcolor[rgb]{1,0,0}{\bf #1}} |
|
130 \newcommand{\w}[1]{\color{white}{#1}} |
|
131 \newcommand{\g}[1]{\color{myColor}{#1}} |
|
132 |
|
133 \usepackage{color} |
|
134 \definecolor{myColor}{rgb}{0.9,0.9,0.9}% Wir definieren im RGB-Farbraum |
|
135 |
|
136 |
|
137 \newcommand{\myDef}[1]{\parbox{\columnwidth}{\addtocounter{ctr}{1}{\w .}\\[-0.2cm]\textbf{Definition\ \Nummer:}\\#1}} |
|
138 \newcommand{\mySatz}[2]{\colorbox{myColor}{\parbox{\columnwidth}{\addtocounter{ctr}{1}{\g .}\\[-0.2cm]\textbf{Satz\ \Nummer:}\ #1\\ #2}}} |
|
139 \newcommand{\myBeweis}[1]{\textit{\textbf{Beweis:}\\ #1}} |
|
140 \newcommand{\myAlg}[2]{\parbox{\columnwidth}{\addtocounter{ctr}{1}\textbf{Algorithmus\ \Nummer:}\ \ #1\\#2}} |
|
141 \newcommand{\myProg}[1]{\fbox{\parbox{\columnwidth}{#1}}} |
|
142 |
|
143 \newcommand{\add}[1]{\addtocounter{#1}{1}} |
|
144 \newcommand{\zahl}[1]{\setcounter{#1}{Z}} |
|
145 \newcommand{\Q}[2]{\parbox{\columnwidth}{$^{[\arabic{#1}/#2]}$ }} |
|
146 |
|
147 \newcommand{\Nummer}{\thesection.\arabic{ctr}} |
|
148 |
|
149 %------------------------------------------------------------- Beginn ----------------------------------------------------------------------- |
|
150 |
|
151 \title{Greates common divisor \\ for multivariable Polynomials} |
|
152 \author{By\\Diana Meindl\\meindl$_-$diana@yahoo.com} |
|
153 \date{} |
|
154 |
|
155 \begin{document} |
|
156 \maketitle |
|
157 {\w .}\\[12cm] |
|
158 \begin{center} |
|
159 Presented to \\ |
|
160 A.Univ.Prof. Dipl.-Ing. Dr. Wolfgang Schreiner (RISC Insitute)\\ |
|
161 and\\ |
|
162 Dr. techn. Walther Neuper (Institut für Softwaretechnologie, TU Graz) |
|
163 \end{center} |
|
164 \newpage |
1 {\w .}\hspace{6.5cm}\textbf{Abstact}\\[0.5cm] |
165 {\w .}\hspace{6.5cm}\textbf{Abstact}\\[0.5cm] |
2 %Hab noch keine Ahnung, was ich da rein schreiben soll, aber alles wird gut :) HOFFENTLICH!!!!!!\\ |
166 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). |
3 %Allgemeine Einleitun? |
|
4 \section{Background} |
167 \section{Background} |
5 %Warum ich diese Arbeit schreibe? |
168 The ISAC-project is a research and development project at the Institute for Software Technology of the Graz University of Technology. ISAC is an educational mathematics assistant, a single-stepping system for applied mathematics based on the computer theorem prover Isabelle. The novelty is given by the human-readable knowledge base including Isabelles HOL-theories and by the transparently working knowledge interpreter (a generalization of 'single stepping' algebra systems). 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. 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 |
6 \section{Goal of the thesis} |
170 \section{Goal of the thesis} |
7 \subsection{Current situation} |
171 \subsection{Current situation} |
8 %Lernsystem, das Wert auf "`Durchsichtigkeit"' legt. |
172 Zur Zeit ist keine gute Implimentierung vorhanden. Um polynomiale Brüche zu kürzen, darum besteht die Notwendigkeit eienr Implimentierung in Isabelle, auf die von Isac zugegriffen wird. |
9 \subsection{Problem} |
173 \subsection{Problem} |
10 %Das Kürzen von Multivariablen Polynomen ist noch nicht zufriedenstellend implimentiert. |
174 |
|
175 In Isac möchte man gerne Brüche kürzen können und dies nicht nur mit einer Variablel sondern auch mit mehrern Variablen. 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 in Isabelle. |
11 \subsection{Expected results} |
176 \subsection{Expected results} |
12 %richtige implimentierung in isac basierend auf Isabelle.\\ |
177 Polynome kürzen und addieren ( wenn sie in Normalform sind)\\ |
13 %Funktional programmiert und Schrittweise nach zu voll ziehren.\\ |
178 Für reale koeffizienten eventuell auch für imaginäre oder rationale.\\ |
14 %Funktonen: Was wurde gemacht, Schrittweise auswählen, was man zuerst machen will, falls es mehrer Möglichkeiten gibt.(zumindest bei Univariaten Polynomen) |
179 richtige implimentierung in isac basierend auf Isabelle.\\ |
|
180 Funktional programmiert mit guten Beschreibungen, was gerade gemacht wird.\\ |
|
181 |
15 |
182 |
16 \section{State of the art} |
183 \section{State of the art} |
17 %Was ist vorhanden, was kann ich aus welchen Büchern für meine Arbeit verwenden? |
184 Was ist vorhanden, was kann ich aus welchen Büchern für meine Arbeit verwenden |
18 %SCHEI?E; das weiß ich doch nicht GGGRRRRR hätt wohl doch früher anfangen sollen. :( |
185 Es gibt verschiedene CAS die bereits einen Algrotihmus implimentiert haben, wie haben die das gemacht, und welcher ist für mich am besten. |
19 |
186 |
20 %\newpage |
187 %\newpage |
21 \section{Thesis structure} |
188 \section{Thesis structure} |
22 the proposed table of contents of the thesis on the chapter level is as follows: |
189 the proposed table of contents of the thesis on the chapter level is as follows: |
23 \begin{enumerate} |
190 \begin{enumerate} |
24 \item Introduction (7$-$10 pages)\\ |
191 \item Introduction (2-3 pages) |
25 This chapter will tell about the \textit{ISAC}$-$Project, whats the goal of the thesis and will also contain the basic mathematical definitions. |
192 \item The \textit{ISAC}-Project (5 - 7 pages)\\ |
|
193 This chapter will describe the \textit{ISAC}-Project and the goals of the project. |
26 \item Univariate Polynomials (15-20 pages)\\ |
194 \item Univariate Polynomials (15-20 pages)\\ |
27 This chapter will describe different Algorithms for univariate polynomials. |
195 This chapter will describe different Algorithms for univariate polynomials, with different coefficients. |
28 \item Multivariate Polynomials (20-25 pages)\\ |
196 \item Multivariate Polynomials (20-25 pages)\\ |
29 This chapter will describe different Algorithms for multivariate polynomials. |
197 This chapter will describe different Algorithms for multivariate polynomials, with different coefficients |
30 \item Functional programming (2-5 pages) |
198 \item Functional programming and SML(2-5 pages)\\ |
31 \item Implimentation in \textit{ISAC}$-$Project (15-20 pages) |
199 The basic idea of this programming languages. |
32 \item Conclusion (2$-$3 pages) |
200 \item Implimentation in \textit{ISAC}-Project (15-20 pages) |
|
201 \item Conclusion (2-3 pages) |
33 \end{enumerate} |
202 \end{enumerate} |
34 %\newpage |
203 %\newpage |
35 |
204 |
36 \section{Timeline} |
205 \section{Timeline} |
37 %Werd nie fertig.\\ |
206 %Werd nie fertig.\\ |
38 \begin{center} |
207 \begin{center} |
39 \begin{tabular}{|l|l|l|} |
208 \begin{tabular}{|l|l|l|} |
40 \hline |
209 \hline |
41 \textbf{Time}&\textbf{Thesis}&\textbf{Project}\\ |
210 \textbf{Time}&\textbf{Thesis}&\textbf{Project}\\ |
42 ??? & Univariate Polynomials & \\ |
211 \hline |
43 ??? & Multivariate Polynomials & \\ |
212 & Functional programming & Grundlagen Funktionales Programmieren\\ |
44 ??? & Conclusion and Introduction & Summary and Conclusions of Experiments\\ |
213 \hline |
|
214 & Univariate Polynomials & Implimentation of the Algorithm\\ |
|
215 & & for univariate Polynomials \\ \hline |
|
216 & Multivariate Polynomials & \\ \hline |
|
217 & The Isac-Project &Implimentation of the Algorithm\\ |
|
218 & & for multivariate Polynomials \\ \hline |
|
219 & Conclusion and Introduction & Summary and Conclusions of Experiments\\ |
45 \hline |
220 \hline |
46 \end{tabular} |
221 \end{tabular} |
47 \end{center} |
222 \end{center} |
48 |
223 |
49 \section{Bibliography} |
224 \section{Bibliography} |
50 mindestens 10 |
225 mindestens 10 |
51 \begin{enumerate} |
226 \begin{enumerate} |
52 \item |
227 \item Franz Winkler, \textit{Polynomial Algorithms in Computer Algebra}, Springer,1996 |
53 \item |
228 \item M. Mignotte, \textit{An inequality about factors of polynomial} |
54 \item |
229 \item M. Mignotte, \textit{Some useful bounds} |
55 \item |
230 \item W. S. Brown and J. F. Traub. \textit{On euclid's algorithm and the theory of subresultans}, Journal of the ACM (JACM), 1971 |
56 \item |
231 \item Bruno Buchberger, \textit{Algorhimic mathematics: Problem types, data types, algorithm types}, Lecture notes, RISC Jku A-4040 Linz, 1982 |
57 \item |
232 \item Bird/Wadler, \textit{Einführung in die funktionale Programmierung}, Carl Hanser and Prentice-Hall International, 1992 |
58 \item |
233 \item Tateaki Sasaki and Masayuki Suzuki, \textit{Thre new algorithms for multivariate polynomial GCD}, J. Symbolic Combutation, 1992 |
59 \item |
234 \item |
60 \item |
235 \item |
61 \item |
236 \item |
62 \end{enumerate} |
237 \end{enumerate} |
|
238 |
|
239 \end{document} |