Computer Science

Computer Science

 Computing science addresses the theory, design and application of information-processing machines. Its beginnings date to 1946 at the U of Pennsylvania and the first electronic computer, ENIAC (Electronic Numerical Integrator and Computer).

During the 1950s, 4 main areas of focus emerged. "Hardware" concentrated on the construction of reliable equipment with faster central-processing units (CPUs), larger memories and more input and output devices to solve increasingly ambitious problems. Another area covered "systems software," programming languages and logical techniques and structures needed to direct hardware resources and other programs.

These hardware and software systems rapidly expanded the range of applications, the third area of research and development. The initial applications were in MATHEMATICS, followed by science and engineering, then business, social science and eventually almost every field of endeavour. As these 3 areas developed, theorists worked on algorithms (descriptions of processes) expressed in a language understood by computers. This fourth area of study, the "theory of computation," questioned what it meant for algorithms to be efficient and searched for them in a wide variety of contexts. The theory started with the work of Alan Turing, who identified mathematical computability with the ability of a primitive computer to come to a halt in its program.

During the 1960s, computing science emerged as a distinct discipline, separated in many universities from mathematics and electrical engineering departments and from the computing service bureaus with which it was first associated. Formal computer-science programs were initiated. Courses in data structures, programming languages and the theory of computation are the starting points for computing science specialists.

In Canada, a large software and computer-service-based industry has evolved. Most hardware manufacturing is done by US- and Japan-based companies. Canada has thousands of small startup software companies. There have been many major successes, including industry leaders in the areas of telecommunications (Nortel), software (COREL), and graphics (Alias Wavefront). Major research laboratories can be found at the NATIONAL RESEARCH COUNCIL (Ottawa) and IBM Canada (Toronto).

In today's information-based economy, the demand for computer expertise out-strips the supply. The primary source for manpower has been universities and community colleges. Computing science is part of the core curriculum of many university programs in the sciences, engineering, arts and medicine. Most Canadian universities offer an undergraduate degree in computing science, and there are over 2 dozen graduate computing science programs in Canada. A 4-year university education emphasizes the science of computing, as well as practical applications. Colleges and technical schools typically offer 2-year programs, with emphasis on programming and applications.

All of these programs are popular and are usually oversubscribed. Many provinces have introduced programs to double the number of students graduating with a computing degree. Nevertheless, the supply may not meet the needs of industry.

C.C. GOTLIEB and JONATHAN SCHAEFFER

