ComputerScienceGlossaryOld

From Motley Bytes Wiki
Jump to: navigation, search

Computer Science Glossary of Terms and Abbreviations

  • API: Application Programming Interface.
  • AVL: As in AVL tree. Named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. The heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where {\displaystyle n} n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
  • Big Οh or Big Omicron: Provides a growth rate for an algorithm's upper bound. Worst case.
    • General notation: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(N) = \Omicron(f(N))} (Means "is" or "satisfies", not exact equivalence.)
    • Meaning: For all N ≥ 1, a positive constant c exists such that T(N) ≤ cf(N).
  • Big Omega: Provides a growth rate for an algorithm's lower bound. Best case.
    • General notation: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(N) = \Omega(f(N))}
    • Meaning: For all N ≥ 1, a positive constant c exists such that T(N) ≥ cf(N).
  • Big Theta: Provides a growth rate that is both an upper and lower bound. Sort of average case.
    • General notation: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(N) = \Theta(f(N))}
    • Meaning: For all N ≥ 1, T(N) = Ο(f(N) and T(N) = Ω(f(N)).
  • Complexity class: The set of problems that can be solved using a specific amount of computational resources.
  • CORBA: The Common Object Request Broker Architecture is a standard defined by the Object Management Group (OMG) designed to facilitate the communication of systems that are deployed on diverse platforms. Opinion: CORBA popularity seems to be fading, probably because of complexity issues.
  • GTK+: Formerly GIMP Toolkit. A cross-platform widget toolkit for creating graphical user interfaces. It is, along with Qt, one of the most popular toolkits for Wayland and X11 windowing systems.
  • Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.
  • Heuristic algorithm: An algorithm that quickly determines a near optimal or approximate solution.
  • HMVC: Hierarchical Model–View–Controller.
  • IDL: Interface description language, any computer language used to describe a software component's interface. For example, OMG IDL for CORBA.
  • IIOP: Internet Inter-ORB Protocol is a protocol that makes it possible for distributed programs written in different programming languages to communicate over the Internet. IIOP is a critical part of a strategic industry standard, the Common Object Request Broker Architecture (CORBA).
  • MVA: Model–view–adapter.
  • MVC: Model–view–controller is an architectural pattern commonly used for developing user interfaces that divides an application into three interconnected parts.
    • Components:
      • The model is the central component of the pattern. It is the application's dynamic data structure, independent of the user interface. It directly manages the data, logic and rules of the application.
      • The view can be any output representation of information, such as a chart or a diagram. Multiple views of the same information are possible, such as a bar chart for management and a tabular view for accountants.
      • The controller accepts input and converts it to commands for the model or view.
    • Interactions:
      • The model is responsible for managing the data of the application. It receives user input from the controller.
      • The view means the presentation of the model in a particular format.
      • The controller responds to the user input and performs interactions on the data model objects. The controller receives the input, optionally validates it and then passes the input to the model.
    • The MVC pattern has subsequently evolved, giving rise to variants such as hierarchical model–view–controller (HMVC), model–view–adapter (MVA), model–view–presenter (MVP), model–view–viewmodel (MVVM), and others that adapted MVC to different contexts.
  • MVP: Model–view–presenter (MVP).
  • MVVM: Model–view–viewmodel.
  • NP complexity class: The set of problems that can be solved using a non-deterministic machine in polynomial time. A non-deterministic Turing machine can be implemented as a deterministic Turing machine with at most an exponential increase in runtime complexity. So, problems in NP can be solved with at most exponential runtime complexity.
  • NP-complete complexity class: The set of problems in NP to which all other NP problems can be reduced in polynomial time. A problem A is polynomial-time reducible to another problem B if a polynomial-time algorithm exists that maps A to B, such that the solution to B provides the solution to A.
  • NP-Hard complexity class. The class NP-hard is the set of problems that are at least as hard as NP-complete.
  • OMG: Object Management Group, an international, open membership, not-for-profit technology standards consortium. Includes OMG IDL.
  • OMG IDL: The IDL for CORBA.
  • ORB: In Common Object Request Broker Architecture (CORBA), an Object Request Broker (ORB) is the programming that acts as a "broker" between a client request for a service from a distributed object or component and the completion of that request.
  • P complexity class: The set of problems that can be solved using a deterministic machine in polynomial time. A Turing machine is deterministic machine, so a problem in P can be solved using a Turing machine with a polynomial runtime complexity.
  • P ≠ NP: The generally accepted assumption, but no proof has yet been found.
  • Qt: (pronounced "cute") A cross-platform application framework and widget toolkit for creating classic and embedded graphical user applications that run on various platforms.
  • REST: Representational State Transfer.
  • RMI: Remote Method Invocation.
  • Self-adjusting heuristic: An algorithm that modifies a data structure based on how that data structure is used. Ex: Many self-adjusting data structures, such as red-black trees and AVL trees, use a self-adjusting heuristic to keep the tree balanced. Tree balancing organizes data to allow for faster access.
  • SOAP: SOAP (originally Simple Object Access Protocol) is a messaging protocol specification for exchanging structured information in the implementation of web services in computer networks.
  • Turing machine: A model of computing developed by Alan Turing to reason about general purpose computers.
    • A Turing machine has a one-dimensional tape divided into cells, where each cell can hold one symbol from a finite tape alphabet denoted by Γ (Gamma).
    • The tape alphabet must contain a blank symbol (represented by ∗) and at least one other symbol.
    • The Turing machine has a head that always points to a cell of the tape.
    • A Turing machine has a finite set of states, denoted by Q. Q includes three special states:
      • q0: The start state.
      • qacc: The accept state.
      • qrej: The reject state.
    • A Turing machine's actions are defined by a transition function δ (delta).
      • The input to the transition function is the current state and current symbol.
      • The output of the transition function is:
        • The next state.
        • The symbol to be written to the current cell
        • The direction to move the head (L denotes move left, and R denotes move right).
    • A configuration of a Turing machine consists of the tape contents, current state, and tape cell currently pointed to by the head.
    • The Turing machine proceeds in a series of steps dictated by the transition function.
      • Ex: The transition function δ(q,b) = (r,a,L) denotes that when the Turing machines is in state q and the current symbol is b, the Turing machine will write a to the current cell, transition to state r, and moves the head one cell to the left. If the head is supposed to move left and is already in the leftmost tape cell, then the head stays in the same location after the step.
  • Wayland: A computer protocol that specifies the communication between a display server and its clients.