AI Content Remover

AI Content Remover — independent reviews, comparisons, pricing and step-by-step guides on Aizhi.

• 

  Cloud-based quantum computing

  Cloud-based quantum computing refers to the remote access of quantum computing resources—such as quantum emulators, simulators, or processors—via the internet. Cloud access enables users to develop, test, and execute quantum algorithms without the need for direct interaction with specialized hardware, facilitating broader participation in quantum software development and experimentation. In 2016, IBM launched the IBM Quantum Experience, one of the first publicly accessible quantum processors connected to the cloud. In early 2017, researchers at Rigetti Computing demonstrated programmable quantum cloud access through their software platform Forest, which included the pyQuil Python library. Since the early-2020s, cloud-based quantum computing has grown significantly, with multiple providers offering access to a variety of quantum hardware modalities, including superconducting qubits, trapped ions, neutral atoms, and photonic systems. Major platforms such as Amazon Braket, Azure Quantum, and qBraid aggregate quantum devices from hardware developers like IonQ, Rigetti Computing, QuEra, Pasqal, Oxford Quantum Circuits, and IBM Quantum. These platforms provide unified interfaces for users to write and execute quantum algorithms across diverse backends, often supporting open-source SDKs such as Qiskit, Cirq, and PennyLane. The proliferation of cloud-based access has played a key role in accelerating quantum education, algorithm research, and early-stage application development by lowering the barrier to experimentation with real quantum hardware. Cloud-based quantum computing has expanded access to quantum hardware and tools beyond traditional research laboratories. These platforms support educational initiatives, algorithm development, and early-stage commercial applications. == Applications == Cloud-based quantum computing is used across education, research, and software development, offering remote access to quantum systems without the need for on-site infrastructure. === Education === Quantum cloud platforms have become valuable tools in education, allowing students and instructors to engage with real quantum processors through user-friendly interfaces. Educators use these platforms to teach foundational concepts in quantum mechanics and quantum computing, as well as to demonstrate and implement quantum algorithms in a classroom or laboratory setting. === Scientific Research === Cloud-based access to quantum hardware has enabled researchers to conduct experiments in quantum information, test quantum algorithms, and compare quantum hardware platforms. Experiments such as testing Bell's theorem or evaluating quantum teleportation protocols have been performed on publicly available quantum processors. === Software Development and Prototyping === Developers use cloud-based platforms to prototype quantum software applications across fields such as optimization, machine learning, and chemistry. These platforms offer SDKs and APIs that integrate classical and quantum workflows, enabling experimentation with quantum algorithms in real-world or simulated environments. === Public Engagement and Games === Quantum cloud tools have also been used to create educational games and interactive applications aimed at increasing public understanding of quantum concepts. These efforts help bridge the gap between theoretical content and intuitive learning. == Existing platforms == qBraid Lab by qBraid is a cloud-based platform for quantum computing. It provides software tools for researchers and developers in quantum, as well as access to quantum hardware. qBraid provides cloud based access to Microsoft Azure Quantum and Amazon Braket devices including IQM, QuEra, Pasqal, Rigetti, IonQ, QIR simulators, Amazon Braket simulators, and the NEC Vector Annealer, as of August 2025. qBraid's base version is free, where unlimited hardware and simulator access is available with the purchase of credits. Quandela Cloud by Quandela is the platform to access first cloud-accessible European photonic quantum computer. The computer is interfaced using the Perceval scripting language, with tutorials and documentation available online for free. Xanadu Quantum Cloud by Xanadu is a platform with cloud-based access to three fully programmable photonic quantum computers. Forest by Rigetti Computing is a tool suite for cloud-based quantum computing. It includes a programming language, development tools and example algorithms. LIQUi> by Microsoft is a software architecture and tool suite for quantum computing. It includes a programming language, example optimization and scheduling algorithms, and quantum simulators. Q#, a quantum programming language by Microsoft on the .NET Framework seen as a successor to LIQUi|>. IBM Quantum Platform by IBM, providing access to quantum hardware as well as HPC simulators. These can be accessed programmatically using the Python-based Qiskit framework, or via graphical interface with the IBM Q Experience GUI. Both are based on the OpenQASM standard for representing quantum operations. There is also a tutorial and online community. Quantum in the Cloud by The University of Bristol, which consists of a quantum simulator and a four qubit optical quantum system. Quantum Playground by Google is an educational resource which features a simulator with a simple interface, and a scripting language and 3D quantum state visualization. Quantum in the Cloud is an experimental quantum cloud platform for access to a four-qubit nuclear magnetic resonance-NMRCloudQ computer, managed by Tsinghua University. Quantum Inspire by Qutech is the first platform in Europe providing cloud-based quantum computing to two hardware chips. Next to a 5-qubit transmon processor, Quantum Inspire is the first platform in the world to provide online access to a fully programmable 2-qubit electron spin quantum processor. Amazon Braket is a cloud-based quantum computing platform hosted by AWS which, as of June 2025, provides access to quantum computers built by IonQ, Rigetti, IQM, and QuEra. Braket also provides a quantum algorithm development environment and simulator. Forge by QC Ware is a cloud-based quantum computing platform that provides access to D-Wave hardware, as well as Google and IBM simulators. The platform offers a 30-day free trial, including one minute of quantum computing time. Quantum-as-a-Service by Scaleway is a cloud-based platform created in 2022 to access to real quantum hardware from IQM Quantum Computers, Alpine Quantum Technologies, Quandela and Pasqal. It also include access to GPU-powered emulators such as Aer, Qsim and Quandela proprietary emulation.

  Read more →
• 

  Read–write conflict

  In computer science, in the field of databases, read–write conflict, also known as unrepeatable reads, is a computational anomaly associated with interleaved execution of transactions. Specifically, a read–write conflict occurs when a "transaction requests to read an entity for which an unclosed transaction has already made a write request." Given a schedule S S = [ T 1 T 2 R ( A ) R ( A ) W ( A ) C o m . R ( A ) W ( A ) C o m . ] {\displaystyle S={\begin{bmatrix}T1&T2\\R(A)&\\&R(A)\\&W(A)\\&Com.\\R(A)&\\W(A)&\\Com.&\end{bmatrix}}} In this example, T1 has read the original value of A, and is waiting for T2 to finish. T2 also reads the original value of A, overwrites A, and commits. However, when T1 reads from A, it discovers two different versions of A, and T1 would be forced to abort, because T1 would not know what to do. This is an unrepeatable read. This could never occur in a serial schedule, in which each transaction executes in its entirety before another begins. Strict two-phase locking (Strict 2PL) or Serializable Snapshot Isolation (SSI) prevent this conflict. == Real-world example == Alice and Bob are using a website to book tickets for a specific show. Only one ticket is left for the specific show. Alice signs on first to see that only one ticket is left, and finds it expensive. Alice takes time to decide. Bob signs on and also finds one ticket left, and orders it instantly. Bob purchases and logs off. Alice decides to buy a ticket, to find there are no tickets. This is a typical read–write conflict situation.

  Read more →
