Python E-Book

James R. Parker

• Herausgeber: Packt Publishing
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 840

Veröffentlichungsjahr: 2024

Beschreibung

This book introduces programming concepts using Python 3, designed for beginners and hobbyists with no prior programming experience. It covers loops, strings, functions, files, graphics, multimedia, algorithms, classes, and more. Many examples are based on video game development, making learning engaging and practical. The book uses a just-in-time presentation style, providing material when it's needed, and includes companion files with source code, exercises, projects, and figures.
The course starts with an overview of modern computers and basic programming concepts. It progresses through topics like repetition, sequences, functions, file input/output, classes, graphics, data manipulation, and multimedia. The latter chapters focus on basic algorithms, programming for the sciences, writing good programs, parsing, and communicating using graphics and Pygame.
By the end of the course, students will have a solid understanding of programming fundamentals, enhanced by practical applications in video game development. This approach not only makes learning enjoyable but also equips students with the skills needed for further studies in computer science and programming.

Leseprobe

PYTHON

An Introduction to Programming

Second Edition

James R. ParkerUniversity of Calgary

Copyright ©2021 by MERCURY LEARNING AND INFORMATION LLC. All rights reserved.

This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display, or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher.

Publisher: David Pallai

MERCURY LEARNINGAND INFORMATION

22841 Quicksilver Drive

Dulles, VA 20166

[email protected]

www.merclearning.com

[phone]

James R. Parker. PYTHON: An Introduction to Programming, Second Edition.

ISBN: 978-1-683926-24-5

The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others.

Library of Congress Control Number: 2020952465

212223321     Printed on acid-free paper in the United States of America

Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc.

For additional information, please contact the Customer Service Dept. at 800-232-0223 (toll free).Digital versions of our titles are available at:www.academiccourseware.com and other e-vendors.All companion files are available by writing to the publisher at [email protected].

The sole obligation of MERCURY LEARNING AND INFORMATION to the purchaser is to replace the book and/or disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.

CONTENTS

Preface

Chapter 0: Modern Computers

0.1   Calculations by Machine

0.2   How Computers Work and Why We Made Them

0.2.1   Numbers

Example: Base 4

Convert Binary Numbers to Decimal

Convert Decimal Numbers to Binary

Arithmetic in Binary

0.2.2   Memory

0.2.3   Stored Programs

0.3   Computer Systems Are Built in Layers

0.3.1   Assemblers and Compilers

0.3.2   Graphical User Interfaces (GUIs)

Widgets

0.4   Computer Networks

0.4.1   Internet

0.4.2   World Wide Web

0.5   Representation

0.6   Summary

Chapter 1: Computers and Programming

1.1   Solving a Problem Using a Computer

1.2   Executing Python

1.3   Guess a Number

1.4   Rock–Paper–Scissors

1.5   Solving the Guess a Number Problem

1.6   Solving the Rock-Paper-Scissors Problem

1.6.1   Variables and Values–Experimenting with the Graphical User Interface

1.6.2   Exchanging Information with the Computer

1.6.3   Example 1: Draw a Circle Using Characters

1.6.4   Strings, Integers, and Real Numbers

1.6.5   Number Bases

1.6.6   Example 2: Compute the Circumference of Any Circle

1.6.7   Guess a Number Again

1.7   IF Statements

1.7.1   Else

1.8   Documentation

1.9   Rock-Paper-Scissors Again

1.10   Types Are Dynamic (Advanced)

1.11   Summary

Chapter 2: Repetition

2.1   The WHILE Statement

2.1.1   The Guess-A-Number Program Revisited

2.1.2   Modifying the Game

2.2   Rock–Paper–Scissors Revisited

2.2.1   Random Numbers

2.3   Counting Loops

2.4   Prime or Non-Prime

2.4.1   Exiting from a Loop

2.4.2   Else

2.5   Loops That Are Nested

2.6   Draw a Histogram

2.7   Loops in General

2.8   Exceptions and Errors

