Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2018 | Buch

A Brief Historical Outline Kapitel lesen Erstes Kapitel lesen

Computational Thinking

First Algorithms, Then Code

verfasst von: Prof. Paolo Ferragina, Prof. Fabrizio Luccio

Verlag: Springer International Publishing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This book offers a gentle motivation and introduction to computational thinking, in particular to algorithms and how they can be coded to solve significant, topical problems from domains such as finance, cryptography, Web search, and data compression.

The book is suitable for undergraduate students in computer science, engineering, and applied mathematics, university students in other fields, high-school students with an interest in STEM subjects, and professionals who want an insight into algorithmic solutions and the related mindset. While the authors assume only basic mathematical knowledge, they uphold the scientific rigor that is indispensable for transforming general ideas into executable algorithms. A supporting website contains examples and Python code for implementing the algorithms in the book.

Inhaltsverzeichnis

Frontmatter
Chapter 1. A Brief Historical Outline
Abstract
Computation, in the sense of computing numbers, has existed since ancient times. In a papyrus written around 1650 B.C., the scribe Ahmes described to Egyptians how to multiply by doubles, halves, and additions according to a method known long before his writing. We begin with a modern version of this method, as an unconventional introduction to our work. In Ahmes’s papyrus the product factors are two positive integers, say a,b.
Paolo Ferragina, Fabrizio Luccio
Chapter 2. A Problem with Which to Begin
Abstract
PROBLEM. Among three coins of identical appearance one could be false and of different weight from the other two. Using a twin-pan balance to compare the coins’ weights, find the false coin if there is one, and in this case determine whether it weighs more or less than the other two with no more than two weighings.
The solution is very simple. We invite you to find it on your own before going on in our discussion, which will become progressively more complicated and, we hope, more interesting.
Paolo Ferragina, Fabrizio Luccio
Chapter 3. Algorithms and Coding
Abstract
The word “algorithm” (from the medieval Latin “algorismus”) appeared for the first time in an important document dated 1202, in fact on the very first page of the mathematical treatise “Liber Abaci” written by Leonardo Fibonacci. Today, the word is firmly established in almost all languages together with the English word “coding.” The two words together indicate how to organize and describe a series of actions to achieve a desired result: the algorithm constitutes the stage of designing and evaluating the strategy on which to build single actions, while coding reflects the operational phase that leads to the execution of those actions on a particular computing device, such as a PC, tablet, smartphone, or smartwatch.
Paolo Ferragina, Fabrizio Luccio
Chapter 4. The Tournament
Abstract
The final phase of the football World Cup is played as a knockout stage: those who lose are eliminated, so at each round the number of teams is halved. The number of teams, say n, is initially a power of 2, for example n = 24 = 16. In this case, the sixteen teams play in the octofinals from which eight winning teams emerge that meet in the quarterfinals; the four winning teams play in the semifinals, and finally two teams play in the final from which the world champion team emerges. Note that these numbers 16, 8, 4, 2, and 1 are all powers of 2 with decreasing exponents: the last one is 20 = 1.
Paolo Ferragina, Fabrizio Luccio
Chapter 5. A Financial Problem
Abstract
How many times has this happened to you? You read in a newspaper the closing prices of the New York Stock Exchange (NYSE), notice the trend of a specific company’s share price \(\mathcal{S}\), and angrily exclaim: “Had I known it before, I would be rich now!”
Paolo Ferragina, Fabrizio Luccio
Chapter 6. Secret Messages
Abstract
The art of exchanging secret messages has probably fascinated humankind from the earliest times, but the information we have today is related to writing only because nothing has been recorded about cave-dwellers’ secret messages. It is precisely to written messages that this chapter refers: in the end they are sequences of characters and their transformation into a disguised form, and their subsequent interpretation, require appropriate algorithms. Let’s then enter into the field of cryptography, etymologically “hidden writing”, where we will find new interesting forms of coding.
Paolo Ferragina, Fabrizio Luccio
Chapter 7. Putting Things in Order
Abstract
How many times have you tried to play cards with your friends but did not have a new deck of cards available, so you had to be content with recovering a used one from a drawer? Unless you have been involved in gambling, where the perfect state of the cards is a necessary condition to ensure the absence of special marks that could easily identify some of them, any deck of cards in good condition is okay in all games for leisure, provided that it is complete. But how can we establish that it is? Or, better, considering the subject of this text, how can we establish this condition as quickly as possible?
Paolo Ferragina, Fabrizio Luccio
Chapter 8. “Easy” and “Difficult” Problems
Abstract
In the previous chapter we reviewed two algorithms to sort the n elements contained in a vector C[0 : n−1]: INSERTION SORT and MERGE SORT, which belong to the Olympus of classical algorithms. The first one, built according to a simple strategy, has a time complexity proportional to n2; the second one, which is more sophisticated, has a time complexity proportional to n log2 n, and is thus more efficient than the first.
Paolo Ferragina, Fabrizio Luccio
Chapter 9. Search Engines
Abstract
It has been a little more than 25 years since the internauts first had the opportunity to search for documents of interest to them on the newly created Web (1991) by specifying a sequence of keywords. The context was very different from the present one: there were just a few internauts and the Web consisted of only a few million well-maintained and reliable documents (aka pages) belonging to governmental or university sites. The search engines of the era, whose names such asWanderer and Aliweb are now forgotten, were based on extremely elementary algorithms for searching for the user-specified keywords through meta-information that the authors of the pages had associated to them. The search proceeded on the words contained in the archived pages using a linear scan similar to that described in Chapter 3: this was possible due to the limited number of pages existing on the Web at that time and the queries sent to the search engine.
Paolo Ferragina, Fabrizio Luccio
Chapter 10. Data Compression
Abstract
The advent of Big Data and the Internet of Things has revived a strong interest, both in academia and industry, in the compression of large datasets. This is because of its three main benefits:
  • it reduces the amount of space needed to store data, thus virtually increasing the size of a computer’s memory;
  • it reduces the time needed to transfer data between computers, thus virtually increasing the bandwidth of the network over which these data are transmitted; and
  • it may speed up the execution of algorithms because their working dataset may fit into memory levels that are faster to access but smaller in size, such as the (various levels of) caches available in modern computers and computing devices.
Paolo Ferragina, Fabrizio Luccio
Chapter 11. Recursion
Abstract
Do you remember the tournament problem among n players we discussed in Chapter 4? The proposed algorithm, based on the tree of matches (Figures 4.3 and 4.4), goes from the leaves, where all the players are placed, up to the root, where the champion resides, determining and storing in each level the winners of the different rounds. However, the sequence of matches could be defined the other way around, that is, from the root to the leaves, establishing that the tournament is organized as the match between the winners of two tournaments among n / 2 players allocated to the two halves of the knockout stage; and these two tournaments are equally defined among groups of n / 4 players, down to the matches between pairs of players in the leaves (as is known, in order to simplify calculations the organizers admit a number of participants equal to a power of two).
Paolo Ferragina, Fabrizio Luccio
Backmatter
Metadaten
Titel
Computational Thinking
verfasst von
Prof. Paolo Ferragina
Prof. Fabrizio Luccio
Copyright-Jahr
2018
Electronic ISBN
978-3-319-97940-3
Print ISBN
978-3-319-97939-7
DOI
https://doi.org/10.1007/978-3-319-97940-3