Relationship with Other Disciplines

 Computers are involved in every aspect of our lives - education, business, government, leisure - often in ways of which we are unaware. It is not surprising that they have also become a central feature of scientific and academic fields. Eg, in literary studies computers have been used to electronically construct concordances (lists of when specific words are used) so scholars can study how an author uses a specific word or phrase (by discovering all its occurrences in that author's writing) and can compare how that author uses it with how other authors use it. In the sciences, computers are used in a variety of ways. Eg, in biology computers are used to determine such things as the proper sequence of amino acids in a protein. Physicists, chemists and meteorologists test their theories by running simulations of complex physical, chemical or atmospheric events. In the areas of government and warfare, such simulations are used to give researchers potential outcomes of an tactical decisions. Computational advances have also made it possible to use virtual reality as a way to train people to react most efficiently in some situations where it is too dangerous or expensive to train them in reality, such as fire fighting, nuclear reactor accidents, or intricate surgery.

An important way in which computing science as a discipline has interacted with other disciplines is by exporting and importing basic concepts to/from other disciplines. Alan Turing defined the abstract, logical notion of computation in the 1930s, and computers have been developed since then to embody this abstract concept. His definition of a computer as being in a "state," having a piece of information being presented to it, and having a memory in which to store the results of simple computations were all carried out in the abstract realm of logic. It is not surprising that there is a special link between logic and computing science.

Even before computers were invented, logic concentrated on the conceptual issues of "What can in theory be computed?" and "How can this or that topic be computed?" These investigations led to a logical or mathematical framework in which modern computers are situated (see Connectionism below). Some of these logical investigations were originally pursued for other ends, but have been adapted to computing science. Eg, the study of deontic logic (in which there is an operator meaning "it ought to be that...") and temporal logic (in which there are operators describing "what happens before what") have been used to describe the machine states of a computer as a program is being executed. Fuzzy logic, in which there are an infinite number of truth values (rather than just True and False), has had a huge impact on computer control theory; it is used in controllers for everything from cameras to refrigerators.

Logic has been used as a way to demonstrate that a given program will perform in the manner claimed by its specifications. The idea is that the specifications can be transformed into a logic statement and the various actions taken by the program can likewise be described in logic symbolism. The goal is to show the equivalence of both statements. This is called "program verification" and it can be carried out either by a person or by a computer program. Program verification in either way is a difficult and expensive matter, and in practice is carried out only for small, but crucial, parts of a large program. Nonetheless, research in this area may lead to future breakthroughs where programs can be guaranteed to work before they are used.

Just as computing science has borrowed and enlarged upon ideas from other fields, there are many examples of other fields that have incorporated computing science concepts. Eg, "feasible mathematics" is concerned with the sort of mathematical functions that can be actually computed in a reasonable amount of time on a computer. This is in contrast with "pure mathematics," which has no such additional constraint. There has been a very fruitful collaboration between scholars of both disciplines to determine the properties of feasible mathematics and the results that can be proved by such "feasible methods."

Formal LINGUISTICS studies the formal properties of languages, and includes issues such as syntactically analyzing sentences of natural languages and constructing semantic representations that describe their meaning. This field has interacted with computing science in 2 ways. First, high-level computer programming languages are translated into "machine code" (which is directly understood by computers) by means of compilers that employ a phase of syntactic analysis of the high-level language (see Programming Languages). The formal mathematical properties of the parsing process originally discovered in the context of compiler construction exist in the similar study of the "human parsing mechanism" studied in linguistics (and psycholinguistics). Second, one of the original areas of research in ARTIFICIAL INTELLIGENCE (AI) was computational linguistics - the attempt to get computers to interact with humans in a natural language. Although this goal remains a long way off, the many issues raised by the attempt have had an important impact on linguistics as a field. Of course, in conducting this research, computational linguistics is guided by linguistics research.

A very important and influential area in which other fields have borrowed from computing science is the new field of cognitive science. Historically speaking, cognitive PSYCHOLOGY has studied ways people perform (intelligent) actions. When computing science became a prominent field, one of the ideas borrowed from it was "the information processing metaphor." According to this metaphor, what is important in the study of human cognition is the way information is processed. Adopting this metaphor formed a new branch of cognitive psychology and became prevalent in other disciplines concerned with human cognition, such as some areas of linguistics, PHILOSOPHY, and ANTHROPOLOGY Scholars who were in one of these traditional fields but who adopted the information-processing metaphor began to form new research groups, new journals, and even new university departments.

The new field also attracted some researchers in NEUROSCIENCE, who challenged the dominant (Turing) view of computation as symbol manipulation and urged instead the idea that computer theory should emulate human brain functioning. This viewpoint is called connectionism, and it forms an important area of computing science in which the human brain becomes a metaphor for computation. It does not specifically try to mimic the human brain, but rather uses the ideas discovered in the study of the human brain as a way to efficiently perform statistical classification. From this use has evolved yet another important interaction between the fields of computing science and STATISTICS. The areas of AI and database theory in particular have borrowed from statistical theory, and much research is conducted in statistical learning theory, statistical natural language processing, and data mining. In particular, the vast amount of information that has been stored on computers over the decades is now being re-analyzed by data mining techniques to discover previously unnoticed correlations among the data.

Besides abstract theory, computing science is concerned with the construction of actual computers. Hence, there is a strong relationship between computing science and the fields of ELECTRICAL ENGINEERING and materials science. The components of computer registers, of computer memory, of computer chips, and VLSI (Very Large Scale Integrated) circuits are the product of electrical engineering research applied to the special needs of computers. Similarly, the search for faster computer processors and memory have led to important breakthroughs in materials science, which describes the properties of the materials from which the physical computers are made. An intriguing development in this realm is research into "quantum computing," where the physical substratum of computers is replaced by subatomic particles and the signals that are sent between different components follow the "tunneling laws" of quantum mechanics.

Finally, since computing science is concerned with both physical pieces of equipment and the programs people can use on this equipment, there is an area of research called human computer interaction that investigates the best ways to allow people to interact with computers. This includes describing "user friendly" computer interfaces, designing ergonomic and aesthetic computers, defining ways in which people will feel more psychologically at ease in learning and using programs.

JEFF PELTIER

Computer Hardware

Computer hardware refers to the physical equipment that stores computer software comprising digital data and computer programs; responds to the sequences of data processing instructions included in the programs; and exchanges information with its environment through input and output devices.

Computer hardware comprises multiple subsystems. Power supplies provide electrical power at the appropriate voltages to the other subsystems. Input devices, such as the keyboard, mouse and image scanner, permit data and commands to be sent into the computer. Output devices, such as the video screen and printer, allow data and command signals to be sent out of the computer. Storage devices, such as removable magnetic diskettes, magnetic hard discs and optical hard discs, hold the software. Communications subsystems, such as modems and network interfaces, allow a computer to exchange information with other computers over a data network. Finally, CPUs must be present. Each CPU is a "brain" that decodes the sequence of instructions in a program and executes the corresponding data processing and control actions. SEMICONDUCTOR integrated circuits (ICs) or chips, each containing many millions of microscopic transistor switches, are used to implement all subsystems in a modern digital computer. Memory systems that use magnetic and optical media are used to provide large-capacity software storage.

Theoretical Computing Science

Theoretical computing science addresses the questions of what problems can be solved with computers, whether they are difficult or easy to solve, and whether there are problems that cannot be solved. Although the theory is motivated by the practical concerns of computing, it is not overly concerned with the details of a particular computer chip or how to solve a particular problem. Instead computation theory asks general questions about such problems as how computers should be organized or how difficult scheduling problems are to solve. Computing scientists then use these general results when they encounter similar practical problems.

Artificial Intelligence

AI addresses the design and creation of intelligent agents, artificial entities that exist in some environment, perceive information from that environment and act intelligently to solve problems within that environment. One environment for artificially intelligent agents is the physical 3-dimensional world. But an environment can be anything defined as external to the agent. It might be the environment of cyberspace, or the environment defined by a set of sensor readings or measurements constantly recording the status of a piece of machinery that must be monitored for possible failure. The environment could include a human with whom the agent must cooperate to create a plan or schedule for a factory. For all these cases and others, an artificially intelligent agent must act in ways we would regard as intelligent to achieve a particular set of goals.

Much of the confusion about AI arises from what we mean by intelligence. Intelligence is not "IQ" (Intelligence Quotient) as it is used to describe differences between people's skills and abilities. Instead, the kind of intelligence that concerns AI is the kind of general cognitive abilities that allow all people to communicate, solve problems, learn, understand and reason.

The second area of confusion about AI concerns the idea that there could be artificial intelligence-that intelligence could be a property of machines as well as a property of people and animals. It is not just any machine that AI researchers think could have qualities of intelligence, but specifically the digital computer. Alan Turing, in the 1950s, had the crucial insight that the digital computer was a special machine, not because it could store and manipulate numbers, but because it could store and manipulate symbols - internal states (particular voltage settings) that stand for something. One internal state might correspond to the concept "2" and another state might correspond to "the letter k."

The other important feature of the digital computer, Turing realized, was that its machine states could also stand for instructions. An add instruction could just be a particular machine state that causes other machine states (corresponding to "2" and "3") to be manipulated in certain ways to create a third machine state (corresponding to "5"). Through a series of instructions that change machine states in a particular way, the computer can accomplish "adding."

What does this mean for intelligent behavior? Turing also realized that machine states and machine instructions did not have to concern only numbers and manipulations of numbers. Numbers are only a single kind of concept. There was no reason that machine states could not also correspond to non-numeric concepts, such as "dog," "glass," "probably," "person," or "heart disease." There was no reason that other machine states could not specify relations between these concepts, such as "If x is a dog, then x is an animal." And most importantly, there was no reason that machine instructions could not be written about how to manipulate those non-numeric concepts in particular ways. If adding 2 and 3 can be achieved as a program that manipulates certain machine states to produce other machine states, then why not a program for learning what a dog is, or for predicting a glass that is dropped will probably break, or for combining medical knowledge and patient information to diagnose whether the patient has heart disease? In sum, Turing and others believed that the ability to represent and process symbols underlies the ability to act.

The perspective of a computer as a symbol processor-a device that holds internal states and runs programs over them-and the so-called Physical Symbol System Hypothesis-that symbol processing is both necessary and sufficient for intelligent behavior-lead naturally to the proposal that a digital computer can exhibit intelligent behavior. AI is concerned with identifying computational theories of intelligent behavior for physical devices that have internal states and can take instructions on how to manipulate those internal states. A computational theory is a set of computing processes: one internal state followed by another, and another, and so forth. A computational theory of knowledge defined this way would yield a set of process specifications, and we would be able to turn those specifications into a computer program. Thus, we can view the human brain as a physical object that follows extremely complex programs that cause sequences of brain states to operate sequentially. In ways we do not fully understand, these sequences of physical states allow people to learn, understand, communicate and solve problems.

Because of the complexity of a program that functions like a brain, AI researchers work on understanding much smaller pieces of the issue, hoping that one day a unified theory of machine intelligence will emerge. Some researchers work on formalizing computational models for knowledge of the physical world, such as space, TIME [X-REF 8015] and causality. Other work focuses on problem, and how large amounts of information can be recognized as "relevant" to a situation. Still other researchers are concerned with learning, reasoning with highly specialized knowledge (eg, medical knowledge) and understanding language. The challenge is to understand these components of intelligence in ways that are both precise and general-precise enough so that software systems can be designed and implemented to carry them out and general enough that we would not have to build a different learning program, for example, every time the topic being learned changed.

Some work in AI is concerned with computational theories of human intelligence, that is, with building and testing computer simulations of human memory or human learning. How humans think, reason, and learn may offer insights into specifying these abilities as computational processes. But humans and machines are very different and so a good deal of AI research is focused on developing computational theories of intelligent behavior that work for machines, without concern about whether such theories account for human thinking.

From this practical perspective, it does not matter if artificial agents "really" think or not. There will be important advances as long as AI researchers can design agents to act intelligently in solving important specialized problems, such as medical diagnosis, image recognition, forecasting, or process control. AI systems that do this such specialized problem solving already exist.

Many of these systems have certain computational techniques and methods in common that have emerged from the study of AI over the past several decades. These include the representation of knowledge as individual components that have meaning independent from the rest of the complete system. Thus, a machine might have machine states corresponding to the relation "If x is a dog, then x is mortal." And the truth of that relation can be evaluated independently of other rules in the system. Because this sort of knowledge is so extensive and often imprecise, AI systems often use approximations and alternative ways of encoding the same information so that the machine can compute the best possible inferences or conclusions, within the limits of its computing resources. Indeed, much of what is required for intelligent behavior by agents is recognized as computationally intractable and advances in heuristic (trial and error) search, often studied in the area of game-playing, are important as general methods for machine intelligence. Many exciting challenges remain in this field. One challenge concerns whether today's digital computers, no matter how fast they become, have the right design to support an effective computational theory of machine intelligence. Many researchers who work on neural net programs and machines believe that machine intelligence will only be possible with hardware designs that more closely match the design of human and animal brains. The fact that computers are still limited in areas where humans perform very well (such as general learning, common sense reasoning and language comprehension) indicates that AI researchers must continue to explore computational mechanisms required to achieve those abilities in machines. Whether or not AI duplicates or even exceeds human intelligence is not an issue. The combination of human intelligence with machine intelligence may allow us to tackle problems that neither machines nor humans could solve successfully alone.

RENÉE ELIO

Databases

Throughout human history, knowledge has been gathered and stored in numerous manners for diverse reasons. The amount of data which must be dealt with can be quite small and simple (eg, most personal collections of music CDs) or large and complex (eg, information collected by Immigration Canada including applicants' photographs and fingerprints). Briefly, a database is an organized and structured collection of data items. In the past, the vast majority of data items were textual; today this is no longer true and databases now store images, video and others types of data. To manage these ever increasing collections of data, a database management system (DBMS) or database system for short, is needed.

The most important database theory is related to approaches to modelling and representing data (commonly referred to as the data model). The best-known and used data model today is the Relational Model introduced in 1970 by Dr. E.F. Codd, a former Royal Air Force pilot during WWII, who, after working in Ottawa, joined the IBM San Jose Laboratory to work on databases. Relational DBMSs represent a database as a collection of tables - the definition of these tables is referred to as the database schema. Each such table aims to represent either an entity, such as students or courses, or to model a relationship, such as courses taken. Each table has a collection of tuples (or rows), which in turn are composed of several attributes (or columns). This well-defined structure allows the use of computational techniques, both software and hardware-oriented, to store, update, delete and query large collections of data, eg, large databases.

One important aspect of a database is its querying capabilities. Query languages, unlike procedural programming languages, allow users to express what data they wish to retrieve from the database by referring to the properties that the data should have, rather than indicating how the data should be retrieved. They are similar to programming languages, however, in the sense that they are syntactically and semantically well defined. These languages also allow updates (insertions, deletions and modifications) of the database as well as the database schema. Another important aspect of a DBMS is its transaction capabilities. These capabilities include concurrency control and reliability. Concurrency control is the ability of the system to maintain the correctness of the data in the database even when multiple users access it concurrently. Eg, if a person is adding money to a bank account from an ATM while another user is withdrawing money from the same account at another ATM, the DBMS synchronizes the actions of both users to ensure that the account balance remains valid. Reliability refers to the ability of the DBMS to ensure that the database is correct following a crash. Eg, if a program is updating an employee database by giving everyone a raise and a system failure occurs after only half of the employees get their raises, the DBMS ensures, upon recovery, that the database either reflects all of the changes or none of them.

There are other older database models, such as the hierarchical and network models. Although considerable progress has been made towards the object-oriented model, the relational model still dominates the market place. The current trend is to merge the object-oriented and relational models to develop an object-relational DBMS. These systems are more capable of modeling complex entities and complex relationships. Consequently, a wealth of research has emerged regarding so-called non-traditional databases, such as spatial and temporal databases, and, more recently, multimedia databases. Significant work has been done to develop parallel as well as distributed DBMSs.

With the advent of the World Wide Web and widely available wireless communications, the area of databases is witnessing a huge demand for support of new types of data and new operating modes.

Computer Graphics and the Human-Computer Interface

Computer graphics is the technology of making pictures with computers. The human-computer interface is the way we communicate with our computers. These fields are closely related. Early researchers were convinced that enabling computer display of pictures would create a whole new range of applications, and would fundamentally change the way people talk to their computers, making communication more intuitive and natural. History has shown that they were correct.

In their early days, computers only supported communication with their human users through textual prompts and commands, input with paper cards and later, keyboards. Doug Engelbart was dissatisfied with the status quo. His vision, described in his classic paper Augmenting the Human Intellect: A Conceptual Framework, was that technology provided the means for maximizing the potential of the human intellect, the most valuable resource on the planet. In his efforts towards this end, Engelbart invented the mouse in 1962, and also outlined all the basic elements of today's graphical user interface (GUI), including windows and menus. Thus the "modern" user interface is actually 37 years old.

Also in the early 60s, David Evans and Ivan Sutherland began working to realize the possibilities they saw in computer graphics. In 1963, Sutherland published a classic paper, Sketchpad: A Man-Machine Graphical Communication System. He described a light-pen based system in which users would actually touch and point at the shapes they were manipulating. In later papers, Sutherland pioneered the development of computer graphics and virtual reality, introducing in 1968 the first head mounted display, a device which places computer screens on the user's head, and allows the displayed images to respond to head motion.

The ideas and technologies formed in those early days are now pervasive. Twenty years after Engelbart invented the mouse, Steve Jobs discovered the GUI at Xerox's Palo Alto Research Center (PARC), and implemented it in Apple's operating system in the early 80s. Today the GUI is ubiquitous. Many of the ideas that Engelbart discussed have been realized in the World Wide Web (WWW). It is interesting to note that the Internet existed quietly for over 20 years, and only took off after the development of the browser at the National Center for Supercomputing Applications (NCSA) in Illinois: it was the user interface that realized the potential of the Internet's network technology. Good user interfaces are a basic enabling technology that improve the effectiveness of any application.

Computer graphics has permeated our society. In the late 60s and early 70s, the technology developed quickly, and was employed primarily in design, creating the computer aided design (CAD) industry. Evans and Sutherland founded a company in their names in the late 60s, focusing on CAD applications and pioneering the computer simulator industry. In the early 80s, graphics technology reached the personal computer, and the computer gaming industry began. Today, the revenues of the computer gaming industry exceed box office receipts of the film industry in North America. Ed Catmull was a pioneer in bringing computer graphics technology to film, and today is a leader at Pixar, producer of the first feature length computer animated film. Computer graphics is also used in a number of other important applications, including visualization, which turns complex information into pictures, enabling researchers and scientists from any field to see the meaningful patterns and relationships in the data they collect.

Canada has played a very important role in the development of these 2 fields. In the early 60s, the U of Toronto founded one of the first academic computer graphics labs in N America, the Dynamic Graphics Project. The lab is or has been home to a number of computer graphics and human-computer interface pioneers, some of whom have received Academy awards for their work in the film industry. At the National Research Council, Marceli Wein and Nestor Burtnyk pioneered the use of key framing (a standard technique from hand drawn animation) in computer animation, and applied these techniques with the National Film Board to make one of the first computer animated films, Hunger. This computer animation was the first to receive wide recognition in the film industry, with an award at Cannes in 1973 and a nomination for an Academy Award in 1974. Canada continues to be a leader in these fields, and is home to a number of other important labs and corporations. Canada is also home to the oldest regularly-scheduled computer graphics and human-computer interface conference, Graphics Interface.

One of the driving problems of computer graphics has been photorealism, the effort to make realistic-looking pictures with computers. In its early years, this goal took the form of a number of basic problems, such as hidden surface removal, the effort to show objects occluding other objects. To understand this problem, put your hands in front of your face, and cover your left hand with your right. The right hand "occludes" your left hand. Now imagine that even though your left hand is behind your right hand, you see your left hand occluding your right hand! Sounds silly, but such a situation occurs easily in computer graphics, unless care is taken to avoid it. The goal of photorealism has largely been achieved. Researchers are beginning to focus on a number of other problems. Among these are computer representation of realistic-looking motion, and non-photorealistism, which makes pictures that purposefully do not look real, but instead may look like paintings or sketches.

For many years, human-computer interface researchers focused on perfection of and support for the GUI interface largely envisioned by Doug Engelbart and researchers at Xerox PARC. More recently, researchers have begun to examine other sorts of interfaces. These include tangible and ubiquitous user interfaces, which embed computers (and interfaces) in everyday objects; interfaces for the disabled; for collaborative work and cooperation, perhaps over distances; and 3D interfaces, which support interaction with computers in 3-dimensional, virtual reality environments. Internet The Internet is a network of computers interconnected globally. These connected computers, called hosts, communicate using a standard protocol known as TCP/IP. They are connected by phone and dedicated lines, and special devices, called routers, which direct the flow of information. The information transmitted on the Internet is broken down into small parts called packets. These packets are sent independently and can take different routes from the sending machine to the receiving machine. The Internet started as the ARPANET, an initiative of the Advanced Research Projects Agency, during the Cold War in 1969. By building the ARPANET, the US Department of Defense wanted to explore the possibility of a communication network that could survive a nuclear attack. The idea was to be able to continue to communicate between connected computers even if one of the computers is shut down or its connection severed. Initially the network connected four sites, but very rapidly, many research centres and universities were connected. The introduction of TCP/IP in the early 1980s helped interconnect various research networks, which resulted in the Internet with ARPANET as a backbone. During the same period, the National Science Foundation (NSF) in the US established 6 supercomputer centres. In 1986, a dedicated network (NSFNET), funded by the NSF, connected these centres and became the new Internet backbone when ARPANET was dismantled. Since then, the growth in the number of hosts and the growth in data packet traffic on the backbone have increased exponentially. The Internet is not just in N America, but involves many networks world-wide. The growth of the Internet accelerated even more with the advent of the WWW. The WWW is often mistakenly confused for the Internet. In reality, the Internet subsumes the Web. Along with the growth of the Internet, there has been an important increase in the number of software tools to make use of the multitude of resources in the network. Moreover, different transfer protocols have been adopted each creating a "subspace" of resources within the Internet. The WWW is such a subspace within the Internet. Other subspaces or services on the Internet include FTP, e-mail and newsgroups. FTP is a File Transfer Protocol, which is used to transfer files from one machine to the other. Electronic mail (e-mail) is one of the main uses of the Internet and was one of its first applications. E-mail is a way to send messages from a user on a computer to a recipient user on a destination machine, both machines being connected via a network. The message can contain any text such as a business memo or a personal letter. Today, e-mail can contain multimedia such as sound, images or video. Network news groups (USENET) are a collection of hosts that receive network news groups, which are discussion groups or forums about a variety of topics. Network news is a mechanism for broadcasting messages from one host to a large number of hosts. A message or article sent to a news group is received by a host on USENET. People who access the USENET hosts can read the messages. This connection simulates the message broadcast. People who access news groups can browse and read articles, post new messages or reply to particular messages. News group messages are archived and are accessible on-line. There are thousands of news groups on different topics from scientific or technical, to political or esoteric. The large collection of articles posted daily on USENET contributes significantly to the rapid expansion of the size of the on-line resource accumulation. Other communication services are added and enhanced regularly. Services like net telephony, net fax, Chat tools and video conferencing contribute significantly to the large number of on-line resources on the Internet. Author: OSMAR R. ZAIANE World-Wide Web The WWW is the interactive multimedia information delivery service on the Internet. It is based on the notion of hypertext, a text document that has links to other hypertext documents. In 1992, an internal project at CERN, the European Laboratory for Particle Physics in Switzerland, led by Tim Berners-Lee and Robert Caillau, attempted to make distribution of information easy for physicists working around the world and exchanging data. The WWW was born out of this project and was very rapidly adopted by Internet users for its ease of use, interactivity and multimedia support. Documents on the web are formatted using HTML (HyperText Markup Language), and hypertext links within the documents are used to travel from current documents to others. HTML allows annotating documents using hypertext links and colours, and mixing text with images and other media in the same document. When the WWW browser Mosaic was released in 1993, the web became widely used thanks to the "point and click" interface of Mosaic. No Internet service used to share information across the Internet allows simple browsing and ease of use like the WWW, which allows users to browse large collections of information across the network without having to log in or know in advance where to look for information. The WWW became the technology of choice to deploy information on the Internet and was the major reason for the Internet's tremendous growth in terms of the amount of information published and the use of the network. Finding real information is often a hit-and-miss process. While browsing to look for particular information, a user may drift and end up reading other possibly interesting pages, which may be irrelevant to the original quest, a phenomenon similar to browsing an encyclopaedia. This is why tools such as the search engines were created. A search engine is a tool that helps find documents in the WWW containing keywords. When given these keywords, search engines return a list of documents that contain the words or phrases. Search engines do not search the whole WWW whenever a request is sent to them. There are programs, known as crawlers and spiders, that traverse the web, download documents, analyze them and store information about them in an index that can be queried. Search engines use such indices to retrieve quickly the list of documents that contain given words.

OSMAR R. ZAIANE

Programming Languages

Computers perform tasks by following a set of simple instructions called machine instructions. They can perform complex tasks because they can perform simple instructions very quickly. In fact, modern computers can perform billions of instructions per second. The set of instructions that an individual computer can understand is determined by the kind of CPU the computer contains. Eg, an Intel Pentium processor supports a different set of instructions than a Motorola G3 processor. To solve a particular problem, a computer programmer can select a specific group of instructions and order them in a particular order. The group of ordered instructions is called a computer program. The computer follows the instructions in a program to solve a problem. The instructions tell the computer how to input information from a user and store it in memory locations, how to move the information from memory to the CPU, how to manipulate the information in the CPU, how to move the information back to memory locations and how to output the solution information to the user. When people first started writing computer programs in the 1950s, they used machine language instructions, which are difficult for humans to use. Each machine language instruction is represented by a number in the binary (base 2) number system. Eg, here is a small segment of a machine language program for the Intel 8086 CPU that computes the number 2 ( (500 + 50): 1011 1000 1111 0100 0000 0001 0000 0101 0011 0010 0000 0000 1101 0001 1110 0000 This computation is done by a series of 3 machine language instructions: 1) Move the number 500 to a CPU location called the AX register. 2) Add 50 to the contents of this register. 3) Multiply the contents of the register by 2 by shifting all of the bits in the register one bit to the left. It is very difficult to see how a binary machine language program can represent this series of 3 instructions. The binary digits 1011 1000 mean "move a number to the AX register." The number to move is given by the next 4 groups of binary digits, but in a strange way. The digits 1111 0100 represent "244." The digits 0000 0001 represent "256" which, when added to 244, gives 500. The binary digits 0000 0001 mean "add a number to the AX register." The number to add is given by the next 4 groups where 0011 0010 represents 50 and 0000 0000 represents 0 - the number to add is 50. The last 4 groups of binary digits 1101 0001 1110 0000 mean "shift the contents of the AX register one bit to the left." Writing programs in binary machine language was cumbersome and error-prone. A "higher-level" language was easier for people to understand. Assembly languages provided the first step from representing instructions as numbers to representing instructions as symbols. Here is the same program in assembly language: MOV AX, 01F4H ADD AX, 0032H SAL AX,1 The first instruction moves the hexadecimal (base 16) number 01F4 (500) to the AX register. The second instruction adds the hexadecimal number 0032H (50) to the contents of the AX register. The third instruction shifts the contents of the AX register one bit to the left (multiplies by 2). When it was introduced assembly language was a huge step towards making computer programs easier to write. Programs called assemblers were also invented. An assembler is a computer program that translates an assembly language program into a machine language program, relieving programmers of this tedious and error-prone task. A series of even higher-level programming languages soon evolved where the programmer did not even have to refer to the parts of the computer directly. Instead, the programmer used symbolic variable names to refer to locations in the computer's memory or CPU registers. The sample program could now be written even more simply in a language like FORTRAN as: X = 2 * (500 + 50) (where "*" means multiply) Programs called compilers translate the high-level source program into machine language code. Many different compilers could translate the same high-level source program into many different machine languages for many different CPUs., giving rise to portable computer programs . Today, there are hundreds of different programming languages, which can be divided into 4 broad categories, based on the computational model they use. The categories are imperative, functional, logic-based and object-oriented, each of which solves problems in a fundamentally different way. Within a family, the syntax of the languages varies, but the general approach to solving a problem is the same, so understanding a language in one category, makes it fairly easy to learn another in the same category. But why have more than one language category? Why not use the "best" category of languages? The answer is that there is not a single "best" language category. Any problem solvable by languages from one category can be solved by languages from any category. However, different problems are much easier to solve using languages from different categories. The oldest and most popular language category is the imperative or procedural category, eg. FORTRAN, COBOL, Algol, Pascal, C, Modula-2 and Ada. To solve a problem using the imperative model, a programmer writes a series of instructions that change the contents of memory locations. The program is done when memory contains the answers to the problem. This model is based directly on machine languages, although it is much easier to write a modern procedural program than to write a machine language program. The basic 3 operations in a procedural programming language are store, which stores a value in memory; fetch, which refers to a value previously stored in memory; and arithmetic, which computes a new value from one or more old values. These operations are used in an assignment statement. Other statements also exist to input information from, and output information to, the user. Control structures group statements and specify the order in which they are performed. There are 3 different categories of control structures: sequences, selection control structures and repetition control structures. A sequence is a collection of statements, performed sequentially in the order they are written. A selection control structure conditionally performs statements from 2 groups. A repetition control structure performs a group of statements more than once.