2.8.1   Problem: A Final Look at Guess a Number

2.9   Summary

Chapter 3: Sequences: Strings, Tuples, and Lists

3.1   Strings

3.1.1   Comparing Strings

3.1.2   Slicing – Extracting Parts of Strings

3.1.3   Editing Strings

3.1.4   String Methods

3.1.5   Spanning Multiple Lines

3.1.6   For Loops Again

3.2   The Type Bytes

3.3   Tuples

3.3.1   Tuples in For Loops

3.3.2   Membership

3.3.3   Delete

3.3.4   Update

3.3.5   Tuple Assignment

3.3.6   Built-in Functions for Tuples

3.4   Lists

3.4.1   Editing Lists

3.4.2   Insert

3.4.3   Append

3.4.4   Extend

3.4.5   Remove

3.4.6   Index

3.4.7   Pop

3.4.8   Sort

3.4.9   Reverse

3.4.10   Count

3.4.11   List Comprehension

3.4.12   Lists and Tuples

3.4.13   Exceptions

3.5   Set Types

3.5.1   Example: Craps

3.6   Summary

Chapter 4: Functions

4.1   Function Definition: Syntax and Semantics

4.1.1   Problem: Use the function poundn to Draw a Histogram

4.1.2   Problem: Generalize the Histogram Code for Other Years

4.2   Function Execution

4.2.1   Returning a Value

4.2.2   Parameters

4.2.3   Default Parameters

4.2.4   None

4.2.5   Example: The Game of Sticks

4.2.6   Scope

4.2.7   Variable Parameter Lists

4.2.8   Variables as Functions

Example: Find the maximum value of a function

4.2.9   Functions as Return Values

4.3   Recursion

4.3.1   Avoiding Infinite Recursion

4.4   Creating a Python Module

4.5   Program Design Using Functions–The Game of Nim

4.5.1   The Development Process Exposed

4.6    Summary

Chapter 5: Files: Input and Output

5.1   What Is a File? A Little Theory

5.1.1   How Are Files Stored on a Disk?

5.1.2   File Access is Slow

5.2   Keyboard Input

5.2.1   Problem: Read a number from the keyboard and divide it by 2

5.3   Using Files in Python: Less Theory, More Practice

5.3.1   Open a File

File Not Found Exceptions

5.3.2   Reading from Files

End of File

Common File Input Operations

CSV Files

The With Statement

5.4   Writing to Files

Example: Write a table of squares to a file.

5.4.1   Appending Data to a File

Example: Append another 20 squares to the table of squares file.

5.5    Summary

Chapter 6: Classes

6.1   A Casual Introduction to Classes

6.2   Classes and Types

6.3   Classes as Encapsulated Modules

6.4   Classes as Data Abstractions

6.5   The Python Class – Syntax and Semantics

6.5.1   A Really Simple Class

6.5.2   Encapsulation

6.6   Classes and Data Types Again

6.6.1   Example: A Deck of Cards

6.6.2   A Bouncing Ball

6.6.3   Cat-A-Pult

Basic Design

Detailed Design

6.7   Subclasses and Inheritance

6.7.1   Non-Trivial Example: Objects in a Video Game

6.8   Duck Typing

6.9    Summary

Chapter 7: Graphics

7.1   Introduction to Graphics Programming

7.2   Graphics in Python–Pygame

7.3   Initializing Pygame

7.3.1   Colors

7.4   The Event LOOP

7.5   Drawing

Example: Create a Page of Note Paper

Example: Creating a Color Gradient

7.5.1   Lines and Curves

Example: Note Paper Again

7.6   Arcs and Curves

7.6.1   Polygons

7.6.2   Text

7.6.3   Example: A Histogram

7.6.4   Example: A Pie Chart

7.6.5   Images

Pixels, Again

Example: Identifying a green car

Example: Thresholding

Transparency

7.6.6   Generative Art

7.7   Summary

Chapter 8: Manipulating Data

