Angewandte Mathematik, SS11

Montags, 8:15 - 11:30, R2.012 und Dienstags, 13:30 - 16:45, R2.014
Dozentin: Doina Logofătu  ^


Die Vorlesung verwendet C, C++ oder Java als Programmiersprache.
Der Kurs folgt dem Buch Algorithmen und Problemlösungen mit C++ (einige Themen findet man auch in [2]).
Dieses Lehrbuch zur Vorlesung ("Kursbuch") findet man in unserer Bibliothek (auch Online im Campus).

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.

Online Platform: ACM Uva Online Judge
Electronic Board: acm.uva.es/board/
Bitte nicht vergessen!: Kopfkommentar



StudentIn / Team

Accepted

gelöste Probleme

Johannes Vogel
Felix Schramm
16
[11172][10424][382][960][10929][10622][10139][495][10302][10341][12015][10432][11936][11984]
[11554][11960]

Präsentation

Florian Stein
Franz Sommer
32
[11172][10424][10038][960][543][686][382][967][10235][10622][10220][11876][374][424]
[10370][591][11152][11385][541][11799][107][880][264][10035][694][10137][10105][10023]
[12004][10491][11984][10182]

Präsentation

Tuan Anh Tran
Stefan Haas
7
[11172][11734][424][10340][10925][10783][11805]
Marius Ritter
Stefan Zehenbauer
Thomas Wende
19
[11172][11734][412][382][543][686][424][10079]
[11879][10622][324][374][11219][107][10023][11309][11970][11936][11984]

Präsentation
Primfaktorzerlegung.jar   ListenerPrimConverter.java  Primfaktorzerlegung.java

Benjamin Vogt
Sebastian Strumpf
42
[10424][11734][10104][382][412][543][686][11172][11879][568][10139][10622][10235][967]
[10392][11878][324][424][623][10220][495][10055][10176][10297][11385][201][918][11461]
[11715][10491][11346][107][10105][11309][101][107][374][10105][10929][11955][11962][12015][11936]

Präsentation    Handout  Teil1  Teil2 
ASCII_Mandelbrot      TO_TXT
Escaping_from_Fractal_Bacterium

Gulchiroy Toshtemirova
2
[11172][11734]

Fotos Referate 24. Juni, 1. Juli

Daniel Brielbeck
Georg Weber
36
protokoll_1    [11172][10071][10038]
protokoll_2    [
10424][10370]
protokoll_3
    [11879][623][10929]
protokoll_4    [10139][10622]
[748][374][10494][10523][424][11448][10106][713][913][10079][11479][579][591][10302][10105][485]
[530][107][10491][10790][10288][11955][10432][11936][11984][12004]

Referat Handout   Vortrag   Demo-Programm

Michael Unverzart
Manuel Wurth
44
[382][10038][10071][10370][11172][11734][10189][10235][10394][10490][623][10929][11879][10622]
[424][748][10106][10176][10220][10523][11448][591][913][10079][602][11777][10302][10127][10303][10784][10338]
[542][10008][10790][10918][10499][11962][10432][11984][893][10070][11356][12019][602]

Präsentation

Benedikt Zönchen
Erik Wenzel

52
[10193][10370][10071][11734][10038][11661][102][10424][10189][11608][382][11172][11877]
[623][10311][11879][11716][543][412][10235][10929][686][10139][10622][160][11466][538][374][495][424][10229][311]
[369][541][729][941][107][10105][10719][482][10007][11525][542][10341][12015][12024][146][11960]

Präsentation  Handout
Main.java  Permutation.java  PermutationAplet.java

Andreas Maier
Markus Schöllner

33
[382][11172][10929][10490][10139][350][424][10055][10106][10523]
[485]
[10079][10370][11479][10023][392][10329][10338][10213][10008][10018][10334][11069]
[10183][12015][530][10107][10007][10432][11936][11984][10312][10790]

Präsentation  Handout  Beispiele

