Conception et complexité des algorithmes - Comment penser de cette manière?

Ma question est d'ordre général: comment commencer à penser en termes de conception d'algorithmes et de complexité? Je vais suivre un cours d'études supérieures en conception d'algorithmes. Je m'y étais inscrit plus tôt mais je l'ai abandonné plus tard parce que je ne pouvais pas suivre. Je dois suivre ce cours comme une exigence.

Y a-t-il une «astuce» pour penser de cette façon? Je sais que c'est assez grossier, mais parfois une nouvelle perspective aide à penser différemment un sujet.

Le principal problème que j'ai avec ce cours (et des cours théoriques similaires) est: comment savoir que les solutions que je propose sont correctes? Je trouve que la partie théorique est arbitraire, surtout quand on «prouve» qu'un certain algorithme agit ou se comporte d'une certaine manière?

Notre cours utilisera le texte standard: Introduction aux algorithmes par CLRS.

Y a-t-il des manuels / sites / livres / etc. qui pourrait offrir un moyen de devenir confiant dans ce domaine?

Merci à tout le monde,

Jason Dane

Je pense que les cours sur la conception d'algorithmes et la complexité de calcul sont toujours difficiles pour les étudiants qui ne connaissent pas ces matières, car ils nécessitent un certain degré de maturité mathématique et de résolution de problèmes. Dans mon premier cours d'études supérieures sur la "complexité informatique", un de mes amis qui avait son diplôme en mathématiques pures m'a dit combien il était surpris par le fait que, bien que ce cours ne nécessite pas beaucoup de connaissances en mathématiques (du moins, c'est ce qui a été dit dans le plan du cours), il a en fait nécessité presque toutes les compétences qu'il a acquises à travers tous ses diplômes de premier cycle en mathématiques pures!

J'ai découvert que je connaissais le plus «la voie» (quand je commence mes études supérieures) en lisant et en faisant des exercices du livre de Sipser . Assurez-vous de faire les exercices parce que vous voulez apprendre la résolution de problèmes et la maturité mathématique et pas seulement un tas de faits ou de définitions.

Cependant, le livre de Sipser n'est bon que pour les choses complexes et complètes NP, il ne suffira pas de remplacer le livre CLRS. Le seul problème avec le livre CLRS est que son avantage d'une couverture complète pourrait devenir sa faiblesse car le livre peut sembler assez effrayant ou écrasant pour les étudiants. Donc, mon conseil est que vous devriez vraiment aller à la bibliothèque et rechercher des livres sur les algorithmes, les parcourir un par un et choisir ceux qui correspondent le mieux à votre mode de pensée. Et encore une fois n'oubliez pas de faire des exercices!

Pour les algorithmes, je suggère personnellement les livres suivants (en plus de ceux suggérés par Sadeq et JeffE):

• Le très beau livre très lisible Algorithms de S. Dasgupta, CH Papadimitriou et UV Vazirani.
• Les notes du tueur (ou projet de livre) par Jeff Erickson. (Comme JeffE est trop modeste pour suggérer ses propres notes, je dois le faire moi-même.)

En général, chaque fois que vous étudiez un certain algorithme ou structure de données, si l'exposition de votre manuel n'est pas assez claire pour vous, la meilleure façon est de rechercher sur google des notes de cours sur ce sujet particulier. Dans certains cas, différentes explications de la même chose vous donnent éventuellement une image complète. Du moins, c'est comme ça que ça marche pour moi.