Understanding and Using Linear Programming

Author: Jiri Matousek,Bernd Gärtner

Publisher: Springer Science & Business Media

ISBN: 3540307176

Category: Mathematics

Page: 226

View: 881


The book is an introductory textbook mainly for students of computer science and mathematics. Our guiding phrase is "what every theoretical computer scientist should know about linear programming". A major focus is on applications of linear programming, both in practice and in theory. The book is concise, but at the same time, the main results are covered with complete proofs and in sufficient detail, ready for presentation in class. The book does not require more prerequisites than basic linear algebra, which is summarized in an appendix. One of its main goals is to help the reader to see linear programming "behind the scenes".

Approximation Algorithms and Semidefinite Programming

Author: Bernd Gärtner,Jiri Matousek

Publisher: Springer Science & Business Media

ISBN: 3642220150

Category: Mathematics

Page: 251

View: 6525


Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material. There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms. This book follows the “semidefinite side” of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms.


Structures for Algorithms and Applications

Author: Jesus De Loera,Joerg Rambau,Francisco Santos

Publisher: Springer Science & Business Media

ISBN: 9783642129711

Category: Mathematics

Page: 535

View: 3690


Triangulations presents the first comprehensive treatment of the theory of secondary polytopes and related topics. The text discusses the geometric structure behind the algorithms and shows new emerging applications, including hundreds of illustrations, examples, and exercises.

Geometric Methods and Applications

For Computer Science and Engineering

Author: Jean Gallier

Publisher: Springer Science & Business Media

ISBN: 9781441999610

Category: Mathematics

Page: 680

View: 2595


This book is an introduction to the fundamental concepts and tools needed for solving problems of a geometric nature using a computer. It attempts to fill the gap between standard geometry books, which are primarily theoretical, and applied books on computer graphics, computer vision, robotics, or machine learning. This book covers the following topics: affine geometry, projective geometry, Euclidean geometry, convex sets, SVD and principal component analysis, manifolds and Lie groups, quadratic optimization, basics of differential geometry, and a glimpse of computational geometry (Voronoi diagrams and Delaunay triangulations). Some practical applications of the concepts presented in this book include computer vision, more specifically contour grouping, motion interpolation, and robot kinematics. In this extensively updated second edition, more material on convex sets, Farkas’s lemma, quadratic optimization and the Schur complement have been added. The chapter on SVD has been greatly expanded and now includes a presentation of PCA. The book is well illustrated and has chapter summaries and a large number of exercises throughout. It will be of interest to a wide audience including computer scientists, mathematicians, and engineers. Reviews of first edition: "Gallier's book will be a useful source for anyone interested in applications of geometrical methods to solve problems that arise in various branches of engineering. It may help to develop the sophisticated concepts from the more advanced parts of geometry into useful tools for applications." (Mathematical Reviews, 2001) "...it will be useful as a reference book for postgraduates wishing to find the connection between their current problem and the underlying geometry." (The Australian Mathematical Society, 2001)

The Multivariate Algorithmic Revolution and Beyond

Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday

Author: Hans L. Bodlaender,Rodney Downey,Fedor V. Fomin,Dániel Marx

Publisher: Springer

ISBN: 3642308910

Category: Computers

Page: 506

View: 4701


Parameterized complexity is currently a thriving field in complexity theory and algorithm design. A significant part of the success of the field can be attributed to Michael R. Fellows. This Festschrift has been published in honor of Mike Fellows on the occasion of his 60th birthday. It contains 20 papers that showcase the important scientific contributions of this remarkable man, describes the history of the field of parameterized complexity, and also reflects on other parts of Mike Fellows’s unique and broad range of interests, including his work on the popularization of discrete mathematics for young children. The volume contains several surveys that introduce the reader to the field of parameterized complexity and discuss important notions, results, and developments in this field.

Endliche Gruppen

Eine Einführung in die Theorie der endlichen Gruppen

Author: H. Kurzweil

Publisher: Springer-Verlag

ISBN: 3642953131

Category: Mathematics

Page: 190

View: 869


Numerische Behandlung partieller Differentialgleichungen

Author: Christian Großmann,Hans-Görg Roos

Publisher: Springer-Verlag

ISBN: 9783519220893

Category: Mathematics

