A report on Computer science and Algorithm

Charles Babbage, sometimes referred to as the "father of computing".

Flowchart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" or "true" (more accurately, the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).

Ada Lovelace published the first algorithm intended for processing on a computer.

Ada Lovelace's diagram from "note G", the first published computer algorithm

Logical NAND algorithm implemented electronically in 7400 chip

Flowchart examples of the canonical Böhm-Jacopini structures: the SEQUENCE (rectangles descending the page), the WHILE-DO and the IF-THEN-ELSE. The three structures are made of the primitive conditional GOTO (IF test THEN GOTO step xxx, shown as diamond), the unconditional GOTO (rectangle), various assignment operators (rectangle), and HALT (rectangle). Nesting of these structures inside assignment-blocks result in complex diagrams (cf. Tausworthe 1977:100, 114).

The example-diagram of Euclid's algorithm from T.L. Heath (1908), with more detail added. Euclid does not go beyond a third measuring and gives no numerical examples. Nicomachus gives the example of 49 and 21: "I subtract the less from the greater; 28 is left; then again I subtract from this the same 21 (for this is possible); 7 is left; I subtract this from 21, 14 is left; from which I again subtract 7 (for this is possible); 7 is left, but 7 cannot be subtracted from 7." Heath comments that "The last phrase is curious, but the meaning of it is obvious enough, as also the meaning of the phrase about ending 'at one and the same number'."(Heath 1908:300).

A graphical expression of Euclid's algorithm to find the greatest common divisor for 1599 and 650.

"Inelegant" is a translation of Knuth's version of the algorithm with a subtraction-based remainder-loop replacing his use of division (or a "modulus" instruction). Derived from Knuth 1973:2–4. Depending on the two numbers "Inelegant" may compute the g.c.d. in fewer steps than "Elegant".

In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

- Algorithm

Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory and automation) to practical disciplines (including the design and implementation of hardware and software).

- Computer science

9 related topics with Alpha

3rd century BC Greek mathematician Euclid (holding calipers), as imagined by Raphael in this detail from The School of Athens (1509–1511)

Mathematics

2 links

Area of knowledge that includes such topics as numbers , formulas and related structures (algebra), shapes and the spaces in which they are contained (geometry), and quantities and their changes (calculus and analysis).

The distribution of prime numbers is a central point of study in number theory. This Ulam spiral serves to illustrate it, hinting, in particular, at the conditional independence between being prime and being a value of certain quadratic polynomials.

The quadratic formula expresses concisely the solutions of all quadratic equations

Rubik's cube: the study of its possible moves is a concrete application of group theory

The Babylonian mathematical tablet Plimpton 322, dated to 1800 BC.

Archimedes used the method of exhaustion, depicted here, to approximate the value of pi.

The numerals used in the Bakhshali manuscript, dated between the 2nd century BC and the 2nd century AD.

Leonardo Fibonacci, the Italian mathematician who introduced the Hindu–Arabic numeral system invented between the 1st and 4th centuries by Indian mathematicians, to the Western World.

Leonhard Euler created and popularized much of the mathematical notation used today.

Carl Friedrich Gauss, known as the prince of mathematicians

Euler's identity, which American physicist Richard Feynman once called "the most remarkable formula in mathematics".

Mathematics is essential in many fields, including natural sciences, engineering, medicine, finance, computer science and social sciences.

Algorithms - especially their implementation and computational complexity - play a major role in discrete mathematics.

Lorenz cipher machine, used in World War II to encrypt communications of the German High Command

Cryptography

1 links

Practice and study of techniques for secure communication in the presence of adversarial behavior.

Alphabet shift ciphers are believed to have been used by Julius Caesar over 2,000 years ago. This is an example with k = 3. In other words, the letters in the alphabet are shifted three in one direction to encrypt and three in the other direction to decrypt.

Reconstructed ancient Greek scytale, an early cipher device

First page of a book by Al-Kindi which discusses encryption of messages

16th-century book-shaped French cipher machine, with arms of Henri II of France

Enciphered letter from Gabriel de Luetz d'Aramon, French Ambassador to the Ottoman Empire, after 1546, with partial decipherment

Symmetric-key cryptography, where a single key is used for encryption and decryption

