Quelle est la seule théorie informatique que je devrais connaître? [fermé]

27

En parlant comme quelqu'un avec un diplôme en génie électronique plutôt qu'en informatique, quel est le peu d'informatique que je devrais connaître pour faire de moi un meilleur programmeur dans le monde réel ?

(Par monde réel, je veux dire quelque chose que je vais utiliser et dont je bénéficierai dans mon travail quotidien de programmeur - par exemple, je suggère que la normalisation de la base de données est d'une utilité plus pratique que la compréhension d'un tri rapide pour lequel il y a beaucoup des bibliothèques).

Jon Hopkins
la source
42
1 (désolé, je devais)
haylem
5
oh, ou le plus important! (J'y vais maintenant ...)
haylem
L'informatique théorique stackexchange confirme ce que tout le monde mentionne ici: la complexité, les structures de données et les algorithmes. cstheory.stackexchange.com/tags
chrisaycock
2
Je ressens le besoin de m'opposer à cette question. Il n'y a pas "un bit" qui serait suffisant pour apprendre, et de plus, il n'y a pas (à mon humble avis) un bit "le plus important". Il y a plusieurs aspects qui sont (encore une fois, à mon humble avis) également essentiels pour CS. Je pense donc que même si les réponses à cette question peuvent être intéressantes, la question aurait pu être mieux formulée.
Konrad Rudolph
1
Si vous n'aviez pas déjà votre eeng, j'aurais dit la logique booléenne et / ou la théorie des nombres discrets. Presque tous ifet loopinstruction utilise jamais écrit un sous - ensemble de ces deux domaines d'étude.
Steven Evers

Réponses:

52

Si je dois choisir un seul bit, ce qui est une décision difficile, je dirais aller pour la notation Big O . Comprendre les implications de O (n), O (ln n), O (n²), O (2 ^ n), O (n!) Vous aide à éviter de nombreuses erreurs coûteuses, dont le type fonctionne bien dans le environnement de test mais échoue de façon désastreuse dans la production.

user281377
la source
2
+1 et je dirais que plus important que de savoir que O (n ^ 2) est pire que O (lg n) (par exemple), c'est de savoir comment dériver le Big-O pour un morceau de code donné.
Dean Harding
3
Désapprouve fortement. Ce truc est relativement trivial, et il y a des sujets plus intéressants dans CS. De plus, je pense que la plupart des gens pensent intuitivement à la complexité, bien qu'ils ne l'appellent peut-être pas la complexité et qu'ils ne l'appellent peut-être pas quadratique, exponentielle, etc.
Magnus Wolffelt
Magnus: D'après mon expérience, la plupart des non-programmeurs ne pensent pas du tout à la complexité, ils supposent intuitivement O (n) pour tous les problèmes.
user281377
Je n'ai pas encore besoin de cela officiellement.
CaffGeek
1
Chad: Il n'y a rien dans la notation Big O qui soit trop formaliste, mais sans nom pour les choses, vous pouvez à peine penser à ces choses, et encore moins en parler avec vos pairs.
user281377
19

C'est une question, tout le monde aura une réponse différente. Je dirais: la théorie de la complexité est l'élément le plus important, que vous n'apprenez pas directement en tant que programmeur de toute façon (comme les algorithmes et les structures de données), mais ce qui peut avoir un impact sur votre travail. Cela aide si je sais qu'un problème a une complexité cubique, je sais qu'il évoluera mal si la taille du problème augmente.

Mnementh
la source
J'ajouterais que cela aide beaucoup de savoir si vous résolvez un problème qui peut facilement être reformulé dans un langage plus simple.
philosodad
La complexité est importante en tant que concept, mais le calcul ne l'est souvent pas. Comprendre ce qui est moins complexe est l'élément le plus important.
Bill
@Bill: Exactement. Mais cette partie est la seule chose que vous n'obtenez pas nécessairement par la pratique. La théorie est très utile à cet égard.
Mnementh
12

Découvrez les structures de données, les algorithmes et la complexité.

Pas trop juste pour comprendre qu'une machine n'est pas une boîte magique avec une puissance illimitée. Vous ne pouvez rien y jeter et vous attendre à ce qu'il croque en quelques millisecondes. Il a des limites que vous connaissez. Vous devez apprendre à ne pas les tester avec votre code.

Jetez également un œil aux approches courantes pour résoudre des problèmes de conception particuliers dans la programmation. Modèles de conception, nommément. Ne les adorez pas, prenez simplement les idées qu'ils communiquent.

La connaissance de la modélisation de bases de données est également essentielle.

Après cela, ce ne sont que différents langages de programmation, frameworks et bibliothèques qui implémentent ou vous permettent d'implémenter les concepts de base. Ramassez ce que vous aimez et entraînez-vous avec ceux-ci.


la source
Particularités - il existe de nombreux algorithmes et structures de données.
Jon Hopkins
Juste les bases pour avoir une idée des choses. Prenez un livre pas trop épais et parcourez-le.
1
C'est un peu plus d' un bit.
7

C'est une question un peu difficile.

Tous les aspects de l'informatique sont importants d'une manière ou d'une autre.

En termes de ce dont vous bénéficierez au jour le jour, probablement un aperçu général du fonctionnement de votre code "sous le capot" du code au CPU.

Il est important de comprendre Big O Notation, et également de comprendre comment votre code peut être exécuté est également très important dans des situations réelles.

Nuit noire
la source
7

Ouais, cela m'a poussé à réfléchir pendant des heures.

Au cours du processus, j'ai dû supprimer certaines des réponses courantes données ici.

PAS DE LISTE

  1. Grande notation O (n) . Difficile de le dire ici, mais non, nous pouvons intuitivement résoudre les inefficacités et comparer différents ensembles de procédures sans même avoir entendu parler à distance de l'analyse algorithmique asymptotique.

  2. Langages fonctionnels Non, une seule famille de langage n'est qu'une approche pour réfléchir aux problèmes. Pourquoi seul ce bit devrait-il avoir de l'importance?

  3. Arrêter le problème Certains sont tout simplement trop spécifiques et les gens ont vécu leur vie sans savoir qu'ils existaient.

  4. Écoutez Si vous n'écoutez pas, vous vivez dans votre propre monde. Pas nécessairement préjudiciable!

  5. Cycle de développement logiciel Nah! Nous pouvons encore bousculer notre chemin vers un logiciel incroyable ou un effort héroïque en solo.

  6. théorie de la complexité, je suppose que cela pourrait être, mais sans tous les formalismes

Cette idée de Comp Science

Je dirais - " Abstractions Abstractions Abstractions ... ". Apprenez-en plus. Voir des exemples autour d'elle et apprendre à construire en l'utilisant. C'est partout. L'ensemble de l'informatique, de l'ingénierie et des applications ressemble à des couches sur des couches d'abstraction.

Une fois que vous savez cela, vous commencez à bien regarder autour de vous.

Lorsque vous voyez quelqu'un utiliser list insertionin pythonet not append, vous souriez parce que vous savez que les listes python sont construites en utilisant l'abstraction de tableaux où les insertions sont coûteuses et ajoutent moins cher.

Ce n'est qu'un exemple.

pyfunc
la source
+1 pour une réponse à laquelle vous avez évidemment beaucoup réfléchi.
Jon Hopkins
juste un commentaire sur votre commentaire sur le problème de l'arrêt: "Vivre la vie sans connaître l'existant" est vrai pour N'IMPORTE QUEL sujet d'informatique.
4

Théorie des automates et FSM. :-)

