Quel genre de maths m'aidera à résoudre les problèmes de programmation?

Question

J'ai étudié divers problèmes et algorithmes de programmation dans le but d'améliorer mes compétences en programmation et en résolution de problèmes. Mais, je continue à courir dans la description comme celle-ci:

"Soit A = [a1, a2, ..., an] être une permutation des entiers 1,2, ..., n Une paire d'indices (i, j), 1 < = i < = j < = n, est une inversion de la permutation A si ai> aj On nous donne des entiers n> 0 et k> = 0. Quel est le nombre de permutations d'éléments n? contenant exactement k inversions? " (SOURCE: http://www.spoj.pl/problems/PERMUT1/)

Quel type de maths ai-je besoin d'étudier pour que ce genre de description de problème ait du sens pour moi?

Answer 1

J'étais dans ce genre d'embarras il y a environ un mois. Jusqu'à ce que je suis venu à propos de ce poste de Steve Yegge - Math for Programmers

Très instructif, fortement recommandé lire. Espérons qu'après la lecture, vous obtiendrez des indications pour le prendre à partir de là. Bonne chance.

Answer 2

Mathématiques discrètes. Il traite de beaucoup de combinatoire, de probabilité, etc., ce qui est ce que vous avez dans votre problème. (http://en.wikipedia.org/wiki/Discrete_mathematics)

La possibilité de lire une équation d'ensemble ne blesse probablement pas non plus.

Answer 3

Cela ressemble à un problème de permutation typique. http://www.mathsisfun.com/combinatorics/combinations-permutations.html

Answer 4

Je recommande d'avoir un oeil à l'un (ou les deux) des éléments suivants:

Graham, Knuth Patashnik: Mathématiques Béton

Knuth: L'art de la programmation informatique (Vol 1)

Ce ne sont pas des lectures faciles, et vous voulez au moins avoir une formation de base en mathématiques au secondaire, mais elles mènent bien au genre de mathématiques que vous décrivez dans votre question, et ont beaucoup d'exercices.