• 

  Uncertain database

  An uncertain database is a kind of database studied in database theory. The goal of uncertain databases is to manage information on which there is some uncertainty. Uncertain databases make it possible to explicitly represent and manage uncertainty on the data, usually in a succinct way. == Formal definition == At the basis of uncertain databases is the notion of possible world. Specifically, a possible world of an uncertain database is a (certain) database which is one of the possible realizations of the uncertain database. A given uncertain database typically has more than one, and potentially infinitely many, possible worlds. A formalism to represent uncertain databases then explains how to succinctly represent a set of possible worlds into one uncertain database. == Types of uncertain databases == Uncertain database models differ in how they represent and quantify these possible worlds: Incomplete databases are a compact representation of the set of possible worlds – the use of NULL in SQL, arguably the most commonplace instantiation of uncertain databases, is an example of incomplete database model. Probabilistic databases are a compact representation of a probability distribution over the set of possible worlds. Fuzzy databases are a compact representation of a fuzzy set of the possible worlds. Though mostly studied in the relational setting, uncertain database models can also be defined in other relational models such as graph databases or XML databases. === Incomplete database === The most common database model is the relational model. Multiple incomplete database models have been defined over the relational model, that form extensions to the relational algebra. These have been called Imieliński–Lipski algebras: Relations with NULL values, also called Codd tables c-tables v-tables === Example === The following table is a relation of an incomplete database, described in the formalism of NULL values: There are infinitely many possible worlds for this incomplete database, obtained by replacing the "NULL" values with concrete values. For instance, the following relation is a possible world:

  Read more →
• 

  In-place algorithm

  In computer science, an in-place algorithm is an algorithm that operates directly on the input data structure without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called not-in-place or out-of-place. In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, counting everything including function calls and pointers. However, this form is very limited as simply having an index to a length n array requires O(log n) bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though non-constant extra space for its operation. Usually, this space is O(log n), though sometimes anything in o(n) is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity (DSPACE), counting pointer lengths. Therefore, the space requirements here have an extra log n factor compared to an analysis that ignores the lengths of indices and pointers. An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as log-space reductions, it is more typical to always ignore output space (in these cases it is more essential that the output is write-only). == Examples == Given an array a of n items, suppose we want an array that holds the same elements in reversed order and to dispose of the original. One seemingly simple way to do this is to create a new array of equal size, fill it with copies from a in the appropriate order and then delete a. function reverse(a[0..n - 1]) allocate b[0..n - 1] for i from 0 to n - 1 b[n − 1 − i] := a[i] return b Unfortunately, this requires O(n) extra space for having the arrays a and b available simultaneously. Also, allocation and deallocation are often slow operations. Since we no longer need a, we can instead overwrite it with its own reversal using this in-place algorithm which will only need constant number (2) of integers for the auxiliary variables i and tmp, no matter how large the array is. function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp As another example, many sorting algorithms rearrange arrays into sorted order in-place, including: bubble sort, comb sort, selection sort, insertion sort, heapsort, and Shell sort. These algorithms require only a few pointers, so their space complexity is O(log n). Quicksort operates in-place on the data to be sorted. However, quicksort requires O(log n) stack space pointers to keep track of the subarrays in its divide and conquer strategy. Consequently, quicksort needs O(log2 n) additional space. Although this non-constant space technically takes quicksort out of the in-place category, quicksort and other algorithms needing only O(log n) additional pointers are usually considered in-place algorithms. Most selection algorithms are also in-place, although some considerably rearrange the input array in the process of finding the final, constant-sized result. Some text manipulation algorithms such as trim and reverse may be done in-place. == In computational complexity == In computational complexity theory, the strict definition of in-place algorithms includes all algorithms with O(1) space complexity, the class DSPACE(1). This class is very limited; it equals the regular languages. In fact, it does not even include any of the examples listed above. Algorithms are usually considered in L, the class of problems requiring O(log n) additional space, to be in-place. This class is more in line with the practical definition, as it allows numbers of size n as pointers or indices. This expanded definition still excludes quicksort, however, because of its recursive calls. Identifying the in-place algorithms with L has some interesting implications; for example, it means that there is a (rather complex) in-place algorithm to determine whether a path exists between two nodes in an undirected graph, a problem that requires O(n) extra space using typical algorithms such as depth-first search (a visited bit for each node). This in turn yields in-place algorithms for problems such as determining if a graph is bipartite or testing whether two graphs have the same number of connected components. == Role of randomness == In many cases, the space requirements of an algorithm can be drastically cut by using a randomized algorithm. For example, if one wishes to know if two vertices in a graph of n vertices are in the same connected component of the graph, there is no known simple, deterministic, in-place algorithm to determine this. However, if we simply start at one vertex and perform a random walk of about 20n3 steps, the chance that we will stumble across the other vertex provided that it is in the same component is very high. Similarly, there are simple randomized in-place algorithms for primality testing such as the Miller–Rabin primality test, and there are also simple in-place randomized factoring algorithms such as Pollard's rho algorithm. == In functional programming == Functional programming languages often discourage or do not support explicit in-place algorithms that overwrite data, since this is a type of side effect; instead, they only allow new data to be constructed. However, good functional language compilers will often recognize when an object very similar to an existing one is created and then the old one is thrown away, and will optimize this into a simple mutation "under the hood". Note that it is possible in principle to carefully construct in-place algorithms that do not modify data (unless the data is no longer being used), but this is rarely done in practice.

  Read more →