One round (out of 8.5) of the IDEA cipher, used in most versions of PGP and OpenPGP compatible software for time-efficient encryption of messages

Public-key cryptography, where different keys are used for encryption and decryption.

Whitfield Diffie and Martin Hellman, authors of the first published paper on public-key cryptography.

In this example the message is only signed and not encrypted.
1) Alice signs a message with her private key.
2) Bob can verify that Alice sent the message and that the message has not been modified.

Variants of the Enigma machine, used by Germany's military and civil authorities from the late 1920s through World War II, implemented a complex electro-mechanical polyalphabetic cipher. Breaking and reading of the Enigma cipher at Poland's Cipher Bureau, for 7 years before the war, and subsequent decryption at Bletchley Park, was important to Allied victory.

Poznań monument (center) to Polish cryptanalysts whose breaking of Germany's Enigma machine ciphers, beginning in 1932, altered the course of World War II

NSA headquarters in Fort Meade, Maryland

Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, electrical engineering, communication science, and physics.

Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around computational hardness assumptions, making such algorithms hard to break in actual practice by any adversary.

Data structure

1 links

In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data.

Usually, efficient data structures are key to designing efficient algorithms.

Programming language

1 links

Any set of rules that converts strings, or graphical program elements in the case of visual programming languages, to various kinds of machine code output.

A selection of programming language textbooks; only a few of the thousands available.

Parse tree of Python code with inset tokenization

Syntax highlighting is often used to aid programmers in recognizing elements of source code. The language above is Python.

Programming languages are one kind of computer language, and are used in computer programming to implement algorithms.

Programming language theory is a subfield of computer science that deals with the design, implementation, analysis, characterization, and classification of programming languages.

Computability theory

1 links

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

Nowadays these are often considered as a single hypothesis, the Church–Turing thesis, which states that any function that is computable by an algorithm is a computable function.

Computation

0 links

Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).

An especially well-known discipline of the study of computation is computer science.

Computational geometry

0 links

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.

Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry.

Artificial intelligence

0 links

Intelligence demonstrated by machines, as opposed to the natural intelligence displayed by animals including humans.

An ontology represents knowledge as a set of concepts within a domain and the relationships between those concepts.

A parse tree represents the syntactic structure of a sentence according to some formal grammar.

Feature detection (pictured: edge detection) helps AI compose informative abstract structures out of raw data.

Kismet, a robot with rudimentary social skills

A particle swarm seeking the global minimum

Expectation-maximization clustering of Old Faithful eruption data starts from a random guess but then successfully converges on an accurate clustering of the two physically distinct modes of eruption.

A neural network is an interconnected group of nodes, akin to the vast network of neurons in the human brain.

Representing images on multiple layers of abstraction in deep learning

For this project the AI had to learn the typical patterns in the colors and brushstrokes of Renaissance painter Raphael. The portrait shows the face of the actress Ornella Muti, "painted" by AI in the style of Raphael.

AI Patent families for functional application categories and sub categories. Computer vision represents 49 percent of patent families related to a functional application in 2016.

The word "robot" itself was coined by Karel Čapek in his 1921 play R.U.R., the title standing for "Rossum's Universal Robots"

AI also draws upon computer science, psychology, linguistics, philosophy, and many other fields.

Cukier, Kenneth, "Ready for Robots? How to Think about the Future of AI", Foreign Affairs, vol. 98, no. 4 (July/August 2019), pp. 192–98. George Dyson, historian of computing, writes (in what might be called "Dyson's Law") that "Any system simple enough to be understandable will not be complicated enough to behave intelligently, while any system complicated enough to behave intelligently will be too complicated to understand." (p. 197.) Computer scientist Alex Pentland writes: "Current AI machine-learning algorithms are, at their core, dead simple stupid. They work, but they work by brute force." (p. 198.)

Euler diagram for P, NP, NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)

P versus NP problem

0 links

Major unsolved problem in theoretical computer science.

The graph shows the running time vs. problem size for a knapsack problem of a state-of-the-art, specialized algorithm. The quadratic fit suggests that the algorithmic complexity of the problem is O((log(n))2).

Diagram of complexity classes provided that P ≠ NP. The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by Ladner's theorem.

The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P".

The problem has been called the most important open problem in computer science.