Angewandte Mathematik


Mo, 15:15 - 16:45 und Mi, 15:15 - 16:45, Raum R1.009

Dozenten: Manfred Gruber ^, Doina Logofătu  ^
Tutor: Evgeni Pavlidis



Das Seminar beginnt pünktlich am jeweils ersten Termin in der ersten Semesterwoche. Für alle Termine besteht laut Studien- und Prüfungsordnung Anwesenheitspflicht - auch für die Termine der ersten Woche!

Inhalt der Lehrveranstaltung

Mit diesem Seminar werden zwei Ziele verfolgt: es wird geübt, wie ein Problem mittlerer Schwierigkeit mit mathematischer Modellierung und unter Einsatz von Informatik-Mitteln gelöst werden kann. Das mathematische Modell geht der eigenen Implementierung bzw. dem Einsatz von Mathematik-Software voraus. Zu demonstrieren ist der Ökonomiegewinn, der durch den Einsatz mathematischer Methodik erreicht wird. Die Teilnehmer sollen Teamarbeit und Präsentation einüben. Beispielhaft seien genannt:

(a) Bearbeitung von Themen aus Zahlen- und Graphentheorie, Kombinatorik, Mengenlehre u.ä. verbunden mit eigenen Implementierungen der Teilnehmer
(b) Bearbeitung eines mathematischen Themas unter Rückgriff auf Computeralgebrasysteme.

Die Veranstaltung verwendet Java als Programmiersprache und Mathematica.

*** Präsentationen Mittwochs,  ab 20.05 im Raum R 1.006 ! ***

Online Platform: ACM Uva Online Judge

Common Mistakes in Online and Real-time Contests
Competition Strategies
ACM Programming Contest 2008 Teilnahme unseres Teams, nächstes Regional: http://2009.nwerc.eu/

ICPC ACM World Final, Stockholm 2009

Electronic Board: acm.uva.es/board/

Kopfkommentar

Team

Accepted

gelöste Probleme

C. Miesel, R. Seilbeck, A. Wolfram
Wettbewerb Teilnahme

50

[113][128][160][209][264][280][294][324][343][369][374][382][389][401][406][424][438][465][484][493][530][534][543]
[575][636][686]
[808][880][903][10000][10062][10070][10104][10106][10127][10139][10235][10305]
[10324][10464]
[10469][10473][10523][10622][10789][10920][11172][11185][11461][11479]

C. Posselt, J. Schubert

43

[112][256][288][371][382][389][445][446][484][485][534][575][579][583][623][640][750][784][10023][10038][10070]
[10106][10107]
[10260][10282][10303][10323][10338][10392][10473][10519][10579][10622][10670][10699][10812]
[10815][11063][11172][11185][11233][11417][11466]

D. Wilfert, J. Studt

41

[102][122][147][185][272][357][382][392][401][439][446][465][471][490][534][542][543][601][638][674][686][725][759]
[902][10007][10034][10106][10193][10213][10220][10515]
[10722][10814][10862][10921][10925][10929][10992]
[11056][11192][11220]

C. Mitterreiter, R. Luigs
35
[324][369][382][438][458][485][494][534][543][591][602][674][694][974][10007][10055][10070][10198][10303][10334]
[10340][10370]
[10394][10469][10473][10579][10696][10722][10783][10921][11121][11172][11219][11223][11462]

M. Mohr, R. Schirm, F. Mathauser

32

[146][352][382][439][444][445][446][458][483][485][494][534][541][543][583][615][686][729][784][10099][10101]
[10189][10370][10424][10473][10579]
[10622][10699][11172][11219][11233][11503]

F. Seidl, M. Sachse

26

[136][374][382][383][412][443][534][575][579][784][944][993][10042][10082][10099][10116][10162][10222][10469]
[10473][10579][10679][11152][11223][11309][11526]

M. Pesl, R. Reichart, E. Uzeirovic

