:: wikimiki.org ::

Algorithm

Algorithm

In mathematics and computer science an algorithm (the word is derived from the name of the Persian mathematician Al-Khwarizmi) is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state (contrast with heuristic). Algorithms can be implemented by computer programs, although often in restricted forms; mistakes in implementation and limitations of the computer can prevent a computer program from correctly executing its intended algorithm. The concept of an algorithm is often illustrated by the example of a recipe, although many algorithms are much more complex; algorithms often have steps that repeat (iterate) or require decisions (such as logic or comparison). Correctly performing an algorithm will not solve a problem if the algorithm is flawed or not appropriate to the problem. For example, a hypothetical algorithm for making a potato salad will fail if there are no potatoes present, even if all the motions of preparing the salad are performed as if the potatoes were there. Different algorithms may complete the same task with a different set of instructions in more or less time, space, or effort than others. For example, given two different recipes for making potato salad, one may have peel the potato before boil the potato while the other presents the steps in the reverse order, yet they both call for these steps to be repeated for all potatoes and end when the potato salad is ready to be eaten. Certain countries, such as the USA, controversially allow some algorithms to be patented, provided a physical embodiment is possible (for example, a multiplication algorithm may be embodied in the arithmetic unit of a microprocessor).

Formalized algorithms

Algorithms are essential to the way computers process information, because a computer program is essentially an algorithm that tells the computer what specific steps to perform (in what specific order) in order to carry out a specified task, such as calculating employees’ paychecks or printing students’ report cards. Thus, an algorithm can be considered to be any sequence of operations which can be performed by a Turing-complete system. Typically, when an algorithm is associated with processing information, data is read from an input source or device, written to an output sink or device, and/or stored for further use. Stored data is regarded as part of the internal state of the entity performing the algorithm. For any such computational process, the algorithm must be rigorously defined: specified in the way it applies in all possible circumstances that could arise. That is, any conditional steps must be systematically dealt with, case-by-case; the criteria for each case must be clear (and computable). Because an algorithm is a precise list of precise steps, the order of computation will almost always be critical to the functioning of the algorithm. Instructions are usually assumed to be listed explicitly, and are described as starting 'from the top' and going 'down to the bottom', an idea that is described more formally by flow of control. So far, this discussion of the formalisation of an algorithm has assumed the premises of imperative programming. This is the most common conception, and it attempts to describe a task in discrete, 'mechanical' means. Unique to this conception of formalized algorithms is the assignment operation, setting the value of a variable. It derives from the intuition of 'memory' as a scratchpad. There is an example below of such an assignment. See functional programming and logic programming for alternate conceptions of what constitutes an algorithm.

Implementation

Algorithms are not only implemented as computer programs, but often also by other means, such as in a biological neural network (for example, the human brain implementing arithmetic or an insect relocating food), or in electric circuits or in a mechanical device. The analysis and study of algorithms is one discipline of computer science, and is often practiced abstractly (without the use of a specific programming language or other implementation). In this sense, it resembles other mathematical disciplines in that the analysis focuses on the underlying principles of the algorithm, and not on any particular implementation. One way to embody (or sometimes codify) an algorithm is the writing of pseudocode. Some writers restrict the definition of algorithm to procedures that eventually finish. Others include procedures that could run forever without stopping, arguing that some entity may be required to carry out such permanent tasks. In the latter case, success can no longer be defined in terms of halting with a meaningful output. Instead, terms of success that allow for unbounded output sequences must be defined. For example, an algorithm that verifies if there are more zeros than ones in an infinite random binary sequence must run forever to be effective. If it is implemented correctly, however, the algorithm's output will be useful: for as long as it examines the sequence, the algorithm will give a positive response while the number of examined zeros outnumber the ones, and a negative response otherwise. Success for this algorithm could then be defined as eventually outputting only positive responses if there are actually more zeros than ones in the sequence, and in any other case outputting any mixture of positive and negative responses.

Example

One of the simplest algorithms is to find the largest number in an (unsorted) list of numbers. The solution necessarily requires looking at every number in the list, but only once at each. From this follows a simple algorithm: # Look at each item in the list. If it is larger than any that has been seen so far, make a note of it. # The latest noted item is the largest in the list when the process is complete. And here is a more formal coding of the algorithm in pseudocode: Algorithm LargestNumber Input: A non-empty list of numbers L. Output: The largest number in the list L. largest ← -∞ for each item in list L, do if the item > largest, then largest ← the item return largest Notes on notation:
- "←" is a loose shorthand for "changes to". For instance, with "largest ← the item", it means that the largest number found so far changes to this item.
- "return" terminates the algorithm and outputs the value listed behind it. As it happens, most people who implement algorithms want to know how much of a particular resource (such as time or storage) a given algorithm requires. Methods have been developed for the analysis of algorithms to obtain such quantitative answers; for example, the algorithm above has a time requirement of O(n), using the big O notation with n as the length of the list. At all times the algorithm only needs to remember a single value; the largest number found so far. Therefore this algorithm has a space requirement of O(1). (Note that the size of the inputs is not counted as space used by the algorithm.) For a more complex example see Euclid's algorithm.

History

Euclid's algorithm The word algorithm comes from the name of the 9th century Persian mathematician Abu Abdullah Muhammad bin Musa al-Khwarizmi. The word algorism originally referred only to the rules of performing arithmetic using Hindu-Arabic numerals but evolved into algorithm by the 18th century. The word has now evolved to include all definite procedures for solving problems or performing tasks. The first case of an algorithm written for a computer was Ada Byron's notes on the analytical engine written in 1842, for which she is considered by many to be the world's first programmer. However, since Charles Babbage never completed his analytical engine the algorithm was never implemented on it. The lack of mathematical rigor in the "well-defined procedure" definition of algorithms posed some difficulties for mathematicians and logicians of the 19th and early 20th centuries. This problem was largely solved with the description of the Turing machine, an abstract model of a computer formulated by Alan Turing, and the demonstration that every method yet found for describing "well-defined procedures" advanced by other mathematicians could be emulated on a Turing machine (a statement known as the Church-Turing thesis). Nowadays, a formal criterion for an algorithm is that it is a procedure that can be implemented on a completely-specified Turing machine or one of the equivalent formalisms. Turing's initial interest was in the halting problem: deciding when an algorithm describes a terminating procedure. In practical terms computational complexity theory matters more: it includes the problems called NP-complete, which are generally presumed to take more than polynomial time for any (deterministic) algorithm. NP denotes the class of decision problems that can be solved by a non-deterministic Turing machine in polynomial time.

Classes

There are many ways to classify algorithms, and the merits of each classification have been the subject of ongoing debate. One way of classifying algorithms is by their design methodology or paradigm. There is a certain number of paradigms, each different from the other. Furthermore, each of these categories will include many different types of algorithms. Some commonly found paradigms include:
- Divide and conquer. A divide and conquer algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively), until the instances are small enough to solve easily.
- Dynamic programming. When a problem shows optimal substructure, meaning the optimal solution to a problem can be constructed from optimal solutions to subproblems, and overlapping subproblems, meaning the same subproblems are used to solve many different problem instances, we can often solve the problem quickly using dynamic programming, an approach that avoids recomputing solutions that have already been computed. For example, the shortest path to a goal from a vertex in a weighted graph can be found by using the shortest path to the goal from all adjacent vertices.
- The greedy method. A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a "greedy" choice can be made of what looks best for the moment.
- Linear programming. When solving a problem using linear programming, the program is put into a number of linear inequalities and then an attempt is made to maximize (or minimize) the inputs. Many problems (such as the maximum flow for directed graphs) can be stated in a linear programming way, and then be solved by a 'generic' algorithm such as the Simplex algorithm.
- Search and enumeration. Many problems (such as playing chess) can be modelled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. This category also includes the search algorithms and backtracking.
- The probabilistic and heuristic paradigm. Algorithms belonging to this class fit the definition of an algorithm more loosely. # Probabilistic algorithms are those that make some choices randomly (or pseudo-randomly); for some problems, it can in fact be proved that the fastest solutions must involve some randomness. # Genetic algorithms attempt to find solutions to problems by mimicking biological evolutionary processes, with a cycle of random mutations yielding successive generations of 'solutions'. Thus, they emulate reproduction and "survival of the fittest". In genetic programming, this approach is extended to algorithms, by regarding the algorithm itself as a 'solution' to a problem. Also there are # Heuristic algorithms, whose general purpose is not to find a optimal solution, but an approximate solution where the time or resources to find a perfect solution are not practical. An example of this would be local search, taboo search, or simulated annealing algorithms, a class of heuristic probabilistic algorithms that vary the solution of a problem by a random amount. The name 'simulated annealing' alludes to the metallurgic term meaning the heating and cooling of metal to achieve freedom from defects. The purpose of the random variance is to find close to globally optimal solutions rather than simply locally optimal ones, the idea being that the random element will be decreased as the algorithm settles down to a solution. Another way to classify algorithms is by implementation. A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming. Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time. Those computers are sometimes called serial computers. An algorithm designed for such an environment is called a serial algorithm, as opposed to parallel algorithms, which take advantage of computer architectures where several processors can work on a problem at the same time. The various heuristic algorithms would probably also fall into this category, as their name (e.g. a genetic algorithm) describes its implementation.

