J’ai bossé pour le 1000 moto GP

Un job pourri

Pour gagner un peu d’argent pour les vacances, j’ai travaillé 3 jours sur le circuit des 24h pour une entreprise de restauration, ne sachant pas trop à quoi m’attendre.

Nous étions près de 200 salariés répartis en plusieurs stades sur tout le circuit. Je me retrouvais à m’occuper de la caisse derrière un stand importants, avec une grosse équipe d’une vingtaine de d’employé, nous étions 4/5 caissiers.

…

URL de quelques radios que j’écoute

Radio

• Radioalpa: https://www.radioalpa.com:8001/live.mp3
• La grande Évasion : http://radio.lagrandeevasion.fr/evasion.mp3
• FIP : http://icecast.radiofrance.fr/fip-hifi.aac
  • http://icecast.radiofrance.fr/fiprock-hifi.aac
  • http://icecast.radiofrance.fr/fipgroove-hifi.aac
  • http://icecast.radiofrance.fr/fippop-hifi.aac
  • http://icecast.radiofrance.fr/fipelectro-hifi.aac
  • http://icecast.radiofrance.fr/fipworld-hifi.aac
  • http://icecast.radiofrance.fr/fipreggae-hifi.aac
  • http://icecast.radiofrance.fr/fipnouveautes-hifi.aac
  • http://icecast.radiofrance.fr/fipjazz-hifi.aac
• j-POP : https://listen.moe/stream
• k-POP : https://listen.moe/kpop/stream
• rock en flac : https://stream.radioparadise.com/rock-flac

…

Classes de complexité

	Déterministe	Non-déterministe
temps	P, EXPTIME	NP, NEXPTIME
espace	LOGSPACE, PSPACE, EXPSPACE	NLOGSPACE

Complexité algorithmique

• O(1) : constant
• O(n) : linéaire
• O(log n) : logarithmique
• O(n log n) : quasi-linéaire
• O(n²) : quadratique
• O(n³) : cubique
• O(nᵏ) : polynomial
• O(2ⁿ) : exponentielle
• O(n!) : factorielle

		Algorithme
constant	O(1)	set
logarithmique	O(log n)	liste
linéaire	O(n)	recherche dichotomique, dans un tableau trié
quasi-linéaire	O(n log n)	tri d’un tableau (fusion)
quadratique	O(n²)	tri d’un tableau (insertion)
cubique	O(n³)	multiplication de matrices
polynomial	O(nᵏ)
exponentielle	O(2ⁿ)	problème du sac à dos
factorielle	O(n!)	problème du voyageur de commerce

Problèmes complexes

Problème du voyageur de commerce

• Problème NP-complet
• O(n!)
• 10 villes : 3 628 800

Problème du sac à dos

• Knapsack problem
• Problème NP-complet
• O(2ⁿ)
• 20 objets : 1 048 576

Problème du plus court chemin

• Aussi appelé longest common subsequence
• Problème NP-complet
• O(n²)
• 100 villes : 10 000

Stable marriage problem

• Aussi appelé problème des mariages stables (stable matching problem) ou problème des épouses de Gale et Shapley (Gale–Shapley algorithm)
• Problème NP-complet
• O(n²)
• 100 personnes : 10 000
• Algo 1 : Gale–Shapley (O(n²))

Vertex cover

• Aussi appelé couverture par sommets
• Algo 1 : brute force (O(2ⁿ))
• Algo 2 : approximation (O(n))
• Algo 3 : heuristique du degré (O(n²))

Clique

• Algo 1 : brute force (O(2ⁿ))
• Algo 2 : approximation (O(n))

Independent set

• Algo 1 : brute force (O(2ⁿ))
• Algo 2 : approximation (O(n))

Modularité

• Algo 1 : brute force (O(2ⁿ))
• Algo 2 : approximation (O(n))

Distance de Manhattan

• Algo 1 : brute force (O(n²))

Heuristique

• 2-approximation
• Degree

Problème d’optimisation	Problème de décision
meilleure solution	oui/non
NP-complet	NP-difficile

…