26

[200][382][386][436][484][960][10006][10041][10079][10139][10178][10193][10312][10323][10370][10405][10469]
[10696][10780][10784][10970][11152]
[11172][11185][11221][11219]

H. Sayli, U. Taskin

21

[382][484][713][10055][10082][10106][10213][10254][10341][10346][10469][10494][10499][10579][10591][10815]
[11115][11161][11172][11448][11462]

J. Tschannerl, D. Leib

18

[138][382][446][484][694][913][10035][10082][10220][10346][10408][10433][10493][10673][10722][10924][10970]
[11309]

M. Stadler, J. Müller

15

[128][344][386][382][543][576][706][10070][10220][10305][10361][10903][10924][11172][11185]


Mathematica-Lösungen

#
Autor(en)
gelöste Probleme
1
Prof. Dr. M. Gruber
382-Perfection (382.nb   382in.dat   382out.dat)
2
Wolfram Demonstrations Project
10104 - Extended Euclid Algorithmus
3 Wolfram Demonstrations Project 960 - Gaussian Primes
4
Wolfram Demonstrations Project 10394 - Twin (+ cousin + sexy) Primes
5 Wolfram Demonstrations Project 543, 686 - Golbach Conjecture
6 Wolfram Demonstrations Project 382-Perfection - Positive Integer Explorer
7
Prof. Dr. M. Gruber 543 - Golbach Conjecture (543.nb  543in.dat  543out.dat)
8
Wolfram Demonstrations Project  10408 - Farey Sequence  - Ford Circles
9
R. Stöhr, Prof. Dr. M. Gruber 10579 - Fibonacci Numbers (10579.nb, 10579in.dat, 10579out.dat)
10
R. Stöhr, Prof. Dr. M. Gruber 11185 - Ternary (11185.nb11185gen.nb)
11
H. Sayli, U. Taskin 10254   -  The Priest Mathematician (10254.nb)

Kursablauf

SW *
KW *
Thema
Vorlesung
Praktikum
1
16

OnlineJudge-Einführung
Infoveranstaltung
Vorlesung01
The 3n+1 Problem (100), Stacking Boxes (103)

Booklet Printing (637), The House of Santa Claus (291)

2
17

Mengen, Relationen, Cantor-Diagonalisierung

[2] S. 59

The Departament of Redundancy Departament
(484), Count on Cantor (264),  Cantor Fractions (880), Relational Operator (11172)

3
18

- Teiler, Teilbarkeit
- Primzahlen, Fundamentalsatz der Arithmetik, 
- ggT, kgV,
- Goldbachsche Vermutung

[2] S. 81

- Anzahl Teiler
- schnelles Potenzieren

Power of Cryptography (113), Factors and Factorials (160),
Perfection (382), Divisors (294), Prime Cuts (406), Pi (412),
Goldbach's Conjecture (543), Prime Factors (583),  Gaussian Primes (960), Twin Primes (10394), Circular (967), Count DePrimes (11408),  GCD (11417), Largest Prime Divisor (11466), Euclid Problem (10104), Goldbach Conjecture II (686), Simply Emirp (10235), Goldbach and Euler (10311), Prime Time (10200), Less Prime (10852), You can say 11 (10929), Factovisors (10139), Summation of Four Primes (10168), Prime Distance (10140), Divison (725), Count the factors (10699), GCD+LCM (11317), Factoring Large Numbers (10392), Digit Primes (10533), Semi-prime H-Numbers (11105), Next Same-Factored (11099), Mr. Azad and His Son!!!!! (10490), Factorizing Large Integers (11476)

4
19

Zahlen, Zahlen, Zahlen







Brute Force

[2] S. 132,