Fabian Trampusch
Robert Schwarz

22
[11172][10038][568][10929][10139][10622][465][10106][10450][623][10970][11461]
[918][11461][107][392][498][10719][10268][10586][12015][11966]

Präsentation  Polygon_Integral  Newtonverfahren  Polynomfunktionsammlung  PolynomialGCD

Peter Weismann,
Primin Schneider

18
[11172][412][10699][11417][543][424][11115][10925][10812]
[10523][374]
[485][10340][10903][11170][10927][11152][11326]

Präsentation

Gent Selmanaj,
Marco Schuster,
Christoph Westerfield
21
[11172][10110][10490][11875]][10038][10071][10424][583][623][10622][10139][374][10055][10464][11715][10392][591]
[11479][107][392][146]

Präsentation

Bastian Hoecker
Philipp Hauck Thalheim

1
[11716]
Christoph Waldleitner
Christian Weber
Marco Wolff
21
[11172][10038][10699][10929][382][10929][10622][10139][11466][406][10220][424][11219][11479][10642][10719]
[482][537][10181][10109][10309]

Präsentationen:  10181 Puzzle Problem    10109 Solving Systems of Linear Equations  
                             10309 Turn the Lights Off


Kursablauf

SW *
KW *
Thema
Vorlesung
Praktikum

1


OnlineJudge-Einführung
Infoveranstaltung





Warm-Up


Vorlesung01







Beispiele:
The 3n+1 Problem (100), Stacking Boxes (103)
Booklet Printing (637), The House of Santa Claus (291)



Relational Operator (11172), Big Number of Teams will solve This (11734),  Informants (11659), Love Calculator (10424), Perfection (382), B2-Sequence (11063), Above Average (10370), Jolly Jumpers (10038), All You Need Is Love! (10193), LC-Display (706), Ecological Bin Packing (102), Power of Cryptography (113), Digital Fortress (11716), sqrt log sin (11703), Big Mod (374), Product (10106), Super long sums (10013), Minesweeper (10189), No Problem (11608), Hello World! (11636),
Burger Time? (11661), Back to High School Physics (10071), Ecological Premium (10300),  Triangle Wave (488), Hangman Judge (489), Linear Cellular Automata (457), Marvelous Mazes (445), Power Crisis (151), 487--3279 (755), The Coca-Cola Store (11877), Homework Checker (11878), Reverse and Add (10118)


2


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

[1] S. 81

- Anzahl Teiler
- schnelles Potenzieren


Tafelbild 28.03

Tafelbilder
4.04: 1, 2, 3
5.04: 1, 2, 3, 4
11.04: 1



Light, more light (10110), Multiplying by Rotation (550),  Just the Facts (568), Uniform Generator (408), Pseudo-Random Numbers (350), How many zero's and how many digits? (10061), Code Refactoring (10879), 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), Doom's Day (11774),
Again Prime? No time (10780), Factorial Frequences (324), Perfect P-th Powers (10622), Brick Game (11875), N+NOD(N) (11876), 500! (623), Benefit (11889), Multiple of 17 (11879), Jumping Champion (914), Reverse Prime (11610),

3

Große Zahlen, Modulo


Variable Range Related



Greedy

[2] S. 104, 302

[Big Num]

Gamma_Funktion
(für 10323)]


[2] S. 283
[Greedy]

Tafelbilder
18.04: 1
19.04: 1 2 3
25.04: 1

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),


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)

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





4


Verschiedene Formeln
















Simulation

Ebene Geometrie,
[1] S. 137


Square Root Algorithms


Tafelbilder
3.05: 1  2  3  4

9.05: 1  2  3  4
10.05: 1  2
16.05: 1  2  3

