# Can you explain algorithms to a mathphobe

## RESEARCH LEARNING WITH THE HELP OF OPTIMIZATION TASKS USING A CLASSICAL LOCALIZATION PROBLEM

Transcript

1 RESEARCH LEARNING WITH THE HELP OF OPTIMIZATION TASKS USING A CLASSICAL LOCALIZATION PROBLEM EXAMPLE Martin Guggisberg Torsten Linnemann Beat Trachsler 49th GDM Annual Conference Basel 2015 Where is the best location for a playground? This task does not have a closed algebraic solution and thus offers an introduction to reality-related situations of research-based learning. Using the example of the historical Fermat problem, this should be demonstrated for teaching at secondary level 2. In addition to numerical methods, solutions with GeoGebra are presented.

2 AGENDA 1. Case study playground 2. Reduction of the problem size 3. Use of numerical methods 4. Interactive experiments A CASE EXAMPLE OF INQUIRED LEARNING

3 WHERE IS THE BEST PLACE FOR A PLAYGROUND? Roth-Sonnen Nicole, Leuders, T., Barzel, B., & Hussmann, (2005). Computer, internet and the like in math lessons. (P. 190) Berlin: Cornelsen. PUPILS SLIP INTO THE ROLE OF AN REVIEWER As short a path as possible? Directly (through the site) or following a street? Should houses with more children be given an equivalent weighting?

4 DIRECT WAY 0:38 Link to GeoGebraTube: Spielplatz_Entfernung by Torsten Linnemann ECKENHAUSEN, PATHS ALONG A SQUARE GRID 0:39 Link to GeoGebraTube: spielplatz_eckenhausen by Torsten Linnemann

5

6 FERMAT'S HISTORICAL PROBLEM STATEMENT FROM THE 17TH CENTURY "Where is a point P in a triangle, if the sum of all distances from this point P to the three corners is to be minimal?" Dörrie, H. (2013). 100 great problems of elementary mathematics. Courier Dover Publications.

7 NUMEROUS NUMERALS the Fermat problem, the Fermat-Torricelli problem, the Steiner problem, the Steiner-Weber problem, the Weber problem, the Fermat-Weber problem, the weber facility problem, the one median problem, the median center problem, the spatial median problem, the minimum aggregate travel point problem

8 MODERN FORMULATION 0:38 Link to GeoGebraTube: Ulrich Steinmetz's new power plant building Where is the best location for a power plant? Where should a playground be built? equivalent question? Everyday reference?

9 There are different ways to define the center of the triangle. Swiss Math Book Volume 8 LU18 Link to GeoGebraTube

10 A GEOMETRIC EVIDENCE FOR N = 3 Link to Geogebra Material EVIDENCE WITH ROUTE TRAIN (LU 18, ICT additional material)

11 PROCEDURE: 1. In the triangle ABC we place the point P. 2. Now we rotate the triangle ABP by 60 around the point B. This creates an equilateral triangle BPP. The line A P PC now corresponds to the sum of the distances from P to the corners of the triangle ABC. 3. If you move the point P so that the line A P PC becomes straight, you have found the minimum distance sum. OTHER SOLUTIONS: Approximation Algorithms for Facility Location Problems

12 CONSIDERATION AS AN OPTIMIZATION PROBLEM The optimization problem formulated in this way is understandable for schoolchildren, but cannot be solved without tools

13 FOR N = 3 AN ANGLE OF 120 CAN BE OBSERVED Fermat point focus WEISZFELD ALGORITHM by Andrew Vázsonyi, alias Endre Weiszfeld () born in Budapest

14 Computers have the potential to turn the biggest math-phobe into a math user, if not a lover. Andrew Vázsonyi in his book: Which Door has the Cadillac Adventures of a Real-Life Mathematician

15 WEISZFELD ALGORITHM H. Üster, R.F. Love, The convergence of the Weiszfeld algorithm, Computers & Mathematics with Applications, Volume 40, Issues 4 5, August September 2000, Pages, ISSN WEISZFELD ALGORITHM WITH JAVASCRIPT (I) geometric_median = function (epsilon) {var P, Q; P = {}; P.x = gb.getXcoord ("CM"); P.y = gb.getYcoord ("CM"); }; while (true) {Q = median_approx (p); if (eukl_distance (p, Q)

16 WEISZFELD ALGORITHM WITH JAVASCRIPT (II) median_approx = function (p) {var W, x, y, d, w, _len, _i, Q; W = x = y = 0.0; Q = {}; _len = xl.length for (_i = 0; _i <_len; _i ++) {Q.x = xl [_i]; Q.y = yl [_i]; d = eukl_distance (q, p); if (d! = 0) {w = 1.0 / d; W + = w; x + = q.x * w; y + = q.y * w; }} Q.x = x / w; Q.y = y / w; return Q; }; CONVERGENCE BEHAVIOR Link to GeoGebraTube: Weiszfeld algorithm by Martin Guggisberg

17 EXPERIMENTING PHENOMENOLOGY 0:46 Fermat point center of gravity

18 Varignon Frame by Pierre de Varignon Canbolat, M. S., & Wesolowsky, G. O. (2012). On the use of the Varignon frame for single facility Weber problems in the presence of convex barriers. European Journal of Operational Research, 217 (2), link FURTHER POTENTIAL OF INTERACTIVE EXPERIMENTS

19

20 WHERE IS THE CENTER OF EUROPE? 0:27 Link to GeoGebraTube

21 THANKS TO Torsten Linnemann Beat Trachsler GeoGebra institute PH FHNW Switzerland Literature Balinski, M. L., (1966). On finding integer solutions to linear programs. In Proc. IBM Scientific Computing Symposium on Combinatorial Problems (S) Bruder, R. (2014). Research, exploration, problem solving. In Linneweber-Lammerskitten, H. (Ed.). Didactics of Mathematics. Basic education and competency building in the classes I and II. Seelze: Klett / Kallmeyer. Barzel, B., Büchter, A., & Leuders, T. (2014). Mathematik Methodik, manual for the secondary level I and II. 11th edition Berlin: Cornelsen Verlag. Dörrie, H. (2013). 100 great problems of elementary mathematics. Courier Dover Publications. Engelhaupt, H. (2004). Shortest Paths, Part I. Mathematics Information, 41, Gassner, C., & Hohenwarter, M. (2012). GeoGebraTube & GeoGebraWeb. Contributions to mathematics teaching Kaenders, R., & Schmidt, R. (2011). Understand more math with GeoGebra. Vieweg + Teubner, Wiesbaden. Ludwig, M., Oldenburg, R. (2007). Learning through experimentation Action-oriented approaches to mathematics. mathematik lehren, 141, 4-11 Roth, J., & Weigand, H. G. (2014). Inquiry-Based Learning in Mathematics Classes: An Approach. Contributions to mathematics lessons 2014 (S). Münster: WTM-Verlag Roth-Sonnen N., Leuders, T., Barzel, B., & Hussmann, (2005). Computer, internet and the like in math lessons. (P. 190) Berlin: Cornelsen. Weiszfeld, E. (1937). Sur le point pour lequel la somme des distances de n points donnés est minimum. Tôhoku Mathematical Journal, 43,