Page: 572

View: 5712


Mathematiker, Naturwissenschaftler und Ingenieure erhalten mit diesem Lehrbuch eine Einführung in die numerische Behandlung partieller Differentialgleichungen. Diskutiert werden die grundlegenden Verfahren - Finite Differenzen, Finite Volumen und Finite Elemente - für die wesentlichen Typen partieller Differentialgleichungen: elliptische, parabolische und hyperbolische Gleichungen. Einbezogen werden auch moderne Methoden zur Lösung der diskreten Probleme. Hinweise auf aktuelle Software sowie zahlreiche Beispiele und Übungsaufgaben runden diese Einführung ab.

Kombinatorische Optimierung

Theorie und Algorithmen

Author: Bernhard Korte,Jens Vygen

Publisher: Springer-Verlag

ISBN: 3540769196

Category: Mathematics

Page: 675

View: 4324


Das Lehrbuch ist die deutsche Übersetzung der 4., wesentlich erweiterten Auflage des Titels „Combinatorial Optimization – Theory and Algorithms". Es gibt den neuesten Stand der kombinatorischen Optimierung wieder und liefert vornehmlich theoretische Resultate und Algorithmen mit beweisbar guten Laufzeiten und Ergebnissen, jedoch keine Heuristiken. Enthalten sind vollständige Beweise, auch für viele tiefe und neue Resultate, von denen einige bisher in der Lehrbuchliteratur noch nicht erschienen sind. Mit Übungen und umfassendem Literaturverzeichnis.

Meine Zahlen, meine Freunde

Glanzlichter der Zahlentheorie

Author: Paulo Ribenboim

Publisher: Springer-Verlag

ISBN: 3540879579

Category: Mathematics

Page: 391

View: 317


Paulo Ribenboim behandelt Zahlen in dieser außergewöhnlichen Sammlung von Übersichtsartikeln wie seine persönlichen Freunde. In leichter und allgemein zugänglicher Sprache berichtet er über Primzahlen, Fibonacci-Zahlen (und das Nordpolarmeer!), die klassischen Arbeiten von Gauß über binäre quadratische Formen, Eulers berühmtes primzahlerzeugendes Polynom, irrationale und transzendente Zahlen. Nach dem großen Erfolg von „Die Welt der Primzahlen" ist dies das zweite Buch von Paulo Ribenboim, das in deutscher Sprache erscheint.

Wissenschaftliches Rechnen mit MATLAB

Author: Alfio Quarteroni,Fausto Saleri

Publisher: Springer-Verlag

ISBN: 3540293078

Category: Mathematics

Page: 269

View: 1709


Aus den Rezensionen der englischen Auflage: Dieses Lehrbuch ist eine Einführung in das Wissenschaftliche Rechnen und diskutiert Algorithmen und deren mathematischen Hintergrund. Angesprochen werden im Detail nichtlineare Gleichungen, Approximationsverfahren, numerische Integration und Differentiation, numerische Lineare Algebra, gewöhnliche Differentialgleichungen und Randwertprobleme. Zu den einzelnen Themen werden viele Beispiele und Übungsaufgaben sowie deren Lösung präsentiert, die durchweg in MATLAB formuliert sind. Der Leser findet daher nicht nur die graue Theorie sondern auch deren Umsetzung in numerischen, in MATLAB formulierten Code. MATLAB select 2003, Issue 2, p. 50. [Die Autoren] haben ein ausgezeichnetes Werk vorgelegt, das MATLAB vorstellt und eine sehr nützliche Sammlung von MATLAB Funktionen für die Lösung fortgeschrittener mathematischer und naturwissenschaftlicher Probleme bietet. [...] Die Präsentation des Stoffs ist durchgängig gut und leicht verständlich und beinhaltet Lösungen für die Übungen am Ende jedes Kapitels. Als exzellenter Neuzugang für Universitätsbibliotheken- und Buchhandlungen wird dieses Buch sowohl beim Selbststudium als auch als Ergänzung zu anderen MATLAB-basierten Büchern von großem Nutzen sein. Alles in allem: Sehr empfehlenswert. Für Studenten im Erstsemester wie für Experten gleichermassen. S.T. Karris, University of California, Berkeley, Choice 2003.

Diskrete Mathematik