8.1   Dictionaries

8.1.1   Example: A Naïve Latin – English Translation

8.1.2   Functions for Dictionaries

8.1.3    Dictionaries and Loops

8.2   Arrays

8.3   Formatted Text, Formatted I/O

8.3.1   Example: NASA Meteorite Landing Data

8.4   Advanced Data Files

8.4.1   Binary Files

Example: Create a File of Integers

8.4.2   The Struct Module

Example: A Video Game High Score File

8.4.3   Random Access

Example: Maintaining the High Score File in Order

8.5   Standard File Types

8.5.1   Image Files

8.5.2   GIF

8.5.3   JPEG

8.5.4   TIFF

8.5.5   PNG

8.5.6   Sound Files

8.5.7   WAV

8.5.8   Other Files

8.5.9   HTML

8.5.10   EXE

8.6    Summary

Chapter 9: Multimedia

9.1   Mouse Interactions

Example: Draw a Circle at the Mouse Cursor

Example: Change Background Color Using the Mouse

9.1.1   Mouse Buttons

Example: Draw Lines Using the Mouse

Example: A Button

9.2   The Keyboard

Example: Pressing a “q” Creates a Random Circle   

Example: Reading a Character String

9.3   Animation

9.3.1   Object Animation

Example: A Ball in a Box

Example: Many Balls in a Box

9.3.2   Frame Animation

Example: Read Frames and Play Them Back as an Animation

Example: Simulation of the Space Shuttle Control Console (A Class That Will Draw an Animation at a Specific Location)

9.4   RGBA Colors – Transparency

9.5   Sound

Example: Play a Sound

Example: Control Volume Using the Keyboard

Example: Play a Sound Effect at the Right Moment: Bounces

Music

9.6   Summary

Chapter 10: Basic Algorithms

10.1   Sorting

10.1.1   Selection Sort

10.1.2   Merge Sort

10.2   Searching

10.2.1   Timings

10.2.2   Linear Search

10.2.3   Binary Search

10.3   Random Number Generation

10.3.1   Linear Congruential Method

10.4   Cryptography

10.4.1   One-Time Pad

10.4.2   Public Key Encryption (RSA)

10.4.3   Example: Encrypt the Message “Depart at Dawn” Using RSA

10.5   Compression

10.5.1   Huffman Encoding

10.5.2   LZW Compression

10.6   Hashing

10.6.1   DJB2

10.6.2   SDBM

10.7   Summary

Chapter 11: Programming for the Sciences

11.1   Finding Roots of Equations

11.2   Differentiation

11.3   Integration

11.4   Optimization: Finding Maxima and Minima

11.4.1   Newton Again

11.4.2   Fitting Data to Curves – Regression

11.4.3   Evolutionary Methods

11.5   Longest Common Subsequence (Edit Distance)

11.5.1   Determining Longest Common Subsequence (LCS)

11.5.2   NumPy

11.5.3   One Dimensional Arrays (Vectors)

11.5.4   Two Dimensional Arrays (Matrices)

11.5.5   Sample Problem: Finding Paths

11.5.6   Linear Regression Again

11.6   Summary

Chapter 12: How To Write Good Programs

12.1   Procedural Programming – Word Processing

12.1.1   Top-Down

12.1.2   Centering

12.1.3   Right Justification

12.1.4   Other Commands

12.2   Object Oriented Programming – Breakout

12.3   Describing the Problem as a Process

12.3.1   Initial Coding for a Tile

12.3.2   Initial Coding for the Paddle

12.3.3   Initial Coding for the Ball

12.3.4   Collecting the Classes

12.3.5   Developing the Paddle

12.3.6   Ball and Tile Collisions

12.3.7   Ball and Paddle Collisions

12.3.8   Finishing the Game

12.4   Rules for Programmers

12.5   Summary

Chapter 13: Communicating with the Outside World

13.1   Email

Example: Sending an email

13.1.1   Reading email