References

- Important algorithm-related publications

External links

-
- Algana.co.uk [http://www.algana.co.uk/ Algorithm analysis and puzzles.] Free source code for algorithm Java applets and C++ modules
- Gaston H. Gonnet and Ricardo Baeza-Yates: Example programs from [http://www.dcc.uchile.cl/~rbaeza/handbook/ Handbook of Algorithms and Data Structures.] Free source code for many important algorithms.
- [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures]. "This is a dictionary of algorithms, algorithmic techniques, data structures, archetypical problems, and related definitions."
- [http://www.nr.com Numerical Recipes]
- [http://www.algosort.com/ Computer Programming Algorithms Directory]
- [http://dmoz.org/Computers/Algorithms/ Computers/Algorithms @ dmoz.org]
- [http://groups-beta.google.com/group/algogeeks "Algogeeks" Google Group] - Discuss ideas, algorithms, challenges related to programming. Also announcements about Online Programming Contests will be posted in this group.
- [http://musicalgorithms.ewu.edu/ Musicalgorithms] An interesting way of using algorithms to make music.
- [http://www.algorithmist.com/ The Algorithmist] is a resource dedicated to anything algorithms - from the practical realm, to the theoretical realm. There are also links and explanation to problem sets.
- [http://www.algogeeks.com/ AlgoGeeks] Community of algorithm enthusiastics actively involved in algorithm discussions, knowledge, problems and solutions, thus creating resource for algorithms, puzzles and problems
- Category:Discrete mathematics Category:Computer science Category:Mathematical logic Category:Arabic words ko:알고리즘 ja:アルゴリズム th:อัลกอริทึม

Computer science

Computer science, an academic discipline (abbreviated CS or compsci), is a body of knowledge generally about computer hardware, software, computation and its theory. The discipline itself includes, but is not limited to, the fundamentals of computer languages, operating systems and mathematical foundations of computer science. The study of these fundamentals may lead to a wide variety of topics, such as algorithms, formal grammars, programming languages, program design, artificial intelligence and computer engineering. There exist a number of technical definitions of computer science. The status of computer science as a science is often challenged, typically arguing that it is more like mathematics and that it does not follow the scientific method, however these facts are not unanimously accepted. In popular language, the term computer science is often confusingly used to denominate anything related to computers.

History of computer science

Evolutionary

Before the 1920s, computers were human clerks that performed calculations. They were usually under the lead of a physicist. Many thousands of computers were employed in commerce, government, and research establishments. Most of these computers were women, and they were known to have a degree in calculus. After the 1920s, the expression computing machine refered to any machine that performed the work of a human computer, especially those in accordance with effective methods of The Church-Turing Thesis. The thesis states that a mathematical method is effective if it could be set out as a list of instructions able to be followed by a human clerk with paper and pencil, for as long as necessary, and without ingenuity or insight. Machines that computed with discrete values became known as the analog kind. They used machinery that represented discrete numeric quantities, like the angle of a shaft rotation or difference in electrical potential. Digital machinery, in contrast to analog, were able to render a state of a numeric value and store each individual digit. Digital machinery used difference engines or relays before the invention of faster memory devices. The phrase computing machine gradually gave away, after the late 1940s, to just computer as the onset of electronic digital machinery became common. These computers were able to perform the calculations that were performed by the previous human clerks. Since the values stored by digital machines were not bound to physical properties like the analog device, a logical computer, based on digital equipment, was able to do anything that could be described "purely mechanical." Alan Turing, known as the Father of Computer Science, invented such a logical computer, also known as a Turing Machine, that evolved into the modern computer from the tasks performed by the previous human clerks. These new computers were also able to perform non-numeric computations, like music. Computability, by logical computers, began a science by being able to make evident which was not explicitly defined into ordinary sense more immediate.

Academic discipline

Computer science has roots in electrical engineering, logic, mathematics, and linguistics. In the last third of the 20th century computer science emerged as a distinct discipline and developed its own methods and terminology. Originally, CS was taught as part of mathematics or engineering departments, for instance at the University of Cambridge in England and at the Gdansk University of Technology in Poland, respectively. Cambridge claims to have the world's oldest taught qualification in computing. The first computer science department in the United States was founded at Purdue University in 1962, while the first college entirely devoted to computer science was founded at Northeastern University in 1982. Most universities today have specific departments devoted to computer science, while some conjoin it with engineering, with applied mathematics, or other disciplines. Most research in computer science has focused on von Neumann computers or Turing machines (computation models that perform one small, deterministic step at a time). These models resemble, at a basic level, most real computers in use today. Computer scientists also study other models of computation, which includes parallel machines and theoretical models such as probabilistic, oracle, and quantum computers.

Careers

Some of the potential careers for those who study computer science are listed below:

Demographics

- Nearly half of all computer programmers held a bachelor’s degree in 2002; about 1 in 5 held a graduate degree. [http://www.bls.gov/oco/ocos110.htm]
- Computer programmer employment is expected to grow much more slowly than that of other computer specialists.
- Education requirements range from a 2-year degree to a graduate degree. [http://www.bls.gov/oco/ocos042.htm]
- Employment, other than computer programmer, is expected to increase much faster than the average as organizations continue to adopt increasingly sophisticated technologies.

Sub-disciplines of computer science

Computer Science has a number of major sub-fields which can be classified by a number of means (for example the [http://www.acm.org/class/1998/overview.html ACM classification system]).

Algorithms

The study of algorithms is aimed at creating techniques that will enable a computer to perform a certain task in an efficient manner. An algorithm is a set of well-defined instructions for accomplishing some task, often explained by analogy with a culinary recipe. Algorithms are often implemented in software, and advancing the state of the art in algorithms is responsible for many of the most spectacular successes in computing. An algorithms specialist may come up with methods to accomplish new tasks, but just as often, they will work on improving the efficiency of an existing algorithm. These improvements can come in "time" (the length of time it takes for the algorithm to work) and "space" (the amount of computer memory the algorithm consumes. The field of algorithms is highly formal and many things can be proved about a given algorithm (using complexity theory), including roughly how long it will take to complete, as compared to the size of its input (the number of options it must consider). One interesting open question in algorithms concerns the complexity classes P and NP, and whether or not P = NP. If it does, then a whole range of seemingly difficult algorithms can in theory be performed quickly.

Data structures

A data structure is a way to store data so that it can be remembered and retrieved efficiently. A well-designed data structure means that an algorithm can be performed using as little memory space and time as possible. Some data structures are very simple: the simplest is an array which is simply a numbered list of items. Since the memory of a computer is usually modelled as an array (of bytes), this is also one of the most important data structures in computer science. For example, strings of text are usually modelled as arrays. But there are many other data structures such as linked lists, trees, hash tables and many others that are quite different but critical to the science. Type theory classifies data at a most basic (mathematical) level into different types, such as integers, complex numbers, strings, etc. and deals with how those types can interact. Abstract data types, at a more concrete level, deal with how types and data structures are used in software programming.

Listing of sub-disciplines

Computer science is closely related to a number of fields. These fields overlap considerably, though important differences exist:

Major fields of importance for computer science

External links

- [http://www.dmoz.org/Computers/Computer_Science/ Open Directory Project: Computer Science]
- [http://www.techbooksforfree.com/science.shtml Downloadable Science and Computer Science books]
- [http://liinwww.ira.uka.de/bibliography/ Collection of Computer Science Bibliographies]
- [http://www.geocities.com/tablizer/science.htm Belief that title "science" in "computer science" is inappropriate] Category:Computer science ko:컴퓨터 과학 ja:情報工学 simple:Computer science th:วิทยาการคอมพิวเตอร์

Mathematician

A mathematician is a person whose area of study and research is mathematics. Today, most mathematicians are professors at a university or other research institution; however, a minority have a non-academic career and are often known as amateur mathematicians. While a number of misinformed people may believe mathematics is fully understood (as it is often presented this way in elementary textbooks), in fact, there is ongoing research into many areas of mathematics. In fact, the publication of new discoveries in mathematics continues at an immense rate in hundreds of scientific journals, many of them devoted to mathematics and many devoted to subjects to which mathematics is applied (such as theoretical computer science and theoretical physics). Unlike the other sciences, research in mathematics generally does not consist of performing experiments. Rather, mathematics is about problem-solving, where truths are deduced from other known truths. Computer experiments and other numerical evidence might be a part of this process, but in the end, mathematics research is about constructing proofs of theorems. In particular, calculation is not a big part of mathematics research, and mathematicians need not have any extraordinary ability in adding or multiplying numbers. See mental calculators to read about prodigies at performing such calculations.

Motivation

Mathematicians are typically interested in finding and describing patterns that may have originally arisen from problems of calculation, but have now been abstracted to become problems of their own. Problems have come from physics, economics, games, generalizations of earlier mathematics, and some problems are simply created for the challenge of solving them. Although much mathematics is not immediately useful, history has shown the eventually applications are found. For example, number theory originally seemed to be without purpose, but after the invention of computers it gained countless applications to algorithms and cryptography.

Differences

Mathematicians differ from philosophers in that the primary questions of mathematics are assumed (for the most part) to transcend the context of the human mind; the idea that "2+2=4 is a true statement" is assumed to exist without requiring a human mind to state the problem. Not all mathematicians would strictly agree with the above; the philosophy of mathematics contains several viewpoints on this question. Mathematicians differ from physical scientists such as physicists or engineers in that they do not typically perform experiments to confirm or deny their conclusions; and whereas every scientific theory is always assumed to be an approximation of truth, mathematical statements are an attempt at capturing truth. If a certain statement is believed to be true by mathematicians (typically as special cases are confirmed to some degree) but has neither been proven nor disproven to logically follow from some set of assumptions, it is called a conjecture, as opposed to the ultimate goal, a theorem that is proven true. Unlike physical theories, which may be expected to change whenever new information about our physical world is discovered, mathematical theories are static. Once a statement is considered a theorem, it remains true forever.

Demographics

As is the case in many scientific disciplines, the field of mathematics has been disproportionately dominated by men. Among the minority of prominent female mathematicians are Emmy Noether (1882 - 1935), Sophie Germain (1776 - 1831), Sofia Kovalevskaya (1850 - 1891), Rózsa Péter (1905 - 1977), Julia Robinson (1919 - 1985), Mary Ellen Rudin, Eva Tardos, Émilie du Châtelet, Mary Cartwright and Marianna Csörnyei.

Quotes

...beware of mathematicians, and all those who make empty prophecies. The danger already exists that the mathematicians have made a covenant with the devil to darken the spirit and to confine man in the bonds of Hell. :-Saint Augustine, De Genesi ad Litteram (actually "mathematicians" in this context refers mainly to astrologers and such) A mathematician is a machine for turning coffee into theorems. :-Paul Erdős Die Mathematiker sind eine Art Franzosen; redet man mit ihnen, so übersetzen sie es in ihre Sprache, und dann ist es alsobald ganz etwas anderes. (Mathematicians are [like] a sort of Frenchmen; if you talk to them, they translate it into their own language, and then it is immediately something quite different.) :-Johann Wolfgang von Goethe Some humans are mathematicians; others aren't. :-Jane Goodall (1971) In the Shadow of Man

Jokes

Several old jokes common amongst the scientific disciplines illustrate the difference between the mathematical mind and that of other disciplines. One goes as follows: :An engineer, a physicist, and a mathematician are all staying at a hotel one night when a fire breaks out. The engineer wakes up and smells the smoke; he quickly grabs a garbage pail to use as a bucket, fills it with water from the bathroom, and puts out the fire in his room. He then refills the pail and douses everything flammable in the room with water. He then returns to sleep. :The physicist wakes up, smells the smoke, jumps out of bed. He picks up a pad and pencil and makes some calculations, glancing frequently at the flames. He then measures exactly 15.6 liters of water into the garbage pail, and throws it on the flames, which are extinguished. Smiling, he returns to sleep. :Finally the mathematician wakes up. He too grabs a pad and begins furiously writing; glancing at the flames; and then writing more. After a while he gets a satisfied look on his face; entering the bathroom, he produces a match, lights it, and then extinguishes it with a bit of running water. "Aha! A solution exists," he murmurs - and returns to his slumbers. Another joke goes thus: :Three men are flying in a hot air balloon and suddenly they realize that they are lost. Luckily they see a man plowing a field and ask, "Where are we?". The man on the ground thinks for a minute and then answers, "You are in a hot air balloon". One of the men in the air then says to his friends, "He was a mathematician - he thought before answering, his answer was totally right and totally useless" And another: :An astrologer, a chemist, and a mathematician are on a bus during their first visit to Scotland. They see a black sheep grazing alone in a pasture as they drive by. The astrologer excitedly exclaims, "Ah, this shows Scottish sheep are black!" The chemist didactically corrects him: "No, no, it just shows some Scottish sheep are black." The mathematician then says, "Actually, we can only be sure there is at least one Scottish sheep of which at least one side is black" And finally: : An experiment is being made. A physicist (or an engineer) and a mathematician are asked to boil hot water, but the kettle is in the living room. The physicist goes to the living room, takes the kettle, returns to the kitchen and puts it on the stove and boils the water. The mathematician does the same. In the second stage, the kettle is in the kitchen and the two are again asked to boil hot water. The physicist simply puts the kettle on the stove and boils the water. However, the mathematician takes the kettle, puts it in the living room and declares: "We have already solved this problem!"

Links and references

References

- A Mathematician's Apology, by G. H. Hardy. Memoir, with foreword by C. P. Snow.
- Reprint edition, Cambridge University Press, 1992; ISBN 0521427061
- First edition, 1940
- Dunham, William. The Mathematical Universe. John Wiley 1994.

External links

- [http://www-history.mcs.st-and.ac.uk/history/index0.html The MacTutor History of Mathematics archive], a very complete list of detailed biographies.
- [http://genealogy.math.ndsu.nodak.edu/ The Mathematics Genealogy Project], which allows to follow the succession of thesis advisors for most mathematicians, living or dead. Category:Mathematical science occupations
- ja:数学者 ko:수학자 th:นักคณิตศาสตร์ __NOTOC__

Al-Khwarizmi

right Al-Khwarizmi was a Persian scientist, mathematician, astronomer/astrologer, and author born around 800 and died around 840. The word Algebra is derived from the title of one of his books Al-Jabr wa-al-Muqabilah and consequently some have considered him the father of Algebra although the subject was in existence long before his time.

Introduction

Khwarizmi was born in the town of Khwarizm (now Khiva), in Khorasan province of Persia (now in Uzbekistan). Some historians argue though that he was born in Qutrubulli, a small town near Baghdad as mentioned in the works of al-Tabari. He accomplished most of his work in the period between 813 and 833. Mathematical historian Gandz gives this opinion of Khwarizmi's algebra: :"Khwarizmi's algebra is regarded as the foundation and cornerstone of the sciences. In a sense, Khwarizmi is more entitled to be called "the father of algebra" than Diophantus because Khwarizmi is the first to teach algebra in an elementary form and for its own sake, Diophantus is primarily concerned with the theory of numbers." (1) and Mohammad Khan, says: :"In the foremost rank of mathematicians of all time stands Khwarizmi. He composed the oldest works on arithmetic and algebra. They were the principal source of mathematical knowledge for centuries to come in the East and the West. The work on arithmetic first introduced the Hindu numbers to Europe, as the very name algorism signifies; and the work on algebra ... gave the name to this important branch of mathematics in the European world..."(2)

Contributions

He made major contributions to the fields of algebra, trigonometry, astronomy/astrology, geography and cartography by translating important works from Sanskrit and other languages. His systematic and logical approach to solving linear and quadratic equations gave shape to the discipline of algebra, a word that is derived from the name of his 830 book on the subject, al-Kitab al-mukhtasar fi hisab al-jabr wa'l-muqabala (الكتاب المختصر في حساب الجبر والمقابلة) or: "The Compendious Book on Calculation by Completion and Balancing". The book was first translated into Latin in the 12th century, from which the title and term Algebra derives. His book On the Calculation with Hindu Numerals written about 825, was principally responsible for the diffusion of the Indian system of numeration in the Middle-East and then Europe. The book was translated into Latin in the 12th century as Algoritmi de numero Indorum. From the name of the author, rendered in Latin as algoritmi, originated the term algorithm. Much of his contributions were based on the original research of the Hindus in Astronomy and Greek, and other sources. He appropriated the place-marker symbol of zero, which originated in India. Al-Khwarizmi systematized and corrected Ptolemy's data in geography as regards to Africa and the Middle east. Another major book was his Kitab surat al-ard ("The Image of the Earth"; translated as Geography), which presented the coordinates of localities in the known world based, ultimately, on those in the Geography of Ptolemy but with improved values for the length of the Mediterranean Sea and the location of cities in Asia and Africa. He also assisted in the construction of a world map for the caliph al-Ma'mun and participated in a project to determine the circumference of the Earth, supervising the work of 70 geographers to create the map of the then "known world".(3) When his work became known in Europe through Latin translations, it made a significant contribution to the advancement of mathematics in Europe. He also wrote on mechanical devices like the clock, astrolabe, and sundial. His other contributions include tables of trigonometric functions, refinements in the geometric representation of conic sections, and aspects of the calculus of two errors.

Alternate spellings of name

Abu Abdullah Muhammad bin Musa al-Khwarizmi (Arabic and Persian: ابو عبدالله محمد ابن موسى الخوارزمي) also spelled Muhammad ibn-Musa al-Khwarizmi, Muhammad ibn-Musa al-Khowarizmi, Mohammad Bin Musa Al-Khawarizmi, and Abu Jaʿfar Muhammad ibn-Musa Al-Khowarizmi

Famous works

- Al-Jabr wa-al-Muqabilah from whose title came the name "Algebra"
- Kitab al-Jam'a wal-Tafreeq bil Hisab al-Hindi (on Arithmetic, which survived in a Latin translation but was lost in the original Arabic)
- Kitab Surat-al-Ard (on geography)
- Istikhraj Tarikh al-Yahud (about the Jewish calendar)
- Kitab al-Tarikh (literally, the book of history)
- Kitab al-Rukhmat (about sun-dials)

References

(1): S Gandz, The sources of al-Khwarizmi's algebra, Osiris, i (1936), 263-77. (2): A A al'Daffa, The Muslim contribution to mathematics (London, 1978). (3): From his biography in Encyclopædia Britannica.

Other sources to use

Books: #Biography in Dictionary of Scientific Biography (New York 1970-1990). #J N Crossley, The emergence of number (Singapore, 1980). #A F Faizullaev, The scientific heritage of Muhammad al-Khwarizmi (Russian) (Tashkent, 1983). #S Gandz (ed.), The geometry of al-Khwarizmi (Berlin, 1932). #E Grant (ed.), A source book in medieval science (Cambridge, 1974). #O Neugebauer, The exact sciences in Antiquity (New York, 1969). #R Rashed, The development of Arabic mathematics : between arithmetic and algebra (London, 1994). #R Rashed, Entre arithmétique et algèbre: Recherches sur l'histoire des mathématiques arabes (Paris, 1984). #F Rosen (trs.), Muhammad ibn Musa Al-Khwarizmi : Algebra (London, 1831). Articles: #K F Abdulla-Zade, al-Khwarizmi and the Baghdad astronomers (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 178-183. #M Abdullaev, al-Khwarizmi and scientific thought in Daghestan (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 228-232. #A Abdurakhmanov, al-Khwarizmi : great mathematician (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 149-151. #M A Akhadova, The mathematics of India and al-Khwarizmi (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 238-240. #S al-Khalidi, al-Khwarizmi : scholar of astronomical and mathematical geography (Arabic), in Proceedings of the Seventh Annual Conference on the History of Arabic Science (Arabic) (Aleppo, 1986), 55-63. #A Allard, La diffusion en occident des premières oeuvres latines issues de l'arithmétique perdue d'al-Khwarizmi, J. Hist. Arabic Sci. 9 (1-2) (1991), 101-105. #P G Bulgakov, al-Biruni and al-Khwarizmi (Russian), in Mathematics and astronomy in the works of scientists of the medieval East (Tashkent, 1977), 117-122, 140. #J N Crossley and A S Henry, Thus spake al-Khwarizmi : a translation of the text of Cambridge University Library ms. Ii.vi.5, Historia Math. 17 (2) (1990), 103-131. #Y Dold-Samplonius, Developments in the solution to the equation cxÛ + bx = a from al-Khwarizmi to Fibonacci, in From deferent to equant (New York, 1987), 71-87. #R Z Du, al-Khwarizmi and his algebraic treatise (Chinese), Math. Practice Theory (1) (1987), 79-85. #K Fogel, How al-Khwarizmi became known in Germany (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 85-91. #J P Hogendijk, al-Khwarizmi's table of the "sine of the hours" and the underlying sine table, Historia Sci. 42 (1991), 1-12. #B B Hughes, Robert of Chester's Latin translation of al-Khwarizmi's 'al-Jabr', Boethius : Texts and Essays on the History of the Exact Sciences XIV (Stuttgart, 1989). #D K Ibadov, The work of al-Khwarizmi in the estimation of Eastern encyclopedic scholars of the 10th - 16th centuries (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 265-268. #W Kaunzner, Über eine frühe lateinische Bearbeitung der Algebra al-Khwarizmis in MS Lyell 52 der Bodleian Library Oxford, Arch. Hist. Exact Sci. 32 (1) (1985), 1-16. #E S Kennedy, Al-Khwarizmi on the Jewish calendar, Scripta Math. 27 (1964), 55-59. #A S Kennedy and W Ukashah, al-Khwarizmi's planetary latitude tables, Centaurus 14 (1969), 86-96. #M M Khairullaev, al-Khwarizmi and his era (Russian), Voprosy Istor. Estestvoznan. i Tekhn. (3) (1983), 121-127. #P Kunitzsch, al-Khwarizmi as a source for the 'Sententie astrolabii', in From deferent to equant (New York, 1987), 227-236. #G P Matvievskaya, The algebraic treatise of al-Khwarizmi (Russian), in On the history of medieval Eastern mathematics and astronomy (Tashkent, 1983), 3-22. #G P Matvievskaya, History of the study of the scientific work of al-Khwarizmi (Russian),, in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 72-82. #C A Nallino, Al'Khuwarizimi e il suo rifacimento della Geografia di Tolomeo, Raccolta di scritti editie inediti V (Rome, 1944), 458-532. #K H Parshall, The art of algebra from al-Khwarizmi to Viète : a study in the natural selection of ideas, Hist. of Sci. 26 (72, 2) (1988), 129-164. #M A Pathan, Al-Khwarizmi, Math. Ed. 6 (2) (1989), 92-94. #D Pingree, al-Khwarizmi in Samaria, Arch. Internat. Hist. Sci. 33 (110) (1983), 15-21. #B A Rosenfeld, 'Geometric trigonometry' in treatises of al-Khwarizmi, al-Mahani and ibn al-Haytham, in Vestigia mathematica (Amsterdam, 1993), 305-308. #B A Rozenfeld, al-Khwarizmi's spherical trigonometry (Russian), Istor.-Mat. Issled. 32-33 (1990), 325-339. #B A Rozenfeld, Number theory, geometry and astronomy in al-Khwarizmi's 'Book of Indian arithmetic' (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 66-72. #B A Rozenfeld and N D Sergeeva, The astronomical treatises of al-Khwarizmi (Russian), Istor.-Astronom. Issled. 13 (1977), 201-218. #M M Rozhanskaya, The historical-astronomical value of al-Khwarizmi's "zij" (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 158-165. #A S Sadykov, al-Khwarizmi : his era, life and work (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 8-13. #M Sani, The life and work of al-Khwarizmi, Menemui Mat. 4 (1) (1982), 1-9. #K S Siddikov, Muhammad al-Khwarizmi : creator of algebra (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 152-154. #S Kh Sirazhdinov and G P Matvievskaya, Muhammad ibn Musa al-Khwarizmi and his contribution to the history of science (Russian), Voprosy Istor. Estestvoznan. i Tekhn. (1) (1983), 108-119. #Z K Sokolovskaya, The "pretelescopic" period of the history of astronomical instruments. al-Khwarizmi in the development of precision instruments in the Near and Middle East (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 165-178. #B van Dalen, Al'Khwarizmi's astronomical tables revisited : analysis of the equation of time, in From Baghdad to Barcelona (Barcelona, 1996), 195-252. #K Vogel, Wie wurden al-Khwarizmi s mathematische Schriften in Deutschland bekannt?, Sudhoffs Arch. 68 (2) (1984), 230-234. #A I Volodarskii, al-Khwarizmi and Indian mathematics (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 232-238. #E Yu Yusupov and M M Kharullaev, The creative legacy of al-Khwarizmi and his place in the history of science (Russian), Voprosy Filos. (8) (1983), 140-146, 174. #Kh Zemanek, Manuscripts of al-Khwarizmi's works (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 115-121. #V K Zharov, Instrumental counting in al-Khwarizmi's arithmetical treatise (Russian), in The great medieval scientist al-Khwarizmi (Tashkent, 1985), 154-157.

External links

- [http://members.aol.com/bbyars1/algebra.html al'Khwarizmi & algebra]
- [http://members.tripod.com/~wzzz/KHAWARIZ.html Mohammad Bin Musa Al-Khawarizmi]
- [http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Al-Khwarizmi.html Abu Ja'far Muhammad ibn Musa Al-Khwarizmi] in the MacTutor archive Khwarizmi Khwarizmi Khwarizmi Khwarizmi Kkwarizmi Kkwarizmi ko:알 콰리즈미 ms:Abu Abdullah Mohammad Ibn Musa al-Khawarizmi ja:フワーリズミー simple:Al-Khwarizmi th:อัลคอวาริซมีย์

Heuristic (computer science)

In computer science, besides the common use as "rule of thumb" (see heuristic), the term heuristic has two well-defined technical meanings.

Heuristic algorithms

Two fundamental goals in computer science are finding algorithms with provably good run times and with provably good or optimal solution quality. A heuristic is an algorithm that gives up one or both of these goals; for example, it usually finds pretty good solutions, but there is no proof the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will always be the case. Often, one can find specially crafted problem instances where the heuristic will in fact produce very bad results or run very slowly; however, these instances might never occur in practice because of their special structure. Therefore, the use of heuristics is very common in real world implementations.

Heuristics in shortest-path problems

For shortest path problems, the term has a different meaning. Here, a heuristic is a function,

h(n)

defined on the nodes of a search tree, which serves as an estimate of the cost of the cheapest path from that node to the goal node. Heuristics are used by informed search algorithms such as Greedy best-first search and A
- to choose the best node to explore. Greedy best-first search will choose the node that has the lowest value for the heuristic function. A
- will expand nodes that have the lowest value for

g(n)+h(n)

, where

g(n)

is the (exact) cost of the path from the initial state to the current node. If

h(n)

is admissible—that is, if

h(n)

never overestimates the costs of reaching the goal—, then A
- will always find an optimal solution. The classical problem involving heuristics is the n-puzzle. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible.

Effect of heuristics on computational performance

In any searching problem where there are

b

choices at each node and a depth of

d

at the goal node, a naive searching algorithm would have to potentially search around

b^d

nodes before finding a solution. Heuristics improve the efficiency of search algorithms by reducing the branching factor from

b

to a lower constant

b'

, using a cutoff mechanism. The branching factor can be used for defining a partial order on the heuristics, such that

h_1(n) < h_2(n)

h_1(n)

has a lower branch factor than

h_2(n)

for a given node

n

of the search tree. Heuristics giving lower branching factors at every node in the search tree are preferred for the resolution of a particular problem, as they are more computationally efficient.

Finding heuristics

The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively researched in the artificial intelligence community. Several common techniques are used:
- Solution costs of sub-problems often serve as useful estimates of the overall solution cost. These are always admissible. For example, a heuristic for a 10-puzzle might be the cost of moving tiles 1-5 into their correct places. A common idea is to use a pattern database that stores the exact solution cost of every subproblem instance.
- The solution of a relaxed problem often serves as a useful admissible estimate of the original. For example, manhattan distance is a relaxed version of the n-puzzle problem, because we assume we can move each tile to its position in a single step.
- Given a set of admissible heuristic functions

h_1(n), h_2(n), ..., h_i(n)

, the function

h(n) = \max\

is an admissible heuristic that dominates all of them. Using these techniques a program called ABSOLVER was written (1993) by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube.

Recipe

:This article discusses culinary recipes. For a discussion of the semiconductor IC recipes used by the semiconductor fabs, see, for example, integrated circuit. integrated circuit A recipe is a set of instructions that show how to prepare or make something, especially a culinary dish. Modern culinary recipes normally consist of several components:
- The name (and often the locale or provenance) of the dish,
- How much time it will take to prepare the dish
- The required ingredients along with their quantity
- Equipment and environment needed to prepare the dish
- An ordered list of detailed preparation procedures (called Method).
- The number of servings that the dish will give.
- A rough estimate of the number of calories or joules contained per serving.
- A note on how long the dish will keep and its suitability for freezing. In the early history of recipes, many of these components were omitted or reduced to a note that required oral instruction, some of which may only have the name and the ingredients of a dish. Recipe writers sometimes also list variations of the traditional dish.

What else might be included

- Special handling requirements (how are eggs or butter stored? At what temperature should they be when cooking starts?)
- Garnishing or serving advice (add a sprig of parsley for color).

Additional facts often included in recipes

Recipe writers often add additional facts about the recipe, and, depending upon who you are, they are considered redundant or essential. Such facts may include the history of the dish, nutritional information, dietary information, philosophical ramblings about the soul-enriching or health-benefiting properties of the dish, or what wonderful hostess in what particular town first served the dish to the author. Nutritional information normally includes food energy, vitamin content, fat content, etc.

Where are recipes to be found

People have written recipes as recipe cards, recipe books, recipes worked into needlepoint, and computer recipe databases, among others. Take notes when making your favorite dish and share your recipe in the list of recipes or Wikibooks cookbook. The composer Leonard Bernstein set four recipes to music in his set of songs, La Bonne Cuisine (1947).

Etymology

It originated as the Latin word recipe = "take back" (imperative), i.e. an instruction to take the items listed out of the storage where they had been stored earlier.

External links

- [http://www.recipenetwork.co.uk Recipe Network] A user submited recipe database, UK based.
- [http://www.vigder.com Recipe Exchange] A community built Recipe site. New recipes sumbitted every day with a searchable database.
- [http://www.cookbookwiki.com CookbookWiki.com] A community built Recipe Wiki. Over 20,000 recipes.
- [http://www.leftoverchef.com LeftoverChef.com] Leftover Recipes for Leftover Turkey, Leftover Chicken
- [http://www.potato-recipe.com Potato Recipe Collection] Lots of recipes, Learn cooking using potatoes
- [http://www.recipepizza.com Pizza Recipes] including doughs, sauces and toppings
- [http://www.chabad.org/library/article.asp?AID=93784 Kosher recipes] chabad.org
- [http://www.homebasics.ca/recipes.asp Homebasics Recipes] A Canadian source of fresh and delicious food ideas, recipes and menus. 1000's of free printable recipes.
- [http://www.foodgeeks.com/ Foodgeeks.com] A recipe website with over 7,000 recipes.
- [http://www.stratsplace.com/rogov/art_writing_recipes.html The Art of Writing Workable Recipes] is a history of recipe writing, an analysis of contemporary recipe styles, and a treatise on what constitutes a well-written recipe.
- [http://www.elook.org/recipes/ eLook Recipes] Over 48,000 recipes.
- [http://mythunderbay.ezthemes.com/recipes/index.php Free Recipe Archive]1000's of free access Recipes
- [http://www.foodnetwork.com/food/recipes Food Network Recipes]
- [http://www.bbc.co.uk/food/recipes/ BBC Food Recipes]
- [http://www.recipesbycathy.com Recipes by Cathy] specializes in healthy but delicious cooking.
- [http://www.cellartastings.com/en/food-spanish-recipes.html Spanish Recipes]
- [http://www.realcajunrecipes.com/ RealCajunRecipes.com features more than 800 recipes from Cajun Country. Photos included.]
- [http://welovefreebies.com/folders/Free_Recipes_and_CookBooks/ Free Recipes and Cookbooks] Directory of free recipes and cookbooks
- [http://www.sudairy.com/mer/ Middle Eastern Recipes] A collection of over 600 at Sudairy.com
- [http://www.turkishcookbook.com Binnur's Turkish Cookbook] Delicious, healthy and easy-to-make Turkish recipes.
- [http://www.yummycrockpotrecipes.com Crock Pot Recipes]
- [http://www.healthy-quick-meals.com Easy and Healthy Recipes]
- [http://recipes.electrictoolbox.com Recipe Database]
- [http://www.recipezaar.com Recipezaar - The World's Largest Cookbook]
- [http://www.recipesource.com Recipe Source] lots of recipes, anyone can submit their own
- [http://www.e-gourmet-recipes.com Gourmet Recipes] Free Gourmet Recipes
- [http://www.findmearecipe.com Find me a Recipe] Searchable database of over 100,000 recipes Category:Cooking ja:レシピ

Software patent debate

:For general information on software patents, see the main article. There is heated debate as to whether and to what extent it should be possible to patent software and computer-implemented inventions as a matter of public policy. A particularly active focus of the debate in recent times has been the proposed European Union directive on the patentability of computer-implemented inventions, also known as the "CII Directive" or the "Software Patent Directive," which was ultimately rejected by the EU Parliament in July 2005.
Economic overview
Some of the main economic consequences in general to be expected from patentability are summarised in the following table, taken from Hall (2003) [http://emlab.berkeley.edu/users/bhhall/papers/BHH%20on%20BMP%20May03WP.pdf]: The relative economic significance of each of these effects varies strongly from one industry to another. Supporters of software patentability generally believe the positives decisively outweigh the negatives. Skeptics argue that the particular nature of software and the software industry exacerbate the likely costs of patentability, while making the expected benefits less real or less important than in other industries.
Arguments for patentability
Arguments commonly given in defense of software patents or in defense of the patentability of computer-implemented inventions (which could be defined differently) include:
- Patenting software inventions promotes investment in research and development.
- Many panelists in a recent US Federal Trade commision study expressed the opinion that patent monopolies in the software industry diverted money away from R&D and into defensive patent activity.
- If we did not have software patents we would not have technologies like CDs, mobile phones and ABS brakes.
- Software "as such" is not patentable in Europe but these technologies are certainly available.
- Software can be patented in Europe provided that it produces a "technical effect". A technical effect might be the improved operability of a cell phone. See patents by [http://www.interdigital.com InterDigital] for examples. (e.g. [http://www.freepatentsonline.com/EP1303928.html "ADAPTIVE UPLINK/DOWNLINK TIMESLOT ASSIGNMENT IN A HYBRID WIRELESS TIME DIVISION MULTIPLE ACCESS/CODE DIVISION MULTIPLE ACCESS COMMUNICATION SYSTEM"]) These patents are licensed worldwide, including to European companies (e.g. [http://phx.corporate-ir.net/phoenix.zhtml?c=116582&p=irol-newsArticle&ID=739068&highlight= Philips]).
- The need for protection is demonstrated by the huge number of software patents filed.
- This is like saying that the need for thieves is demonstrated by the large number of locks installed.
- The huge number of software patents filed is caused by (large) software companies feeling that they need to protect themselves against the threat of competitors using patents as weapons against them.
- Software patents incentive schemes motivate employees to produce patentable ideas.
- As opposed to building useful software systems that would directly benefit the company.
- The United States has led in creating companies, creating jobs, because it has had the best intellectual-property system.
- The U.S. became dominant in software before software was patentable in the U.S. It is now losing that lead.
- The U.S. patent system has caused serious harm to small companies in the U.S. and has allowed emergence of litigation-only companies that attempt to extract patent revenue without producing any real value.
- Litigation companies help small companies by providing deep pockets in case a small company's patents are infringed. The litigation company will fund the legal expenses of a lawsuit (typically 2 to 10 million US dollars) so that a small company can afford to bring a patent infringement lawsuit against a big company that is infringing their patents. In exchange, the litigation company receives a substantial fraction of the settlement.
- Litigation companies also provide a means for investors in small companies to recover some of their investment should the small company go out of business. The litigation company will buy the patents and investors will recover at least some of their funds.
- Software patents can increase the valuation of small companies.
- Certainly, and a lawsuit for unintentional software patent infringement can destroy small companies. The question is which of the two is most likely and how important small companies are, compared to big ones, for the competition in the free market.
- A patent must publicly disclose the invention and so educate other inventors.
- The very obscure language makes "published" patents extremely difficult to search and review, even by patent professionals.
- This disclosure does not have its intended effect for software, because source code is not required to be disclosed.
- Software invention requires considerable investment that should be protected.
- Copyright adequately protects that investment. The risk of unforseeable patent infringement strongly discourages investment.
- International law provides that any invention can be protected by patents (see software patents under TRIPs Agreement).
- It is unclear whether software is an invention for the purposes of TRIPs, and copyright law may offer more appropriate protection than patent law.
- It is inventions that should be encouraged and patentable. The distinction between hardware and software is academic.
- Software patent monopolies clearly do not add net economic value to society. Patents may add value for other fields of endeavour such as pharmaceuticals.
- The distinction between hardware and software is essential, because for software there is no concept of manufacturing. For hardware, manufacturing cost amounts for majority of cost. This is not the case for software, where R&D costs dominate.
- Organizations have the right to protect their intellectual property.
- This statement contains an unstated premise that software is something which is subject to intellectual property law. The software patent debate is about this very issue.
- The claims in a patent application clearly define the protection being sought by way of a patent.
- Claims often do not clearly define the scope of an invention; generalised claims are not valid because they do not precisely describe the invention or how it works.
-
- Claims are examined by patent examiners to determine if an inventor is entitled to the breadth of protection they ask for. In the business method area, almost all claims are initially rejected. Inventors then typically amend their claims to reduce the scope of coverage. Nonetheless, only about 5 to 10% of the current business method patent applications issue as a patent with any claims at all.
-
- If members of the public feel that an examiner has allowed an overly general claim in a patent, they may file an interpartes examination in the U.S., a lawsuit in US Federal Court, or an opposition proceeding in Europe or Japan to argue that claims are overly broad and should not be allowed.
-
- Approximately 5% of all patents that issue from the European patent office are challenged by one or more members of the public in an opposition proceeding. About half of the claims that are opposed are found to be overly broad and are either rejected or reduced in scope. Opposition proceedings can take 2 to 5 years to complete.
-
- Almost no patents in the US are challenged in an interpartes reexamination since it weakens an infringer's ability to defend themselves if they fail in the interpartes reexamination and are then sued for patent infringement.
-
- [http://www.bakosenterprises.com/IP/IPB.html The Patent Act of 2005 (H.R.2795)] has been introduced into the US Congress by Representative Lamar Smith (R - TX) to reform the US patent system. Among other reforms, this act would introduce a full patent opposition system into the US similar to the European system. If the bill passes in its current form, members of the public will have much greater capability to challenge patents that they feel are invalid.
Arguments against patentability
Opponents of software patents argue that:
- Traditional copyright has provided sufficient protection to facilitate massive investment in software development.
- Copyright can be easily circumvented by reimplementing code because it does not place restrictions on the underlying ideas. "[P]rotection conferred by copyright alone is considered too risky. This attitude can easily be understood when considering the huge investments made in order to develop these programs."
- Ideas should not be patentable, so patents should not place restrictions on ideas.
- Competition is beneficial to society. Reimplementation of ideas in better ways should be encouraged.
- Independent economic studies argue that patents are not productive (see software patents).
- These studies are generally written by economists that may not understand patents or copyrights.
- Economists typically take a wider view than patent attorneys, whose perspective tends to reflect primarily only the implications for their (patent-seeking) clients.
- Software is fundamentally about actually building and marketing systems rather than "inventing" individual cute ideas.
- The whole is the sum of the parts. Making restrictive divisions on individual ideas would inhibit colloboration and cooperation to combine the ideas into a greater one.
- A vast number of trivial software patents have been granted by government patent offices that directly profit by granting them.
- Public servants are generally honorable and not self serving.
- Politicians are generally honorless and self serving.
- They still seem to award patents for applications that are either obvious, have existing prior art, or have over-general claims.
- Most patented inventions have been or could easily be independently invented due to their trivial "inventive step".
- If this was true then they would have already been invented (and patented) by someone else.
- And they have. Such patents are still awarded. Many software patents awarded in the U.S. are overlapping with each other without being found in prior-art searches.
- Developers cannot avoid patents of standards and interfaces even though the invention may not be useful otherwise.
- Being used in a standard demonstrates the high value of a patent.
- More likely, it demonstrates that the patent-holder has managed to keep knowledge of the patent from the standardization organization until it is too late to change the standard. Standardization organizations usually do not allow patented technology in standards.
- Legal actions involving nebulous intellectual property issues are very expensive, slow and unpredictable.
- They can be avoided by paying royalties that are properly due to patent holders.
- It is not reasonable to expose small companies to the risk of being required to pay such royalties for independent software development without clear mechanism to avoiding the risk.
- It is impossible to tell whether claims of patent infringement are valid due to their obscure language and weak examination.
- Patent attorneys are experts at determining these issues.
- Then why doesn't anybody seem to know a good way of avoiding any risk of patent infringement
- before
- the risk realises?
- Enterprises that receive numerous dubious patent infringement notices cannot afford to simply pay what each patent holder demands.
- If an enterprise uses a large amount of other people's intellectual property they should expect to pay high fees.
- No enterprise wants to misuse rights of others. However, it is not possible to avoid patented technology, because no mechanism for avoiding patent-related risk exists.
- Software patents introduce substantial business risk that discourages investment.
- This risk is avoided if companies commission professional patent searches of the publicly available databases.
- This does not actually avoid the risk, because nobody can predict whether some other company has a patent application covering the software, which is not currently available in patent databases, or whether somebody will successfully patent that software in future.
- Having to search those databases and match your product with badly written and obscured patent language of huge number of patents is time-consuming, costly and does not provide adequate level of certainty.
- Software patents are likely to destroy open source and small to medium software enterprises (SMEs) that do not have a large defensive patent portfolio.
- If SMEs are not as inventive as large corporations then society would benefit from their removal.
- The number of patents filed is not a measure of inventiveness.
- The value to society should not be measured by inventiveness.
- The costs of software distribution are minimal compared to the cost of manufacture of physical goods. Therefore, methods of protection intended for protecting availability of physical goods are not applicable to software, because no manufacturing is necessary for software to become widely available. Thus, patents should not apply to software.
- Software invention requires considerable investment that should be protected.
- Certainly, but, this investment is not adequately protected by patents, which only protects manufacturing. Patents are only relevant for R&D if you assume that manufacturing is the primary contributor for overall cost (and therefore should be primary source of revenue, so R&D would by default not be the target of investment). For software industry, this assumption is not true, since majority of revenue does not come from manufacturing.
- Granting a monopoly on an idea when this is not offset by sufficiently balanced disclosure of an associated method of manufacture of material goods will harm society, because it will prevent use of the idea without the corresponding benefit to society that would justify it.
- Ideas are not patentable, inventions are. For a software or computer-implemented inventions to be patented, it needs to be disclosed in a manner sufficient clear and complete for the man skilled in the art to reduce it to practice.
- Since all software are just descriptions of ideas, it is not clear which software can be inventions and which cannot. All software can be reduced to practice trivially by running it in a computer, but it does not seem reasonable to hold all software as patentable due to this fact.
- Source code for software is the preferred form for making modifications to the software, so it would seem that "sufficiently clear" should mean "source code for the invention is disclosed".
- Trivial pieces of software would be subject to numerous claims of patent infringement. It would be impossible to write any software that would not infringe a patent.
- Trivial pieces of software by definition are obvious or do not involve an inventive step and so are not patentable.
- However, since it is not clear where is the line between obvious and non-obvious, it is not possible to know this beforehand. Is, say, the Linux kernel obvious by this standard? The Linux kernel is a relatively small piece of code.
- It is impossible to determine beforehand whether a particular piece of software or particular kind of design of software infringes patents. Thus, patent-related risk cannot be eliminated by software developers by any means.
- Patents are available through free databases. Patent search experts can help.
- If it seems easy, please perform this determination for the Debian Linux distribution and explain the method by which you did it.
- Patent search databases do not seem to help at all with this task, because even identifying the parts that are in theory patentable seems like a very difficult task.
- Software is a field of mathematics. Software is a mathematical algorithm, a fancy mathematical equation, a calculation. Mathematical algorithms, equations, and calculations are not inventions any more than a number can be an invention.
- Some software or computer-implemented inventions are concrete and have a technical character and are not merely mathematical methods. They should be patentable. This requirement is not met by pure mathematical methods.
- All software is by definition a description of a mathematical method (that is, an algorithm or a way of structuring those algorithms.). If it does not try to get a monopoly on a mathematical method, then it is not a software patent.
- Pure mathematical algorithms are not patentable in the United States (State Street v. Signature Financial Group, Inc., 47 USPQ2d 1596, 1601-02 [Fed. Cir. 1998]) or any other country in the world.
- It is clearly not reasonable to require software developers to hire attorneys just to determine whether there is a risk of patent infringement.
- All developers of new technology in the engineering arts, manufacturing arts, pharmaceutical arts, electronics arts, chemical arts, and biological arts hire attorneys to mitigate the risk that they infringe on someone else's patents.
- In all of those cases, the processes patented require expensive equipment to develop and reproduce. In the case of software, a kid at home on a cheap PC can write an application, and distribute it to millions via the Internet. Is that kid supposed to hire attorneys to mitigate the risk that he or she might infringe on someone's patents?
- There are a large number of patents outside of the field of software that cover inventions that are inexpensive to develop and easy to copy. The Starbucks© cardboard insulating sleeve for their coffee cups is one example. This invention is covered by [http://www.freepatentsonline.com/5205473.html US patent 5,205473].
- Someone who infringes the Starbucks patent by making millions of copies of the sleeve and giving them away for free is liable for the lost profits or a reasonable royalty of the patent owner. [http://www.uspto.gov/web/offices/pac/mpep/consolidated_laws.pdf (See 35 USC 384)]. If they do it on purpose, the damages could be trebled.
- Software does pose a special problem because the cost of distribution of millions of copies is well within the means of an ordinary individual (e.g. a kid on a cheap PC). It would be difficult to justify suing an individual for patent infringement since it is unlikely that the individual has enough assets to compensate the inventor(s) for their damages or cover their legal costs. Lawsuits are rarely brought for total damages that are less than $3,000,000 since the legal fees can easily run $2,000,000 or more.
- Patent examination (US) is too slow. As of June 2005, the average [http://patft.uspto.gov/netahtml/search-adv.htm delay] between when a patent application is filed and when it is examined is over three years. By the time patent applications issue as patents, the inventions claimed therein are already in the public domain. This hurts inventors who see their inventions copied without permission, investors who fail to earn a suitable return on the salaries they paid to inventors and the public, which is faced with the uncertain prospects as to exactly what inventions are in the public domain and which inventions will be covered by a pending patent application.
Quotes supporting patentability

Bill Gates (Microsoft) 2005
"...There are some new modern-day sort of communists who want to get rid of the incentive for musicians and moviemakers and software makers under various guises. They don't think that those incentives should exist... I'd be the first to say that the patent system can always be tuned...the United States has led...because we've had the best intellectual-property system."
Harald Hagedorn (SAP Patent Department) 2002
"...software is a multi-billion dollar industry with expected growth-rates of 10% p.a. during the next years ... like in any other industry such growth can only be sustained if patents are available."
Quotes against patentability

Bill Gates (Microsoft) 1991
Internal memo "If people had understood how patents would be granted when most of today's ideas were invented and had taken out patents, the industry would be at a complete standstill today...The solution is patenting as much as we can. A future startup with no patents of its own will be forced to pay whatever price the giants choose to impose. That price might be high. Established companies have an interest in excluding future competitors."

Oracle Corporation 1994

Submission to USPTO "Oracle Corporation opposes the patentability of software. The Company believes that existing copyright law and available trade secret protections, as opposed to patent law, are better suited to protecting computer software developments..."
Prof. Hasso Plattner when Chair of SAP Board
"...SAP would not need patents to protect its investments and is collecting them only as a defensive weapon to prepare for litigation in the U.S..."
Pierre Haren, board director of ILOG 2001
"...The American experience of software patents is a disaster. Before imitating them we should rather try to see if they won't agree to change their system..."
Robert Barr (Cisco Systems Intellectual Property Department) 2002
"...The time and money we spend on patent filings, prosecution, and maintenance, litigation and licensing could be better spent on product development and research leading to more innovation..."
Douglas Brotz (Adobe Systems) 1994
"...I believe that software per se should not be allowed patent protection..."
Jim Warren (Autodesk) 1994
"...There is absolutely no evidence, whatsoever—not a single iota—that software patents have promoted or will promote progress..."
Mitch Kapor 1994 (Founder of Lotus 123)
"Because it is impossible to know what patent applications are in the application pipeline, it is entirely possible, even likely, to develop software which incorporates features that are the subject of another firm's patent application. Thus, there is no avoiding the risk of inadvertently finding oneself being accused of a patent infringement simply because no information was publicly available at the time which could have offered guidance of what to avoid."
R. Buckminster Fuller 1939
"The patent files are glutted with relative nonsense." (Fuller, R. Buckminster, Nine Chains to the Moon, Doubleday Anchor, 1971 p 277)
Notes

- [http://www.ftc.gov/os/2003/10/innovationrpt.pdf US Federal Trade Commission 2003 patent report]
- [http://www.patents4innovation.org/ Patents4Innovation]
- [http://www.wipo.int/sme/en/e_commerce/pat_help.htm Ways in Which Patents can Help Your E-Commerce Business]
- [http://insight.zdnet.co.uk/software/windows/0,39020478,39183197,00.htm "Restricting IP rights is tantamount to communism"]
- [http://www.nosoftwarepatents.com/en/m/basics/index.html]
- IPR Helpdesk, Patentability of Computer Programs [http://www.ipr-helpdesk.org/documentos/docsPublicacion/pdf_xml/8_patentabilityComputerPrograms%5B0000001159_00%5D.pdf]
- [http://www.nosoftwarepatents.com/en/m/basics/inflation.html]
- [http://www.timesonline.co.uk/printFriendly/0,,1-5-1443489,00.html The Times 17Jan05]
- [http://swpat.ffii.org/papers/europarl0309/cons0401/tab/index.en.html FFII Directive Analysis]
- [http://www.indianembassy.org/Economy/1.htm Indian Government Reference]
- [http://swpat.ffii.org/log/04/nath12/index.en.html "Indian Government Orders Legalisation of Software Patents"]
- [http://swpat.ffii.org/penmi/2002/europarl11/index.en.html FFII - Europarl Hearings]
- [http://www.oreillynet.com/pub/a/policy/2002/08/15/lessig.html?page=2 Lawrence Lessig]
- [http://www.base.com/software-patents/statements/oracle.html]
- [http://www.industrie.gouv.fr/observat/innov/carrefour/tabsyn.htm French] (in French)
- [http://swpat.ffii.org/vreji/quotes/index.en.html FFII]
- [http://www.base.com/software-patents/kapor.html]
References

- Mark H. Webbink, A New Paradigm for Intellectual Property Rights in Software, 2005 Duke L. & Tech. Rev. 0012 (2005) [http://www.law.duke.edu/journals/dltr/articles/2005dltr0012.html]
See also

- Debates within software engineering
External links

Sites in favor of the patentability of computer-implemented inventions

- [http://www.patents4innovation.org Patents4Innovation.org], a web site to promote innovation and competition in e-Europe.
- [http://www.eicta.org EICTA web site] (see also: European Information, Communications and Consumer Electronics Technology Industry Associations or EICTA)
- [http://www.spectrum.ieee.org/WEBONLY/publicfeature/jun04/0604aca.html Article] from IEEE on the business model of Acacia Technologies Group.
- [http://www.iusmentis.com/patents/software/epc/ iusmentis.com] is a web site from a patent attorney. It contains a good explanation of how patents work.
- [http://www.ipjur.com/03.php3 ipjur.com] Patent Attorney Axel H Horns' Blog on Intellectual Property Law.
Sites against software patents

- Foundation for a Free Information Infrastructure (FFII)
- [http://webshop.ffii.org/ Webshop example] Demonstrates the extent of software patents.
- [http://swpat.ffii.org/papers/eubsa-swpat0202/index.en.html Opposition by FFII to software patent legislation in Europe]
- [http://www.ffii.org.uk/ftc/ftc.html The report from the hearings of the FTC] a summary of what was said to the FTC.
- [http://www.nosoftwarepatents.com No Software Patents - a web campaign supported by companies (1&1, Red Hat, MySQL)]
- [http://www.bitlaw.com/software-patent/history.html The History of Software Patents] from BitLaw.
- Free Software Foundation: transcript and audio of [http://www.cl.cam.ac.uk/~mgk25/stallman-patents.html Software patents – Obstacles to software development] which Richard Stallman gave about software patents (the audio archive linked contains two more speeches about software patents)
- [http://ifso.ie/ Irish Free Software Organisation (IFSO)]
- competition law bodies (BEUC)
- European SME groups (UEAPAME, CEA-PME, dmmv, DIHK, WKO, ...)
- [http://www.noepatents.org EU campaign NoEpatents (Eurolinux-alliance)] with more than 360 000 European signatures one of the largest Internet campaigns ever.
- League for Programming Freedom
- [http://www.researchoninnovation.org/patent.pdf Sequential Innovation, Patents, and Imitation] by James Bessen and Eric Maskin
- [http://perens.com/Articles/Patents.html Software Patents vs. Free Software] by Bruce Perens
- [http://www.pro-innovation.org/rapport_brevet/brevets_plan-en.pdf Report on Software Patentability by Conseil des Mines Study Group - Stimulating Innovation in the Information Society]
- [http://www.esr-pollmeier.de/swpat/index_en.html SWpat information page by ESR Pollmeier (German SME), opposed to swpat]
- AEL (Association Electronique Libre) Wiki [http://wiki.ael.be/index.php/FightingSWPatents Software Patent Main Project page]
- [http://wiki.ael.be/index.php/PatentHistory on patent history, e.g. Diamond vs. Diehr]
- [http://wiki.ael.be/index.php/BigDemo27aug Coverage of Brussels 27 aug 2003 demo, AEL, Belgium]
- [http://wiki.ael.be/index.php/PatentInformationLeafletsLinks List of local campaign sites]
- http://www.softwarepatents.co.uk/
- attac (Globalisation critics)
- W3C: [http://www.w3.org/2003/10/27-rogan.html Letter from Tim Berners-Lee to Rogan] (about Eolas Plugin Patent):
- [http://codeliberty.org Code Liberty] is a web site dedicated to the rights of software authors, and argues that patents are incompatible with the Berne Copyright Convention, and the WIPO and WTO treaties.
- [http://lists.ffii.org/mailman/listinfo/us-parl Us action against Software patents]
- [http://www.libroblanco.com Libro blanco del software libre] FOSS situation in Spain
- [http://www.advogato.org/article/7.html Steven Young's legal advice]
- [http://www.patenti.si www.patenti.si] Slovene web site dedicated clarify running SWPAT discoussion. Category:Computer law Category:Debates Category:Patent law

Software patent

Software patents and patents on computer-implemented inventions (CII) are a class of patents and one of many legal aspects of computing. There is intense debate as to what extent such patents should be granted, if any. The Free On-line Dictionary of Computing provides a general definition of a "software patent" as "a patent intended to prevent others from using some programming technique", while the European Patent Office (EPO) provides a general definition of a "computer-implemented invention": :"an expression intended to cover claims which involve computers, computer networks or other conventional programmable apparatus whereby prima facie the novel features of the claimed invention are realised by means of a program or programs" [http://www.european-patent-office.org/legal/gui_lines/e/c_iv_2_3_6.htm] or, expressed in other words, :"an invention whose implementation involves the use of a computer, computer network or other programmable apparatus, the invention having one or more features which are realised wholly or partly by means of a computer program" [http://cii.european-patent-office.org/law_practice/index.en.php].

Software patents vs copyright

Software patents are sometimes confused with software copyright. Under international agreements, such as the WTO's TRIPs Agreement, any software written is automatically covered by copyright. This regulates the direct copying of the program code. Applying for, and being granted a patent gives stronger restrictive power. It covers the programming method itself, independently of any implementation in code. Usually, reimplementing a program will avoid copyright infringement, but not patent infringement. Like all patents, software patents are enforceable regardless of whether the competitors were aware of the patent (patent applications are kept secret for at least 18 months) and the software was completely independently developed. A patent holder may prevent others from using their invention absolutely, or licence it at terms they dictate. There are strong sanctions for patent infringement, including triple damages in the USA if the infringement is considered deliberate, which means knowing of the patent but not licensing it (even under the assumption it was invalid). As laid out in TRIPS, patents are required to last 20 years after filing, provided the maintenance or renewal fees are paid.

History

The first software patent ever granted is probably a patent for a "computer having slow and quick access storage, when programmed to solve a linear programming problem by an iterative algorithm, the iterative algorithm being such that (...)" applied for in 1962 by British Petroleum Company ([http://www.cippm.org.uk/pdfs/JILT%20kretschmer%2011_03.pdf], see end of page 3). The patent relates to solving simultaneous linear equations. The USPTO has traditionally not considered software to be patentable because by statute patents can only be granted to "processes, machines, articles of manufacture, and compositions of matter". In particular patents cannot be granted to "scientific truths" or "mathematical expressions" of them. This means that most of the fundamental techniques of software engineering have never been patented. The USPTO maintained this position, that software was in effect a mathematical algorithm, and therefore not patentable into the 1980's. The position of the USPTO was challenged with a landmark 1981 Supreme Court case, Diamond v. Diehr. The case involved a device that used computer software to ensure the correct timing when heating, or curing, rubber. Although the software was the integral part of the device, it also had other functions that related to real world manipulation. The court then ruled that as a device to mold rubber, it was a patentable object. The court essentially ruled that while algorithms themselves could not be patented, devices that utilized them could. This ruling wasn't as straightforward as many would like and this forced many electronic device makers into the courts to establish their inventions were in fact patentable. [http://www.bitlaw.com/software-patent/history.html] As a result, in 1982 the U.S. Congress created a new court (the Federal Circuit) to hear patent cases. The court made patents generally easier to uphold by presuming patents were valid unless proved invalid and weakening the defence of nonobviousness. By the early 1990s the patentability of software was well established, and in 1996 the USPTO issued [http://www.bitlaw.com/source/soft_pats/final.html Final Computer Related Examination Guidelines]. See Software patents under United States patent law. In Europe, the EPO (and other national patent offices) has been issuing many software patents since the 1980s, although (or since) Article 52 of the European Patent Convention excludes "programs for computers" (Art. 52(2)) but only to the extent it relates to activies "as such" (Art. 52(3)). See Software patents under the European Patent Convention. In India, a clause to include software patents was quashed by the Indian Parliament in April 2005. The recent expansion of the internet and e-commerce has led to many patents being applied for and being granted for related software and business methods. There have been several successful enforcement trials in the USA.

Law

Jurisdictions

Substantive law regarding the patentability of software and computer-implemented inventions, and case law interpreting the legal provisions, are different under different jurisdictions. The national jurisdictions relating to software patents in Europe and in the European Union are not harmonized even though some harmonization has been brought into the national jurisdictions in the 1970s and 1980s. Interpretation of the substantive law varies to some extent from state to state. In 2002, in order to harmonize the national laws a step further, the EU Commission proposed a Directive on the patentability of computer-implemented inventions, but settling the exact terms of the Directive has proven highly controversial. In 2003, the European Parliament deeply amended the original draft from the Commission. Two years later, the Council of the European Union (i.e. national government ministers) mostly reinstated the original text, but the text was eventually rejected by the Parliament on July 6, 2005. The proposed directive will not become law. Software patents under multilateral treaties:
- Software patents under TRIPs Agreement
- Software patents under the Patent Cooperation Treaty
- Software patents under the European Patent Convention Software patents under national laws:
- Software patents under United States patent law
- Software patents under United Kingdom patent law
- Software patents under German patent law

Scope of software patentability

As noted above both the EU and the US have traditionally restricted the ability to patent software. This has led to several proposals for some very narrow definitions of what software actually is. For example:
- A piece of code not relating to "the use of controllable forces of nature to achieve predictable results".
- A piece of code relating solely to the "processing, handling and presentation of information"
- A piece of code with no "technical effect" (depending in turn on how one chooses to define "technical")
- A piece of code as an abstract listing, not actually running on a programmable device
- A piece of code with merely literary merit, rather than any identifiable functional benefits A further difficulty in drawing a clear boundary between software patents and other patents may come from the fact that a patent claim can be written so as to embrace many different implementations (some using purely mechanical or electrical means, others using software), for instance by using functional features under certain jurisdictions (for example, "means for controlling"). The expression "computer-implementable inventions" has been coined to refer to this reality. Additionally, under the so-called doctrine of equivalents and its analogues, a patent that on its face does not appear to require software can be infringed in certain circumstances if software is used as an equivalent of (that is, to substitute for) a non-software element, making even more difficult to draw the boundary.

Computer-implemented invention

The term "computer-implemented invention" was put forward by the European Commission, based on an expression used by the European Patent Office [http://www.european-patent-office.org/legal/gui_lines/e/c_iv_2_3_6.htm], and proposed as "any invention the performance of which involves the use of a computer, computer network or other programmable apparatus and having one or more prima facie novel features which are realised wholly or partly by means of a computer or computer programs." [http://europa.eu.int/comm/internal_market/en/indprop/comp/com02-92en.pdf] The term has been criticized as a politically motived obfuscation manoeuver [http://elis.ugent.be/~jmaebe/swpat/cii.html]. The German chancellor Schröder is quoted as saying "the manuscript is titled with 'software patents' - wait, I may no longer say that - well the 'protection of computer-implemented inventions'" [http://www.heise.de/tp/r4/artikel/17/17825/1.html]. The terms "software-enabled invention", "software-related invention", "software-operated invention" are also sometimes used to convey a similar meaning.

Litigation

Several successful litigations show that software patents are enforceable in the USA. For example, Eolas was awarded $565 million from Microsoft. See List of software patents for more examples. So far there does not appear to have been any case before a European Court where infringement of a software patent has been proved and damages have been awarded. However, there have been a few court ca