Luccio / Pagli / Steel Mathematical and Algorithmic Foundations of the Internet

Erscheinungsjahr 2011
ISBN: 978-1-4398-3139-7
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 221 Seiten

Reihe: Chapman & Hall/CRC Applied Algorithms and Data Structures series

To truly understand how the Internet and Web are organized and function requires knowledge of mathematics and computation theory. Mathematical and Algorithmic Foundations of the Internet introduces the concepts and methods upon which computer networks rely and explores their applications to the Internet and Web. The book offers a unique approach to mathematical and algorithmic concepts, demonstrating their universality by presenting ideas and examples from various fields, including literature, history, and art.

Progressing from fundamental concepts to more specific topics and applications, the text covers computational complexity and randomness, networks and graphs, parallel and distributed computing, and search engines. While the mathematical treatment is rigorous, it is presented at a level that can be grasped by readers with an elementary mathematical background. The authors also present a lighter side to this complex subject by illustrating how many of the mathematical concepts have counterparts in everyday life.

The book provides in-depth coverage of the mathematical prerequisites and assembles a complete presentation of how computer networks function. It is a useful resource for anyone interested in the inner functioning, design, and organization of the Internet.

Zielgruppe

Computer scientists; undergraduate students in computer science and computer engineering.

Autoren/Hrsg.

Luccio, Fabrizio

Pagli, Linda

Steel, Graham

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
• Mathematik | Informatik Mathematik Operations Research Graphentheorie
• Mathematik | Informatik EDV | Informatik Digital Lifestyle Internet, E-Mail, Social Media
• Mathematik | Informatik Mathematik Operations Research Spieltheorie
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

An Unconventional Introduction to the Internet

Exponential Growth

Sequences and Trees
The expressiveness of sequences

Comparing sequences

From sequences to trees

The Algorithm: The Key Concept
Functions, algorithms, and decidability
Computational complexity

Searching: a basic Internet problem

Lower bounds

A world of exponential problems

Computation goes green

A World of Randomness
Probability theory develops

Randomness as incompressibility

Compressing and hashing

Randomized algorithms

Example: file sharing on the Internet

Randomness and humans (instead of computers)

Networks and Graphs
The adjacency matrix and its powers

The random growth of graphs

Power laws: the rich get richer

Giant Components, Small Worlds, Fat Tails, and the Internet
The emergence of giant components

The perception of small worlds

Fat tails

The DNS tree: between names and addresses

The Internet graph

The Web graph

Graph communities and the Web

Parallel and Distributed Computation
The basic rules of cooperation

Working in parallel: some logical problems

A distributed world

Some logically hard problems

A closer look at routing

Browsers and Search Engines
Caching Web pages

From browsers to search engines

The anatomy of a search engine
Spamming the Web

Epilogue
From mail to telephones

Storing information

The hypertext revolution

Where are we now, and where are we going?

Index

Über Autor(innen)

Fabrizio Luccio and Linda Pagli are professors of informatics at the University of Pisa.
Graham Steel is an INRIA research fellow at LSV, CNRS & ENS de Cachan.