Control structures describe the way that statements are grouped. Data structures describe the way that simple data is grouped into larger data elements. The most popular data structure used in imperative programming languages is called an array, a collection of data elements that are indexed by numbers. In a functional programming language, problems are solved by creating a function that takes user input and outputs the answer. Lisp, APL and ML are examples of functional programming languages. The basic functions can be considered as "black-boxes". For example, there is a squaring function that squares its input and a sum function that adds its 2 inputs: [Insert graphic]

These functions could be written as: square(3) -> 9 sum(3,4) -> 7 Writing a program consists of breaking a large problem up into a series of smaller problems, each of which can be solved by a basic function. The functions are composed to provide a solution to the original problem. Just as imperative programming languages use arrays to group data, functional programming languages use lists. There are 3 basic functions that are defined for lists. head(aList) // returns the first element of a list tail(aList) // returns the list minus its first element list(anElement,aList) // returns a list in which the element is added as a new first // element of the list Functional programming languages do not use control structures; they make use of a conditional function that evaluates the first input. If the first input is true, the conditional returns its second input. If the first input is false, the conditional returns its second input. conditional(equal(X,0), 0, divide(Y,X)) Functional programming languages do not have repetition control structures. Instead they use recursion where a function calls itself. For example, here is the definition of a recursive function that computes the length of list and a program that calls this function. length(aList) = if(empty(aList), 0, sum(length(tail(aList),1)); length([1,2,3]) -> 3; In a logic-based language, a program consists of a series of statements about what is known and a single question that states the problem. A logic interpreter then tries to answer the question by inferring new information from the existing information. Prolog and SQL are the most popular logic programming languages. For example, here is a program that computes Kevin's grandmother. Mother(Dorothy,Kevin); Mother(Maggie,Dorothy); MaternalGrandmother(gm,gc) <- Mother(gm,m),Mother(m,gc); ?MaternalGrandmother(who,Kevin) -> Maggie In words, this program says: "Dorothy is the mother of Kevin and Maggie is the mother of Dorothy"; and "someone is the maternal grandmother of a grandchild if that grandmother is the mother of the mother of the grandchild." The answer to the question "who is the maternal grandmother of Kevin" is Maggie. A logic-based program is more concerned with what is known than specifically how to solve a problem. In an object-oriented programming language, problems are solved by creating groups of objects and invoking methods on them. Smalltalk, Java and C++ are examples of object-oriented languages, although both Java and C++ are actually hybrid languages with both object-oriented and imperative constructs. An object is a program entity that remembers information and can respond to method invocations. Groups of objects that share the same set of methods are called classes. Besides providing a set of program statements for each of its methods, a class defines some internal state that each of its objects must remember. For example, we might define a person class that has methods, "what is your name," "remember that this person is your mother," "who is your mother?," and "who is your maternal grandmother?." In addition, we might require that each person object remember a name string and its mother. When an object is created, it is initialized using an initialization method. For example here is the code for the class Person that we have just described, together with some code that creates 3 people and asks the last person for his mother. Class Person { Person(String name) { //initialize me with a name this.name = aString; } void rememberYourMother(Person aPerson) { this.mother = aPerson; } Person whoIsYourMother() { return this.mother; } Person whoIsYourMaternalGrandmother() { return this.mother.whoIsYourMother() } private String name; // remember my name private Person mother; // remember my mother } mPerson = new Person("Maggie"); dPerson = new Person("Dorothy"); dPerson.rememberYourMother(mPerson); kPerson = new Person("Kevin"); kPerson.rememberYourMother(dPerson); kPerson.whoIsYourMaternalGrandmother() -> mPerson This class has an initialization method and 3 other methods. The first method is used to initialize a new person to have a particular name. The code simply remembers the name. The second method remembers that some person is the mother. The third method simply returns the remembered mother. The fourth method computes the maternal grandmother by asking the mother for her mother. This class has an initialization method and 3 other methods. The first method is used to initialize a new person to have a particular name. The code simply remembers the name. The second method remembers that some person is the mother. The third method simply returns the remembered mother. The fourth method computes the maternal grandmother by asking the mother for her mother. A large object-oriented program consists of many different kinds of objects that collaborate to solve problems.