• 

  Pyramid (image processing)

  Pyramid, or pyramid representation, is a type of multi-scale signal representation developed by the computer vision, image processing and signal processing communities, in which a signal or an image is subject to repeated smoothing and subsampling. Pyramid representation is a predecessor to scale-space representation and multiresolution analysis. == Pyramid generation == There are two main types of pyramids: lowpass and bandpass. A lowpass pyramid is made by smoothing the image with an appropriate smoothing filter and then subsampling the smoothed image, usually by a factor of 2 along each coordinate direction. The resulting image is then subjected to the same procedure, and the cycle is repeated multiple times. Each cycle of this process results in a smaller image with increased smoothing, but with decreased spatial sampling density (that is, decreased image resolution). If illustrated graphically, the entire multi-scale representation will look like a pyramid, with the original image on the bottom and each cycle's resulting smaller image stacked one atop the other. A bandpass pyramid is made by forming the difference between images at adjacent levels in the pyramid and performing image interpolation between adjacent levels of resolution, to enable computation of pixelwise differences. == Pyramid generation kernels == A variety of different smoothing kernels have been proposed for generating pyramids. Among the suggestions that have been given, the binomial kernels arising from the binomial coefficients stand out as a particularly useful and theoretically well-founded class. Thus, given a two-dimensional image, we may apply the (normalized) binomial filter (1/4, 1/2, 1/4) typically twice or more along each spatial dimension and then subsample the image by a factor of two. This operation may then proceed as many times as desired, leading to a compact and efficient multi-scale representation. If motivated by specific requirements, intermediate scale levels may also be generated where the subsampling stage is sometimes left out, leading to an oversampled or hybrid pyramid. With the increasing computational efficiency of CPUs available today, it is in some situations also feasible to use wider supported Gaussian filters as smoothing kernels in the pyramid generation steps. === Gaussian pyramid === In a Gaussian pyramid, subsequent images are weighted down using a Gaussian average (Gaussian blur) and scaled down. Each pixel containing a local average corresponds to a neighborhood pixel on a lower level of the pyramid. This technique is used especially in texture synthesis. === Laplacian pyramid === A Laplacian pyramid is very similar to a Gaussian pyramid but saves the difference image of the blurred versions between each levels. Only the smallest level is not a difference image to enable reconstruction of the high resolution image using the difference images on higher levels. This technique can be used in image compression. === Steerable pyramid === A steerable pyramid, developed by Simoncelli and others, is an implementation of a multi-scale, multi-orientation band-pass filter bank used for applications including image compression, texture synthesis, and object recognition. It can be thought of as an orientation selective version of a Laplacian pyramid, in which a bank of steerable filters are used at each level of the pyramid instead of a single Laplacian or Gaussian filter. == Applications of pyramids == === Alternative representation === In the early days of computer vision, pyramids were used as the main type of multi-scale representation for computing multi-scale image features from real-world image data. More recent techniques include scale-space representation, which has been popular among some researchers due to its theoretical foundation, the ability to decouple the subsampling stage from the multi-scale representation, the more powerful tools for theoretical analysis as well as the ability to compute a representation at any desired scale, thus avoiding the algorithmic problems of relating image representations at different resolution. Nevertheless, pyramids are still frequently used for expressing computationally efficient approximations to scale-space representation. === Detail manipulation === Levels of a Laplacian pyramid can be added to or removed from the original image to amplify or reduce detail at different scales. However, detail manipulation of this form is known to produce halo artifacts in many cases, leading to the development of alternatives such as the bilateral filter. Some image compression file formats use the Adam7 algorithm or some other interlacing technique. These can be seen as a kind of image pyramid. Because those file format store the "large-scale" features first, and fine-grain details later in the file, a particular viewer displaying a small "thumbnail" or on a small screen can quickly download just enough of the image to display it in the available pixels—so one file can support many viewer resolutions, rather than having to store or generate a different file for each resolution.

  Read more →
• 

  Semantic translation

  Semantic translation is the process of using semantic information to aid in the translation of data in one representation or data model to another representation or data model. Semantic translation takes advantage of semantics that associate meaning with individual data elements in one dictionary to create an equivalent meaning in a second system. An example of semantic translation is the conversion of XML data from one data model to a second data model using formal ontologies for each system such as the Web Ontology Language (OWL). This is frequently required by intelligent agents that wish to perform searches on remote computer systems that use different data models to store their data elements. The process of allowing a single user to search multiple systems with a single search request is also known as federated search. Semantic translation should be differentiated from data mapping tools that do simple one-to-one translation of data from one system to another without actually associating meaning with each data element. Semantic translation requires that data elements in the source and destination systems have "semantic mappings" to a central registry or registries of data elements. The simplest mapping is of course where there is equivalence. There are three types of Semantic equivalence: Class Equivalence - indicating that class or "concepts" are equivalent. For example: "Person" is the same as "Individual" Property Equivalence - indicating that two properties are equivalent. For example: "PersonGivenName" is the same as "FirstName" Instance Equivalence - indicating that two individual instances of objects are equivalent. For example: "Dan Smith" is the same person as "Daniel Smith" Semantic translation is very difficult if the terms in a particular data model do not have direct one-to-one mappings to data elements in a foreign data model. In that situation, an alternative approach must be used to find mappings from the original data to the foreign data elements. This problem can be alleviated by centralized metadata registries that use the ISO-11179 standards such as the National Information Exchange Model (NIEM).

  Read more →
• 

  Information architecture

  Information architecture is the structural design of shared information environments, in particular the organisation of websites and software to support usability and findability. The term information architecture was coined by Richard Saul Wurman. Since its inception, information architecture has become an emerging community of practice focused on applying principles of design, architecture and information science in digital spaces. Typically, a model or concept of information is used and applied to activities which require explicit details of complex information systems. These activities include library systems and database development. == Definition == The term information architecture has different meanings in different branches of information systems or information technology. === User experience === In user experience design, information architecture has been described as the structural design of shared information environments, comprising the study and practice of organising and labelling web sites, intranets, online communities, and software to support user experience, in particular, the findability and usability of information. It has also been described as an emerging community of practice focused on bringing principles of design and architecture to the digital landscape. === Information systems === Technically speaking, information architecture comprises the combination of organization, labeling, search and navigation systems within websites and intranets, serving as a navigational aid to the content of information-rich systems. === Data architecture === Information architecture can be described as a subset of data architecture where usable data is constructed, designed, and arranged in a fashion most useful to the users of data. === Systems design === In the field of systems design, for example, information architecture is a component of enterprise architecture that deals with the information component when describing the structure of an enterprise. Some system design practitioners regard information architecture as strictly the application of information science to web design, which considers such issues as classification and information retrieval, and not factors like user experience and information design. == Principles == Principles of information architecture include the following: The principle of objects The principle of choices The principle of disclosure The principle of exemplars The principle of front doors The principle of multiple classification The principle of focused navigation The principle of growth == History == Richard Saul Wurman is credited with coining the term information architecture in relation to the design of information. From 1998 to 2015, Peter Morville and Louis Rosenfeld were co-authors of Information Architecture for the World Wide Web. Other authors include Jesse James Garrett and Christina Wodtke.

  Read more →
