Ohjelmoinnin matematiikka

Seuraavat eivät ole ohjelmoinnin matematiikkaa:

• derivointi ja integrointi
• differentiaaliyhtälöt
• lineaarialgebra

Kuka sanoi näin? Valitse oikeat! verbose_off ok_text Teit oikeat valinnat! /* Vihje: valitse viisi. */ only_no_yes_on hide_expr 5 = hide_expr 0

• Turhautunut opiskelija
• Tyypillisen suomalaisen tutkinnon suunnittelija
• Association for Computing Machinery
• IEEE Computer Society
• Osaamistarveselvitykset, USA ja UK
• Osaamistarveselvitykset, Suomi
• tai

Tarvitaanko ohjelmoinnissa matematiikkaa?

• Puolitushaku on hyvin yksinkertainen algoritmi.
• Se vastaa sitä, miten puhelinnumeroita etsittiin paperisista luetteloista nimen perusteella.
• Bentley kokeili 1980-luvulla, kuinka monta % ammattimaisista ohjelmoijista saa sen oikein.
  verbose_off ok_text Kyllä, noin 10 %. Todellinen luku voi olla pienempi, koska Bentley hyväksyi oikeiksi ne, joista hän ei saanut selville oliko se oikein. only_no_yes_on hide_expr 1 = hide_expr 0

  0 %	40 %	80 %
  10 %	50 %	90 %
  20 %	60 %	100 %
  30 %	70 %

  tai
• Pattis tutki 20 oppikirjaa 1988. Kuinka monessa niistä puolitushaku oli oikein?
  verbose_off ok_text Kyllä, vain viidessä. 😞 only_no_yes_on hide_expr 5 = tai
• Ei ole merkkejä, että tilanne olisi sittemmin parantunut.
• Ohjelmoinnin matemaattiset menetelmät ovat sittemmin kehittyneet, mutta niitä opetetaan vähän.

Mikä on ohjelmoinnin matematiikkaa? ACM Valmarin painotuksella:

1. Propositiologiikka: sievennä
   
   verbose_off ok_text Oikein! prop_logic f_nodes 4 !(P /\ Q \/ !P) <=>
   (P \/ !Q) /\ P <=> FF \/ P /\ !Q
   tai
2. Lausekeoppi: kirjoita kuvan mukainen kaava
   verbose_off ok_text Oikein! tree_compare x^4 = (-x)^4 >= -x^2; x^4 = -x^4 >= -x^2
   tai
3. Predikaattilogiikka: ”sano
   jokin alkio on erisuuri kuin seuraava”
   verbose_off ok_text Oikein! array_claim A[1...n] EE i; 1 <= i < n: A[i] != A[i+1] <=> EE i; 1 <= i <= n: A[i] != A[i+1]
   tai
4. Looginen päättely.
   verbose_off ok_text Oikein! modulo 23 n >= 2 <=> n > 2 \/ n = 2 ==> EE k: k < n <=> EE k: k <= n
   tai
5. Todennäköisyyslaskenta.
6. Modulaarinen aritmetiikka.
   verbose_off ok_text Oikein! modulo 19 EE a: a^3 = x <=> x<=1 \/ x=7 \/ x=8 \/ x=11 \/ x=12 \/ x=18
   tai
7. Puut ja graafit.
8. Joukko-oppi.
9. Lisää joukko-oppia.
10. Äärelliset automaatit yms.