DUANE SZAFRON

Software Engineering

The term "software engineering" was used first in the late 60s. It received special attention at the first workshop on software engineering held in Rome in 19681 where the looming software crisis was identified, a crisis brought on by the production of very powerful third generation computers such as IBM's 360 and Digital Equipment's PDP-10 series of computers that could run simultaneously multiple computing tasks for multiple users on one machine. The complexity of the software for this new generation of machines was such that no one person could understand it. The new software was large enough and complex enough that only teams of software experts could develop and maintain the software reliably.

Unfortunately, the software crisis of the early 70s has never died away as the demands for software continue to grow. The variety of applications required is obvious because of the ubiquitous nature of computers. Almost every mechanical device today uses a computer application and wherever there is a computer there must be software.

Software Construction

Constructing software is like constructing buildings-there are many similarities between how software is constructed and more traditional engineered products such buildings, plastics and roadways. In particular, the roles of people needed to produce a physical product are similar to those necessary to develop software. Imagine, for example, the process of building houses or office buildings and the people involved in it. Sometimes the owners and future residents commission the house, or a real-estate development company may decide that more housing is needed in an area. Similarly, in the case of building a new software system, often the future users have the idea for it, usually because they identify a problem that could be addressed by a computer program. In other situations, a software company, after researching the market, may decide that an opportunity for a new product exists.