• 

  Chinese speech synthesis

  Chinese speech synthesis is the application of speech synthesis to the Chinese language (usually Standard Chinese). It poses additional difficulties due to Chinese characters frequently having different pronunciations in different contexts and the complex prosody, which is essential to convey the meaning of words, and sometimes the difficulty in obtaining agreement among native speakers concerning what the correct pronunciation is of certain phonemes. == Concatenation (Ekho and KeyTip) == Recordings can be concatenated in any desired combination, but the joins sound forced (as is usual for simple concatenation-based speech synthesis) and this can severely affect prosody; these synthesizers are also inflexible in terms of speed and expression. However, because these synthesizers do not rely on a corpus, there is no noticeable degradation in performance when they are given more unusual or awkward phrases. Ekho is an open source TTS which simply concatenates sampled syllables. It currently supports Cantonese, Mandarin, and experimentally Korean. Some of the Mandarin syllables have been pitched-normalised in Praat. A modified version of these is used in Gradint's "synthesis from partials". cjkware.com used to ship a product called KeyTip Putonghua Reader which worked similarly; it contained 120 Megabytes of sound recordings (GSM-compressed to 40 Megabytes in the evaluation version), comprising 10,000 multi-syllable dictionary words plus single-syllable recordings in 6 different prosodies (4 tones, neutral tone, and an extra third-tone recording for use at the end of a phrase). == Lightweight synthesizers (eSpeak and Yuet) == The lightweight open-source speech project eSpeak, which has its own approach to synthesis, has experimented with Mandarin and Cantonese. eSpeak was used by Google Translate from May 2010 until December 2010. The commercial product "Yuet" is also lightweight (it is intended to be suitable for resource-constrained environments like embedded systems); it was written from scratch in ANSI C starting from 2013. Yuet claims a built-in NLP model that does not require a separate dictionary; the speech synthesised by the engine claims clear word boundaries and emphasis on appropriate words. Communication with its author is required to obtain a copy. Both eSpeak and Yuet can synthesis speech for Cantonese and Mandarin from the same input text, and can output the corresponding romanisation (for Cantonese, Yuet uses Yale and eSpeak uses Jyutping; both use Pinyin for Mandarin). eSpeak does not concern itself with word boundaries when these don't change the question of which syllable should be spoken. == Corpus-based == A "corpus-based" approach can sound very natural in most cases but can err in dealing with unusual phrases if they can't be matched with the corpus. The synthesiser engine is typically very large (hundreds or even thousands of megabytes) due to the size of the corpus. === iFlyTek === Anhui USTC iFlyTek Co., Ltd (iFlyTek) published a W3C paper in which they adapted Speech Synthesis Markup Language to produce a mark-up language called Chinese Speech Synthesis Markup Language (CSSML) which can include additional markup to clarify the pronunciation of characters and to add some prosody information. The amount of data involved is not disclosed by iFlyTek but can be seen from the commercial products that iFlyTek have licensed their technology to; for example, Bider's SpeechPlus is a 1.3 Gigabyte download, 1.2 Gigabytes of which is used for the highly compressed data for a single Chinese voice. iFlyTek's synthesiser can also synthesise mixed Chinese and English text with the same voice (e.g. Chinese sentences containing some English words); they claim their English synthesis to be "average". The iFlyTek corpus appears to be heavily dependent on Chinese characters, and it is not possible to synthesize from pinyin alone. It is sometimes possible by means of CSSML to add pinyin to the characters to disambiguate between multiple possible pronunciations, but this does not always work. === NeoSpeech === There is an online interactive demonstration for NeoSpeech speech synthesis, which accepts Chinese characters and also pinyin if it's enclosed in their proprietary "VTML" markup. === Mac OS === Mac OS had Chinese speech synthesizers available up to version 9. This was removed in 10.0 and reinstated in 10.7 (Lion). === Historical corpus-based synthesizers (no longer available) === A corpus-based approach was taken by Tsinghua University in SinoSonic, with the Harbin dialect voice data taking 800 Megabytes. This was planned to be offered as a download but the link was never activated. Nowadays, only references to it can be found on Internet Archive. Bell Labs' approach, which was demonstrated online in 1997 but subsequently removed, was described in a monograph "Multilingual Text-to-Speech Synthesis: The Bell Labs Approach" (Springer, October 31, 1997, ISBN 978-0-7923-8027-6), and the former employee who was responsible for the project, Chilin Shih (who subsequently worked at the University of Illinois) put some notes about her methods on her website.

  Read more →
• 

  Autognostics

  Autognostics is a new paradigm that describes the capacity for computer networks to be self-aware. It is considered one of the major components of Autonomic Networking. == Introduction == One of the most important characteristics of today's Internet that has contributed to its success is its basic design principle: a simple and transparent core with intelligence at the edges (the so-called "end-to-end principle"). Based on this principle, the network carries data without knowing the characteristics of that data (e.g., voice, video, etc.) - only the end-points have application-specific knowledge. If something goes wrong with the data, only the edge may be able to recognize that since it knows about the application and what the expected behavior is. The core has no information about what should happen with that data - it only forwards packets. Although an effective and beneficial attribute, this design principle has also led to many of today's problems, limitations, and frustrations. Currently, it is almost impossible for most end-users to know why certain network-based applications do not work well and what they need to do to make it better. Also, network operators who interact with the core in low-level terms such as router configuration have problems expressing their high-level goals into low-level actions. In high-level terms, this may be summarized as a weak coupling between the network and application layers of the overall system. As a consequence of the Internet end-to-end principle, the network performance experienced by a particular application is difficult to attribute based on the behavior of the individual elements. At any given moment, the measure of performance between any two points is typically unknown and applications must operate blindly. As a further consequence, changes to the configuration of given element, or changes in the end-to-end path, cannot easily be validated. Optimization and provisioning cannot then be automated except against only the simplest design specifications. There is an increasing interest in Autonomic Networking research, and a strong conviction that an evolution from the current networking status quo is necessary. Although to date there have not been any practical implementations demonstrating the benefits of an effective autonomic networking paradigm, there seems to be a consensus as to the characteristics which such implementations would need to demonstrate. These specifically include continuous monitoring, identifying, diagnosing and fixing problems based on high-level policies and objectives. Autognostics, as a major part of the autonomic networking concept, intends to bring networks to a new level of awareness and eliminate the lack of visibility which currently exists in today's networks. == Definition == Autognostics is a new paradigm that describes the capacity for computer networks to be self-aware, in part and as a whole, and dynamically adapt to the applications running on them by autonomously monitoring, identifying, diagnosing, resolving issues, subsequently verifying that any remediation was successful, and reporting the impact with respect to the application's use (i.e., providing visibility into the changes to networks and their effects). Although similar to the concept of network awareness, i.e., the capability of network devices and applications to be aware of network characteristics (see References section below), it is noteworthy that autognostics takes that concept one step further. The main difference is the auto part of autognostics, which entails that network devices are self-aware of network characteristics, and have the capability to adapt themselves as a result of continuous monitoring and diagnostics. == Path to autognostics == Autognostics, or in other words deep self-knowledge, can be best described as the ability of a network to know itself and the applications that run on it. This knowledge is used to autonomously adapt to dynamic network and application conditions such as utilization, capacity, quality of service/application/user experience, etc. In order to achieve autognosis, networks need a means to: Continuously monitor/test the network for application-specific performance Analyze the monitoring/test data to detect problems (e.g., performance degradation) Diagnose, identify and localize sources of degradation Automatically take actions to resolve problems via remediation/provisioning Verify the problems have been resolved (potentially rolling back changes if ineffective) Subsequently, continue to monitor/test for performance

  Read more →