13.1.2   Example: Display the Subject Headers for Emails in the Inbox

13.2   FTP

13.2.1   Example: Download and Display the README File from an FTP Site

13.3   Communication Between Processes

13.3.1   Example: A Server That Calculates Squares

13.4   Twitter

13.4.1   Example: Connect to the Twitter Stream and Print Specific Messages

13.5   Communicating with Other Languages

13.5.1   Example: Find Two Large Relatively Prime Numbers

13.6   Summary

Chapter 14: Parsing–The Structure of Data

14.1   Grammars

14.2   PYJ and JULIA

14.3   Language Symbols and Scanning

14.4   Parsing a Programming Language

14.5   WHILE Statements

14.6   FOR Statements

14.7   IF Statements

14.8   Expressions

14.9   Functions

14.10   Examples

Chapter 15: Communicating Using Graphics: Windows, User Interfaces, and Pygame

15.1   A Paint Program

Interface

15.2   Building the Mondrean Interface

15.3   Selecting

15.4   The Buttons

Drawing

15.5   Images and Surfaces

15.6   Stacks: Undraw and Redraw

15.7   Color Selection

15.8   Image File Selection

Index

Preface

Welcome to the second edition! This is a book that is intended to be used to teach programming to introductory students. There is material here for intro CS, but also for Science and other disciplines. I still believe that programming is an essential skill for all professionals and especially academics in the 21st century and I have tried to make that clear in the contents of this book.

There are two new chapters and some seriously revised ones. First, the book exclusively uses the Pygame library. The Glib module has been updated but is no longer used in this book. This means that Chapters 7, 9, and 12 are quite different from those in the previous edition. Also, Pygame no longer supports video, so rather than build a new module from scratch, video is not discussed.

The new Chapter 14 concerns parsing. This can be a more advanced topic, but parsing is a good thing to know about for many reasons, not the least of which is to deal with user input effectively. The main example is a programming language for which a parser (and compiler) will be written. The language was developed for this book and is called PyJ: it is a small subset of the Julia language, which in turn is a variation on Python designed for efficiency.

The new Chapter 15 involves graphical input. Here a paint-type program will be developed, so as to clarify ideas in mouse input and graphical output. The resulting program (Mondrean) is actually usable for making drawings.

I use a “just-in-time” approach, meaning that I try to present new information just before or just after the reader needs it. As a result, there are a lot of examples, and those examples were carefully selected to fit into the place they reside in the text. Not too soon, and not too late.

I believe in object-oriented programming. My master’s thesis in the late 1970s was on that subject, and I cut my teeth on Simula, was there when C++ was created, and knew the creator of Java. I do not believe that object-oriented programming is the only solution, though, and realized early that good objects can only be devised by someone who can already program. I am therefore not an “objects first” teacher. I am a “whatever works best” teacher.

A lot of my examples involve games. That’s because undergraduate students play games. They understand them better than, say, accounting or inventory systems, which have been typical early assignments. I believe in presenting students’ assignments that are interesting. Not all students like games, and certainly not computer games, but a large number do. And they come to a game assignment with prior knowledge of the genre.

I have taught computer science for 26 years, and then moved to the arts. That’s because of many things, but my experience teaching in a Drama department and more recently in the Art department has helped me immensely in understanding the role of computing and programming in general. I strongly feel that every student in a university should know how to write, and know how to program a computer. If you can’t understand the computer, you are at the whim of programmers who, unseen in downtown high-rises and basements, who dictate how the world will work by default. The (sometimes poor) design decisions made, and the lack of attention paid to human needs results in actual policy being formed, and that is simply wrong. It’s not always true that the code is bad, but when it is, it can have far reaching consequences.

Here is a truth: nobody wants to run your program. What they want is to get their work done, or play their game, or send their email. If you are an excellent programmer then you will enable that, and nobody will know your name. But nobody will curse your code either. The truth is that good code is invisible. It simply allows things to flow smoothly. Bad code is memorable. It interferes, makes people frustrated and angry. If you believe in karma, then I know what you would prefer.