The team assembled for a large building project usually includes an architect, a civil engineer, a construction manager and construction workers. The owners explain their needs to the architect, (eg, appearance of the façade, cost considerations, number and purposes of rooms). The architect produces a concept for the building and draws diagrams from different perspectives to help everyone visualize it. The diagrams usually undergo several changes based on input from the various people involved.

Every software system too has an architect, who is experienced with similar projects and is responsible for producing a blueprint for the system which provides the basis for the involved parties to describe their requirements. Eg, the users specify how the system should behave, its functions, and how fast it should respond. The software company's business strategists may specify attributes required to distinguish the product from similar competing products. The project manager ensures that product delivery will occur on the specified date.

After the architectural design phase for a building and development of the construction schedule, the actual construction starts. The progress of the work is monitored against the schedule and adjustments are made as required. In the initial phases, changes may still be made to the architectural drawings. In these cases, the construction schedule and team may also change. In this regard, the building construction phase closely resembles the software development phase. The development of a software system follows a project plan that outlines the responsibilities of each developer in the team and lists the milestones that must be accomplished before the project is complete. The development process is very complex. Buildings have parts ranging in size from huge girders that support entire ceilings or floors to the smallest rivets or screws. Software systems have parts ranging in size from large subsystems such as the graphical user interface or the database support system to a single instruction, such as an addition, that the computer can execute.

Large building projects, such as Toronto's Sky Dome has many millions of parts and hundreds of workers, architects and designers involved in its construction. Large software systems, such as Nortel's main digital switching system, contain over twenty million lines of code developed by more than 1000 software specialists. In conjunction with the programming activity, software developers produce the documentation necessary to install, use and evolve these programs. For large systems, the task of documenting the programs is very important and can be as big as the task of program development. Small personal software programs can be developed successfully without extensive documentation, but here again, the building analogy holds in the sense that a doghouse is typically developed with little or no building plans, architects and civil engineers.

Finally, after the building is finished and inhabited it requires maintenance, both regular tasks, like roof replacement every twenty years, or fixes in response to unexpected events, like basement repairs after a flood. Similarly, software systems need maintenance after they are deployed. Eg, the system may be installed on a new type of computer, which typically will require recompilation of the programs. Or a "bug" may be found and then a module may be modified or new modules may be added to correct the error. Even more interestingly, the users may come up with new requirements for functionality enhancements, performance improvements and interface configuration changes. These may lead to substantial changes to the code and new system versions.

There are many other similarities between building and software construction, but perhaps it is more interesting to explore the key differences.

Essential Differences

One major difference is that once built, large buildings like Sky Dome don't need the same level of worker involvement for maintenance. This is not the case for large software systems. Most such systems evolve rapidly due to changing user requirements or changing software or hardware platforms upon which the systems operate. As a consequence, the number of people involved in a rapidly evolving software system actually increases over time - some say it is like building Sky Dome continuously. Undoubtedly some of our current software systems are amongst the most complex systems ever built. Because of this complexity new tools and techniques have been developed to assist in the continuous understanding, reverse engineering and re-factoring of complex software systems.

In fact it is quite common that the old software, often called "legacy software," is not discarded but is enhanced over time. Resultantly, the apparent new release of some software is not entirely new and contains some of the key functionality that was constructed many versions in the past. This is why the Y2K (Year 2000) problem had such pervasive effects on computer systems and our society more generally. In many instances, existing software for banking systems, insurance systems, health systems and even elevators had embedded legacy software that stored the year part of a date as 2 digits. Typically the software using 2-digit years was created in the 70s or early 80s when the cost of digital storage was 1 billion times more expensive than it was 2 decades later. Reengineering tools and techniques played a major role in assisting developers to solve the Y2K problem in their organizations.

Another key difference in the construction of software is that the notion of a margin of safety in design does not really exist. In building construction , a margin of safety can be added to handle unforeseen events, such as a major earthquake or tornado. But how does one the margin of safety in software? Programs are based on logic (true or false). Generally, the idea that something can be a little more true or a little more false than something else makes no sense. Eg, the conditions that 3 sides A, B and C form an equilateral triangle are: if A = B = C then ... Can we make this condition a bit more true? Surprisingly, some may answer yes! Suppose A, B and C are all equal but have the value zero or a negative value. Set {A, B, C} will not form an equilateral triangle with these inputs. If we add a bit more logic that tests to ensure that one of A, B or C is positive, before executing the conditional statement then we have a better, "more accurate" program.

The difficulty with this argument is that the original condition was not correct and therefore the design is erroneous or incomplete. There is no fundamental set of strength equations in software that is analogous to those used for computing the safety margin and additional costs of increasing the strength of a support beam. When we test software we cannot keep adding load until the logic breaks. One simple logic error in a million-line program can destroy a rocket on its launch pad. Adding additional checking may solve the problem, but it is not guaranteed and it certainly cannot be added based on strength equations. Building with logic components is inherently different than building with physical components.

Software systems are much more dynamic than most physical systems like bridges, automobiles and dams, which do not change dramatically over time. In addition, strategies used by individual programmers or small focused teams do not work as well for larger teams working on larger software development projects. Many projects are delivered late, or not at all, and often cost 2 to 3 times the original budget estimates. The "engineering" of software requires some new practices and different scientific basis than traditional engineering, which relies heavily on the physical sciences of chemistry, physics and geology. This does not imply that some of the good practices followed in traditional engineering could and should not apply in software engineering. Concern for public safety, developing systematic (repeatable) and measured methods for construction, and continually learning new developments in the discipline should all apply to software engineers as well.

A Bright Future

Thirty years after its formation, software engineering remains a rapidly growing, dynamic discipline that is still young and not well understood. Yet, it is one of the fastest growing areas of economic growth and employment. Between 1995 and 1997, ICT accounted for one-third of US economic growth with similar levels of growth in Canada and most of the other major industrialized countries. In the first 3 years of the new millennium, an estimated shortage of more than one million software workers is predicted in N America and Europe alone.

Software professionals are currently mostly computer scientists. But increasingly people from other areas get involved in the process of developing and maintaining software. Computer engineers, for example, develop software to embed in process control systems. Business administrators are becoming increasingly more involved in the design of the information systems required by their business processes. With the rapid increase of e-business activities, almost all commercial and government sectors have a software presence on the Internet, and consequently almost all professionals become more or less familiar with the software process. By the same token, this pervasiveness of software systems implies that being a software professional is one of the most challenging and creative endeavors in which one could be involved. The areas of involvement are limitless and the opportunities to learn are lifelong.