• 

  Artificial intuition

  Artificial intuition is a theoretical capacity of an artificial software to function similarly to human consciousness, specifically in the capacity of human consciousness known as intuition. == Comparison of human and the theoretically artificial == Intuition is the function of the mind, the experience of which, is described as knowledge based on "a hunch", resulting (as the word itself does) from "contemplation" or "insight". Psychologist Jean Piaget showed that intuitive functioning within the normally developing human child at the Intuitive Thought Substage of the preoperational stage occurred at from four to seven years of age. In Carl Jung's concept of synchronicity, the concept of "intuitive intelligence" is described as something like a capacity that transcends ordinary-level functioning to a point where information is understood with a greater depth than is available in more simple rationally-thinking entities. Artificial intuition is theoretically (or otherwise) a sophisticated function of an artifice that is able to interpret data with depth and locate hidden factors functioning in Gestalt psychology, and that intuition in the artificial mind would, in the context described here, be a bottom-up process upon a macroscopic scale identifying something like the archetypal (see τύπος). To create artificial intuition supposes the possibility of the re-creation of a higher functioning of the human mind, with capabilities such as what might be found in semantic memory and learning. The transferral of the functioning of a biological system to synthetic functioning is based upon modeling of functioning from knowledge of cognition and the brain, for instance as applications of models of artificial neural networks from the research done within the discipline of computational neuroscience. == Application software contributing to its development == The notion of a process of a data-interpretative synthesis has already been found in a computational-linguistic software application that has been created for use in an internal security context. The software integrates computed data based specifically on objectives incorporating a paradigm described as "religious intuitive" (hermeneutic), functional to a degree that represents advances upon the performance of generic lexical data mining.

  Read more →
