---
title: "cpxa - Cours 1 : subject"
tags: cpxa, cours
---
{%hackmd theme-dark %}

$$
\newcommand{\vt}[3]{
\begin{pmatrix}
{#1} \\
{#2} \\
{#3}
\end{pmatrix}
}
\newcommand{\limto}[1]{\xrightarrow[#1]{}}
$$

# Complexité des algorithme - Cours 0 : Subject

[`video`](url_video)
[`cours`](url_cours)
[`slides`](url_slides)

## Introduction
$T(n)$ fonction du temps pris par l'algo en fonction de la taile de l'entrée.
complexité temporele

$S(N)$ complexité spacial (memorie)

ce que on as faire:
- notation: $O, \Theta, \Omega$
- etdude d'algo iteratif
- etude des algo recustive (notamtent les diviser pour règner)
- theoreme generale
- les algo de programation dynamique

## Orgamisation

10 semaines soit 12 seance soit 7 td.

50% exo sur moodle (30min par semaine) a faire en groupe.

50% 3 qcm le lundi matin (moodle exam).

## Rappels

$$
log_2\ log_{10}
$$

on utilise pas le $ln$ logarithme neperient et non plus $\log_a(x) = \frac{\ln(x)}{ln(a)}$

$$
\log(3000) = \log_{10} (3 \times 1000) \\
= \log_{10}(3) + \log_{10}(1000) \\
= 3 + \log_{10}(3) \\
$$

$$
\log_{10}(3141582) = log(3.141582\times 10^6) \\
\simeq 6,...
$$

autement dit
$$
10^a \le x < 10^b
\iff a\le \log_{10}(x) < b
$$

## Some classique

$$
S = \sum_{i = 0}^n i = \frac{n(n+1)}2
$$

$$
S = 2 + 4 + 6 + 8 + 10 + \dots + 100\\
S = 100 + 98 + \dots + 2 \\
S =
$$

$$
\sum_{i = 0}^{n}i^2 = \sum_{i = 0}^{n} (i + 1)^3 = \\
\sum_{i = 1}^{n +1 } i^3 = \sum_{i = 1}^{n} (n + 1)^3
\sum_{i = 0}^n (i ^3 + 3 i^2 + 3i + 1) = \sum_{i = 1}^n + \sum
$$

$$
3(n + 1)^3 = 6C(n) + 3\frac{n (n+1)}{2} + 2(n + 1) \\
C(n) = \frac{2(n+1)^3 - 3n(n+1) - 2(n+1)}6 \\
= \frac{n +1}(2n^2 + 4n +2-3n-2)6 \\
= \frac{(n+1)(2n+1)n}6
$$

$$
G=\sum_{i=0}^n x^i \\
G = 1 + x + x^2 + \dots + x^n \\
xG = x + x^2 + \dots + x^n + x^{n+1} \\
(x-1)G = x^{n+1} -1\\
G = \frac{x^{n+1} - 1}{x-1}
$$

si $x = 1$

$$
\lim_{x\to 1} \frac{x^{n+1} - 1}{x-1} = \lim_{x\to1}\frac{(n+1)x^n}1 = n + 1
$$

> voire la regle de l'hopital

## Notation partie entiere

- $\lfloor x \rfloor$ = plus grand entier $\le x
- $\lceil x\rceil$ = plus petit entier $\ge x$

sert a :

$$
x \in \mathbb R , n \in \mathbb N,
x \le n
$$

def fruits(n):
  for i in range(5, n):
    print("kiwi")
    for j in range(10, 20):
      print("pomme")
    for j in range(1, i):
      print("bannane")
    for j in range(10, i):
      print("orange")

kiwi(15) = 15
pomme(15) = 100
banane(15) = 4 + 5 + 6 + ... + 13 = (4 + 13) * 10 / 2 = 85
orange(15) = 1 + 2 + 3 + 4 = 10

$$
kiwi(n) = \sum_{i = 5}^{n-1} 1 = \begin{cases} n - 5 & \text{si}\ n > 5\\ 0 \end{cases}\\
pome(n) = \sum_{i = 5}^{n-1}\sum_{j = 10}^{19} 1 = \sum_{i = 5}^{n-1} 10 = 10(n - 5) = 10\ kiwi(n) \\
banane(n) = \sum_{i = 5}^{n - 1} \sum{j=1}^{i-1} 1 = \sum_{i = 5}^{n-1}(i - 1) = \frac{(4 + n - 2)(n -5)}2 = \frac{(n+2)(n-5)}2
$$

# Sort

## selection sort

def select_sort(A):
  n = len(A)
  for i in range(0, n - 1): # n - 1 (nombre de comparaison)
    min_i = i # n - 2
    for j in range(i + 1, n)
      if A[j] < A[min_i]: # (n - 1)
      min_i = j
    swap(A, i, min_i)

## invesertion sort

def insertion_srort(A):
  n = len(A)
  for i in range(n - 1):
  k = A[i]
  j = i - 1
  while j >= 0 and A[j] > k
    A[j + 1] = A[j]
    j = j - 1
  A[j+1] = k

lineaire dans le meilleur cas
quadatique dans le cas moyen et pire cas

## arbre binaire complet