Prasoon Saurav
la source
3

Cas d'utilisation concurrentielle des structures de données.

Il existe des situations où une carte avec des arbres rouge-noir est requise pour garantir les performances et d'autres où vous ne pouvez pas utiliser un tableau, encore une fois pour garantir les performances. Savoir quand choisir quelle structure de données est une compétence inestimable.

Fanatic23
la source
3

il n'y a que trois chiffres qui comptent:

  • zéro
  • une
  • beaucoup
Steven A. Lowe
la source
mais cela ne signifie-t-il pas que «3» est également important?
Javier
Il est censé être zéro, un et l'infini: en.wikipedia.org/wiki/Zero_One_Infinity
Thomas Owens
@Javier: 3 est un sous-ensemble de plusieurs
Steven A. Lowe
@Thomas: dit qui?
Steven A. Lowe
@Steven Ma compréhension n'est peut-être pas à 100%, ici, mais je pense que l'idée est que vous n'avez rien de quelque chose, une seule chose, ou le nombre de choses que vous avez devrait être illimité. Si vous ne vous limitez à aucune ou à une seule instance, vous ne devez pas limiter les instances. Cependant, je ne suis pas entièrement sûr POURQUOI c'est le cas (je ne connais que vaguement le concept Zero / One / Infinity).
Thomas Owens
3