Canadian researchers have had strong influences on the development of software engineering research and practice, and include David Parnas, of McMaster U (software design, information hiding); Ric Holt from the U of Waterloo and U of Toronto (programming languages); John Mylopoulos from the U of Toronto and Hausi Muller from the U of Victoria Toronto (Software Bookshelf and Rigi); Nazim Madhavji of McGill U (Process cycle Model); Gail Murphy of UBC (Reflexion Model); members of the Software Engineering Research Lab at the U of Alberta (Froehlich, Hoover, Stroulia and Sorenson-Hooks Model); and James Gossling of Sun Microsystems (co-inventor of Java). Supercomputing In many fields of science and engineering, there are often small but influential groups of people who continually push the limits of technology. Eg, Formula One racing pushes car designers to build better automobiles in search of the fastest car possible. Similarly, the military imperatives of the Cold War produced a number of advanced technologies, including the sub-field of computing science known as "supercomputing." Supercomputers are defined as the fastest computers available at a given time. More generally, supercomputers are part of the research and engineering effort to design high-performance computers. Associated with supercomputing are a set of typical problems and a history of technology innovation. Supercomputers are applied to weather prediction, modelling, bioinformatics, and the design of military weapons. Many of the ideas and technologies introduced in supercomputers trickled down to the mainstream consumer decades after their invention. Eg, contemporary desktop computers contain special hardware support for vector processing, an idea refined and pushed to new levels of performance in the supercomputers of the 70s and 80s. There will always be computer users for whom the fastest mainstream computer is not fast enough. Although the rate at which computers increase in speed every year is astounding, some scientists and engineers have problems large enough or complicated enough that they can always use more computing power. Eg, analyzing the genetic data gathered as part of the HUMAN GENOME PROJECT for similarities in sequences and structures is a large problem. The shear amount of genetic data and the scope of the calculations involved make the problem too large for anything but the biggest and fastest computers available. When a desktop computer is insufficient to solve a problem, supercomputers of one of 3 basic categories can be used instead. The first kind of supercomputer uses special hardware to perform common calculations quickly. Eg, vector processors were introduced in supercomputers to speed up the performance of mathematical calculations containing vectors, or ordered lists of numbers. By the nature of mathematics involving vectors, the same or a similar computation is required for each number in the list. Consequently, the computation can be completed at the same time, or in parallel, for each number. For computations that contain many vectors, such as graphics, the special-purpose hardware improves performance by a substantial margin. But, for computations that do not involve vectors or graphics, more general-purpose supercomputers may be required. The second kind of supercomputer uses teams of processors connected to a common main memory, called a shared-memory multiprocessor. The shared memory is like a common bulletin board that the processors can use to post data and to read the data posted by other processors. By breaking a large problem into smaller sub-problems, giving different sub-problems to different processors so that they can be computed in parallel, and then combining the partial answers into the final answer, the overall problem can be solved faster than if a single processor attempted the entire computation. The data associated with breaking a problem down, keeping track of the parallel computations, and combining the partial answers can all be stored in the common shared memory. Although such a computer is relatively easier to write programs for, efficiently allowing many processors to access the same shared memory requires expensive hardware to connect the processors to the memory such that there is no performance bottleneck. The third kind of supercomputer uses multiple processors connected by a high-speed network, called a distributed-memory multicomputer or a cluster of workstations. Unlike a shared-memory computer, a distributed-memory computer does not have a common memory by which the different processors can communicate to coordinate their parallel computations. The processors exchange data by sending messages between processors. Only the sender and receiver of the message can see the data. The advantage of a cluster approach is that the expensive hardware for supporting a common memory is not needed. Also, it is easier to assemble a cluster of commodity workstations by connecting them with a network than it is to design special hardware to connect them to a shared memory. Given their exceptionally high performance for relatively low cost, clusters are becoming more and more popular among scientists. The recent trend towards open source software, software that is readily available for use and customization without substantial cost, is also fueling a trend towards cluster supercomputing. The main drawback to clusters is that they are more difficult to program than shared-memory computers because coordinating a parallel computation by sending messages is more difficult than reading and writing to a common memory.

PAUL LU

Vision and Robotics

Throughout history people have been imagining intelligent mechanized devices that perform human-like tasks. Although drawings, books, plays and movies have imagined many robots, and automatic mechanisms have been built, movie portrayals of robots are far more intelligent than most existing robots because there are still many science and engineering problems to be solved. However, very sophisticated robots are in use today. Although they may not look like humans, they perform diverse tasks. Typically robots are industrial manipulators, computer controlled arms and hands (Figure 1). Arc-welders, spot welders and spray painters accounted for about 80% of the industrial robots in use in the 80s. Increasing numbers of mobile robots (or self-guided vehicles) are being used for tasks such as the transportation of materials within factories and hospitals, exploration of unsafe terrain and even for conducting tours of museums.

Various scientists and technologists have used different definitions of a robot. A robot is an automatic, responsive, re-programmable machine. It is a mechanical device designed for doing work, a machine, where operations are executed automatically, without external help. The robot can be programmed to perform many jobs and is responsive, eg, must be able to react based on sensory input. This broad definition of a robot incorporates many of the current robots in use in industry and research laboratories. Robots that are remotely controlled by a human are called tele-operated. Tele-operation is advantageous in hazardous environments such as chemical spills and bomb disposal. The space shuttle arm designed by Canadian Space Agency (SPAR industries) is an example of a tele-operated robot. The astronaut inside the spacecraft controls the arm movement. ROBOTICS,[X-REF 6890] the study of robots, is an interdisciplinary field drawing on computer science, electrical and mechanical engineering, psychology, and physiology. Robots in industry move quickly from point to point, appearing to be most capable and agile. This ease, however, comes about because every movement was painstakingly programmed by a human. If objects are not exactly in the location that was programmed, the robot fails. This programming and fixaturing limits the use of robots in many non-industrial settings. Areas for which robotic solutions are desired but research is still required includes: assistance to elderly and handicapped; material handling systems; food preparation and handling; waste handling systems; military and law enforcement; construction; agriculture; mining; and surgery. These diverse areas contain similar challenges - these applications involve un-engineered environments, unlike factory automation where objects can be precisely positioned. To succeed, robots must possess the ability to sense and reason about physical objects in the environment. In addition these applications require flexibility, the ability to respond rapidly to change, and that the robots be able to interact safely with humans. The sophistication of a robot depends on its sensory perception and the software that provides the interpretation and corresponding action. There are numerous sensors employed on robotic systems. Sensors are usually a transducer of some kind whose inputs are physical phenomena and whose outputs consist of electronic signals. Eg, force sensors produce a voltage signal proportional to the applied force. The voltage is converted into a digital format for use within a computer program. Improved sensors are needed for the advancement of robotics. One sensor, a camera, provides information on the brightness or color of the scene. The acquisition of images and extraction of information from images is studied in the field of computer vision. There is general agreement (not 100% consensus!) that any advanced robot requires real-time computer vision, which to date can be achieved in a limited fashion. Adding visual perception to a robot will greatly enhance its applicability in un-engineered environments. In computer vision typically the goal is to extract information from images obtained by a video camera. Object recognition strives to determine what is in the image. Other information extracted from images includes geometric properties (size, shape, location) of objects. Many systems use stereo, 2 cameras, much like human eyes. The "image," as the computer sees it, is a large array of numbers, called pixels (picture elements). One representation of color images uses 3 values, RGB (red/green/blue) for each pixel (Figure 2). While images are easily interpreted by the human eye, a computer vision system must process the array of numbers and associate objects with the numeric values. This problem is extremely difficult and can only be solved for specialized situations. In addition, vision systems require careful calibration to determine the relationship between the size of objects in the image and the size of objects in the world. Vision systems are also sensitive to the lighting conditions. What appears identical to a human, when represented in a computer, appears very different to a computer vision system. Table 1 shows how Figure 2 is represented to a computer. From this seemingly unintelligible collection of numbers, the vision system must identify the objects in the image, by trying to detect edges (changes in pixel values), as shown in Figure 3. [Insert graphic] Color Image Red Band of Image Green Band of Image Blue Band of Image Figure 2: A color image. Each pixel of the color image is made of three values, red/green/blue. Each color "band" of the above image is shown separately as a grey level image where black indicates high pixel values and white indicates low pixel values. [Insert Table] Red Green Blue Table 1: Actual numeric pixel Values (sub-sampled every 4th pixel) for the RGB images shown in Figure 2. These values are what the computer "sees." [Insert graphic] Image Edges Image Regions Identified "objects" Figure 3: The image in Figure 2 is processed using a edge detection algorithm and a region detection algorithm. The resulting "objects" are detected by the computer vision system. [Insert graphic] Figure 4: The same object viewed under variable lighting. Although easily recognized by humans as the same object, the actual pixel values will vary significantly due to the lighting. Eg, the upper left hand corner of the object is grey in the left picture and white in the right picture. Given the complexity of processing images, why should a robot use computer vision? Computer vision systems have a large dynamic range, they can see both small objects and large objects, close objects and distant objects. Vision systems can be remotely situated - they can obtain information about an object without physically contacting the object. Vision systems are passive, they do not need to emit energy in order to acquire data (unlike laser, sonar and infrared robotic sensors which must emit energy in order to sense the environment). Vision systems are flexible in that they can be "reprogrammed" to perform different tasks (such as recognition of different objects). In recent years, vision systems have been affordable (the multi-media craze has helped to drop the price of cameras and digitizers). Even with the above mentioned drawbacks, vision systems have been successfully used for inspection tasks in automation where high speed imaging systems can inspect objects faster than humans. A stereo vision system was used on the Mars Rover where the environment (temperature, atmosphere, lighting) rendered other sensors useless (Figure 4 illustrates how lighting complicates the vision task). Hence, vision does provide a useful sensor even with the difficulty of processing images. In the area of sensors and the corresponding interpretative software, the robot's artificial intelligence, there is still a long way to go until we obtain the anthropomorphic robot depicted in science fiction. There are numerous research issues to be addressed, especially in the area of robotic sensory perception.