Ugly Numbers (136), Humble Numbers (443), Happy Numbers (944),
Quirksome Squares (256), Kaprekar Numbers (974), Fibonacci Numbers (10579),
Charmichael Numbers (10006), Bangla Numbers (10101),  Self Numbers (640), Smith Numbers (10042), Super Divisible Numbers (995), Cyclic Numbers (942), Selfdescribing Sequence (10049), Ackermann (371), Taxicab Numbers (962), Factorial Factors (884), Farey Sequence (10408), Magic Numbers (471), Pyramid Number (11522),
Perfect Cubes (386), Complex Numbers (10378), Street Numbers (138), Perfect Pth Powers (10622), Couple-Bachelor-Spinster Numbers (10174), Pairsumonious Numbers (10202), Automorphic Numbers (10433), Persistent Numbers (10527), Almost Prime Numbers (10539), Happy Number (10591), Super Number (10624), Fibinary Numbers (763), Spiral of Numbers (903), Rational Spiral (493), How Many 0's? (11038), Abundance and Perfect Numbers (10914), Square Numbers (11461), Spiral Tap (10920)


Ecological Bin Packing (102), Band Width (140), Finding Rectangles (638)
5
20

Zeichenketten


Tafelbild, 6.04.

Tafelbild, 7.04, Factovis...

Keine Angst vor Palindrome!