23.05: 1  2  3
24.05: 1  2  3  4  5  6



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), 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), Artificial Intelligence? (537), Squares (201), Hypercube (11785), Escape (11784), Miles 2 Km (11780), Automate the Grades (11777), Where's Waldorf? (10010), Car (11715), Numeral Hieroglyphs (11787), Machined Surfaces (414), Word Index (417), Excuses, Excuses! (409),
Master-Mind Hints (340), Train Swapping (299), Tree's a Crowd (152), Krochanska is Here! (11792), Murcia's Skyline (11790), Global Raining at Bididbus (11786), Square Numbers (11461),
Grocery Store (11236), Andy's first dictionary (10815), List of Conquests (10420), Reverse and Add (10018), What's Chryptanalysis? (10008), Bicoloring (10004),
Glas Beads (719), UNIX ls (400), Intersection (191), Anagrams (156), Searching Quickly (123),  Argentina (11804), Bafana, Bafana (11805), Horror Dash (11799), Puzzle (227),
Circle Through Three Points (190), Long Multiplication (338), The Bases are Loaded (355), Square Pegs and Round Holes (356), Inscribed Circles in Isosceles Triangles (375),
Fifth Bank of Swamp Company (426), Swamp County Roofs (428), Population Explosion (447), Majoring in Scales (449), Anagrams (454), Periodic Strings (455), Overlapping Rectangles (460), Mirror, Mirror (466), Key to Success (468),
Boogle Blitz (487), Parantheses Balance (673), Jack and Jill (697), Index (698), Triangular Museum (744), Biorhythms (756),
Interpreter (10033), Chainsaw Massacre (10043),
Da Vinci Code (11385), Egypt (11854), SOAP Response (11869), Bee Maja (10182), Count on Cantor (264), Cantor Fractions (880), Beavergnaw (10927), Y3K Problem (893), Dates (11356), Doom's Day Algorithm (12019), 15-Puzzle Problem (10181), Turn the Lights Off (10309)

The Blocks Problem (101), Simulation Wizardry (114), Rock-Paper-Scissors Tournament (10903), Graphical Editor (10267), Check The Check (10196), Minesweeper (10189), Interpreter (10033)

5


Presäntationen


Tipps für Präsentation

Programming Day 29. Mai 2011

Calculus Simplified (11890)
, Beawergnaw (10297), ASCII Mandelbrot (918), 498' (10268), Polynomial Remains (10586), Google is Feeling Lucky (12015),
Lucky Numbers (11970), Binomial Theorem (11955), DNA II (11962)

Programming Day 19. Juni 2011
Bubble Sort (12004), Complete the Set (12011), Fast Matrix Operations (11992), Fire Station (10278), A Change in Thermal Unit (11984),
Galactic Bonding (11966), The Lazy Lumberjacks (11936), Net Profit (11932), Divisor Game (11960), Hapless Hedonism (11554),
Polygon Inside a Circle (10432), Electoral Districts (11793)


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





6



Wahrscheinlichkeitstheorie






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



[Wahrscheinlichkeitstheorie]






[2] S. 153, 189
Combinatorics




France '98 (542), Burger (557), Coupons (10288), Urn-ball Probabilities! (10169), What is the Probability? (10056), Probability (11346),
Joining With Friend (11722), Cows and Cars (10491),
Supermean (10883),


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),
Teams (11609), 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), ID Codes (146)


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

Literatur
 
1.  Doina Logofătu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0763-2, 2010. (online in Campus)
2.  Doina Logofătu, Grundlegende Algorithmen mit Java, Vieweg Verlag, ISBN 978-3-8348-0369-6, 2008. (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/
10. 
Common Mistakes in Online and Real-time Contests
11. 
Competition Strategies

Weiteres
12.  Timus Online Judge
13.  Hinweise für Neueinsteiger
14.  Topcoder: ein weiterer Programmierwettbewerb, der nicht nur Studenten offen steht
15.  Problemsets: http://bbs.cooldavid.org/acm/

Java
15. 
Java™ Platform, Standard Edition 6 API Specification, Online Referenz: http://java.sun.com/javase/6/docs/api/, Sun Microsystems, Inc, 2006.