NICOLA FERRIER

See alsoCOMPUTER SYSTEMS APPLICATIONS; FILM ANIMATION.

Authors contributing to this article:

Computer Architecture and the Von Neumann Bottleneck

The architecture of a computer describes how the CPU, memory and other subsystems are interconnected by signal paths. The first computer designers were faced with many design choices that influenced the usability and performance of their systems. Mathematician John von Neumann was influential in describing how computer programs could be stored together in the same memory unit as the data, thereby simplifying the architecture and improving programming flexibility. Storing programs in memory increases programmer productivity by permitting programs to be assembled in memory using pre-designed program segments. The ability of programs to process other programs as data is essential to such modern software tools as assemblers and compilers.

A limiting factor in computer performance is the speed with which data can be exchanged between the data processing elements and the memory units, where the bulk of the data is stored. This aspect of computers is now called the "Von Neumann bottleneck." Three major components of this bottleneck are the number of simultaneously accessible memories; the limited number of wires connecting the processor and the memory; and the disparity in operating speed between the processor and the typically much slower memory.

The first aspect of the bottleneck can be alleviated partly by using Harvard architecture, where the program and data are stored in separate memories. The second aspect can be alleviated by transferring the data in larger units using more parallel wires; however, the benefits of this solution must offset the resulting increased manufacturing cost. The third aspect can be managed by using a hierarchy of memory subsystems. In a memory hierarchy, faster but more expensive memories at the top of the hierarchy are used to store frequently-used data and instructions in close proximity to the CPU. The contents of the faster memories must be synchronized automatically with the contents of one or more levels of slower memories positioned lower down in the hierarchy. Developing strategies to deal with the von Neumann bottleneck continues to be a central issue in computer architecture design.

The Invisible Computer Infrastructure

The importance of computer hardware in society's technical infrastructure is largely hidden due to computer engineers' success in unobtrusively inserting computer controllers into familiar devices and systems. Additionally, most people would be surprised to learn that the number of personal computers is dwarfed by the 10-fold larger number of unseen embedded computers. These hidden computers control, among other things, automobile and aircraft subsystems, consumer appliances, medical implants and instruments, factories and assembly lines, the telephone system including portable wireless telephone sets, the INTERNET and other data networks, and the power distribution grid. For example, a modern automobile typically contains 20 or more microprocessors that control such functions as the ignition system, antilock brakes, air bag deployment system, dashboard display, and entertainment system. Most people interact directly with identifiable computers, such as desktop personal computers, only through the carefully structured and simplified user interfaces of word processors, spreadsheets, Internet browsers, electronic games and other application programs. The general public is largely unaware of both the extent of their reliance on computer-controlled systems, let alone the complexity of the semiconductor ICs that underlie the changing text and images on their computer screens.

Convergence between Computers, Telecommunications and Entertainment

Convergence between Computers, Telecommunications and Entertainment The evolution of computer hardware has become interwoven with that of TELECOMMUNICATIONS equipment and, increasingly, entertainment devices. Since 1969, the Internet has grown from the first 4 computers of the experimental ARPANET network, to a fast-growing world-wide network connecting tens of millions of computers. Connecting a computer to a network dramatically enhances the computer's usefulness by providing access to such communications-intensive services as electronic mail, remote data storage, distributed data processing, distributed multimedia databases such as the World-Wide Web, remote education and electronic commerce. The communications infrastructure, including the global public telephone network, wireless networks and high-speed data networks, is feasible only with the use of computers. Computer and communications technology is thus interdependent and synergistic.

Similar convergence occurs increasingly between computer and entertainment technologies. Notable examples include high-performance computer games, optical disc storage technology and digital television. The CD-ROM optical data storage device is a modified form of the compact disk (CD) technology originally developed as a storage medium for the recorded music industry. The higher-capacity digital video disk (DVD) will likewise be exploited equally by the computer and entertainment industries. The Internet should be a powerful new medium for delivering movies and music, further evidence of the convergence between entertainment and computer communications.

Beyond Semiconductor Technology

Computer technologies will eventually be developed that are capable of producing faster and more powerful computers than can be produced using semiconductor ICs. Purely optical computing, where information is transmitted and processed directly as light signals, is an attractive proposition given the growing use of optical transmission and switching equipment in communications systems. Purely optically-controlled optical switches would be required to provide the switching function currently performed by electronic transistors. Superconducting computing technology was explored in the 1980s as a potential technology for building supercomputers; perhaps the technical barriers that halted this research effort will be overcome.

The past 50 years of computer history may come to be seen as an anomalous Golden Age, where the potential of a new technology, as in the case of the subsonic jet airliner, was rapidly developed to a level of relative maturity. It is more likely, however, that the next 50 years will lead to a proliferation of dramatically more powerful computer hardware that will make possible new applications that are probably unimaginable today.

BRUCE COCKBURN

Data Mining

With the enormous amount of data stored in files, databases and other repositories, it is increasingly important to develop powerful means for analysis and perhaps interpretation of such data, and for the extraction of knowledge that could help in decision-making. Data mining, also known as Knowledge Discovery from Data (KDD), refers to the extraction of implicit, previously unknown and potentially useful information from large data collections. This is not to be confused with information or data retrieval. Eg, in a library database, data retrieval finds the books written by a given author, or the name of the person who borrowed a given book. Data mining, on the other hand, would find characteristics of readers of a certain type of books, or find relationships between authors of books that are frequently borrowed together. The purpose of data mining is to discover non-obvious information from large data and represent it in ways that can be understood and interpreted by users and decision-makers. The knowledge discovered from data can be, for example, relationships between records or values, descriptions of phenomena occurring in the data, interesting patterns and behaviours, or the forecast of some values. There are 2 main types of data mining: descriptive and predictive. Descriptive data mining seeks to describe the general properties of the existing data, while predictive data mining attempts to perform predictions based on inference on available data.

Data mining is at the confluence of many disciplines, including database management, artificial intelligence, statistics, information retrieval, data visualization and high performance computing. There is a variety of implicit knowledge that can be discovered by diverse data mining techniques:

Data Characterization:

the summarization of general features of objects or records in a data set. Eg, one may want to characterize the buyers of mid-sized sedan cars in Alberta. Age groups and income ranges might be 2 features that summarize this information.

Data Discrimination:

the comparison of the general features of groups of objects. It is basically the simultaneous characterization and contrast of different groups of data. Eg, one may want to compare the buyers in Alberta who buy mid-sized sedan cars with those who buy pick-up trucks. A car dealer could use such information to understand and target customers.

Association analysis:

the discovery of relationships between items that occur together in transactions. Association analysis is commonly used for "market basket analysis." Eg, it could help a department store manager to know which articles are bought together frequently and decide upon product placement or sales strategies.

Prediction:

the forecast of missing numerical values, or increase/decrease trends in time related data. Eg, an analyst may want to forecast the exchange rate value of a given currency, or predict the increase or decrease of a company share value based on past stock exchange activities.

Classification analysis:

the organization of data in given groups or classes. Eg, a credit agency can organize its customers into "safe" clients and "risky" clients based on different attributes of these customers. Classification can also be used for prediction by attributing class labels for some new data. After classifying its current customers, a credit agency could predict, with a certain probability, into which class, "risky" or "safe," a new client may fall.

Clustering and outlier analysis:

Clustering is similar to classification, in that it organizes data into groups with similar characteristics; however, the grouping is done without knowing in advance the number of groups or their labels. The outlier analysis identifies exceptions in data, data elements that cannot be grouped with other data. These exceptions (or outliers) are discarded in some applications, while they are investigated further in other applications to reveal important knowledge about the domain studied.

Data Warehouses

A data warehouse is a repository of data from multiple sources. Usually, the data sources have different structures and are organized differently. The data sources are then known to be heterogeneous because of their structure incompatibility and frequent inconsistencies. The purpose of the data warehouse is to use the data from the different data sources as a whole under the same unified structure. The data from the different sources are thus copied in one unique centralized repository. A data warehouse is very useful for large companies with many branches and departments nation-wide or globally. Regrouping the data from different departments in a data warehouse allows decision-makers in the organization to have an overview of the activities in all the different branches and departments at once. Data warehouses are usually modelled in a multi-dimensional structure. An example of a 2-dimensional structure would be a table representing the sales of products over time. Here the rows represent different products and the columns represent the months of the year. Adding a third dimension representing the location produces a data cube containing the sales of products in time by location. Data warehouses can have many dimensions representing all possible attributes in the application that are useful for analysis and decision-making. Usually the dimensions can be represented at different conceptual levels. Eg, location can be represented at the level "cities" (Vancouver, Toronto, Montreal), "provinces" (BC, Ontario, Quebec) or "countries" (Canada, USA, Mexico).

