Title: Informatik 1 / Definition

Q: executable
A: File of UNIX commands

Q: Hihger-level language
A: Human-readable and portable --> will work on any computer such as C++

Q: Machine language (assembler)
A: Not human-readable and also not portable --> each processor type employs its own assembler language

Q: compiler
A: Translates program into assembler language

Q: variable, type
A: A piece of computer memory that can be used in a program to store, retrieve and manipulate data; it is characterised by a type, which specifies what kind of data is stored and how much memory it requires

Q: Declaration statement
A: Binds variable name to its type and allocates corresponding space in the computer memory

Q: Syntactic errors
A: Errors spotted by the compiler

Q: debugging
A: Fixing a program such that it runs

Q: Semantic errors
A: Variable used before being set; runtime errors; endless loop or "segmentation fault" are often hints at semantic errors

Q: flow-control statements
A: Conditional and iterative statements

Q: Indentation
A: Addition of a number of white spaces at the start of each line

Q: scope
A: Definition range of a function/variable --> outside of this range the program will not know about is --> limited to a program block in which it is declared {...}

Q: global
A: If a function/variable is declared outside of any blocks {...} in a program. --> scope extends to entire source file

Q: library
A: A collection of predefined functions that can be used in the program thorugh #include<...>

Q: Header file
A: Gathers the prototypes of all functions defined in the library.

Q: Object files
A: Contain the definitions of the functions already compiled to assembler.

Q: Convergence
A: How fast a value converges to its limit upon some increasing parameter N.

Q: Scaling
A: Tells how much the computed time needed will increase upon an increasing parameter N. Commonly written in the big O notation --> O[N^x], omitting prefactors and valid for large N.

Q: array
A: Ordered list of variables of the same type, where each variable can be accessed by means of an integer indice.

Q: rank of an array
A: Refers to the nomenclature used for tensors in mathematics: rank-one --> vector, rank-two --> matrix

Q: dimension of an array
A: Number of elements it can contain. An array of dimension N runs from a[0] to a[N-1].

Q: Moore's law
A: The computing power increases on average by a factor 10 every six years.

Q: Computers are...
A: - silly (they don't understand what they are doing)
- tireless (they can perform repetitive tasks forever without complaint)
- reliable (they always give the same output for the same input)
- finite & discrete (they can only handle material that can be mapped to a finite sequence of zero's and one's)
- suited for tasks that can be decomposed precisely in a sequence of simple steps, have to be repeated many times and must be carried out fast

Q: algorithm
A: - the formulation of a procedure to solve a problem that is suitable for a computer
- consists of a sequence of steps involving simple operations
- when an algorithm is carried out by a computer this is called a process

Q: CPU
A: - central processing unit

Q: flop
A: floating-point operation per second

Q: Analog and digital
A: Refers to the way information is stored, processed, transmitted or displayed

Q: bit
A: - Binary information ticket
- represents an information element with two states

Q: Byte multiples
A: Powers of 2 grouped by approximate powers of 10 owing to 2^10= 1024 ≅ 1000

Q: Number system
A: Defined by a chosen base b and a set of b digit symbols (characters) one of them being zero. An arbitrary positive integer number n is then written as a collection of p digits.
F. ex. the binary system relies on a base b=2 and the associated digits {0,1}

Floating-point representation

Q: Loss of significance
A: Corresponds to errors caused by operations producing too small or too large numbers

Q: Overflow
A: Corresponds to x + y too large for a word (also x*y)

Q: Underflow
A: Corresponds to x*y too small for a word

Q: MOSFET
A: - metal-oxide-semidonductor field-effect transistor
- rely on the properties of semi-conductors
- in the E-type, the material goes from insulant to conductor under an applied electric field
- in the D-type, the material goes from conductor to insulant under an applied electric field
- can be used to build three basic types of logic gates --> NOT, AND, OR

Q: Truth table
A: To determine what a circuit does

Q: Clock rate of a processor
A: The frequency at which successive input batches can be processed

Q: Overclocking
A: Increase the clock rate to a limited extent by increasing the CPU core voltage
--> stronger circuits and faster recovery, but also increases power requirement and heating

Q: Algorithmic errors
A: The program will run but it will spit out nonsense because there is an incorrect employment of logics or/and model

Q: Numerical errors
A: - roundoff errors --> finite precision
- truncation errors
- instability errors --> amplification of small error in starting values through increasing iteration

Q: Recursive algorithm
A: An algorithm involving a function that calls itself; recursion is clearly more elegant but iteration is often more efficient

Q: The sentinel trick
A: By extending the array with one dummy element (the sentinel) set to x, we avoid N comparisons in the algorithm

Q: Instruction Set Architecture (ISA)
A: - Corresponds to the set of machine code instructions implemented in a processor
- there are two main categories
  1. Complex Instructions Set Computer (CISC): implement a great variety of complex instructions
  2. Reduced Instruction Set Computer (RISC): implement a small set of simple instructions --> the trend nowadays

Q: Numerical analysis
A: The field concerned with numerical algorithms --> algorithms that attempt to solve problems in a numerical (real-number manipulations) as opposed to an analytical (symbolic) fashion.

Q: Brute force algorithms
A: Try all combinations one by one, the hard way; one of six algorithmic strategies

Q: Greedy algorithms
A: Always select the option which yields the largest immediate progress towards the goal i.e. is locally optimal; one of six algorithmic strategies

Q: Divide and conquer algorithms
A: Split the problem into (usually two) smaller sub-problems, solve these, and combine the solutions; one of six algorithmic strategies

Q: Dynamic programming algorithms
A: Solve all the subproblems, store the solutions in a table, use the solutions of the subproblems to solve the problem; one of six algorithmic strategies

Q: Local search algorithms
A: Guess an arbitrary solution, define/perform local transformation to an alternative solution; if it is better, store it, otherwise discard it; and iterate this procedure; one of six algorithmic strategies

Q: Backtracking and pruning algorithms
A: Rank all possible solutions in a tree, traverse the tree, keep track of the best solution so far, skip the subtrees that cannot contain a better solution; one of six algorithmic strategies

Q: Computer network
A: An interconnected collection of autonomous computers

Q: Interconnected
A: The computers are able to exchange information

Q: Autonomous
A: No clear master/slave relation between computers

Q: Distributed system
A: A set of slave computers subordinated to a master; the existence of multiple autonomous computers is not visible to the users, only to the operating system; the system chooses a machine to carry out the task and behaves like a virtual single computer

Q: Network goals
A: - share resources
- provide stability
- reduce costs
- speed up communication

Q: Internet
A: Associated networks of different topologies

Q: Baudrate
A: Number of (possible) changes of signal per second