Analyse discrète et continue [T6CS011M]

Analyse discrète et continue [T6CS011M]

En pratique

Nature
Elément constitutif
Volume horaire de TD
26
Volume horaire de CM
20
Volume horaire de travail personnel
31
Langue d'enseignement
Français

Description du contenu de l'enseignement

Notions de base sur la complexité temporelle des algorithmes et le traitement des signaux déterministes.

Basic notions on time complexity of algorithms and the processing of deterministic signals

Organisation

Modalités d'organisation et de suivi

  1. analyse asymptotique
    1.         savoir utiliser les notations équivalent, "grand O" , "petit o" et Theta
    2.         calculer des équivalents de suites définies par des séries en utilisant une comparaison série intégrale
    3.         appliquer ces outils au calcul de complexité d'algorithmes écrits sous forme itérative
    4.         connaître les grandes classes de complexité (linéaire, quasi-linéaire, polynomiale, exponentielle) et les exemples important (tris naïfs, algorithme de calcul matriciel, d'arithmétique)
    5.         prolongement possible : calcul de l'asymptotique de suites définies implicitement par "amorçage/pompage" ("bootstrap")
  2. récurrences linéaires
    1.         savoir résoudre des récurrences linéaires à coefficient entiers homogène ou avec second membre de type "polynôme x exponentielle"
    2.         appliquer ces outils au calcul de complexité d'algorithmes récursifs
    3.         connaître des exemples de type "diviser pour régner" tris rapides, algorithmes de Karatsuba, de Strassen ou FFT
    4.         prolongement possibles : récurrences linéaires d'ordre 1 à coefficients non-constant
  3. Intégrale de Lebesgue
    1.         reconnaître une fonction intégrable au sens de Lebesgue, différence avec une intégrale impropre convergente au sens de Riemann
    2.         appliquer les théorème de convergence dominée et de convergence monotone
    3.         appliquer les théorèmes de continuité et dérivation sous le signe "somme"
  4. Convolution
    1.         appliquer des critères d'existence d'une convolution (stabilité L1, BIBO, fonctions causales localement intégrables)
    2.         calculer explicitement des convolutions de fonctions simples, en utilisant les propriétés de commutativité/associativité, et la dérivation
    3.         comprendre les applications concrètes des effets régularisant de la convolution : filtrage de signaux pour l'élimination du bruit, la détection des contours (traitement d'images)
  5. Transformation de Fourier (TF)
    1.         faire des calculs de transformées de Fourier dans L1, appliquer les formules de modulation/translation, dérivation/produit, changement d'échelle, TF d'une convolution
    2.         utiliser la transformation de Fourier dans L2 , appliquer la formule de Plancherel, la formule d'inversion,
    3.         prolongement possibles : recalage de signaux par corrélation croisée, reconstruction d'images par filtrage de Wiener, déconvolution par l'algorithme de Richardson-Lucy,
  6. Séries de Fourier
    1.         Appliquer le théorème de Dirichlet pour des séries de Fourier de fonctions C1 par morceaux
    2.         Appliquer les formules de Plancherel/Parseval pour des fonctions L2
    3.         prolongements possibles : compression de signaux (JPEG), formule de Shannon

 

1 asymptotic analysis
        Landau asymptotic notations : equivalence, " big O ", " little o " and Theta
        compute equivalents of sequences defined by series using an integral/series comparison
        apply these tools to the computation of algorithm complexity in iterative form
        know the major complexity classes (linear, quasi-linear, polynomial, exponential) and important examples (naive sorting, matrix calculation algorithm, arithmetic)
        possible extension: calculation of the asymptotics of sequences defined implicitly by "bootstrap "

2 linear recurrences
        solving linear recurrences with homogeneous integer coefficients or with second member of type " polynomial x exponential "
        apply these tools to the computation of complexity for recursive algorithms
        know " divide and conquer " examples : quick sort, Karatsuba, Strassen or FFT algorithms
        possible extension: linear recurrences of order 1 with non-constant coefficients

3 Lebesgue integral
        recognize an integrable function in the sense of Lebesgue, difference with a convergent improper integral in the sense of Riemann
        apply the dominated convergence and monotonic convergence theorems
        apply the continuity and derivation theorems under the sum/integral  signs

4 convolution
        apply criteria for the existence of a convolution (L1 stability, BIBO, locally integrable causal functions)
        explicitly compute convolutions of simple functions, using the properties of commutativity / associativity and derivation
        understand the concrete applications of the regularizing effects of convolution: filtering of signals for noise elimination, edge detection (image processing)

5 Fourier transformation (TF)
        do Fourier transform computations in L1, apply the modulation / translation, derivative / product, scale change, TF formulas of a convolution
        use the Fourier transformation in L2, apply the Plancherel formula, the inversion formula,
        possible extensions: signal registration by cross correlation, image reconstruction by Wiener filtering, deconvolution by the Richardson-Lucy algorithm,

6 Fourier series
        Apply Dirichlet's theorem for piecewise Fourier series of functions C1
        Apply Plancherel / Parseval formulas for L2 functions
        possible extensions: signal compression (JPEG), Shannon formula

 

 

Informations pédagogiques

Compétences à acquérir

Utiliser les principaux outils d'analyse mathématiques pour l'étude de la complexité des algorithmes et le traitement du signal.

Pré-requis recommandés

  • Mise à niveau : T5CC011M
  • Algèbre : T5CC021M
  • Analyse : T5CC031M

Bibliographie, lectures recommandées

  • Algèbre et analyse cours de mathématiques de première année avec exercices corrigés Stéphane Balac, Frédéric Sturm
  • Analyse et algèbre cours de mathématiques de deuxième année avec exercices corrigés et illustrations avec Maple Stéphane Balac, Laurent Chupin
  • Exercices d'algèbre et d'analyse 154 exercices corrigés de première année Stéphane Balac et Frédéric Sturm
Dernière modification : mer, 06/01/2021 - 09:55