• 

  Best arm identification

  Best arm identification (BAI) is a sequential one-player game where the player has to find the best action (arm) among a list of actions (arms) by collecting information in the most efficient way. It is a multi-armed bandit game as a player only gets information about an arm by playing it. The most common objective in multi-armed bandit games is to minimize the regret (i.e., play the best action as much as possible), but in BAI, the goal is to find the best arm as efficiently as possible. This problem naturally arises in scenarios such as adaptive clinical trials where the number of patients is limited and the quantification of the confidence in a treatment is important. It also arises in hyperparameter optimization where the goal is to find the optimal choice of hyperparameters for an algorithm with the smallest possible number of experiments, as it can be costly in terms of time, energy, or money. == Stochastic multi-armed bandit == The stochastic multi-armed bandit (MAB) is a sequential game with one player and K {\displaystyle K} actions (arms). Each arm has an unknown probability distribution associated with it. At each turn, the player has to choose one action and receive an observation from the probability distribution associated with the arm. The more you play an arm, the more you get information on its probability distribution. === Best arm identification === In BAI the goal is to find the arm that has the probability distribution with the highest mean. BAI may be either fixed confidence or fixed horizon. In a fixed-confidence game, a confidence level δ {\displaystyle \delta } is fixed at the beginning of the game and the goal is to find the best arm with this confidence level in as few turns as possible. In a fixed horizon game, the number of turns T {\displaystyle T} is fixed, and the goal is to find the best arm with the highest possible confidence in T {\displaystyle T} turns. === Math formalisation === We have one player and K {\displaystyle K} actions (arms). Behind each arm k ∈ { 1 , … , K } {\displaystyle k\in \{1,\ldots ,K\}} lies an unknown distribution ν k {\displaystyle \nu _{k}} with mean μ k {\displaystyle \mu _{k}} . Each distribution ν k {\displaystyle \nu _{k}} belongs to a known family D {\displaystyle {\mathcal {D}}} (such as the set of Gaussian distributions or Bernoulli distributions). At each time step t {\displaystyle t} , the player selects an arm a t {\displaystyle a_{t}} and observes an independent sample X t ∼ ν a t {\displaystyle X_{t}\sim \nu _{a_{t}}} from the corresponding distribution. We will note μ ∗ := max μ a {\displaystyle \mu ^{}:=\max \mu _{a}} the highest mean. An arm a {\displaystyle a} that satisfies μ a = μ ∗ {\displaystyle \mu _{a}=\mu ^{}} is called an optimal arm; otherwise it is called suboptimal arm. In best arm identification (BAI) the objective is to identify an optimal arm. Two main settings for BAI appear in the literature: Fixed confidence: In this setting, one typically assumes that there exists a unique optimal arm. A confidence level δ ∈ ( 0 , 1 ) {\displaystyle \delta \in (0,1)} is specified at the beginning. The algorithm must stop at some finite stopping time τ δ < + ∞ {\displaystyle \tau _{\delta }<+\infty } and return an arm a ^ τ δ {\displaystyle {\hat {a}}_{\tau _{\delta }}} such that the probability of error is bounded: P ( a ^ τ δ ≠ a ∗ ) ≤ δ {\displaystyle \mathbb {P} ({\hat {a}}_{\tau _{\delta }}\neq a^{})\leq \delta } . The objective is to minimize the expected sample complexity E [ τ δ ] {\displaystyle \mathbb {E} [\tau _{\delta }]} . Such a setting appears, for example, when a constraint on the confidence is required (for example, if we require a confidence level of 95%, so δ = 1 − 0.95 = 0.05 {\displaystyle \delta =1-0.95=0.05} ). Fixed horizon: In this setting, the number of samples T {\displaystyle T} is fixed in advance. The goal is to design an algorithm that minimizes the probability of misidentifying the optimal arm: P ( a ^ T ≠ a ∗ ) {\displaystyle \mathbb {P} ({\hat {a}}_{T}\neq a^{})} . This setting appears when the number of experiments is limited (for drug tests, the number of patients can be fixed in advance). === Example of simple modelling === In the case where we have K {\displaystyle K} treatments and we want to be sure with a confidence level of 95% which treatment is the best to heal a specific disease. Each treatment heals or does not heal the disease with a probability μ k {\displaystyle \mu _{k}} , which means that each distribution is a Bernoulli distribution, so D {\displaystyle {\mathcal {D}}} is the set of Bernoulli distributions. We can use a BAI algorithm to minimize E [ τ 0.05 ] {\displaystyle \mathbb {E} [\tau _{0.05}]} , the number of patients required to find the best treatment with probability 95%. == Applications == Best arm identification naturally arises in several practical domains: Adaptive clinical trials: The objective is to identify the most effective treatment based on sequentially collected patient data. Each treatment can be modeled as having an underlying distribution of outcomes. The goal is to identify the treatment with the highest expected outcome with high confidence (fixed confidence setting δ {\displaystyle \delta } ) while minimizing the number of drug test patients (minimise E [ τ δ ] {\displaystyle \mathbb {E} [\tau _{\delta }]} ), as it costs to pay patients for this and we would like to use as little as possible less effective drugs. Hyperparameter tuning: Selecting the best configuration for machine learning models efficiently by treating each hyperparameter setting as an arm. The goal is to find the best hyperparameter with as few experiments possible as experiments are costly in time and in energy == Fixed confidence level == In the fixed-confidence setting, the goal is to design an algorithm that identifies the best arm with a prescribed confidence level δ {\displaystyle \delta } while minimizing the expected number of samples. Any such algorithm requires two key components: Stopping rule: A decision criterion that determines when to stop sampling. Formally, this defines a stopping time τ δ {\displaystyle \tau _{\delta }} and returns an arm a ^ τ δ {\displaystyle {\hat {a}}_{\tau _{\delta }}} such that P ( a ^ τ δ ≠ a ⋆ ) ≤ δ {\displaystyle \mathbb {P} ({\hat {a}}_{\tau _{\delta }}\neq a^{\star })\leq \delta } and P ( τ δ < + ∞ ) = 1 {\displaystyle \mathbb {P} (\tau _{\delta }<+\infty )=1} . Sampling rule: A policy π {\displaystyle \pi } that, at each round t {\displaystyle t} , selects the next arm to sample a t {\displaystyle a_{t}} based on all previous observations ( a s , X s ) s < t {\displaystyle (a_{s},X_{s})_{s Read more →

• 

  ISO 15926

  ISO 15926 is a standard for data integration, sharing, exchange, and hand-over between computer systems. The title, "Industrial automation systems and integration—Integration of life-cycle data for process plants including oil and gas production facilities", is regarded too narrow by the present ISO 15926 developers. Having developed a generic data model and reference data library for process plants, it turned out that this subject is already so wide, that actually any state information may be modelled with it. == History == In 1991 a European Union ESPRIT-, named ProcessBase, started. The focus of this research project was to develop a data model for lifecycle information of a facility that would suit the requirements of the process industries. At the time that the project duration had elapsed, a consortium of companies involved in the process industries had been established: EPISTLE (European Process Industries STEP Technical Liaison Executive). Initially individual companies were members, but later this changed into a situation where three national consortia were the only members: PISTEP (UK), POSC/Caesar (Norway), and USPI-NL (Netherlands). (later PISTEP merged into POSC/Caesar, and USPI-NL was renamed to USPI). EPISTLE took over the work of the ProcessBase project. Initially this work involved a standard called ISO 10303-221 (referred to as "STEP AP221"). In that AP221 we saw, for the first time, an Annex M with a list of standard instances of the AP221 data model, including types of objects. These standard instances would be for reference and would act as a knowledge base with knowledge about the types of objects. In the early nineties EPISTLE started an activity to extend Annex M to become a library of such object classes and their relationships: STEPlib. In the STEPlib activities a group of approx. 100 domain experts from all three member consortia, spread over the various expertises (e.g. Electrical, Piping, Rotating equipment, etc.), worked together to define the "core classes". The development of STEPlib was extended with many additional classes and relationships between classes and published as Open source data. Furthermore, the concepts and relation types from the AP221 and ISO 15926-2 data models were also added to the STEPlib dictionary. This resulted in the development of Gellish English, whereas STEPlib became the Gellish English dictionary. Gellish English is a structured subset of natural English and is a modeling language suitable for knowledge modeling, product modeling and data exchange. It differs from conventional modeling languages (meta languages) as used in information technology as it not only defines generic concepts, but also includes an English dictionary. The semantic expression capability of Gellish English was significantly increased by extending the number of relation types that can be used to express knowledge and information. For modelling-technical reasons POSC/Caesar proposed another standard than ISO 10303, called ISO 15926. EPISTLE (and ISO) supported that proposal, and continued the modelling work, thereby writing Part 2 of ISO 15926. This Part 2 has official ISO IS (International Standard) status since 2003. POSC/Caesar started to put together their own RDL (Reference Data Library). They added many specialized classes, for example for ANSI (American National Standards Institute) pipe and pipe fittings. Meanwhile, STEPlib continued its existence, mainly driven by some members of USPI. Since it was clear that it was not in the interest of the industry to have two libraries for, in essence, the same set of classes, the Management Board of EPISTLE decided that the core classes of the two libraries shall be merged into Part 4 of ISO 15926. This merging process has been finished. Part 4 should act as reference data for part 2 of ISO 15926 as well as for ISO 10303-221 and replaced its Annex M. On June 5, 2007 ISO 15926-4 was signed off as a TS (Technical Specification). In 1999 the work on an earlier version of Part 7 started. Initially this was based on XML Schema (the only useful W3C Recommendation available then), but when Web Ontology Language (OWL) became available it was clear that provided a far more suitable environment for Part 7. Part 7 passed the first ISO ballot by the end of 2005, and an implementation project started. A formal ballot for TS (Technical Specification) was planned for December 2007. However, it was decided then to split Part 7 into more than one part, because the scope was too wide. == Need for ISO15926 == In 2004, the National Institute of Standards and Technology (NIST) released a report on the impact of the lack of digital interoperability in the capital projects industry. The report estimated the cost of inadequate interoperability in the U.S. capital facilities industry to be $15.8 billion per year. This was considered likely to be a conservative figure. == The standard == ISO 15926 has thirteen parts (as of February 2022): Part 1 - Overview and fundamental principles Part 2 - Data model Part 3 - Reference data for geometry and topology Part 4 - Reference Data, the terms used within facilities for the process industry Part 6 - Methodology for the development and validation of reference data (under development) Part 7 - Template methodology Part 8 - OWL/RDF implementation Part 9 - Implementation standards, with the focus on standard web servers, web services, and security (under development) Part 10 - Conformance testing Part 11 - Methodology for simplified industrial usage of reference data (under development) Part 12 - Life cycle integration ontology in Web Ontology Language (OWL2) Part 13 - Integrated lifecycle asset planning === Description === The model and the library are suitable for representing lifecycle information about technical installations and their components. They can also be used for defining the terms used in product catalogs in e-commerce. Another, more limited, use of the standard is as a reference classification for harmonization purposes between shared databases and product catalogues that are not based on ISO 15926. The purpose of ISO 15926 is to provide a Lingua Franca for computer systems, thereby integrating the information produced by them. Although set up for the process industries with large projects involving many parties, and involving plant operations and maintenance lasting decades, the technology can be used by anyone willing to set up a proper vocabulary of reference data in line with Part 4. In Part 7 the concept of Templates is introduced. These are semantic constructs, using Part 2 entities, that represent a small piece of information. These constructs then are mapped to more efficient classes of n-ary relations that interlink the Nodes that are involved in the represented information. In Part 8 the Part 7 Templates are defined in OWL and instantiated in RDF. For validation and reasoning purposes all are represented in First-Order Logic as well. In Part 9 these Node and Template instances are stored in an RDF triple store, set up to a standard schema and an API. Each participating computer system maps its data from its internal format to such ISO-standard Node and Template instances. Data can be "handed over" from one triple store to another in cases where data custodianship is handed over (e.g. from a contractor to a plant owner, or from a manufacturer to the owners of the manufactured goods). Hand-over can be for a part of all data, whilst maintaining full referential integrity. Documents are user-definable. They are defined in XML Schema and they are, in essence, only a structure containing cells that make reference to instances of Templates. This represents a view on all lifecycle data: since the data model is a 4D (space-time) model, it is possible to present the data that was valid at any given point in time, thus providing a true historical record. It is expected that this will be used for Knowledge Mining. Data can be queried by means of SPARQL. In any implementation a restricted number of triple stores can be involved, with different access rights. This is done by means of creating a CPF Server (= Confederation of Participating Façades). An Ontology Browser allows for access to one or more triple stores in a given CPF, depending on the access rights. == Projects and applications == There are a number of projects working on the extension of the ISO 15926 standard in different application areas. === Capital-intensive projects === Within the application of Capital Intensive projects, some cooperating implementation projects are running: The DEXPI project: The objective of DEXPI is to develop and promote a general standard for the process industry covering all phases of the lifecycle of a (petro-)chemical plant, ranging from specification of functional requirements to assets in operation. Finalised projects include: The EDRC Project of FIATECH Capturing Equipment Data Requirements Using ISO 15926 and Assessing Conforma

  Read more →
• 

  Database dump

  A database dump contains a record of the table structure and/or the data from a database and is usually in the form of a list of SQL statements ("SQL dump"). A database dump is most often used for backing up a database so that its contents can be restored in the event of data loss. Corrupted databases can often be recovered by analysis of the dump. Database dumps are often published by free content projects, to facilitate reuse, forking, offline use, and long-term digital preservation. Dumps can be transported into environments with Internet blackouts or otherwise restricted Internet access, as well as facilitate local searching of the database using sophisticated tools such as grep.

  Read more →
• 

  List of algorithms

  An algorithm is a fundamental set of rules or defined procedures that are typically designed and used to be a simpler way to solve a specific problem or a broad set of problems. Simply speaking, algorithms define different processes, sets of rules and regulations, or methodologies that are to be followed through in calculations, data processing, data mining, pattern recognition, automated reasoning or other problem-solving operations. With the increasing automation of services, more and more decisions are being made by algorithms. Some general examples are risk assessments, anticipatory policing, and pattern recognition technology. The following is a list of well-known algorithms. == Automated planning == == Combinatorial algorithms == === General combinatorial algorithms === Brent's algorithm: finds a cycle in function value iterations using only two iterators Floyd's cycle-finding algorithm: finds a cycle in function value iterations Gale–Shapley algorithm: solves the stable matching problem Pseudorandom number generators (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality): ACORN generator Blum Blum Shub Lagged Fibonacci generator Linear congruential generator Mersenne Twister === Graph algorithms === Blossom algorithm: algorithm for constructing maximum-cardinality matching on graphs. Coloring algorithm: algorithms for graph (vertex or edge) coloring (subject to constraints, e.g. proper coloring or list coloring) Hopcroft–Karp algorithm: convert a bipartite graph to a maximum-cardinality matching Hungarian algorithm: algorithm for finding a perfect matching Prüfer coding: conversion between a labeled tree and its Prüfer sequence Tarjan's off-line lowest common ancestors algorithm: computes lowest common ancestors for pairs of nodes in a tree Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies. ==== Graph drawing ==== Coin graph drawing algorithms for finite connected planar graphs (approximately computing the theoretical circle-packing given by the Koebe-Andreev-Thurston theorem). See also Fáry's theorem on straight-line drawings of planar graphs. Force-based algorithms (also known as force-directed algorithms or spring-based algorithms) Spectral layout ==== Network theory ==== Network analysis Link analysis Girvan–Newman algorithm: detect communities in complex systems Web link analysis Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities) PageRank TrustRank Flow networks Dinic's algorithm: is a strongly polynomial algorithm for computing the maximum flow in a flow network. Edmonds–Karp algorithm: implementation of Ford–Fulkerson Ford–Fulkerson algorithm: computes the maximum flow in a graph Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph Push–relabel algorithm: computes a maximum flow in a graph ==== Routing for graphs ==== Edmonds' algorithm (also known as Chu–Liu/Edmonds' algorithm): find maximum or minimum branchings Euclidean minimum spanning tree: algorithms for computing the minimum spanning tree of a set of points in the plane Longest path problem: find a simple path of maximum length in a given graph Minimum spanning tree Borůvka's algorithm Kruskal's algorithm Prim's algorithm Reverse-delete algorithm Nonblocking minimal spanning switch say, for a telephone exchange Shortest path problem Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative) Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph Johnson's algorithm: all pairs shortest path algorithm in sparse weighted directed graph Transitive closure problem: find the transitive closure of a given binary relation Traveling salesman problem Christofides algorithm Nearest neighbour algorithm Vehicle routing problem Clarke and Wright Saving algorithm Warnsdorff's rule: a heuristic method for solving the Knight's tour problem ==== Graph search ==== A: special case of best-first search that uses heuristics to improve speed B: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals) Backtracking: abandons partial solutions when they are found not to satisfy a complete solution Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement Beam stack search: integrates backtracking with beam search Best-first search: traverses a graph in the order of likely importance using a priority queue Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph Breadth-first search: traverses a graph level by level Brute-force search: an exhaustive and reliable search method, but computationally inefficient in many applications D: an incremental heuristic search algorithm Depth-first search: traverses a graph branch by branch Dijkstra's algorithm: a special case of A for which no heuristic function is used General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine. Iterative deepening depth-first search (IDDFS): a state space search strategy Jump point search: an optimization to A which may reduce computation time by an order of magnitude using further heuristics Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph SSS: state space search traversing a game tree in a best-first fashion similar to that of the A search algorithm Uniform-cost search: a tree search that finds the lowest-cost route where costs vary ==== Subgraphs ==== Cliques Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph MaxCliqueDyn maximum clique algorithm: find a maximum clique in an undirected graph Strongly connected components Kosaraju's algorithm Path-based strong component algorithm Tarjan's strongly connected components algorithm Subgraph isomorphism problem === Sequence algorithms === ==== Approximate sequence matching ==== Bitap algorithm: fuzzy algorithm that determines if strings are approximately equal. Phonetic algorithms Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames Double Metaphone: an improvement on Metaphone Match rating approach: a phonetic algorithm developed by Western Airlines Metaphone: an algorithm for indexing words by their sound, when pronounced in English NYSIIS: phonetic algorithm, improves on Soundex Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English String metrics: computes a similarity or dissimilarity (distance) score between two pairs of text strings Damerau–Levenshtein distance: computes a distance measure between two strings, improves on Levenshtein distance Dice's coefficient (also known as the Dice coefficient): a similarity measure related to the Jaccard index Hamming distance: sum number of positions which are different Jaro–Winkler distance: is a measure of similarity between two strings Levenshtein edit distance: computes a metric for the amount of difference between two sequences Trigram search: search for text when the exact syntax or spelling of the target object is not precisely known ==== Selection algorithms ==== Introselect Quickselect ==== Sequence search ==== Linear search: locates an item in an unsorted sequence Selection algorithm: finds the kth largest item in a sequence Sorted lists Binary search algorithm: locates an item in a sorted sequence Eytzinger binary search: cache friendly binary search algorithm Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers Jump search (or block search): linear search on a smaller subset of the sequence Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search. Uniform binary search: an optimization of the classic binary search algorithm Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa ==== Sequence merging ==== k-way merge algorithm Simple merge algorithm Union (merge, with elements on the output not repeated) ==== Sequence permutations ==== Fisher–Yates shuffle (also known as the Knuth shuffle): randomly shuffle a finite set Heap's permutation generation algorithm: interchange elements to generate next permutation Schensted algorithm: constructs a pair of Young tableaux from a permutation Steinhaus–Johnson–Trotter algorithm (also known as the Johnson–Trotter algorithm):

  Read more →
• 

  Algorithmic game theory

  Algorithmic game theory (AGT) is an interdisciplinary field at the intersection of game theory and computer science, focused on understanding and designing algorithms for environments where multiple strategic agents interact. This research area combines computational thinking with economic principles to address challenges that emerge when algorithmic inputs come from self-interested participants. In traditional algorithm design, inputs are assumed to be fixed and reliable. However, in many real-world applications—such as online auctions, internet routing, digital advertising, and resource allocation systems—inputs are provided by multiple independent agents who may strategically misreport information to manipulate outcomes in their favor. AGT provides frameworks to analyze and design systems that remain effective despite such strategic behavior. The field can be approached from two complementary perspectives: Analysis: Evaluating existing algorithms and systems through game-theoretic tools to understand their strategic properties. This includes calculating and proving properties of Nash equilibria (stable states where no participant can benefit by changing only their own strategy), measuring price of anarchy (efficiency loss due to selfish behavior), and analyzing best-response dynamics (how systems evolve when players sequentially optimize their strategies). Design: Creating mechanisms and algorithms with both desirable computational properties and game-theoretic robustness. This sub-field, known as algorithmic mechanism design, develops systems that incentivize truthful behavior while maintaining computational efficiency. Algorithm designers in this domain must satisfy traditional algorithmic requirements (such as polynomial-time running time and good approximation ratio) while simultaneously addressing incentive constraints that ensure participants act according to the system's intended design. == History == === Nisan-Ronen: a new framework for studying algorithms === In 1999, the seminal paper of Noam Nisan and Amir Ronen drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract: We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents’ interests are best served by behaving correctly. Following notions from the field of mechanism design, we suggest a framework for studying such algorithms. In this model the algorithmic solution is adorned with payments to the participants and is termed a mechanism. The payments should be carefully chosen as to motivate all participants to act as the algorithm designer wishes. We apply the standard tools of mechanism design to algorithmic problems and in particular to the shortest path problem. This paper coined the term algorithmic mechanism design and was recognized by the 2012 Gödel Prize committee as one of "three papers laying foundation of growth in Algorithmic Game Theory". === Price of Anarchy === The other two papers cited in the 2012 Gödel Prize for fundamental contributions to Algorithmic Game Theory introduced and developed the concept of "Price of Anarchy". In their 1999 paper "Worst-case Equilibria", Koutsoupias and Papadimitriou proposed a new measure of the degradation of system efficiency due to the selfish behavior of its agents: the ratio of between system efficiency at an optimal configuration, and its efficiency at the worst Nash equilibrium. (The term "Price of Anarchy" only appeared a couple of years later.) === The Internet as a catalyst === The Internet created a new economy—both as a foundation for exchange and commerce, and in its own right. The computational nature of the Internet allowed for the use of computational tools in this new emerging economy. On the other hand, the Internet itself is the outcome of actions of many. This was new to the classic, ‘top-down’ approach to computation that held till then. Thus, game theory is a natural way to view the Internet and interactions within it, both human and mechanical. Game theory studies equilibria (such as the Nash equilibrium). An equilibrium is generally defined as a state in which no player has an incentive to change their strategy. Equilibria are found in several fields related to the Internet, for instance financial interactions and communication load-balancing. Game theory provides tools to analyze equilibria, and a common approach is then to ‘find the game’—that is, to formalize specific Internet interactions as a game, and to derive the associated equilibria. Rephrasing problems in terms of games allows the analysis of Internet-based interactions and the construction of mechanisms to meet specified demands. If equilibria can be shown to exist, a further question must be answered: can an equilibrium be found, and in reasonable time? This leads to the analysis of algorithms for finding equilibria. Of special importance is the complexity class PPAD, which includes many problems in algorithmic game theory. == Areas of research == === Algorithmic mechanism design === Mechanism design is the subarea of economics that deals with optimization under incentive constraints. Algorithmic mechanism design considers the optimization of economic systems under computational efficiency requirements. Typical objectives studied include revenue maximization and social welfare maximization. === Inefficiency of equilibria === The concepts of price of anarchy and price of stability were introduced to capture the loss in performance of a system due to the selfish behavior of its participants. The price of anarchy captures the worst-case performance of the system at equilibrium relative to the optimal performance possible. The price of stability, on the other hand, captures the relative performance of the best equilibrium of the system. These concepts are counterparts to the notion of approximation ratio in algorithm design. === Complexity of finding equilibria === The existence of an equilibrium in a game is typically established using non-constructive fixed point theorems. There are no efficient algorithms known for computing Nash equilibria. The problem is complete for the complexity class PPAD even in 2-player games. In contrast, correlated equilibria can be computed efficiently using linear programming, as well as learned via no-regret strategies. === Computational social choice === Computational social choice studies computational aspects of social choice, the aggregation of individual agents' preferences. Examples include algorithms and computational complexity of voting rules and coalition formation. Other topics include: Algorithms for computing Market equilibria Fair division Multi-agent systems And the area counts with diverse practical applications: Sponsored search auctions Spectrum auctions Cryptocurrencies Prediction markets Reputation systems Sharing economy Matching markets such as kidney exchange and school choice Crowdsourcing and peer grading Economics of the cloud == Journals and newsletters == ACM Transactions on Economics and Computation (TEAC) SIGEcom Exchanges Algorithmic Game Theory papers are often also published in Game Theory journals such as GEB, Economics journals such as Econometrica, and Computer Science journals such as SICOMP.

  Read more →