Eine Entdeckungsreise

Author: Jaroslav Nešetril

Publisher: Springer-Verlag

ISBN: 3662067560

Category: Mathematics

Page: 459

View: 6461


Wozu hat eine Einführung in die diskrete Mathematik ein so langes Vorwort? Was wollen wir überhaupt sagen? Es gibt viele Wege zur diskreten Mathematik. Zunächst wollen wir Wegweiser aufstellen, denen wir beim Schreiben zu folgen versucht haben; der Leser mag dann über unseren Erfolg entscheiden. Außerdem geben wir einige eher technische Hinweise, wie man nach diesem Buch eine Vorlesung halten kann, zu den Übungsaufgaben, zur Literatur usw. Hier nun also einige Leitgedanken, die dieses Buch vielleicht von anderen mit ähnlichem Titel und Inhalt unterscheiden . • Mathematisches Denken entwickeln. Unser Hauptziel, wichti ger als das Vermitteln mathematischer Fakten, ist beim Studen ten Verständnis für mathematische Begriffe, Definitionen und Beweise zu wecken und ihn (oder sie!) zu befähigen, Proble me zu lösen, die mehr als nur Standardrezepte erfordern, sowie mathematische Gedanken präzise auszudrücken. Mathematische Denkgewohnheiten sind in vielen Lebensbereichen von Vorteil, z. B. beim Programmieren oder bei der Entwicklung komplexer 1 Anlagen. Viele private (gut zahlende) Firmen scheinen das zu wissen. Sie interessieren sich nicht wirklich dafür, ob der Bewer ber vollständige Induktion im Schlaf kann, aber sie wünschen sich, dass er gewohnt ist, sich komplexe Konzepte in kurzer Zeit anzueignen - mathematische Sätze sind dafür offenbar ein her vorragendes Training.

Das BUCH der Beweise

Author: Martin Aigner,Günter M. Ziegler

Publisher: Springer-Verlag

ISBN: 3662064545

Category: Mathematics

Page: 247

View: 2870


Die elegantesten mathematischen Beweise, spannend und für jeden Interessierten verständlich. "Der Beweis selbst, seine Ästhetik, seine Pointe geht ins Geschichtsbuch der Königin der Wissenschaften ein. Ihre Anmut offenbart sich in dem gelungenen und geschickt illustrierten Buch." Die Zeit

Operations Research


Author: Frederick S. Hillier,Gerald J. Liebermann

Publisher: Walter de Gruyter GmbH & Co KG

ISBN: 3486792083

Category: Business & Economics

Page: 868

View: 7399


Aus dem Vorwort der Autoren: “ bereits in früheren Auflagen sind uns auch bei dieser Auflage der Motivationscharakter und die Einfachheit der Ausführungen wichtiger als exakte Beweise und technische Freiheiten. Wir glauben, dass die vorliegende Auflage für den praxisorientierten Studenten, auch ohne große mathematische Kenntnisse, attraktiver und besser lesbar geworden ist. Dennoch sind wir der Meinung, dass die Theorie der Operations Research nur von der mathematischen Seite her wirklich verstanden und gewürdigt werden kann. Es ist daher auch die fünfte Auflage nach wie vor an den gleichen Leserkreis wie die früheren Auflagen gerichtet, an die Studenten verschiedenster Fachrichtungen (Ingenieurswesen, Wirtschafts- und Sozialwissenschaften sowie mathematische Wissenschaften), die sich manchmal angesichts des riesigen Wortschwalls ihrer Studiengebiete nach einem bißchen mathematischer Klarheit sehnen. Die einzelnen Kapitel lassen sich auf vielfältige Art und Weise zu Kursen oder zum Selbststudium zusammenstellen, da das Buch sehr flexibel angelegt ist. Teil eins liefert eine Einführung in die Thematik des Operations Research. Teil zwei (über lineare Programmierung) und auch Teil drei (über mathematische Programmierung) lassen sich unabhängig von Teil vier (über stochastische Modelle) durcharbeiten.“

Analysis 1

Author: V. A. Zorich

Publisher: Springer-Verlag

ISBN: 3540332782

Category: Mathematics

Page: 598

View: 4301


