Mathématique pour l'informatique

[kaya]

Slt à tous,
j'ai un examen dans 2 semaines et un des modules me sont encore très flou: "Algorithme & Complexité". Si vous pouvez m'aider à faire des recherches ce serait sympa. j'ai déjà trouver un site mais il n'y a aucun lien et j'espère alors que vous pouviez m'aider, voici ce que j'ai trouvé mais ce sont les CONTENUS qui m'intéressent surtout.

Première Partie: Mathématiques Pour L’informatique Théorique (50%)

CHAPITRE I : Rappels et conventions (5%)

I.1.Notations Générales
I.2.Relations
I.3.Fonctions, Applications, Relations
I.4.Applications bijections
I.5.Composition des Applications
I.6.Constructions, Types
I.7.Indexation, Familles d’ensembles
I.8.Relations d’équivalence
I.9.Equivalence d’application


CHAPITRE II : Algèbre abstraite (10%)
II.1. Définitions
II.2. Objet Indéfini
II.3. Sous-Algèbres
II.4. Propriétés des Sous-Algèbres
II.5. Sous-Algèbre Engendrée
II.6. Morphismes d’Algèbre
II.8. Congruences
II.9. Extension de l’ensemble des Opérations


CHAPITRE III : Algèbre formelle (15%)
III.1. Généralités sur les Langages
III.2.Expressions sur un Ensemble
III.3.Proprietes de Simplification
III.4.Construction d’une Algèbre Formelle
III.5.Propriete de Substitution
III.6.Propriete d’Ecriture Unique
III.7.Theoremes d’Interprétation


CHAPITRE IV : Les fonctions (5%)
IV.1.Fonctions, Prédicats
IV.2.Relation d’Ordre sur les Fonctions
IV.3.Alternatives
IV.4.Suite Croissante de Fonctions
IV.5.Proprietes


CHAPITRE V: Les relations (5%)
V.1.Notion de relations
V.2.Relation d’Equivalence
V.2.1. Définitions
V.2.2. Classe d’équivalence
V.2.3. Ensemble Quotient
V.3.Relation d’Ordre
V.3.1. Définitions
V.3.2. Ordre Partiel, Ordre Total
V.3.3. Structure de Treillis Etc.


CHAPITRE VI : Théorie du point fixe (10%)
VI.1. Ensembles Inductifs et Fonctions Continues
VI.2. Théorème du Point Fixe: énoncé et démonstration
VI.3 - Applications du théorème du point fixe
VI.4 - Généralisations du théorème au cas de fonctions non continues


Deuxième Partie : Analyse II (30%)

CHAPITRE I : Les séries (10%)


CHAPITRE II : Introduction aux fonctions a variables complexes (10%)


CHAPITRE III : Les transformations (10%)
III.1. Laplace
III.2 - Fourrier
III.3. en Z


Troisième Partie : ALGEBRE LINEAIRE II (20%)

CHAPITRE I : Rappels de base (5%)
I.1. Espaces Vectoriels, Sous-Espaces Vectoriels
I.2. Bases, Changement de Base
I.3. Produit Scalaire, Espace Euclidien
I.4 - Transformations Linéaires, Opérateurs Linéaires

Chapitre II : Matrices et calcul matriciel (5%)
II.1. Rappel et Définitions de base
II.2. Formes quadratiques
II.3. Vecteurs et Valeurs propres
II.4. Diagonalisation/Triangularisation


Chapitre III : Espace vectoriel des polynômes (10%)
III.1. Définitions des polynômes
III.2. Espace Vectoriel des polynômes
III.3. Polynômes a coefficients réels, a coefficients binaires
III.4. Opérations sur les polynômes
III.5 - Polynômes orthogonaux

[Jake45]

Bonsoir kaya.

Alors ca dépend de ton niveau.

Je dirais que si tu es avant la licence, attends toi plutôt a des choses de type :

écrire un code de telle manière qu'il s'éxécute en un temps raisonnable et mieux encore.
par exemple : si tu as une structure de données triées et que tu cherches un élément, tu peux évidemment parcourir un à un tous les éléments de ta liste jusqu'à le trouver. Mais tu peux également, et c'est préférable, tirer parti du fait que ta structure soit triée pour faire une recherche dichotomique...
Voila le cas typique de ce qu'est l'étude de la compléxité à faible niveau.
Trouver des astuces pour éviter les calculs inutiles.

si tu es d'un niveau plus évolué, tu devrais plutôt regarder les machines de turing, comprendre ce qu'est un programme déterministe ou indeterministe,
théoreme d'incomplétude de gödel, bref la décidabilité et l'indécidabilité.
Associe cela aux fonctions récursive et primitives récursives et soit capable d'utiliser la thèse de church qui permet d'établir une équivalence quelque soit le modèle de calcul utilisé (foctions récursives et algorithmes dans un quelquonque langage impératif).

voilà les notions qu'il faut que tu maitrises pour faire de la compléxité.

J'ai oublié certainement le point le plus important qui est l'équivalence de problèmes NP-complet/difficile par réduction d'un problème en un autre.
par exemple : résoudre une partition optimale revient à une transformation près à résoudre le problème du sac à dos.

Comprendre ce qu'est un problème Non détérministe Polynomial et un problème déterministe Polynomial

[ulmo]

Salut,
Si tu cherches des cours de Caml (c'est le langage que certaines prepa utilisent en info), voici un excellent cours de Michel Quercia :
http://caml.inria.fr/pub/old_caml_site/polycopies/quercia/index-fra.html
(les premiers liens en heut de la page)

Sinon, jette y quand même un coup d'oeil : ils sont d'une grande qualité.

Il y a une petite 10aine d'exos par chapitres, des proclemes et des TP. Tout est corrigé en détaillé. C'est vraiment bien.

[rvfranck]

Salut,

J'ai fait des algos sur les structures de données (tableau, files, piles, etc...) auparavant, mais on ne s'interessait pas au nom et à leur temps d'execution. Là j'ai changé d'établissement scolaire et on étudie la complexité des algos.
Je suis souvent perdu lorsque le prof s'exprime parce qu'ici ils font attention au nom des algos (tri par fusion, rapide, etc...)

J'aimerai donc avoir une liste (avec noms) d'algo sur les structures de données et leur implémentation. Auriez vous un lien?

Merci