You see, software (any computer program) is ubiquitous. Cars, phones, fridges, television, and almost everything in our society is computerized. Decisions made about how a program is to be built tend to live on, and even after many modifications can affect how people use that device or system. Creating good software means making a productive and happy civilization. It sounds trite, but if you think about it I’m sure you will agree.

Python is a great language for beginning programmers. It is easy to write the first programs, because the conceptual overhead is small. That is, there’s no need to understand what ‘void’ or ‘public’ means at the outset. Python does a lot of things for a programmer. Do you want something sorted? It’s a part of the language. Lists and hash tables (dictionaries) are a part of the language. You can write classes, but do not have to, so it can be taught objects first or not. The required indentation means that it is much harder to place code incorrectly in loops or if statements. There are hundreds of reasons why Python is a great idea.

And it is free. This book was written using Python version 3.4, and with the PyCharm API. The modules used that require download are few, but include PyGame and tweepy. All free.

Overview of Chapters

Here’s a breakdown of the book, for instructors. It can be used to teach computer science majors or science students who wish to have a competency in programming.

Chapter 0: Historical and technological material on computers. Binary numbers, the fetch-execute cycle. This chapter can be skipped in some syllabi.

Chapter 1: Problem solving with a computer; breaking a problem down so it can be solved. The Python system. Some simple programs involving games that introduce variables, expressions, print, types, and the if statement.

Chapter 2: Repetition in programming: while and for statements. Random numbers. Counting loops, nested loops. Drawing a histogram. Exceptions (try-except)

Chapter 3: Strings and string operations. Tuples, their definition, and use. Lists and list comprehension. Editing, slices. The bytes type. And set types. Example: the game of craps.

Chapter 4: Functions: modular programming. Defining a function, calling a function. Parameters, including default parameters, and scope. Return values. Recursion. The Game of Sticks. Variable parameter lists, assigning a function to a variable. Find the maximum of a mathematical function. Modules. Game of Nim.

Chapter 5: Files. What is a file and how are they represented? Properties of files. File exceptions. Input, output, append, open, close. Comma separated value (CSV) files. Game of Jeopardy. The with statement.

Chapter 6: Classes and object orientation. What is an object and what is a class? Types and classes. Python class structure. Creating instances, __init__ and self. Encapsulation. Examples: deck of playing cards; a bouncing ball; Cat-a-pult. Designing with classes. Subclasses and inheritance. Video game objects. Duck typing.

Chapter 7: Graphics. The Pygame module. Drawing window; color representation, pixels. Drawing lines, curves, and polygons. Filling. Drawing text. Example: Histogram, Pie chart. Images and image display, getting and setting pixels. Thresholding. Generative art.

Chapter 8: Data and information. Python dictionaries. Latin to English translator. Arrays, formatted text, formatted input/output. Meteorite landing data. Non-text files and the struct module. High score file example. Random access. Image and sound file types.

Chapter 9: Digital media: Using the mouse and the keyboard. Animation. Space shuttle control console example. Transparent colors. Sound: playing sound files, volume, pause. Pygame module for sound.

Chapter 10: Basic algorithms in computer science. Sorting (selection, merge) and searching (linear, binary). Timing code execution. Generating random numbers; cryptography; data compression (including Huffman codes and RLE); hashing.

Chapter 11: Programming for Science. Roots of equations; differentiation and integration. Optimization (minimum and maximum) and curve fitting (regression). Evolutionary algorithms. Longest common subsequence or edit distance.

Chapter 12: Writing good code. A walk through two major projects: a word processor written as procedural code and a breakout game written as object-oriented code. A collection of effective rules for writing good code.

Chapter 13: Dealing with real world interfaces, which tend to be defined for you. Examples are Email (send and receive), FTP, inter-process communication (client-server), Twitter, calling other languages like C++.

Chapter 14: Parsing. Introduction to grammars and BNF. Parsing data. A small compiler for a small language.