Ausführlicher Einblick in die Anfänge der Analysis: von der Einführung der reellen Zahlen bis hin zu fortgeschrittenen Themen wie Differentialformen auf Mannigfaltigkeiten, asymptotische Betrachtungen, Fourier-, Laplace- und Legendre-Transformationen, elliptische Funktionen und Distributionen. Ausgerichtet auf naturwissenschaftliche Fragestellungen und in detaillierter Herangehensweise an die Integral- und Differentialrechnung. Mit einer Fülle hilfreicher Beispiele, Aufgaben und Anwendungen. In Band 1: vollständige Übersicht zur Integral- und Differentialrechnung einer Variablen, erweitert um die Differentialrechnung mehrerer Variablen.

Differentialgleichungen und ihre Anwendungen

Author: Martin Braun

Publisher: Springer-Verlag

ISBN: 3642973418

Category: Mathematics

Page: 596

View: 7842


Dieses richtungsweisende Lehrbuch für die Anwendung der Mathematik in anderen Wissenschaftszweigen gibt eine Einführung in die Theorie der gewöhnlichen Differentialgleichungen. Fortran und APL-Programme geben den Studenten die Möglichkeit, verschiedene numerische Näherungsverfahren an ihrem PC selbst durchzurechnen. Aus den Besprechungen: "Die Darstellung ist überall mathematisch streng und zudem ungemein anregend. Abgesehen von manchen historischen Bemerkungen ... tragen dazu die vielen mit ausführlichem Hintergrund sehr eingehend entwickelten praktischen Anwendungen bei. ... Besondere Aufmerksamkeit wird der physikalisch und technisch so wichtigen Frage nach Stabilität von Lösungen eines Systems von Differentialgleichungen gewidmet. Das Buch ist wegen seiner geringen Voraussetzungen und vorzüglichen Didaktik schon für alle Studenten des 3. Semesters geeignet; seine eminent praktische Haltung empfiehlt es aber auch für alle Physiker, die mit Differentialgleichungen und ihren Anwendungen umzugehen haben." #Physikalische Blätter#

Bernhard Riemann 1826–1866

Wendepunkte in der Auffassung der Mathematik

Author: Detlef Laugwitz

Publisher: Springer-Verlag

ISBN: 3034889836

Category: Mathematics

Page: 348

View: 2318


Das Riemannsche Integral lernen schon die Schüler kennen, die Theorien der reellen und der komplexen Funktionen bauen auf wichtigen Begriffsbildungen und Sätzen Riemanns auf, die Riemannsche Geometrie ist für Einsteins Gravitationstheorie und ihre Erweiterungen unentbehrlich, und in der Zahlentheorie ist die berühmte Riemannsche Vermutung noch immer offen. Riemann und sein um fünf Jahre jüngerer Freund Richard Dedekind sahen sich als Schüler von Gauss und Dirichlet. Um die Mitte des 19. Jahrhunderts leiteten sie den Übergang zur "modernen Mathematik" ein, der eine in Analysis und Geometrie, der andere in der Algebra mit der Hinwendung zu Mengen und Strukturen. Dieses Buch ist der erste Versuch, Riemanns wissenschaftliches Werk unter einem einheitlichen Gesichtspunkt zusammenzufassend darzustellen. Riemann gilt als einer der Philosophen unter den Mathematikern. Er stellte das Denken in Begriffen neben die zuvor vorherrschende algorithmische Auffassung von der Mathematik, welche die Gegenstände der Untersuchung, in Formeln und Figuren, in Termumformungen und regelhaften Konstruktionen als die allein legitimen Methoden sah. David Hilbert hat als Riemanns Grundsatz herausgestellt, die Beweise nicht durch Rechnung, sondern lediglich durch Gedanken zu zwingen. Hermann Weyl sah als das Prinzip Riemanns in Mathematik und Physik, "die Welt als das erkenntnistheoretische Motiv..., die Welt aus ihrem Verhalten im un- endlich kleinen zu verstehen."

Differentialgeometrie von Kurven und Flächen

Author: Manfredo P. do Carmo

Publisher: Springer-Verlag

ISBN: 3322850722

Category: Technology & Engineering

Page: 263

View: 513


Inhalt: Kurven - Reguläre Flächen - Die Geometrie der Gauß-Abbildung - Die innere Geometrie von Flächen - Anhang