[2] S. 25w

 
Easter-Bunny Ostern-Challenge: Easter-Eggs (10857  Osternhase

Pig Latin (492), What's The Frequency, Kenneth? (499), The Decoder (458), Marvelous Mazes (445), Encoder and Decoder (444), Rotating Sentences (490), Kindergraten Counting Game (494), Unix ls (400), Password Search (902), Cript Kicker II (850), Palindromic Subsequence (11404), O: dah, dah, dah! (11223), Magic Square Palindromes (11221), Palindromes (401), Word Scramble (483), TEX Quotes (272), WERTYU (10082), Decode the Mad man (10222), Soundex (10260), Haiku Review (576), Automatic Poetry (10361), Love Calculator (10424), Tell me the frequencies! (10062), Prime Frequency (10789), Prime Words (10924), Longest Palindrome (11151), Group Reverse (11192), Babelfish (10282), Glas Beads (719), Formula 1 (11056), Decoding the Message (11220), Deli Deli (11233), Again Palindrome (10617), Make Palindrome (10453), Andy's
First Dictionary (10815), Find the Telephone (10921), String Factoring (11022), LCD Display (706), Bank (Not Quite O.C.R.) (433),  I Love Strings! (10679), The Vigenere Cipher (856)

---------------------------------------------------------------------------------------------------------------------------------------------------------------
Plätze 1, 2, 3 für bisherige: Schönstes Problem ? Schönstes Programm? Leichtestes/schwierigstes Problem? Schlechtestes Programm?

6
21
Verschiedene Formeln









Ebene Geometrie,
[2] S. 139


Square Root Algorithms








Is this the easiest problem? (11479), Box of Bricks (591), Fermat vs. Pythagoras (106), Johanna and the Odd Numbers (913), The Cat in the Hat (107), Pizza Cutting (10079), Product of Digits (993), H(n) (11526), How Old are You? (11219),
What Day is It? (602), Clock Hands (579), The Circumference of the Circle (438), Continued Fractions (834), Above Average (10370), Polynomial Shutdown (392), Error Correction (541), The Collatz Sequence (694), Square Root (10023), Primary Arithmetic (10035), Triangular Vertices (209), Bee Breeding (808), The Trip (10137), Summation of Polynomials (10302), Odd Sum (10783), Big Chocolate (10970), How Far? (10466), Beat the Spread! (10812), Cos(NA) (11170), Colourful Flowers (11152), Peter's Smoke (10346), Solve It (10341), The Land of Justice (10499), Simple Equations (11565), Last Digit (10162), What is the Median? (10107), Powers Et. Al (10515), f(91) (10696), Power of Matrix (11149), Series of Powers (11190), Polynomial Coefficients (10105), Solving Systems of Linear Equations (10109), B2-Sequence (11063), Can You Solve It? (10642), Play with Floor and Ceil (10673), Conic Distance (10495), Cats with or without Hats (10493),  Series of Pi (10736), Poly the Pollynomial (498), Riemann vs. Mertens (10738), Quotient Polynomial (10719), Diagonal (10784), Again Prime? No time (10780), Back to Intermediate Math (10773), Recover Factorial (10856), 2 the 9s (10922), Fractions Again?! (10976), Leap Year or Not Leap Yaer and... (10070), Complex, difficult and complicated (11042), Very Funny, Mr. Feynman! (11120), Multifactorials (11347)


7
22
Basisumwandlung





Simulation

[2] S. 128, 308

What Base is This? (343), Roman Digititis (344), Roman Numerals (185), Fibonaccimal Base (948), The Bases are Loaded (353), Basically Speaking (389), Cowculations (377),
Kibbles "n" Bits "n" Bits "n" Bits (446), The Return of the Roman Empire (759), Skew Binary (575), To Carry or not to Carry (10469), Ternary (11185), Base -2 (11121), Base64 Decoding (10343), The Stern-Brocot Number System (10077), All You Need Is Love! (10193), Simple Base Conversion (10473), Prime Land (516), Fi-binary Number (11089), Power Signs (11166), The Fun Number System (10705), Cheapest Base (11005), Squares III (636)


The Blocks Problem (101), Simulation Wizardry (114), Rock-Paper-Scissors Tournament (10903), Graphical Editor (10267), Check The Check (10196), Minesweeper (10189), Interpreter (10033), Jolly Jumpers (10038),
8
23
Große Zahlen, Modulo











Variable Range Related


Greedy

[2] S. 104, 302

[Big Num]




[Gamma_Funktion
(für 10323)]





[2] S. 283
[Greedy]


Integer Inquiry (424), Factorial Frequencies (324), Big Mod (374), Modular Fibonacci (10229),
I Love Big Numbers! (10220), Factoring Large Numbers (10392), Software CRC (128), Fibonacci Freeze (495), 500! (623), Ocean Deep! Make it shallow! (10176), Very Easy !!! (10523), Product (10106), Super long sums (10013), Factorial! You Must be Kidding!!! (10323), Zeros and Ones (10324), Big Big Real Numbers (10464), Complete Tree Labeling (10247), The Priest Mathematician (10254), Guess the Number! (10275), Towers of Hanoi (254), Arithmetic Operations with Large Integers (288), Palindorms <---> smordnilaP (290), Overflow (465), Numerically Speaking (619), Adding Reversed Numbers (713), Exponentiation (748), Fibinary Numbers (763), Maximum Sub-sequence Product (787), The Mosquito Killer Mosquitos (10108), Expressions (10157), World Cup Noise (10450), If We Where A Child Again (10494), !! Really Strange !! (10519), Opening Doors (10606), Simplifying Fractions (10814), Connect the Cable Wires (10862), Krakovia (10925), The Ghost of Programmers (10992), Uncle Jack (11115), Help My Brother (II) (11161), Matches (11375), Integer Transmission EXTREME (11438), Who said crisis? (11448),


Hashmat the Brave Warrior (10055), All in All (10340)


Station Balance (410),  Balancing Bank Accounts (538), Minimal Coverage (10020), The Grand Dinner (10249), All in All (10340), Packets (311), Shoemaker's Problem (10026), Advertisment (10148), Editor Nottobad (10602), Work Reduction (10670), Ants (10714)
9
24



Presäntationen








Tipps für Präsentation




Plätze 1, 2, 3 für bisherige:
Schönstes Problem ?
Schönstes Programm? Leichtestes/schwierigstes Problem?


20.05:   PhotosPräs. 01 (
C. Posselt, J. Schubert),                 Präs. 02 (C. Miesel, R. Seilbeck, A. Wolfram)
27.05:   PhotosPräs. 03 (
M. Mohr, R. Schirm, F. Mathauser), Präs. 04 (D. Wilfert, J. Studt)
03.06:   PhotosPräs. 05 (
C. Mitterreiter, R. Luigs),                 Präs. 06 (F. Seidl, M. Sachse)
10.06:   PhotosPräs. 07 (
J. Tschannerl, D. Leib),                   Präs. 08 (M. Pesl, R. Reichart, E. Uzeirovic)
17.06:   PhotosPräs. 09 (
H. Sayli, U. Taskin),                       Präs. 10 (M. Stadler, J. Müller)



10
25

Kombinatorik: Prinzip der Inklusion und Exklusion, Schubfachprinzip, Permutationen, Variationen, Kombinationen, Binomial- und Multinomialkoeffizienten


Wahrscheinlichkeitstheorie


[2] S. 153, 189

Tafelbild, 27.05,
Super Lucky Numbers














[Wahrscheinlichkeitstheorie]

Super Lucky Numbers (10722),

Count of Trees (10007), Pascal Triangle of Death (485), Combinations (369), Multinomial Coefficients (911), Ones (10127), Binomial Showdown (530), How Many Fibs (10183), Find the Ways! (10219),
How Many Trees? (10303), Permutations (941), Permutation (11525), Triangle Counting (11401), Permutation Arrays (482), Mischievous Children (10338), Combinatorial Expression (10329), Combination! Once Again (10532), Combinatorial Summation (10694), No Rectangles (135), ID Codes (146),
Critical Mass (580), The partition of a cake (527), Arif in Dhaka (First Love Part 2) (10294), Counting RNA Sequences (11197), Counting (10198), Determine The Combination (10776), LCM Cardinality (10892), The Hamming Distance Problem (729), The Last Non-zero Digit. (10212), Expressions (10157), How Many Pieces of Land? (10213), Coin Toss (10328), Ray Through Glasses (10334), Say NO to Memorization (10634), Extrapolation using a Difference Table (326), How Many? (986), Expression Bracketing (10312), Coin Toss (10328), Cubes (10601), How Many Points of Intersection? (10790), Tri Triling (10918), A Graph Problem (11069), Necklace (11255), Tiling Dominoes (11270), Mixing Invitations (11282), Sultan's Chandelier (11240), Counting Chaos (11309),





France '98 (542), Burger (557), Coupons (10288), Urn-ball Probabilities! (10169), What is the Probability? (10056), Probability (11346)

11
26

Graphen:

  - kürzeste Wege (Floyd-Warshall)

  - Tiefen- und Breitensuche

  - topologische Sortierung

  - minimaler Spannbaum

[2] S.  251


Tafelbild, 01.07,
534 Frogger


Tafelbild, 01.07,
784 Maze Exploration


[Floyd-Warshall]


[BFS]  [DFS]




[Topologische Sortierung]



[Flooding-Algorithmus]



[Minimal Spannbaum]
[Kruskal] [Prim]



Tree Summing (112), The Postal Worker Rings Once (117), Trees on the level (122), Graph Coloring (193), Tree Recovery (536), Allways on the run (590), Mapping the Route (614), Is it a Tree? (615), The die is cast (657),  Dropping Balls (679), Longest Paths (10000), Bicoloring (10004), All Roads Lead Where? (10009), Wheres's Waldorf? (10010),
Robot Motion (10116), Roads in the North (10308), Ecosystem (626), Numbering Paths (125), Climbing Trees (115), Count the Faces (10178), Virtual Friends (11503)





Frogger (534), Heavy Cargo (544), Risk (567),
Audiophobia (10048), The Tourist Guide (10099), Identifying Concurrent Events (334),  MPI Maelstrom (423), Arbitrage II (436), Page Hopping (821),

Shipping Routes (383), Software Allocation (259), Knight Moves (439), All Walks of length "n" from the first node (677),  We Ship Cheap (762),  Dungeon Master (532), Word Transformation (429), Vertex (280), Traveling Politician (10543), A Node Too Far (336),  Always in the Run (590),  The Net (627), Erdös Numers (10044),


Rare Order (200), Ordering Tasks (10305)



Arbitrage II (436), Wetlands of Florida (469),
The Seasonal War (352), The PATH (601), Grid Colouring (785), Il Giocco dell'X (260), Oil Deposits (572), Monkeys in a Regular Forest (776), Contour Painting (782), Maze Exploration (784),


Frogger (534), Freckles (10034), Highways (10147), Connect the Campus (10397), Killing Alliens in Borg Maze (10307)









                Tafelbild, 08.07
12
27
Dynamische Programmierung: Counting Change, Longest Inc-/Decreasing Sequence, LCS, Matrix Chain Multiplication
[2] S. 403
[1] S. 231
NUS_DP

Longest Common Subsequence (10405), Unidirectional TSP (116), Optimal Array Multiplication Sequence (348),
Matrix Chain Multiplication (442), Let Me Count The Ways (357), Dollars (147), Coin Change (674), Histroy Grading (111), String Computer (164), Budget Travel (222), Testing the CATCHER (231), Strategic Defense Initiative (497), Jill Rides Again (507), String Distance and Transform Process (526), Compromise (531), Triangles (585), Self Numbers (640),  Optimal Array Multiplication Sequence (348), Walking on the Safe Side (825), Largest Submatrix (836), Vacation (10192), Longest Run on a Snowboard (10285), e-Coins (10306), Homer Simpson (10465), Sumsets (10125), Travelling Salesman (10702), Again Palindrome (10617), Make Palindrome (10453), Complete Tree Labeling (10247), The Unreal Tournament (10207), Facing Problem with Trees (10643), Super Lucky Numbers (10722)

13
28, 29
Backtracking






Sorting
[2] S. 403
[1] S. 357

All Squares (155), The Sultan's Successor (167), Getting in Line (216),  The House of Santa Claus (291), Word-Search Wonder (422),
Prime Ring Problem (524), Addition Chains (529), The Settlers of Catan (539), Jugs (571), CD (624), Su Doku (989), LED Test (416), The Tower of Babylon (437), Sum It Up (574), Bundling Newspapers (598), 8 Queens Chess Problem (750),  Not so Mobile (839), Another n-Queen Problem (11195), Sum-up the Primes (10419), 23 out of 5 (10344), Equidivisions (11110), Take the Land (10074)


Dancing Digits (11198), ShellSort (10152), DNA Sorting (612), Flip Sort (10327), Stacks of Flapjacks (120), Age Sort (11462), Vito's Family (10041), Sort! Sort!! and Sort!!! (11321), Ultra QuickSort (10810)

* SW = "Semesterwoche", KW = "Kalenderwoche"

Literatur
 
1.  Doina Logofătu, Grundlegende Algorithmen mit Java, Vieweg Verlag, ISBN 978-3-8348-0369-6, 2008. (online in Campus)
2.  Doina Logofătu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0126-5, 2006. (online in Campus)
3.  Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, 2. Auflage, Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8.
  - Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, Boston 2001, 2002, 2003, 2005
     ISBN 0-262-53196-8. (engl. Orig.-Fass.)
4.
Online Platform: ACM Uva Online Judge
5. ProblemSolve Toolkit: http://www.uvatoolkit.com/problemssolve.php
6. World of Seven
7. Art of Programming Contest
8. Programming Challenges: http://www.programming-challenges.com
9. ICPC Live Archive: http://acmicpc-live-archive.uva.es/nuevoportal/


Weiteres
5.  Timus Online Judge
6.  Hinweise für Neueinsteiger
7.  Topcoder: ein weiterer Programmierwettbewerb, der nicht nur Studenten offen steht