Using a data warehouse, a decision-maker can view the data at any one of these conceptual levels. Drilling-down from a high concept to a lower one allows viewing of specific data. For example, one can drill-down from Canada to view the data about the different provinces, then drill-down on Alberta to view data related to cities such as Calgary and Edmonton. Browsing the data from a low concept, such as cities, to a higher concept such as provinces or countries, is called "roll-up." This process for analyzing multi-dimensional data is known as on-line analytical processing (OLAP).

OSMAR R. ZAIANE, MARIO NASCIMENTO, M. TAMER OZSU

Solving Problems

Some insight into the nature of theoretical computing science can be gained by looking at some simple problems. Two of the fundamental problems of computing are sorting and searching. Putting a set of items into order, and searching the set for a particular item are important parts of many more complex computing tasks. For this reason, they were some of the first problems to be examined by theoreticians.

Consider locating a name in a telephone directory. The directory is organized so you can easily find the phone number of an individual person or business by sorting the names alphabetically by surname and using this order to lay out the pages of the book.

Suppose you want to phone James Marsh and need to search for his name in the directory. Unless your phone book is very short you won't begin at page one and check each name individually. Instead you open the phone book roughly in the middle and check the top of the page to determine where in the alphabet you are. Say you opened it at page 580 with the letter L at the top. Since M is directly after L, and the phone book is ordered alphabetically, you know that the letter M follows shortly after page 580. You open the book a little past 580 at page 616 and scan the page carefully to find "Marsh, J." Because the phone book was sorted by name you could find the entry you wanted very quickly. Instead of carefully scanning through 616 pages of the book, you looked at the top of 2 pages (to find where you were in the alphabet) and only needed to carefully scan one page. This was much faster than looking through the phone book page by page.

The theory of computation tells us that when a book containing over 1000 pages is ordered by surname, it will take at most 10 quick looks at a page followed by one careful scan to find any name. The theory also tells us that this is the best that a person looking for a name can do for books (like dictionaries) organized this way. In general, if there are 2n pages in a phone book, we will have to only look at n of them. There are other ways, called hash indexes, that are faster, but they are only suited to computers and are not easy for humans to use.

Now suppose you wanted to find the phone number of a man in your neighbourhood you just met. He told you his first name and pointed out his house across the street from your own. Unfortunately, the directory is not sorted by address, so you will have to search through it carefully, page by page, looking for a name to match the address. The theory of computation tells us that on average you will have to look through about half the book to find a given address. Sometimes it will take less - you might be lucky enough to find it in the first few pages. Sometimes it will take more, if the address is in the last few pages. It would probably be faster simply to walk over to the person's house.

Alternatively, you could take all the entries in the directory, sort them by address, and create a new directory organized by address. How long would it take? The theory of computation gives us many methods, or algorithms, for sorting, and tells us how much time each one is expected to take. If you want to sort 2n addresses, then theory tells us that we can do it in about n x 2n steps. This is called an upper bound, the most work we have to do. The theory of sorting also tells us that we cannot do much better. The lower bound on sorting says that we will have to do at least n x 2n steps to sort 2n addresses.

Models of Computation

When theoreticians talk about computations, they rarely talk about doing those computations on a real computer. Instead they use an idealized computer, called a model of computation, that has only the most important features of a real computer. The idea is that a model of computation should not depend too much on current computer technology because the technology changes very rapidly, so details of how a program works will change. But, regardless of technology, most computers have common features like memory for storing data and programs, and a computation unit (the CPU) for manipulating the data (eg, by doing arithmetic operations, or moving the data around in memory). The model of computation ignores the details and concentrates on the common features that will remain as technology changes. If a radically new technology arrives, perhaps as optical or quantum computing, then new theoretical models will be introduced.

In the discussion so far, there has only been a single computer (you or the machine). Although real computers are much more complicated, a single computer basically does only one thing at a time. Such a machine is called sequential, and it computes one step after the other. There are many sequential models of computation, but they all share this restriction.

Another more powerful kind of machine contains many computers hooked together. In this machine, each individual computer can work in parallel with others. When theoreticians study parallel machines, they use parallel models of computation. Parallel machines are interesting because they can do many things at once, and potentially can solve problems faster. Parallel computation is the computer equivalent of the adage "Many hands make light work." For example, if a professor has a class of 50 students, and it takes 10 minutes to mark a quiz, then the professor will spend 500 minutes marking. If an assistant is also used, the quizzes can be split between them, and each marks 25 quizzes. The total amount of work is the same, 500 minutes of marking, but each person only spends 250 minutes. If they work simultaneously, then the total elapsed time is halved to 250 minutes. If there are 50 people marking, then the whole job can be done in 10 minutes, a factor of 50 better than one person alone.

Parallel computation is especially useful in search problems, where the computers can operate relatively independently. For instance, in the phone book example above, if we had enough computers to store a different page in each computer, we ask all the computers at the same time to locate the entry for Jim Marsh. With this many computers the time to search has been reduced to just the time to look on a single page. This is true even if the book is not sorted the way we want, as in the case of looking for a specific address or phone number.

The difficulty with parallel computation is in figuring out how to divide up the tasks so that all the computers are kept busy. This is not easy, and not always possible as the number of computers working in parallel increases. In the marking example above, if there were 100 markers, then there would be 2 per paper. It would require some effort to divide the exam book into 2 parts in order that a single exam could be marked in parallel by 2 markers.

Difficult Problems

Sorting and searching are problems with efficient solutions on sequential computers. Eg, finding the shortest path between 2 points on a road grid connecting n cities can be done in about n² steps. Multiplying 2 n-digit numbers takes at most n² steps (there are even faster algorithms).

But many other problems do not appear to have such efficient solutions. Eg, if you have a friend in each one of the n cities in the above road grid, and you want to go on a tour and visit each city exactly once, then return home, finding the shortest length tour, or even finding a tour at all, is very difficult. No one knows how to build a computer program that can find such a tour within n² steps, or n³ or even n¹⁰ steps. The best that can be done by a single machine is about 2n steps. This number of steps is exponential in the number of cities. For 10 friends it is not too bad, about 1000 steps. But if you had 100 friends, it would take about 10³⁰steps, which is 40 trillion years if you can do a billion steps per second. Using a parallel machine does not help, since such a huge number of computers couldn't possibly be manufactured. So although one could imagine how to solve this problem, in practice such a problem is unsolvable.

What is interesting about very difficult problems is that they are all related - NP-complete problems. The problems are so difficult that if you could solve one of them, you could solve all the others. Although much progress has been made on such problems over the last 30 years, theoretical computing science is no closer to finding techniques for efficiently solving them exactly.

Difficult problems have 2 particularly interesting and practical consequences. First, simply because no known efficient algorithm to solve a problem exists does not make the issue any less pressing in practice. Therefore the search for methods that solve most instances of such problems or that give good approximate solutions is a major area of theoretical computing science. Knowing what makes a problem difficult can sometimes lead to a related problem that avoids the difficulty yet still answers much of what was originally desired.

Secondly, one can make a virtue of having certain computations that seem hard to perform, such problems found in cryptography. Cryptography systems exploit difficult problems, like breaking an integer into its prime factors. The system is set up so that breaking the code is equivalent to solving a difficult problem; we can say that breaking the code is difficult. Cryptography is of enormous importance as the use of the Internet makes financial transactions over insecure transmission lines commonplace.

Impossible Problems

In addition to difficult problems, there are problems that cannot be solved by any computer. Eg, there is no program that can take as input another arbitrary program and tell whether or not it would ever stop running. There is no program that can take an arbitrary mathematical statement and then decide if it is true or false. Thus there are fundamental logical limits to what can be computed.

Interestingly, these unsolvable problems were raised even before the first real computer was constructed. Although the actual proof of these results is reasonably complicated, they are all essentially the problem of asking the computer to decide the truth or falsehood of the following sentence: "This sentence is false." The computer must answer true or false, but cannot because if the sentence is true, then it must be false. But if it is false, then it must be true. So it must be that it is neither, which is impossible as far as the computer is concerned.

Canadians in Theoretical Computing Science

Jack Edmonds of the U of Waterloo was one of a number of researchers in the 1960s who observed that to be useful on a reasonably-sized problem a program had to run in polynomial time. In 1971 Steve Cook of the U of Toronto introduced the idea of NP-Complete problems as a way of identifying problems that had no practical solution. Nick Pippenger, of UBC, introduced in the late 1970s the similar classification of problems that are hard for parallel computers. A number of Canadian universities have made an impact in cryptography. Gilles Brassard, of the U de Montréal, is one of the key inventors of quantum cryptography which exploits quantum physics effects to generate hard problems.

J. IAN MUNRO Revised: H. JAMES HOOVER