И.С. Гудилина, Л.Б. Саратовская, Л.Ф. Спиридонова - English Reader in Computer Science, страница 10

Models involving human behavior are unavoidably complex. Such models may not work except the limited cases, and even then they will be made to work by ongoing development rather than by prior analysis. One's trust in the reliability of such models depends on one's assumptions about how biological organisms and societies learm and act.

Knowledge-based systems (KBSs) are important examples of computer models. A KBS is supposed to reproduce the decision of an expert in a domain. Continual testing and improvement must be the standard approach to obtain reliable KBSs. The tests must do more than comparing KBS decision with real situations; they must validate that at all times the recommended actions fulfill the purpose of the system, that the reasoning procedures are valid for the domain, and that the recommended actions are consistently endorsed and assessed as competent by human experts. Tests must include simple realistic cases as well as cases that apply various stresses to the KBS. Some of the tests must be retrospective (comparing KBS decisions with those of experts in the past) and some must be prospective (testing the KBS against experts in real time).

KBSs are founded on the assumption that an expert works from a complete theory of the domain. However experts themselves do not work from complete theories, and much of their expertise cannot be articulated in language. The advocates of neural networks claim they have found a way to overcome the inability to articulate expertise. Neural networks mimic the biological structure of the brain and therefore the expert's approach to gathering and organizing information. Once the networks have been trained, their advocates say, they will be able to acquire the knowledge experts have that cannot be articulated as rules.

Unit 4

Mathematics and the Internet

The relationship between mathematics and the Internet is like that between any language and the works of Shakespeare: his work could not have been conceived without language, while his poems and plays have enriched the language as it evolved.

Computers were born in the language of mathematics. Binary numbers let computers represent words, music, images and more so that machines can now communicate across the Internet with an alphabet of 0's and 1's. The impartial rules of mathematical logic govern computer operations. Internet addressing, and even Web search engines.

Within the Internet, mathematics is at the heart of security for messages and financial transactions. It is the basic tool of data compression, coding, and error correction for transmitting large files. It is the foundation of databases for managing email addresses and for searching the World Wide Web and it is the agent for routing messages and managing networks.

The Internet is also helping advance mathematical research and education. Groups of educators and researchers communicate through email, newsgroups, and special World Wide Web sites. The Internet also supports distributed computing such as the recent cooperative effort which linked computers across dozens of countries to crack a code once thought secure for 20 millennia.

Managing Data on the Internet

As most people know. Internet messages — e-mail, graphics, sound, the results of database searches — are transmitted as strings of 0's and 1's. Mathematics is central to two parts of this digital translation and transmission:

• accurately transmitting a text message, say, that has been translated into binary numbers requires codes for detecting and correcting errors (not to be confused with secret codes), and

• reducing the volume of data in an image, for example, that must be transmitted and then reconstructed as a reasonable likeness of the original, uses the tools of data compression.

When massive strings of 0's and 1's are forced over computer networks, some errors are inevitable, and even small losses of data can be catastrophic. Error detecting codes introduce mathematical tools to detect many of those losses, much like counting the number of pages in a long letter as a way of determining if anything was lost .in the mail.

A standard tool for detecting errors in Internet transmission are cyclic codes; a common choice is CRC-16, a cyclic redundancy code that can detect errors in as many as 16 consecutive bits in a message. CRC-16 can also catch about 99% of errors longer than 16 bits. When an error is detected, the receiving computer simply fails to acknowledge its arrival, and the sender knows to retransmit.

These codes perform a special kind of division on the numerical representation of the message. The sender can attach the remainder from that division to the message without adding much to its length, but the extra information enables the receiver to verify the message by repeating the division. Getting the wrong remainder means the message was corrupted.

Like error correcting codes, data compression ideas are also shared across a wide range of technologies, including the forthcoming digital television. (One second of high definition, uncompressed video would require more than seven hours to arrive over a conventional home modem!) The challenge of data compression is to reduce by many orders of magnitude the volume of data, and hence the transmission time, while preserving all the visually important parts of the image.

Good data compression schemes help World Wide Web graphics appear quickly and attractively on a computer screen. The same tools bring sound files that please the ear, even though selected parts have been removed or reconstructed. Some of the latest data compression ideas use wavelets, a kind of multiscale analysis tool.

Security on the Internet

Security on the Internet is as important as the security of a bank vault. Security concerns encompass privacy of messages, integrity of computers connected to the Internet, and trust in financial transactions, among many other issues. The rapidly growing Internet marketplace, for example, depends heavily on secret codes mat combine centuries-old number theory with discoveries of the past two decades.

Moreover, efforts to break such codes use the Internet to distribute the computing burden over a wide array of machines. That distributed computing in turn depends in a crucial way on modem extensions of an old idea of Fermat for methodically searching for prime factors of large numbers.