Chapter 15: Graphical Interaction. Using the mouse in complicated ways. Drawing, erasing, modifying images.

Chapter Coverage for Different Majors

A computer science introduction could use most chapters, depending on the background of the students, but Chapters 0, 7, 9, and / or 11 could be omitted.

An introduction to programming for science could omit Chapters 0, 10, and 12.

Chapter 13 is always optional, but is interesting as it explains how social media software works under the interface.

Basic introduction to programming for non-science should include Chapters 0, 1, 2, 3, 4, 5, and 7.

Companion Files (A disc is included in the physical book or files are available for downloading from the publisher by writing to [email protected].)

The accompanying disc contains useful material for each chapter.

Selected exercises are solved, including working code when that is a part of the solution.

All significant examples are provided as Python code files, which can be compiled and executed, and can be modified as exercises or class projects. This includes sample data files when appropriate.

All figures are available as images, in full color.

Instructor Ancillaries

Solutions to almost all of the programming exercises given in the text.

MS PowerPoint lectures provided for an entire semester (35 files) including some new examples and short videos.

All of the Python code that appears in the books has been executed, and all complete programs are provided as .py files. Some of the numerous programming examples (over 100) that are explored in the book and for which working code is included:

An interactive breakout game

The Game of Nim

A text formatting system

Plotting histograms and pie charts

Reading Twitter feeds

Play Jeopardy Using a CSV Data Set

Sending and receiving Email

A simple Latin to English translator

Cryptography

Rock-Paper-Scissors

Hundreds of answered multiple choice quiz and sample examination questions in MS Word files that can be edited and used in various ways.

Dedicated Website

Please consider contributing material to the on-line community at https://sites.google.com/site/pythonparker/ and do have fun. If you don’t then you’re doing it wrong.

J. ParkerFebruary 2021

CHAPTER0

MODERNCOMPUTERS

0.1

Calculations by Machine

2

0.2

How Computers Work and Why We Made Them

3

0.3

Computer Systems Are Built in Layers

17

0.4

Computer Networks

21

0.5

Representation

25

0.6

Summary

30

In this chapter

Humans are tool makers and tool users. This is not unique in the animal kingdom, but the facility that humans have with tools and the variety of applications we have for them does make us unique. Starting with mechanical tools (machines) like levers and wheels that could lighten the physical effort of everyday life, more and more complex and specific devices have been created to assist with all facets of our lives. This was extended in the twentieth century to assisting with mental efforts, specifically calculation.

Computers are devices that humans have built to facilitate complex calculations. Early computers were used to do some of the computations needed to design the first nuclear bombs, but now computers seem to be everywhere, embedded within cars and kitchen appliances, and even with our own bodies. The success of these devices in such a wide range of application areas is a result of their ability to be programmed – that is, the device itself is only a potential when first built and has no specific function. It is designed to be configured to do any task that requires calculations, and the configuring process is what we call programming.

To some extent, this has taken the place of a lot of other tool development that used to be done by engineers. When designing a complex machine like an automobile, for example, there used to be a lot of mechanical work involved. The careful timing of the current to the spark plug was accomplished by rotating shafts with sensors, and resulted in the firing of each cylinder at the correct moment. The air to gasoline mixture fed into the engine was controlled by tubes and cables and springs. Now all of these things are done using computers that sense electric and magnetic events, do calculations, and send electrical control signals to actuators in the engine. The same computer can be used to control a refrigerator, make telephone calls on a cellular phone, change channels on a television, and wake you up in the morning. It is the flexibility of the computer that has led to them becoming a dominant technology in human society, and the flexibility comes largely from their ability to be programmed.

 0.1 CALCULATIONS BY MACHINE

People have been calculating things for thousands of years and have always had mechanical aids to help.