La chose la plus importante que j'ai apprise dans CS (et en tant que développeur pendant de nombreuses années et en tant qu'architecte) est la capacité de décomposer un problème en fonction de la volatilité et non de la fonction. Toutes les bonnes conceptions isolent et encapsulent la volatilité. Tous les bons développeurs / architectes le font intuitivement même s'ils ne l'ont pas formalisé dans leur réflexion. Une énorme raison de l'échec d'un projet est l'incapacité à décomposer un problème sur la base de la volatilité et à l'encapsuler. Un échec à encapsuler la volatilité conduit inévitablement à la fuite et à la complexité du projet.

JP Alioto
la source
Qu'entendez-vous exactement par volatilité?
amara
3

Le problème de l'arrêt

Le fait qu'il existe des problèmes informatiques qui ne peuvent tout simplement pas être résolus par un ordinateur.


la source
3

Vous devez connaître suffisamment la théorie des automates pour pouvoir savoir où le problème que vous traitez se situe dans la hiérarchie des langages formels. À partir de cela, vous pouvez comprendre quelques utilisations pratiques importantes, comme pourquoi vous ne devriez pas utiliser un REGEX pour analyser HTML (HTML a besoin d'une grammaire sans contexte pour le décrire), et pourquoi cela prend beaucoup plus de temps pour compiler C ++ par opposition à Java ou C # (C ++ nécessite une machine Turing, tandis que Java et C # peuvent être décrits avec des grammaires sans contexte).

Les niveaux les plus importants de langues formelles sont, du plus faible au plus fort:

  1. Langages qui peuvent être analysés par un automate fini ou un REGEX (les implémentations REGEX avec des références arrières sont plus puissantes que cette catégorie, mais elles ne peuvent toujours pas analyser tout dans la catégorie 2)

  2. Langages qui peuvent être analysés par un automate avec une mémoire de pile ou une grammaire sans contexte.

  3. Langages pouvant être analysés par une machine Turing ou un automate avec une mémoire à accès aléatoire.

Dan Monego
la source
Um non. Une expression régulière analyse une grammaire régulière. C'est exactement la catégorie de grammaire qui peut être acceptée par un automate à états finis. Et une «grammaire Chomsky» ne se réfère pas exclusivement aux grammaires sans contexte, ce que traitent les machines à empiler.
philosodad
@philosodad - La grammaire sans contexte est plus précise, et j'ai mis à jour le message pour utiliser le terme. Je ne comprends pas votre problème avec ce que j'ai dit sur les expressions régulières.
Dan Monego
@Dan - Mon problème est qu'une expression régulière est précisément aussi puissante qu'un automate à états finis, et si vous pouvez analyser N'IMPORTE QUELLE grammaire déterministe sans contexte avec une machine, vous pouvez analyser TOUTES les grammaires déterministes sans contexte.
philosodad
Ou, pour être plus précis: soit vous avez besoin d'une pile, soit vous n'en avez pas. Si vous avez besoin d'une pile pour analyser une langue, alors vous devez avoir une pile pour analyser la langue, et donc, si une langue nécessite une pile pour l'analyser, vous pouvez analyser cette langue.
philosodad
@philosodad - Il existe deux types d'expression régulière - les expressions régulières en théorie et les expressions régulières telles qu'elles sont implémentées dans le logiciel. Vous avez raison sur les expressions régulières théoriques, mais la plupart des implémentations ont plusieurs fonctionnalités au-delà de leur base théorique, et peuvent correspondre à certains langages non réguliers, comme un ^ n pour n non premier. Parce qu'il s'agit d'un fil conducteur sur la théorie dans la pratique, je me suis mis en quatre pour mentionner qu'il y a une différence entre la définition formelle et celle utilisée dans la nature.
Dan Monego
2

Eh bien, je pourrais vous donner une réponse ennuyeuse: la théorie des automates et la théorie de l'information.

Ou je pourrais vous dire ce que j'ai appris d'un consultant en matériel il y a longtemps:

  • "Bon assez" n'est pas suffisant.
Mike Dunlavey
la source
1

Le cycle de vie du développement logiciel est quelque chose que je suggérerais de savoir si vous ne l'avez pas déjà fait. Certes, cela a été introduit dans un cours d'informatique de deuxième année et est quelque chose utilisé à plusieurs reprises dans les projets logiciels. Cela peut être utile pour avoir une idée générale de la façon dont un projet se déroule du début à la fin, mais si vous voulez approfondir, il existe des méthodologies comme Waterfall ou Agile que vous pouvez étudier pour obtenir des connaissances plus spécifiques.

JB King
la source
2
La loi de Murphy: tout ce qui peut mal tourner va mal
Richard
Ce n'est pas la théorie CS, mais c'est une excellente réponse.
justkt
1

Programmation

Du département de mathématiques et d'informatique Hobart et William Smith Colleges vient Computer Science 124 Introduction to Programming :

Les sujets incluent les structures de contrôle, les objets, les classes, l'héritage, les structures de données simples et les concepts de base du développement logiciel.

Si vous ne pouvez pas programmer, vous n'irez pas très loin dans l'informatique du monde réel.

Et, oui, j'ai remarqué que vous êtes programmeur. Il s'agit d'améliorer votre connaissance globale de la théorie de la programmation et des autres approches qui s'offrent à vous.

La programmation informatique est-elle telle que nous la connaissons?

En réponse au commentaire de @Thomas Owens, qui a souligné (à juste titre) que la programmation n'est pas strictement informatique, je voudrais citer un article de Wikipédia sur l'informatique :

... l'informatique se concentre davantage sur la compréhension des propriétés des programmes utilisés pour implémenter des logiciels tels que les jeux et les navigateurs Web, et sur l'utilisation de cette compréhension pour créer de nouveaux programmes ou améliorer ceux existants ...

Ainsi, comme je l'ai lu, en programmant, vous démontrez votre compréhension de la théorie de la programmation. Cela devrait à son tour vous aider à créer un code simple et élégant qui est une joie pour les autres.

Gary Rowe
la source
La programmation n'est pas la théorie CS. En fait, je pourrais facilement affirmer que la programmation n'est pas du tout de l'informatique.
Thomas Owens
@Thomas Owens J'ai mis à jour ma réponse pour confirmer ma prétention qu'elle est valide. Pourriez-vous l'examiner et me faire part de vos réflexions?
Gary Rowe
1
Je ne pense toujours pas que la programmation soit CS. La programmation POURRAIT être utile à un informaticien qui souhaite mettre en œuvre un algorithme ou une structure de données, mais les sujets de la théorie CS (de mon introduction à la théorie CS, donc il y a probablement des sujets plus avancés également) incluent la logique, la théorie des automates, la théorie des graphes , calculabilité, complexité de calcul et analyse d'algorithmes. Je dirais également que les langages de programmation (la théorie derrière la conception et l'implémentation d'un langage) font également partie de l'informatique. Cependant, vous n'avez pas besoin de pouvoir programmer pour être un bon informaticien.
Thomas Owens
@Thomas Owens Je vois votre point, et (met un chapeau puriste) Je suis d'accord. Cependant, le PO demande un bit de CS qui l'aiderait dans le monde réel. Je tiens fermement à mon avis que la théorie de la programmation (telle qu'implémentée dans un bon code) est un bit. J'ai modifié légèrement en conséquence.
Gary Rowe
Ouais. De CS, je dirais que la compréhension des langages de programmation et des paradigmes pourrait aider (surtout si vous implémentez des DSL, mais connaître de nombreux paradigmes comme procédural, fonctionnel, OO, logique aide simplement au développement de logiciels). La compréhension des algorithmes et des structures de données vous aide également à choisir le (s) bon (s) pour résoudre votre problème de la manière la plus efficace. La théorie des automates pourrait aider (j'ai travaillé avec un système qui était un FSM géant une fois, mais je ne sais pas à quel point c'est courant). Je dirais donc que les structures de données, les algorithmes et la théorie PL seraient les choses les plus utiles à savoir de CS.
Thomas Owens
1

Je dois être en désaccord avec Konrad Rudolph. Il y a "un peu" d'informatique que vous devriez connaître pour faire de vous un meilleur "programmeur du monde réel". Si vous ne retirez rien d'autre des réponses que vous obtenez ici, pensez au moins à cela: satisfaire les exigences n'est PAS la même chose que satisfaire le client! Les utilisateurs finaux essaieront TOUJOURS d'utiliser votre programme d'une manière à laquelle vous n'auriez jamais pensé ou codé. TOUJOURS, TOUJOURS, TOUJOURS.

Par conséquent, pour être un meilleur programmeur, vous devez d'abord ÉCOUTER. Écoutez le client. Écoutez leurs besoins. Écoutez leurs désirs. Et surtout, écoutez leur niveau de «tech-pertise». Je ne peux pas vous dire combien de fois j'ai vu un projet construit qui était exactement ce qui avait été demandé, mais pas du tout ce dont le client avait réellement besoin. Tout cela parce que le programmeur rassemblant les demandes n'écoutait pas vraiment.

Quelque chose d'autre que vous pouvez emporter est, à moins que vous n'ayez une formation en conception d'interface utilisateur, demandez à quelqu'un d'éles de concevoir l'interface utilisateur. Je peux TOUJOURS repérer une application où l'interface utilisateur a été conçue par le programmeur et non par un expert. Ce qui est logique et logique pour vous n'aura pas de sens pour le client. Et, si vos clients ne sont pas technophiles, (et qui sont?), Alors votre solution "fonctionnellement correcte, mais esthétiquement laide" rencontrera la chaleur de la mouffette lors d'un dîner.


la source
3
Cette réponse ne traite pas de la théorie CS, ce que Hopkins a demandé.
James
1

Langages fonctionnels!

L'apprentissage des langages fonctionnels vous fait penser en termes d'expressions plutôt qu'en étapes et en états mutables nommés (variables). Cela a un impact significatif sur votre capacité à gérer efficacement les problèmes de programmation quotidiens - surtout maintenant que presque tous les langages populaires ont des fonctionnalités.

Les algorithmes et la théorie de la complexité sont également importants, mais ils sont un peu moins intéressants dans la mesure où ils vous permettent principalement de mettre des noms sur des choses que vous connaissiez et saviez habituellement déjà.

Magnus Wolffelt
la source
0

Que les ordinateurs sont essentiellement des modèles de correspondance, rien de plus. Tout se résume à la machine de Turing - le concept classique de science informatique pour expliquer l'usinage de motifs.

therobyouknow
la source
-2

Résolution de problèmes et désir de continuer à apprendre!

Ils me servent beaucoup mieux que de connaître le tri rapide et la normalisation de la base de données.

Bryan Harrington
la source
6
Ce n'est pas de la théorie informatique, ils s'appliquent également à l'ingénierie électronique (ou à peu près toute autre forme) d'ingénierie.
Jon Hopkins
La façon dont je le vois, de prendre en compte votre exemple en sachant que le tri rapide n'est tout simplement pas utile. Savoir qu'il existe et ce qui fait sa particularité est utile, mais c'est aussi une recherche google si je n'en savais rien. Connaître un algorithme n'est pas non plus utile. Cependant, savoir en créer un et en interpréter un est! Si je pouvais changer ma réponse, la complexité est probablement la plus importante.
Bryan Harrington
1
Vous ne pouvez pas rechercher quelque chose si vous ne savez pas que vous en avez besoin ou qu'il existe. Votre réponse répertorie les qualités importantes qu'un développeur doit posséder, mais ne répond pas à la question posée.
Adam Lear