In set theory, a Cartesian product is a mathematical operation that returns a set from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs where a ∈ A and b ∈ B. Products can be specified using e.g.. A × B =. A table can be created by taking the Cartesian product of a set of columns. If the Cartesian product rows × columns is taken, the cells of the table contain ordered pairs of the form. More a Cartesian product of n sets known as an n-fold Cartesian product, can be represented by an array of n dimensions, where each element is an n-tuple. An ordered pair is a couple; the Cartesian product is named after René Descartes, whose formulation of analytic geometry gave rise to the concept, further generalized in terms of direct product. An illustrative example is the standard 52-card deck; the standard playing card ranks form a 13-element set. The card suits form a four-element set; the Cartesian product of these sets returns a 52-element set consisting of 52 ordered pairs, which correspond to all 52 possible playing cards.
Ranks × Suits returns a set of the form. Suits × Ranks returns a set of the form. Both sets are distinct disjoint; the main historical example is the Cartesian plane in analytic geometry. In order to represent geometrical shapes in a numerical way and extract numerical information from shapes' numerical representations, René Descartes assigned to each point in the plane a pair of real numbers, called its coordinates; such a pair's first and second components are called its x and y coordinates, respectively. The set of all such pairs is thus assigned to the set of all points in the plane. A formal definition of the Cartesian product from set-theoretical principles follows from a definition of ordered pair; the most common definition of ordered pairs, the Kuratowski definition, is =. Under this definition, is an element of P, X × Y is a subset of that set, where P represents the power set operator. Therefore, the existence of the Cartesian product of any two sets in ZFC follows from the axioms of pairing, power set, specification.
Since functions are defined as a special case of relations, relations are defined as subsets of the Cartesian product, the definition of the two-set Cartesian product is prior to most other definitions. Let A, B, C, D be sets; the Cartesian product A × B is not commutative, A × B ≠ B × A, because the ordered pairs are reversed unless at least one of the following conditions is satisfied: A is equal to B, or A or B is the empty set. For example: A =. × C ≠ A × If for example A = × A = ≠ = A ×. The Cartesian product behaves nicely with respect to intersections. × = ∩. × ≠ ∪ In fact, we have that: ∪ = ∪ ∪ [ ( B
String (computer science)
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed. A string is considered a data type and is implemented as an array data structure of bytes that stores a sequence of elements characters, using some character encoding. String may denote more general arrays or other sequence data types and structures. Depending on programming language and precise data type used, a variable declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employ dynamic allocation to allow it to hold a variable number of elements; when a string appears in source code, it is known as a string literal or an anonymous string. In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set called an alphabet. Let Σ be a non-empty finite set of symbols, called the alphabet.
No assumption is made about the nature of the symbols. A string over Σ is any finite sequence of symbols from Σ. For example, if Σ = 01011 is a string over Σ; the length of a string s can be any non-negative integer. The empty string is the unique string over Σ of length 0, is denoted ε or λ; the set of all strings over Σ of length n is denoted Σn. For example, if Σ = Σ2 =. Note that Σ0 = for any alphabet Σ; the set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σn, Σ ∗ = ⋃ n ∈ N ∪ Σ n For example, if Σ = Σ* =. Although the set Σ* itself is countably infinite, each element of Σ* is a string of finite length. A set of strings over Σ is called a formal language over Σ. For example, if Σ =, the set of strings with an number of zeros, is a formal language over Σ. Concatenation is an important binary operation on Σ*. For any two strings s and t in Σ*, their concatenation is defined as the sequence of symbols in s followed by the sequence of characters in t, is denoted st.
For example, if Σ =, s = bear, t = hug st = bearhug and ts = hugbear. String concatenation is an non-commutative operation; the empty string ε serves as the identity element. Therefore, the set Σ* and the concatenation operation form a monoid, the free monoid generated by Σ. In addition, the length function defines a monoid homomorphism from Σ* to the non-negative integers. A string s is said to be a substring or factor of t if there exist strings u and v such that t = usv; the relation "is a substring of" defines a partial order on Σ*, the least element of, the empty string. A string s is said to be a prefix of t if there exists a string u such that t = su. If u is nonempty, s is said to be a proper prefix of t. Symmetrically, a string s is said to be a suffix of t if there exists a string u such that t = us. If u is nonempty, s is said to be a proper suffix of t. Suffixes and prefixes are substrings of t. Both the relations "is a prefix of" and "is a suffix of" are prefix orders. A string s = uv.
For example, if Σ = the string 0011001 is a rotation of 0100110, where u = 00110 and v = 01. The reverse of a string is a string in reverse order. For example, if s = abc the reverse of s is cba. A string, the reverse of itself is called a palindrome, which includes the empty string and all strings of length 1, it is useful to define an ordering on a set of strings. If the alphabet Σ has a total order one can define a total order on Σ* called lexicographical order. For example, if Σ = and 0 < 1 the lexicographical order on Σ* includes the relationships ε < 0 < 00 < 000 <... < 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111... The lexicographical order is total if the alphabetical order is, but isn't well-founded for any nontrivial alphabet if the alphabetical order is. See Shortlex for an alternative string ordering that preserves well-foundedness. A number of additional operations on strings occur in the formal theory; these are given in the article on string operations.
Strings admit the following interpretation as nodes on a graph: Fixed-length strings can be viewed as nodes on a hypercube Variable-length strings can be viewed as nodes on the k-ary tree, where k is the number of symbols in Σ Infinite strings can be viewed as i
A complex number is a number that can be expressed in the form a + bi, where a and b are real numbers, i is a solution of the equation x2 = −1. Because no real number satisfies this equation, i is called an imaginary number. For the complex number a + bi, a is called the real part, b is called the imaginary part. Despite the historical nomenclature "imaginary", complex numbers are regarded in the mathematical sciences as just as "real" as the real numbers, are fundamental in many aspects of the scientific description of the natural world. Complex numbers allow solutions to certain equations. For example, the equation 2 = − 9 has no real solution, since the square of a real number cannot be negative. Complex numbers provide a solution to this problem; the idea is to extend the real numbers with an indeterminate i, taken to satisfy the relation i2 = −1, so that solutions to equations like the preceding one can be found. In this case the solutions are −1 + 3i and −1 − 3i, as can be verified using the fact that i2 = −1: 2 = 2 = = 9 = − 9, 2 = 2 = 2 = 9 = − 9.
According to the fundamental theorem of algebra, all polynomial equations with real or complex coefficients in a single variable have a solution in complex numbers. In contrast, some polynomial equations with real coefficients have no solution in real numbers; the 16th century Italian mathematician Gerolamo Cardano is credited with introducing complex numbers in his attempts to find solutions to cubic equations. Formally, the complex number system can be defined as the algebraic extension of the ordinary real numbers by an imaginary number i; this means that complex numbers can be added and multiplied, as polynomials in the variable i, with the rule i2 = −1 imposed. Furthermore, complex numbers can be divided by nonzero complex numbers. Overall, the complex number system is a field. Geometrically, complex numbers extend the concept of the one-dimensional number line to the two-dimensional complex plane by using the horizontal axis for the real part and the vertical axis for the imaginary part.
The complex number a + bi can be identified with the point in the complex plane. A complex number whose real part is zero is said to be purely imaginary. A complex number whose imaginary part is zero can be viewed as a real number. Complex numbers can be represented in polar form, which associates each complex number with its distance from the origin and with a particular angle known as the argument of this complex number; the geometric identification of the complex numbers with the complex plane, a Euclidean plane, makes their structure as a real 2-dimensional vector space evident. Real and imaginary parts of a complex number may be taken as components of a vector with respect to the canonical standard basis; the addition of complex numbers is thus depicted as the usual component-wise addition of vectors. However, the complex numbers allow for a richer algebraic structure, comprising additional operations, that are not available in a vector space. Based on the concept of real numbers, a complex number is a number of the form a + bi, where a and b are real numbers and i is an indeterminate satisfying i2 = −1.
For example, 2 + 3i is a complex number. This way, a complex number is defined as a polynomial with real coefficients in the single indeterminate i, for which the relation i2 + 1 = 0 is imposed. Based on this definition, complex numbers can be added and multiplied, using the addition and multiplication for polynomials; the relation i2 + 1 = 0 induces the equalities i4k = 1, i4k+1 = i, i4k+2 = −1, i4k+3 = −i, which hold for all integers k. The real number a is called the real part of the complex number a + bi. To emphasize, the imaginary part does not include a factor i and b, not bi, is the imaginary part. Formally, the complex numbers are defined as the quotient ring of the polynomia
In mathematics and digital electronics, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: "0" and "1". The base-2 numeral system is a positional notation with a radix of 2; each digit is referred to as a bit. Because of its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used by all modern computers and computer-based devices; the modern binary number system was studied in Europe in the 16th and 17th centuries by Thomas Harriot, Juan Caramuel y Lobkowitz, Gottfried Leibniz. However, systems related to binary numbers have appeared earlier in multiple cultures including ancient Egypt and India. Leibniz was inspired by the Chinese I Ching; the scribes of ancient Egypt used two different systems for their fractions, Egyptian fractions and Horus-Eye fractions. Horus-Eye fractions are a binary numbering system for fractional quantities of grain, liquids, or other measures, in which a fraction of a hekat is expressed as a sum of the binary fractions 1/2, 1/4, 1/8, 1/16, 1/32, 1/64.
Early forms of this system can be found in documents from the Fifth Dynasty of Egypt 2400 BC, its developed hieroglyphic form dates to the Nineteenth Dynasty of Egypt 1200 BC. The method used for ancient Egyptian multiplication is closely related to binary numbers. In this method, multiplying one number by a second is performed by a sequence of steps in which a value is either doubled or has the first number added back into it; this method can be seen in use, for instance, in the Rhind Mathematical Papyrus, which dates to around 1650 BC. The I Ching dates from the 9th century BC in China; the binary notation in the I Ching is used to interpret its quaternary divination technique. It is based on taoistic duality of yin and yang.eight trigrams and a set of 64 hexagrams, analogous to the three-bit and six-bit binary numerals, were in use at least as early as the Zhou Dynasty of ancient China. The Song Dynasty scholar Shao Yong rearranged the hexagrams in a format that resembles modern binary numbers, although he did not intend his arrangement to be used mathematically.
Viewing the least significant bit on top of single hexagrams in Shao Yong's square and reading along rows either from bottom right to top left with solid lines as 0 and broken lines as 1 or from top left to bottom right with solid lines as 1 and broken lines as 0 hexagrams can be interpreted as sequence from 0 to 63. The Indian scholar Pingala developed a binary system for describing prosody, he used binary numbers in the form of long syllables, making it similar to Morse code. Pingala's Hindu classic titled Chandaḥśāstra describes the formation of a matrix in order to give a unique value to each meter; the binary representations in Pingala's system increases towards the right, not to the left like in the binary numbers of the modern, Western positional notation. The residents of the island of Mangareva in French Polynesia were using a hybrid binary-decimal system before 1450. Slit drums with binary tones are used to encode messages across Asia. Sets of binary combinations similar to the I Ching have been used in traditional African divination systems such as Ifá as well as in medieval Western geomancy.
In the late 13th century Ramon Llull had the ambition to account for all wisdom in every branch of human knowledge of the time. For that purpose he developed a general method or ‘Ars generalis’ based on binary combinations of a number of simple basic principles or categories, for which he has been considered a predecessor of computing science and artificial intelligence. In 1605 Francis Bacon discussed a system whereby letters of the alphabet could be reduced to sequences of binary digits, which could be encoded as scarcely visible variations in the font in any random text. For the general theory of binary encoding, he added that this method could be used with any objects at all: "provided those objects be capable of a twofold difference only. John Napier in 1617 described a system he called location arithmetic for doing binary calculations using a non-positional representation by letters. Thomas Harriot investigated several positional numbering systems, including binary, but did not publish his results.
The first publication of the system in Europe was by Juan Caramuel y Lobkowitz, in 1700. Leibniz studied binary numbering in 1679. Leibniz's system uses 1, like the modern binary numeral system. An example of Leibniz's binary numeral system is as follows: 0 0 0 1 numerical value 20 0 0 1 0 numerical value 21 0 1 0 0 numerical value 22 1 0 0 0 numerical value 23Leibniz interpreted the hexagrams of the I Ching as evidence of binary calculus; as a Sinophile, Leibniz was aware of
Machine code is a computer program written in machine language instructions that can be executed directly by a computer's central processing unit. Each instruction causes the CPU to perform a specific task, such as a load, a store, a jump, or an ALU operation on one or more units of data in CPU registers or memory. Machine code is a numerical language, intended to run as fast as possible, may be regarded as the lowest-level representation of a compiled or assembled computer program or as a primitive and hardware-dependent programming language. While it is possible to write programs directly in machine code, it is tedious and error prone to manage individual bits and calculate numerical addresses and constants manually. For this reason, programs are rarely written directly in machine code in modern contexts, but may be done for low level debugging, program patching, assembly language disassembly; the overwhelming majority of practical programs today are written in higher-level languages or assembly language.
The source code is translated to executable machine code by utilities such as compilers and linkers, with the important exception of interpreted programs, which are not translated into machine code. However, the interpreter itself, which may be seen as an executor or processor, performing the instructions of the source code consists of directly executable machine code. Machine code is by definition the lowest level of programming detail visible to the programmer, but internally many processors use microcode or optimise and transform machine code instructions into sequences of micro-ops, this is not considered to be a machine code per se; every processor or processor family has its own instruction set. Instructions are patterns of bits that by physical design correspond to different commands to the machine. Thus, the instruction set is specific to a class of processors using the same architecture. Successor or derivative processor designs include all the instructions of a predecessor and may add additional instructions.
A successor design will discontinue or alter the meaning of some instruction code, affecting code compatibility to some extent. Systems may differ in other details, such as memory arrangement, operating systems, or peripheral devices; because a program relies on such factors, different systems will not run the same machine code when the same type of processor is used. A processor's instruction set may have all instructions of the same length, or it may have variable-length instructions. How the patterns are organized varies with the particular architecture and also with the type of instruction. Most instructions have one or more opcode fields which specifies the basic instruction type and the actual operation and other fields that may give the type of the operand, the addressing mode, the addressing offset or index, or the actual value itself. Not all machines or individual instructions have explicit operands. An accumulator machine has a combined left operand and result in an implicit accumulator for most arithmetic instructions.
Other architectures have accumulator versions of common instructions, with the accumulator regarded as one of the general registers by longer instructions. A stack machine has all of its operands on an implicit stack. Special purpose instructions often lack explicit operands; this distinction between explicit and implicit operands is important in code generators in the register allocation and live range tracking parts. A good code optimizer can track implicit as well as explicit operands which may allow more frequent constant propagation, constant folding of registers and other code enhancements. A computer program is a list of instructions. A program's execution is done in order for the CPU, executing it to solve a specific problem and thus accomplish a specific result. While simple processors are able to execute instructions one after another, superscalar processors are capable of executing a variety of different instructions at once. Program flow may be influenced by special'jump' instructions that transfer execution to an instruction other than the numerically following one.
Conditional jumps are not depending on some condition. A much more readable rendition of machine language, called assembly language, uses mnemonic codes to refer to machine code instructions, rather than using the instructions' numeric values directly. For example, on the Zilog Z80 processor, the machine code 00000101, which causes the CPU to decrement the B processor register, would be represented in assembly language as DEC B; the MIPS architecture provides a specific example for a machine code whose instructions are always 32 bits long. The general type of instruction is given by the op field. J-type and I-type instructions are specified by op. R-type instructions include an additional field funct to determine the exact operation; the fields used in the
Computer programming is the process of designing and building an executable computer program for accomplishing a specific computing task. Programming involves tasks such as: analysis, generating algorithms, profiling algorithms' accuracy and resource consumption, the implementation of algorithms in a chosen programming language; the source code of a program is written in one or more languages that are intelligible to programmers, rather than machine code, directly executed by the central processing unit. The purpose of programming is to find a sequence of instructions that will automate the performance of a task on a computer for solving a given problem; the process of programming thus requires expertise in several different subjects, including knowledge of the application domain, specialized algorithms, formal logic. Tasks accompanying and related to programming include: testing, source code maintenance, implementation of build systems, management of derived artifacts, such as the machine code of computer programs.
These might be considered part of the programming process, but the term software development is used for this larger process with the term programming, implementation, or coding reserved for the actual writing of code. Software engineering combines engineering techniques with software development practices. Reverse engineering is the opposite process. A hacker is any skilled computer expert that uses their technical knowledge to overcome a problem, but it can mean a security hacker in common language. Programmable devices have existed at least as far back as 1206 AD, when the automata of Al-Jazari were programmable, via pegs and cams, to play various rhythms and drum patterns. However, the first computer program is dated to 1843, when mathematician Ada Lovelace published an algorithm to calculate a sequence of Bernoulli numbers, intended to be carried out by Charles Babbage's Analytical Engine. Women would continue to dominate the field of computer programming until the mid 1960s. In the 1880s Herman Hollerith invented the concept of storing data in machine-readable form.
A control panel added to his 1906 Type I Tabulator allowed it to be programmed for different jobs, by the late 1940s, unit record equipment such as the IBM 602 and IBM 604, were programmed by control panels in a similar way. However, with the concept of the stored-program computers introduced in 1949, both programs and data were stored and manipulated in the same way in computer memory. Machine code was the language of early programs, written in the instruction set of the particular machine in binary notation. Assembly languages were soon developed that let the programmer specify instruction in a text format, with abbreviations for each operation code and meaningful names for specifying addresses. However, because an assembly language is little more than a different notation for a machine language, any two machines with different instruction sets have different assembly languages. Kathleen Booth created one of the first Assembly languages in 1950 for various computers at Birkbeck College. High-level languages allow the programmer to write programs in terms that are syntactically richer, more capable of abstracting the code, making it targetable to varying machine instruction sets via compilation declarations and heuristics.
The first compiler for a programming language was developed by Grace Hopper. When Hopper went to work on UNIVAC in 1949, she brought the idea of using compilers with her. Compilers harness the power of computers to make programming easier by allowing programmers to specify calculations by entering a formula using infix notation for example. FORTRAN, the first used high-level language to have a functional implementation which permitted the abstraction of reusable blocks of code, came out in 1957. In 1951 Frances E. Holberton developed the first sort-merge generator which ran on the UNIVAC I. Another woman working at UNIVAC, Adele Mildred Koss, developed a program, a precursor to report generators. In USSR, Kateryna Yushchenko developed the Address programming language for the MESM in 1955; the idea for the creation of COBOL started in 1959 when Mary K. Hawes, who worked for Burroughs Corporation, set up a meeting to discuss creating a common business language, she invited six people, including Grace Hopper.
Hopper was involved in developing COBOL as a business language and creating "self-documenting" programming. Hopper's contribution to COBOL was based on her programming language, called FLOW-MATIC. In 1961, Jean E. Sammet developed FORMAC and published Programming Languages: History and Fundamentals which went on to be a standard work on programming languages. Programs were still entered using punched cards or paper tape. See computer programming in the punch card era. By the late 1960s, data storage devices and computer terminals became inexpensive enough that programs could be created by typing directly into the computers. Frances Holberton created a code to allow keyboard inputs while she worked at UNIVAC. Text editors were developed that allowed changes and corrections to be made much more than with punched cards. Sister Mary Kenneth Keller worked on developing the programming language, BASIC when she was a graduate student at Dartmouth in the 1960s. One of the first object-oriented programming languages, was developed by seven programmers, including Adele Goldberg, in the 1970s.
In 1985, Radia Perlman developed the Spannin
Computer science is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems, its fields can be divided into practical disciplines. Computational complexity theory is abstract, while computer graphics emphasizes real-world applications. Programming language theory considers approaches to the description of computational processes, while computer programming itself involves the use of programming languages and complex systems. Human–computer interaction considers the challenges in making computers useful and accessible; the earliest foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks such as the abacus have existed since antiquity, aiding in computations such as multiplication and division.
Algorithms for performing computations have existed since antiquity before the development of sophisticated computing equipment. Wilhelm Schickard designed and constructed the first working mechanical calculator in 1623. In 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner, he may be considered the first computer scientist and information theorist, among other reasons, documenting the binary number system. In 1820, Thomas de Colmar launched the mechanical calculator industry when he released his simplified arithmometer, the first calculating machine strong enough and reliable enough to be used daily in an office environment. Charles Babbage started the design of the first automatic mechanical calculator, his Difference Engine, in 1822, which gave him the idea of the first programmable mechanical calculator, his Analytical Engine, he started developing this machine in 1834, "in less than two years, he had sketched out many of the salient features of the modern computer".
"A crucial step was the adoption of a punched card system derived from the Jacquard loom" making it infinitely programmable. In 1843, during the translation of a French article on the Analytical Engine, Ada Lovelace wrote, in one of the many notes she included, an algorithm to compute the Bernoulli numbers, considered to be the first computer program. Around 1885, Herman Hollerith invented the tabulator, which used punched cards to process statistical information. In 1937, one hundred years after Babbage's impossible dream, Howard Aiken convinced IBM, making all kinds of punched card equipment and was in the calculator business to develop his giant programmable calculator, the ASCC/Harvard Mark I, based on Babbage's Analytical Engine, which itself used cards and a central computing unit; when the machine was finished, some hailed it as "Babbage's dream come true". During the 1940s, as new and more powerful computing machines were developed, the term computer came to refer to the machines rather than their human predecessors.
As it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. In 1945, IBM founded the Watson Scientific Computing Laboratory at Columbia University in New York City; the renovated fraternity house on Manhattan's West Side was IBM's first laboratory devoted to pure science. The lab is the forerunner of IBM's Research Division, which today operates research facilities around the world; the close relationship between IBM and the university was instrumental in the emergence of a new scientific discipline, with Columbia offering one of the first academic-credit courses in computer science in 1946. Computer science began to be established as a distinct academic discipline in the 1950s and early 1960s; the world's first computer science degree program, the Cambridge Diploma in Computer Science, began at the University of Cambridge Computer Laboratory in 1953. The first computer science degree program in the United States was formed at Purdue University in 1962.
Since practical computers became available, many applications of computing have become distinct areas of study in their own rights. Although many believed it was impossible that computers themselves could be a scientific field of study, in the late fifties it became accepted among the greater academic population, it is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM released the IBM 704 and the IBM 709 computers, which were used during the exploration period of such devices. "Still, working with the IBM was frustrating if you had misplaced as much as one letter in one instruction, the program would crash, you would have to start the whole process over again". During the late 1950s, the computer science discipline was much in its developmental stages, such issues were commonplace. Time has seen significant improvements in the effectiveness of computing technology. Modern society has seen a significant shift in the users of computer technology, from usage only by experts and professionals, to a near-ubiquitous user base.
Computers were quite costly, some degree of humanitarian aid was needed for efficient use—in part from professional computer operators. As computer adoption became more widespread and affordable, less human assistance was needed for common usage. Despite its short history as a formal academic discipline, computer science has made a number of fundamental contributions to science and society—in fact, along with electronics, it is