When someone programs a computer, they are really communicating with it. It is an imperative and precise communication. Imperative, because the computer has no choice; it is being told what to do and will do exactly that. Precise, because a computer does not apply any interpretation to what it is being told. Human languages are vague and subject to interpretation and ambiguity. There are sentences that are legal in terms of syntax, but have no real meaning: “Which is faster, to Boston or by bus?” is a legal sentence in English that has no meaning. Such vagaries are not possible in a computer language. Computers do not think and so can’t evaluate a command that would amount to “expose the patient to a fatal dose of radiation” with any skepticism. As a result, we, as programmers, must be careful and precise in what we instruct the machine to do.

When humans communicate with each other, we use a language. Similarly, humans use languages to communicate with computers. Such languages are artificial (humans invented them for this purpose, all at once), terse (there are few, if any modifiers, and no way to express emotions or graduations of any feeling), precise (each item in the language means one thing), and written (we do not speak to the computer in a programming language).

Computer languages operate at a high level and do not represent the way the computer actually works. There are a few fundamental things that need to be known about computers. It’s not required to know how they operate electronically, but there are basic principles that should be understood to put the process of using computers in a practical context.

 0.4 COMPUTER NETWORKS

Schools, offices, and some homes are equipped with computer networks, which are wires that connect computers together and software and special hardware that allows the computers to communicate with each other. This allows people to send information to each other through their computers. But how does this really work?

Computers use electricity to perform calculations on binary numbers. Arbitrary voltages represent 0 and 1, and those voltages are sent along a wire no matter how long it is and still be numbers at the receiving end. As long as two computers are connected, this works well, but if two wires are needed to connect any two computers, then six wires are needed to fully connect three computers to each other and twelve to connect four computers. A room with thirty networked computers would be full of wires (870 to each computer)!

Hawaii has an unusual problem when it comes to computer network communication. It is a collection of islands. Linking them by cables is an expensive proposition. In the early 1970s, the technicians at the University of Hawaii decided to link the computers using radio. Radio transmission is similar to wire transmission in many practical ways, and allocating 35 radio frequencies to connect one computer on each island to all of the others would have been possible, but their idea was better. They used a single radio link for all computers. When a computer wanted to send information along the network, it would listen to see if another computer was already doing so. If so, it would wait. If not, it would begin to send data to all of the other computers and would include in the transmission a code for which computer was supposed to receive it. All could hear it, but all would know which computer was the correct destination so the others would ignore it. This system was called Alohanet.

Figure 0.22

Packets transmitted on a network. Red ones are collisions.

There is a problem with this scheme. Two or more computers could try to send at almost the same time, having noted that no other computer was sending when they checked. This is called a collision, and is relatively easy to detect; the data received is nonsense. When that happens, each computer waits for a random time, checks again, and tries again to send the data. An analogy would be a meeting where many people are trying speak at once.

Obviously, the busier the network is, the more likely a collision will be, and the re-transmissions will make things worse. Still, this scheme works very well and is functioning today in the form of the most common networking system in earth – Ethernet.

Ethernet is essentially Alohanet along a wire. Each computer has one connection to it, rather than connections to each of the possible destinations, and collisions are possible. There is another consideration that makes this scheme work better, and that it is use of packets. Information along these networks is sent in fixed-size packages of a few thousand bytes. In this way, the time needed to send a packet should be more or less constant, and it’s more efficient than sending a bit or a byte at a time.

Each packet contains a set of data bytes intended for another computer, so within that packet should be some information about the destination, the sender, and other important data. For instance, if a data file is bigger than a packet, then it is split up into parts to be sent. Thus, a part of the packet is a sequence number indicating which packet it is (e.g., number 3 of 5). If a particular packet never gets received, then the missing one is known, and the receiver can ask the sender for that packet to be resent. There are also codes to determine whether an error has occurred.

 0.4.1 Internet

The Internet is a computer network designed to communicate reliably over long distances. It was originally created to be a reliable communications system that could survive a nuclear attack, and was funded by the military. It is distributed, in that data can be sent from one computer to another in a chain until it reaches its destination.