Prog comp — Cours 1 -Notes de cours et TD Flashcards

Front

Identity

Back

A function that returns its argument unchanged. It is the simplest unary function and is useful as a default or placeholder in higher-order programming.

Front

Integer sqrt

Back

Computes the largest integer i such that i*i <= n by enumerating integers from 1 until the condition holds. Can be written iteratively or recursively; the recursive version may or may not be tail-recursive depending on implementation.

Front

Fibonacci (recursive)

Back

Defines $fib$ by $fib(1)=1$, $fib(2)=1$ and $fib(n)=fib(n-2)+fib(n-1)$ for $n>2$. The straightforward recursive implementation follows this definition exactly, produces a tree of calls, and has exponential time complexity.

Front

Fibonacci cost

Back

The naive recursive Fibonacci has exponential cost because it recomputes subproblems many times; specifically its time complexity grows roughly like the golden ratio to the power of n. It also uses linear call-stack depth and is not tail-recursive in the naive form.

Front

Tail recursion

Back

A recursive function is tail-recursive if the final action of the function is the recursive call, allowing some compilers/runtimes to reuse the current stack frame. Tail recursion can be transformed into an iterative loop and therefore avoids growing the call stack.

Front

Iterative Fibonacci

Back

A linear-time implementation that computes the n-th Fibonacci number by iterating and carrying two accumulators for consecutive Fibonacci values. This approach runs in $O(n)$ time and constant space and is tail-recursive or directly iterative depending on language.

Front

Parity functions

Back

Functions that return true if an integer is even (or odd) and false otherwise, implemented using only the predecessor operation and comparison to 0. Such constraints force use of recursion or iteration to decrement and test, illustrating low-level arithmetic-only programming.

Front

itrans type

Back

In the provided OCaml code, itrans takes a square matrix represented as a mutable 2D array, so its type is typically 'int array array -> unit'. The function swaps symmetric elements in-place to transpose the matrix.

Front

itrans effect

Back

Calling itrans on a concrete matrix mutates the matrix in memory by swapping elements (i,j) and (j,i) for j>=i, resulting in the transposed matrix. The operation is in-place and thus no new matrix is allocated, demonstrating effects of mutable arrays.

Front

map

Back

A higher-order function that takes a function f and a list (or array) and returns a new list of applications of f to each element. map illustrates functional programming by treating functions as first-class values and avoiding mutation.

Front

compose

Back

Takes two functions and a list and chains the computations so that each element is processed by both functions in sequence. Composition supports building complex behavior by combining simpler functions in a functional style.

Front

Binary search

Back

An algorithm that checks whether a value is present in a sorted array by repeatedly halving the search interval. The provided C-style code computes a mid index, compares, adjusts lo/hi, and terminates when the element is found or the interval is empty; it can be converted to a recursive form that may or may not be tail-recursive depending on structure.

Front

Subset-sum check

Back

A recursive backtracking function (check_inner) tests whether a target can be obtained by summing a selected subset of source elements. It explores two branches per element (take or skip), returns true if target becomes zero, and demonstrates exponential search with simple recursion patterns.

Front

Command-line args

Back

Programs can access command-line arguments differently across languages: OCaml via Sys.argv, Java via main(String[] args), C via main(int argc, char **argv), and Python via sys.argv. Using these mechanisms lets small programs accept input like an integer n to compute and print results (e.g., fibonacci).

Front

Naive exponentiation

Back

Defines $x^{n+1}=x * x^n$ and implements exponentiation by multiplying $x$ by itself $n$ times recursively. The naive recursion has linear recursion depth and $O(n)$ multiplications; it can be written tail-recursively to avoid stack growth.

Front

Fast exponentiation

Back

Uses the rules: if n=2*p then $x^n=(x*x)^p$, and if n=2*p+1 then $x^n=x*(x*x)^p$, halving the exponent at each step. This yields a logarithmic-time algorithm (exponentiation by squaring) with $O(\log n)$ multiplications and can be implemented recursively or in tail-recursive/iterative form.

Front

Manhattan distance

Back

Computes shortest path distances on a grid measured as the sum of horizontal and vertical steps, filling a world matrix from a source coordinate while treating wall cells as impassable. The provided recursive flood-fill and a queue-based tail-recursive (BFS) version demonstrate propagation of distances and differences between recursive DFS-like exploration and iterative BFS.

Front

Imperative

Back

A programming style where the program describes a sequence of explicit state-changing operations to perform in order. It tends to be close to machine execution and includes constructs like assignment, loops, and mutable data structures.

Front

Declarative

Back

Specifies what result is desired rather than how to compute it, favoring equations, high-level abstractions, and immutability. Functional and logic programming are substyles that emphasize describing computation outcomes over stepwise state updates.

Front

Procedural

Back

A substyle of imperative programming emphasizing decomposition into procedures or functions, structured control constructs (if/for/while), and modular data organization. It focuses on sequences of commands and local scopes for readability and maintainability.

Front

Object-oriented

Back

Combines data and operations into objects with encapsulation, methods, and fields to model entities; supports abstraction, polymorphism, and modular design. Languages like Java emphasize classes and strong encapsulation while others (Python, OCaml) offer more flexible object models.

Front

Functional programming

Back

Treats computation as evaluation of functions, favors immutability, higher-order functions, and recursion rather than mutable state and loops. Functions are first-class values, enabling composition, partial application, and clearer reasoning via referential transparency.

Front

Lambda

Back

An anonymous function expression used to create function values concisely (e.g., fun x -> expr in OCaml or lambda x: expr in Python). Lambdas enable higher-order programming and are often captured into closures when they reference surrounding variables.

Front

Closure

Back

A function value together with the environment of bound variables it captured at creation time, allowing the function to access those variables later. Closures enable local function factories, callbacks, and safe encapsulation of state in functional code.

Front

Currying

Back

Transforming a function that takes multiple arguments into a sequence of functions each taking a single argument, enabling partial application. In languages like OCaml, functions are curried by default and partial application is a common style for reuse.

Front

Static typing

Back

A typing discipline where variable and expression types are known at compile time, enabling early error detection and optimizations. Languages like OCaml, Java and C use static typing (with OCaml favoring type inference), which restricts possible values a variable can hold.

Front

Dynamic typing

Back

Type checks are deferred to runtime so variables can hold values of any type and types may be interrogated or modified during execution. This offers flexibility (as in Python) but shifts some error detection to execution time and can require runtime type tests.

Front

Expression vs instruction

Back

An expression evaluates to a value, while an instruction performs an action (possibly without returning a useful value). Expression-oriented languages (like OCaml) treat constructs uniformly as values, whereas instruction-oriented languages (like C/Java) distinguish actions and statements.