Internet security can be seen in two complementary parts. One is the problem of sending a message that only the recipient can read, insuring both confidentiality of the message and its fidelity. The other is verifying the identity of the sender of a message. The first amounts to finding a code which is hard to crack while still permitting rapid transmission and decoding. The second is the problem of digital signatures: how can an Internet merchant be sure that the signature on an electronic check is genuine? The solutions to both problems rest squarely on me shoulders of number theory, a deceptively deep branch of mathematics.

Conventional encryption schemes like the Data Encryption Standard (DES) function like a locked mailbox to which the sender and recipient each have the only two keys. The problems here are securely transmitting keys to new pairs of correspondents and managing the large collection of keys a busy correspondent needs. Public-key or RSA systems (named for R. L. Rivest. A. Shamir, and L, Adieman, who published the first workable scheme in 1978, based on ideas of W. Diffie and M. Hellroan) have been likened to open mailboxes that can be slammed shut by any sender who wishes to deposit a message but opened only by the owner of the mailbox, the recipient. That is, anyone can code a message for a given recipient but only the recipient can decode it.

Coding a public-key message requires knowledge of two (large) numbers, the so-called public key; decoding it requires a third number, the private key known only to the recipient. The coding and decoding steps use modular arithmetic, a kind of clock face arithmetic (for example, dividing a journey time of many, many hours by 24 to find the remainder that determines the time of day of arrival).

When new members join a public-key encryption scheme, the first step in establishing their keys is their (random) choice of two large prime numbers. Then the keys are calculated from those prime numbers in a series of steps based on a two-century-old theorem of Euler. The public-key scheme is secure unless those two prime numbers can be recovered by factoring one of the public key numbers; the RSA system uses numbers of 129 digits because their prime factors are so difficult to find.

Indeed, Rivest, Shamir, and Adieman believed their scheme to be so secure that in 1977 they challenged the world to decode a message that had been encoded into 128 digits. At that time, they estimated that factoring would take 23,000 years! Yet in 1994, an informal group of 600 volunteers in more than two dozen countries, communicating through the Internet, collected idle CPU cycles on all sorts of computers — even fax machines — to put to work Carl Pomerance's 1981 quadratic sieve algorithm, a descendant of 350-year-old ideas of Fermat. After eight months of work, the 64 and 65 digit factors were discovered.

The RSA 128 digit challenge number was cracked using the Internet, albeit not very quickly. Distributed computing over the Internet cracked the wall protecting the confidentially of distributed communication! Increased security can be easily attained by using public keys with more digits.

Databases and searching

Powerful Web search engines like AltaVista and Yahoo/ let Internet users find specialized nuggets of information hidden all over cyberspace. The heart of most of these key word. (The entry for "mathematics" in one search index lists 332,966 sites!) Ideally, the search engine returns not just the intersection of all index entries for the given key words but also a priority score reflecting the potential relevance of each listed site to the searcher's needs.

Some of the latest thinking on balancing comprehensive search with relevance has led to a vector space model of the information in the index. The coordinates of the space are the terms in the index, the key word vocabulary through which one can search. Each Web site is a point in that space whose coordinates are determined by its "hits" on the key words, perhaps giving the most relevant key words the largest coordinate values. Sites with similar information are represented by points in this space that are near one another in some sense.

In reality, search engines do not explicitly manipulate matrices with hundreds of thousands of rows and columns. Instead, they rely upon clever computational implementations of databases.

Many databases are built around the mathematical object known as a tree. These trees are like family trees that record relations among parents and children and their ancestors and descendants. An index, for example, might consist of twenty-six family trees, one for each letter of the alphabet. The first level of children would be all legal two-letter combinations, and so on; for example, aardvark would be a distant descendant of aa.

Beyond the parent-child connection, relational databases define additional relationships among their entries. The power of a relational database comes from its ability to manipulate those relations; e.g., performing an intersection operation that can find a common string of letters appearing in two different words. The rules for those manipulations are mathematically defined in a relational algebra or relational calculus specific to that database structure. Mathematics is the framework for describing database constructs, and mathematical tools are the basis for improving their efficiency and reliability.

Routing and network configuration

A local area network of moderate size might have 10,000 pairs of nodes that communicate with one another. The messages they share are like trains running at the speed of light on the tracks of the network. Each car in the train carries part of one message, as if a long letter had been written on a series of postcards, one card per car. Typically, cards from many messages are mixed in one train.

The performance of the network depends on the length of the trains — the size of the message packets — and on the space between the trains. For example, a long message train that arrives at the wrong time can delay many other messages until it passes; short messages properly spaced can be slid in among one another.

The mathematical ideas of queuing theory can predict the behavior of message handling protocols based on information about the size and arrival patterns of these message packets. (The classic application of queuing theory is estimating the waiting time at a bank, given the arrival patterns of customers and the service time of the bank teller.)