DataScienceUB.github.io/index.html at master · DataScienceUB/DataScienceUB.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>

<!DOCTYPE html>


    <meta name="keywords" content="remark,remarkjs,markdown,slideshow,presentation">
    <meta name="description" content="A simple, in-browser, markdown-driven slideshow tool.">


    <title>Apunts d'algorísmica</title>
    <meta charset="utf-8">
	<link rel="stylesheet" type="text/css" href="common/print.css" media="print">
    <style>
      @import url(https://fonts.googleapis.com/css?family=Yanone+Kaffeesatz);
      @import url(https://fonts.googleapis.com/css?family=Droid+Serif:400,700,400italic);
      @import url(https://fonts.googleapis.com/css?family=Ubuntu+Mono:400,700,400italic);

      body { font-family: 'Droid Serif'; }
      h1, h2, h3 {
        font-family: 'Yanone Kaffeesatz';
        font-weight: normal;
      }
      .remark-code,
      .remark-inline-code { font-family: 'Ubuntu Mono'; }
      .red { color: #fa0000; }
      .green { color: #00fa77; }
      .blue { color: #0000fa; }
      .light { color: #aaaaaa; }
      .bold { font-family: 'Yanone Kaffeesatz'; font-size: 1.5em;
              line-height: 0.9em;}
      .code {font-family: 'Ubuntu Mono';}
      .footnote {
        bottom: 12px;
        left: 20px;
        font-size: 0.75em;
        line-height: 0.4em;
      }

      .summary {
        background:#003366;
        color: #ffffcc;
      }

	  .summary a{
        color: #ffddaa;
	  }

      .exam {
        background: #802222;
        color: #ffffcc;
        text-shadow: 0 0 20px #333;
      }

      .inverse {
        background: #800000;
        color: #ffffcc;
      }

      .inverse h1,
      .inverse h2 {
        color: #f3f3f3;
        line-height: 0.8em;
      }
      .pull-left {
        float: left;
        width: 47%;
      }
      .pull-right {
        float: right;
        width: 47%;
      }
      .pull-right ~ p {
        clear: both;
      }
      #slideshow .slide .content code {
        font-size: 0.8em;
      }
      #slideshow .slide .content pre code {
        font-size: 0.9em;
        padding: 15px;
      }
      .inverse {
        background: #272822;
        color: #777872;
        text-shadow: 0 0 20px #333;
      }
      .inverse h1, .inverse h2 {
        color: #f3f3f3;
        line-height: 0.8em;
      }

      /* Slide-specific styling */
      #slide-inverse .footnote {
        bottom: 12px;
        left: 20px;
        font-size: 0.6em;
      }
      #slide-how .slides {
        font-size: 0.9em;
        position: absolute;
        top:  151px;
        right: 140px;
      }
      #slide-how .slides h3 {
        margin-top: 0.2em;
      }
      #slide-how .slides .first, #slide-how .slides .second {
        padding: 1px 20px;
        height: 90px;
        width: 120px;
        -moz-box-shadow: 0 0 10px #777;
        -webkit-box-shadow: 0 0 10px #777;
        box-shadow: 0 0 10px #777;
      }
      #slide-how .slides .first {
        background: #fff;
        position: absolute;
        top: 20%;
        left: 20%;
        z-index: 1;
      }
      #slide-how .slides .second {
        position: relative;
        background: #fff;
        z-index: 0;
      }

      /* Two-column layout */
      .left-column {
        color: #777;
        width: 20%;
        height: 92%;
        float: left;
      }
        .left-column h2:last-of-type, .left-column h3:last-child {
          color: #000;
        }
      .right-column {
        width: 75%;
        float: right;
        padding-top: 1em;
      }
details {
    border: 1px solid #aaa;
    border-radius: 4px;
    padding: .5em .5em 0;
    margin-bottom: 10px;
}

summary {
    font-weight: normal;
    padding: .5em;
    background-color: #f2f2f2;
    margin-bottom: 10px;
}

details[open] {
    padding: .5em;
}

details[open] summary {
    border-bottom: 1px solid #aaa;
    margin-bottom: .5em;
}

div.warnred {
    background-color: #fcf2f2;
    border-color: #dFb5b4;
    border-left: 5px solid #dfb5b4;
    padding: 0.5em;
    margin-top: 10px;
    margin-bottom: 10px;
    }

div.warnblue {
    background-color: #99ccff;
    border-color: #dFb5b4;
    border-left: 5px solid #0066ff;
    padding: 0.5em;
    margin-top: 10px;
    margin-bottom: 10px;
    }

    </style>
  </head>
  <body>
  <textarea id="source">


class: center, middle

<center><img src="images/ub.png" width="150"></center>


# **ALGORÍSMICA**

## Apunts de l’assignatura


Jordi Vitrià, Mireia Ribera

.blue[jordi.vitria@ub.edu] |  .blue[ribera@ub.edu]


---
class: center, middle, inverse


## https://algorismica2019.github.io/


---

class: middle

<div class=warnblue>
<b> Warning: </b> remember to do bookeping
</div>

<div class=warnred>
<b> Warning: </b> remember to do bookeping
</div>


<details>
<summary><b>Pregunta</b>:
Linear Regression with Synthetic Data Colab exercise, which explores linear regression with a toy dataset.
</summary>
<b>Resposta</b> <br>
La solució és...
</details>

<details>
<summary><b>Pregunta</b>: Which of the following model's predictions have been affected by selection bias?

<ul>
  <li>Engineers built a model to predict the likelihood of a person developing diabetes based on their daily food intake. </li>
  <li>Engineers built a model to predict the likelihood of a person developing diabetes based on their daily food intake. </li>
</ul>

</summary>
<b>Resposta</b><br>
Engineers built a model to predict the likelihood of a person developing diabetes based on their daily food intake. </li>
</details>

---

# Índex

+ [Presentació de l'assignatura](#tema0)
+ Tema 1: [Què és un algorisme?](#tema1)
+ Tema 2: Algorismes Numèrics
	+ [Aritmètica Bàsica](#tema2)
	+ [Aritmètica Modular](#modular)
+ Tema 3: [Algorismes per Text](#tema3)
+ Tema 4: [Algorismes i Força Bruta](#tema4)
+ Tema 5: [Dividir i vèncer](#tema5)
+ Tema 6: [Algorismes de Cerca](#tema6)
+ Tema 7: [Hashing](#tema7)
+ Tema 8: Estratègies algorísmiques per resoldre el PVC.


---
name:tema0

class: center, middle, inverse

## Presentació de l'assignatura

---

## Què és aquesta assignatura?

Aquesta assignatura està adreçada a donar la formació bàsica als estudiants sobre l’**anàlisi i disseny** d’algorismes, tant des d’un punt de vista teòric com aplicat. No s’assumeix cap formació prèvia en programació de l’estudiant.

##Què s’espera dels estudiants matriculats?

Els estudiants han de participar de forma activa durant les classes magistrals de teoria (**1,5 hores a la setmana**).

Durant les hores teòrico-pràctiques (o de problemes, **10 sessions de 1,5 hores**)  hauran de dissenyar solucions algorísmiques als problemes plantejats pels professors.

Durant les hores  presencials de pràctiques (**10 sessions de 1,5 hores**) hauran de programar de forma individual una sèrie d’exercicis pràctics.
Les hores no presencials de l’assignatura (4 hores a la setmana) les han de dedicar a l’estudi i a la preparació dels problemes i pràctiques.

---

## Programarem?

Tot i que en aquesta assignatura no és estrictament necessari programar, ho farem amb un llenguatge d’alt nivell: **Python**.

## Com s’organitza l’assignatura?

Usarem dues eines diferents per distribuir la informació i organitzar la feina:
+ **GitHub**, per distribuïr el material formatiu.
	+ Teoria: https://algorismica2019.github.io/
	+ Problemes: https://github.com/algorismica2019/problemes
+ **Campus Virtual** de la UB per la recollida d'exercicis, lliurament de proves presencials i qualificacions.


---

class: center, middle


<center><img src="images/CVUB.png" width="750"></center>

https://campusvirtual.ub.edu/course/view.php?id=17969

---

## Com s’avaluarà l’assignatura? (I)

L’assignatura seguirà un esquema d’avaluació continuada, amb dos elements principals: proves presencials i lliurament d’exercicis.

+ Lliurament via campus virtual de pràctiques (LP): Els professors proposaran una sèrie de pràctiques que hauran de ser lliurades via el campus virtual per part de l’alumne dins el període assenyalat pel professor. 4 d'aquests lliuraments seran avaluats pel professor amb una nota que pot anar de 0 (nota mínima) a 10 (nota màxima). En cas de no haver lliurat les pràctiques dins el període assenyalat, l’alumne obtindrà un 0. La nota final (LP) de la part de lliurament de pràctiques serà la mitja de les 4 pràctiques avaluades.
+ Proves presencials (PP): Es fa un examen parcial (EP) i un examen final (EF). Tots els examens tenen amb una part pràctica (50 % de la qualificació) i una part teòrica (50 % de la qualificació).

Si un alumne no aprova l’examen parcial EP, pot tornar a presentar-se d'aquesta part del curs el dia de l’examen final, obtenint una nota EP2.


---

## Com s’avaluarà l’assignatura? (II)


La nota d’avaluació continuada és

`AC = 0,3 * LP + 0,3 * max (EP, EP2) + 0,4 EF`

sempre que `(LP > 4,0) i (max (EP, EP2)+EF > 4,0)`. Altrament la nota d’avaluació continuada és `min (4,0, (max (EP, EP2) + EF + LP) /2)`.

> Durant la segona prova presencial (Gener) es donarà l’opció de presentar-se de tota l’assignatura o només de la segona part. Si un alumne opta per tornar a presentar-se a la primera part de l'assignatura, en la nota de proves presencials es tindrà en compte la nota millor dels dos intents.

Tots aquells alumnes que no aprovin però obtinguin una `AC>=3,5` tenen dret a una reavaluació al cap d’un dies de la publicació de `AC`. En aquests casos, la nota final de l’assignatura serà la nota de la reavaluació.

---

##I el lliurament de problemes...?

No hi ha una activitat pròpia de lliurament de problemes, però la  part pràctica de les proves presencials pot estar basada en aquests problemes.

--

## Calendari de proves
Tots els exàmens es fan en període no lectiu.

+ La primera prova presencial es farà el 7 de novembre de 15h a 18h.
+ La segona prova presencial (examen final) es farà el 20 de gener de 15h a 20h.
+ La reavalaució es farà el 30 de gener de 15h a 20h.

---

## Bibliografia

### Algorísmica

+ T. H. Cormen et al. Introduction to algorithms, MIT Press, 2001.
+ S.Dasgupta.[Algorithms](http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf), McGrawHill, 2006.
+ V. Levitin, Introduction to the Design and Analysis of Algorithms, ISBN: 0-201-74395-7, Addison-Wesley (2ond edition)
+ S. Skiena. The Algorithm Design Manual, Springer; 2nd edition (August 21, 2008), Language: English, ISBN-10: 1848000693.

### Python

+ A. Downey, J. Elkner and C. Meyers. [How to Think Like a Computer Scientist. Learning with Python.](http://greenteapress.com/thinkpython/thinkCSpy/).

---

class: center, middle, inverse
name:tema1

# Tema 1: **Què és un algorisme?**

---
class: summary

### Resum del tema 1

+ **Conceptes**:

  + Algorisme,
  + Input(entrada),
  + Output(sortida),
  + Correcció,
  + Eficiència (memòria i cicles),
  + Errors (tipus),
  + Conceptes de llenguatge de programació:
      + Primitives (símbols),
      + sintaxi,
      + semàntica estàtica,
      + semàntica.

---

class: center, middle, inverse

## Què és un algorisme?

<iframe src="https://www.bbc.co.uk/ideas/videos/why-algorithms-are-called-algorithms/p07gdlwf/player" width="500" height="440" scrolling="no" style="overflow: hidden" allowfullscreen frameborder="0"></iframe>

---

## Què és un algorisme?

> Definició de la *Wikipedia*: Un algorisme és una seqüència finita, no ambigua i
explícita, d’instruccions per a resoldre un problema.


---

## Què és un algorisme?

La definició d’aquesta assignatura:

.bold[Un algorisme és qualsevol procediment computacional que pren un (o una sèrie) de dades/valors com a *entrada* i genera alguna dada/valor (o sèrie de dades/valors) com a *sortida*.]

+ Els algorismes són les **idees/estratègies** que hi ha darrera els programes per resoldre un determinat problema.
+ Els algorismes són independents del llenguatge en que estan escrits. El mateix algorisme escrit en dos llenguatges diferents pot tenir una aparença superficial molt diferent.
+ Els algorismes sí que depenen de la representació de les dades.
+ Els algorismes interessants són els que resolen problemes generals. Els problemes específics es resolen reduïnt-los a problemes generals.

---

### Exemple computacional (arrel quadrada)

Problema a resoldre mitjançant un algorisme:

> Entrada:	Un nombre `a`

> Sortida:	Un nombre `b` tal que `b*b=a`

> Requeriment: Volem una solució **correcta i eficient**!

--

Hi ha diversos algorismes per calcular aquest valor. El que s'explica a l'escola és un d'ells (i no és exactament simple!).

--

Heró d’Alexandria (10 dC-70 dC) ja en va proposar un altre:

+ Comencem amb un nombre qualsevol `g`.
+ Mentre `g*g` *no s’assembli prou* a `a`:
	+ Calculem un nou candidat `(g+a/g)/2`.
+ Donem com a resultat l'últim valor de `g`.
---

### Exemple computacional (arrel quadrada)


Codificació en Python:

La condició "mentre `g*g` *no s’assembli prou* a `a`" la implementarem
calculant un error d'aproximació: `g*g - a > valor_error`.

```python
def hero(a,error):
    g = 1.0
    while abs(g*g - a) > error:
        g = 1/2*(g+a/g)
    return g
```

Si executem `hero(49,0.0001)`, l'ordinador retorna `7.000000141269659`.

---

## Correcció i Eficiència Algorísmica

Un algorisme és **correcte** si **podem demostrar** que retorna la sortida desitjada per a qualsevol entrada legal (per al problema de l’arrel quadrada, això vol dir nombres positius o 0).

> Demostrar la *correcció* és fàcil per alguns algorismes, difícil per la majoria i fins i tot impossible per alguns!

> Aquest aspecte de l'algorísmica no l'abordarem durant aquest curs.

--

Un algorisme és  **eficient** si es fa amb el mínim nombre de recursos (cicles de càlcul de l'ordinador / temps, memòria de l'ordinador) possible.

> Fer servir algorismes eficients és sempre convenient i moltes vegades una necessitat!
---


## Algorismes i ordinadors

Un ordinador fa només dues coses (però molt ben fetes!):
+ calcular (combinar dades per obtenir altres dades);
+ emmagatzemar (llegir/escriure dades a una memòria) els resultats del càlcul.

Un ordinador convencional fa més de 1.000.000.000 de càlculs per segon i pot emmagatzemar més de 1.000.000.000.000 de bits.

Els algorismes que veurem en aquest curs són procediments per a resoldre problemes que estan basats en el càlcul i emmagatzament de dades en un ordinador convencional.

No veurem algorismes:

+ basats en càlcul paral·lel ni distribuït entre diversos ordinadors;
+ basats en arquitectures no convencionals (p.e. quàntica).

---

## Exemple: el problema del viatjant de comerç (TSP).

Aquest cartell correspon al concurs promogut per *Procter & Gamble* l’any 1962 per recorrer 33 ciutats dels EUA:


<center><img src="images/tsp.png" width="300"></center>

Anem a proposar algorismes per solucionar-ho!

---

## Exemple: el problema del viatjant de comerç (TSP).

Suposem que hem de passar per un conjunt de punts definits i volem minimitzar la distància recorreguda.

A la figura de la dreta tenim una possible instància del problema. A l'esquerra hi ha la millor solució d'aquesta instància, **la que voldriem trobar amb un algorisme que acceptés com a entrada qualsevol conjunt de punts**.red[*].

<center><img src="images/recorregut.png" width="650"></center>

.footnote[.red[*] A la major part dels casos que resoldrem en aquest curs o tindrem accés a la solució correcte del problema o podrem fer un programa molt simple que, donada una solució, comprovi que és correcte. En el cas del problema del viatjant de comerç, no tindrem ni una cosa ni l'altra!]

---

### Propostes


**Solució I**: Escollim un punt aleatori per començar, i anem creant un recorregut seleccionant el *veí més proper* (la ciutat més propera entre les que no ha visitat encara) a cada pas.

<center><img src="images/recorregut2.png" width="650" alt="la solució I resol el problema però amb un recorregut no eficient, al costat es presenta la solució òptima"></center>

És correcte?

--

> Sabem que **no ho és** perquè tenim accés a un *oracle* que ens diu quina és la solució correcte. Més endavant veurem quines opcions tenim si no tenim accés a l'oracle.

---

### Propostes


**Solució II**:

+ Considerem **tots el possibles passos parcials entre dues ciutats**, calculem la seva longitud i ho guardem en un conjunt.
+ Mentre ens quedin passos parcials al conjunt:
	+ Busquem al conjunt el pas parcial més petit `p`.
	+ Afegim `p` al recorregut final sempre i quan no generi un cicle o una doble sortida per un punt.
	+ Eliminem `p` del conjunt de passos parcials.

És correcte?
--


**Solució III**:

Considerem **totes les possibles ordenacions** del conjunt format per totes les ciutats, calculem la distància de cada una de les ordenacions i seleccionem la més curta.

És correcte?
---

### Solucions correctes i eficients!

La solució III anterior **és correcta** però **no és eficient**.

+ No cal demostrar que és correcta: és evident!

+ El nombre de possibles ordenacions d'un conjunt de `n` elements ve donat pel concepte de **factorial**: `n! = n x (n-1) x (n-2) x ... x 1`.

+ El factorial d'un nombre `n` creix molt ràpidament quan `n` es fa gran. Aquest pot ser un nombre molt gran fins i tot pels ordinadors.


|     |     |
|---  |---  |
|  $$20! =$$   |  $$2432902008176640000$$   |
|  $$25! =$$   |  $$1,551121004 \times 10^{25}$$   |
|  $$50! =$$   |  $$3,041409320 \times 10^{64}$$   |
|  $$100! =$$   |  $$9,332621544 \times 10^{157}$$   |

---

## Com expressem els algorismes?

Amb **llenguatges de programació**.

Un llenguatge de programació es defineix per unes **primitives** (símbols), una **sintaxi** (regles de combinació de símbols), una **semàntica estàtica** (combinacions de símbols amb significat) i una **semàntica** (el significat que nosaltres volem donar a l’algorisme).
--


Fins ara hem usat *paraules* o pseudocodi, però també podem usar un llenguatge d’alt nivell, **Python**, molt proper al pseudocodi.

El preu que hem de pagar és que haurem d’**especificar** una mica més les coses.

Els avantatges:
+ aprenem un llenguatge útil;
+ som més formals en les especificacions;
+ podem executar-los i fer simulacions.

---

## Llenguatges

+ **Símbols**: Són la forma d'escriure variables (p.e. `a`), instruccions (p.e. `print()`), etc. Hi ha una sèrie de regles que els defineixen.

+ **Sintaxi**: Són les regles que defineixen les combinacions vàlides de símbols: `3.2 + 4.5` és vàlida, però  `3.2 a 2.3` no ho és.

+ **Semàntica estàtica**: `3.2/’abc’` és sintàcticament correcte perquè l’expressió (`<literal><operador><literal>`) ho és, però no ho és des del punt de vista de la semàntica estàtica.


> Els errors més perillosos quan programem no són els sintàctics, atès que la majoria es poden detectar automàticament o són fàcils de veure!

> Alguns llenguatges detecten quasi tots els errors de semàntica estàtica, però Python només alguns!

+ **Semàntica**: Es refereix a "què" fa el programa (p.e. aquest programa calcula l'arrel quadrada?) i per tant depèn totalment del programador.


---

## Llenguatges


Si no hi ha errors sintàctics ni de semàntica estàtica el programa s'executarà i farà alguna cosa, però no necessàriament la que volem.

Els *entorns de programació* (IDE) ens poden ajudar a detectar els errors sintàctics i alguns errors de semàntica estàtica, però no els semàntics.

Aquest programa no donarà mai cap error:

```python
def suma(a,b):
  '''
  Aquest programa no fa el que ha de fer!
  '''
  return a - b
```

Els únics que podem determinar que no és correcte sóm nosaltres.

---

## Llenguatges

Si un programa té un error que no ha estat detectat:
1. Pot acabar inesperadament la seva execució i generar un error. La majoria de vegades no afecta a la resta de programes de l’ordinador, però hi ha errors que poden causar un error fatal a l'ordinador i aturar-lo.red[*]. En aquest cas, la majoria d'errors són errors de sintaxi o de semàntica estàtica no detectats per l'IDE.
2. Pot ser que mai s’aturi i per tant no generi la resposta. En aquest cas normalment estem davant d'un problema semàntic.
3. Pot aturar-se i generar una resposta que pot ser incorrecta. En aquest cas normalment estem davant d'un problema semàntic.


.footnote[.red[*]Pot ser que els errors només es manifestin per alguna combinació específica dels valors d'entrada i per tant no es detectin sense fer moltes proves. Normalment no podem provar totes les possibilitats!]


---

class: center, middle, inverse
name:tema2

# Tema 2:  **Algorísmes Numèrics**

---
class: summary

### Resum del tema 2

+ [Sistema numeració](#sistnum)
	+ base
	+ nombre de dígits
+ [Seqüència de Fibonacci](#fib)
+ Notació [Gran O](#granO)
+ Aritmètica bàsica
	+ [suma](#suma)
	+ [multiplicació](#mult)
		+ versió d'Al Khwarizmi
	+ [divisió](#div)
+ Aritmètica Modular
	+ [suma](#sumamod)
	+ [multiplicació](#multmod), versió d'Al Khwarizmi
	+ divisió
	+ [potència](#potmod)
+ [Algorisme d'Euclides](#euclides)
+ [Test de primeritat](#testprimer)
	+ [Teorema petit de Fermat](#fermat)
	+ [Teorema de Lagrange](#lagrange)

---
name:sistnum

## Una mica d'història

Cap a l’any 600, a l'Índia, es va inventar el sistema decimal de numeració.

> Un sistema de numeració és un conjunt de símbols i regles de generació que permeten construir tots els nombres vàlids en el sistema.

El seu principal avantatge sobre els que es coneixien a Europa, com el romà, és la seva **base posicional** i la **simplicitat de les operacions** (algorismes) aritmètiques.

--

Els sistemes de numeració romans i egipcis no són estrictament posicionals. Per això, és molt complex dissenyar algoritmes d'ús general (per exemple, per a sumar, restar, multiplicar o dividir).

Un sistema de numeració ve definit doncs per:

 + el conjunt `S` dels símbols permesos en el sistema. En el cas del sistema decimal són `{0,1...9}`; en el binari són `{0,1}`; en l'octal són `{0,1,...7}`; en l'hexadecimal són `{0,1,...9,A,B,C,D,E,F}`.
 + el conjunt `R` de les regles de generació que ens indiquen quins nombres són vàlids i quins no són vàlids en el sistema.


---

## Bases i representació numèrica

Quantes  “unitats” hi ha a 642? Depèn de la base en que està escrit! La **base d’un nombre** determina el nombre de dígits diferents i el valor de les posicions dels dígits.

642  és 600 + 40 + 2 en BASE 10.

La fòrmula que ens permet entendre una base és:

$$ d_n \times R^{n-1} +  \dots + d_2 \times  R + d_1 $$

on `R` és la base del nombre i `d_i` és el dígit a la posició i-èssima del nombre.

$$ 642 = 6_3 \times 10^2 + 4_2 \times 10 + 2_1 $$


DECIMAL és base 10 i té 10 dígits: `0,1,2,3,4,5,6,7,8,9`

BINARI és base 2 i té 2 dígits: `0,1`

HEXADECIMAL és base 16 i té 16 dígits: `0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F`


---

## Una mica d'història

El sistema decimal de numeració va trigar molts anys en arribar a Europa.

El medi de transmissió més important va ser un manual, escrit en àrab durant el segle IX a Bagdad, obra de **Al Khwarizmi**, en el que especificava els procediments per sumar, multiplicar i dividir nombres escrits en base deu.

Els procediments eren precisos, no ambigus, mecànics, eficients i correctes.
És a dir, eren algorismes (per a ser implementats sobre paper i no amb un ordinador!).

Una de les persones que més van valorar aquesta aportació va ser Leonardo Fibonacci.

<center><img src="images/fib.png" width="150" alt="Segell amb el bust de Leonardo Fibonacci"></center>


---
name:fib

## Una mica d'història

Fibonacci és avui conegut sobretot per la seva seqüència:

`0,1,1,2,3,5,8,13,21,34...`

La seqüència es pot definir amb la següent regla:

<center><img src="images/seqfib.png" width="350"></center>

Això encara **no és un algorisme**, és només una definició: A les següents pàgines veurem diferents algorismes per implementar computacionalment aquesta definició!


---
## Una mica d'història

La seqüència creix molt ràpid i es pot demostrar (matemàticament) que el terme `n`-èssim de la seqüència té aproximadament aquest valor:

$$  F_n \approx 2^{0.694n}  $$


Però per calcular **exactament** un terme concret necessitem una fòrmula o un algorisme!


Una primera possibilitat és aquesta (*algorisme recursiu*).red[*]:

```python
def fib1(n):
    if n==0:
        return n
    if n==1:
        return n
    else:
        return fib1(n-1) + fib1(n-2)

fib1(10)
> 55

```

.footnote[.red[*]Un algorisme recursiu és un algorisme que es crida a si mateix.]

---

## Algorisme recursiu de Fibonacci

Els algorismes recursius, per executar-se, creen automàticament còpies d'ells mateixos (amb paràmetres possiblement diferents) creant un arbre. Quan la recursivitat s'acaba, reconstrueixen la solució movent-se cap enrera per l'arbre.

<center><img src="images/fib1.png" width="550"></center>

---

## Algorisme recursiu de Fibonacci

De la mateixa manera que ho fariem per a qualsevol algorisme, ens podem fer tres preguntes (**les tres preguntes bàsiques de l'algorísmica**) sobre l'algorisme que hem escrit:

+ És correcte?
+ Quant trigarà? En aquest cas, té sentit preguntar-ho en funció de `n`, la mida del nombre que passem com a paràmetre?
+ Hi ha alguna manera millor de fer-ho?


---

## Algorisme recursiu de Fibonacci

I les respostes són:

+ **És correcte?**  En aquest cas és evident que sí, atès que segueix exactament la definició!
+ **Quant trigarà?** Es pot demostrar que el nombre de passos computacionals que fa és de l'ordre de `F_n`. Per calcular el terme 200 hauria de fer de l'ordre de `2^138` passos. A l’ordinador més ràpid del món, que pot executar al voltant de 40.000.000.000.000 passos per segon,  necessitaríem més temps que el necessari pel col·lapse del Sol! A la velocitat que els ordinadors augmenten la seva capacitat de càlcul, cada any que passa podríem calcular un nombre de Fibonacci més que l’any anterior!
+ **Hi ha alguna manera millor de fer-ho?** Sí...


---

## Algorisme recursiu de Fibonacci

Per trobar una manera millor, només cal adonar-se de per què és tant lent:


<center><img src="images/fib2.png" width="350"></center>

Hi ha molts càlculs (en aquest cas, crides recursives) que es repeteixen!

Una solució possible és guardar el resultat de cada crida el primer cop que ho calculem i no tornar a calcular-ho.


---

## Algorisme de Fibonacci

Anem a fer-ne una versió basada en **llistes**:

> **_NOTA:_**  _Les llistes en Python són **seqüències mutables d’objectes arbitraris**. Les llistes es manipulen amb diferents mètodes: https://docs.python.org/3/tutorial/datastructures.html_ i s'accedeix als seus elements amb els operadors de `slicing`.


```python
def fib2(n):
    if n==0:
        return 0
    ls = [0,1]
    for i in range(2,n+1):
        ls.append(ls[i-1]+ls[i-2])
    return ls[n]
```


+ És correcte? És evident que és correcte.
+ Quant trigarà? Només executa `(n-1)` vegades la iteració.

Direm que `fib2(n)` és **lineal** (o polinòmic) respecte `n`.
Ara podem calcular fins i tot `fib(100.000.000)`.


--

Però encara ho podem fer millor!

---

## Algorisme de Fibonacci

```python
def fib3(n):
    a,b = 0,1
    for i in range(1,n+1):
        a,b = b, a+b
    return a

fib3(10)
> 55
```

---

## Algorisme de Fibonacci

```python
def fib3(n):
    a,b = 0,1
    for i in range(1,n+1):
        a,b = b, a+b
    return a

fib3(10)
> 55
```

Amb l'eina Code Skulptor podem visualitzar fàcilment el funcionament de qualsevol algorisme:

http://www.codeskulptor.org/viz/index.html


---

## Com hem de comptar els passos computacionals?


Considerarem de la mateixa categoria les instruccions simples com emmagatzemar a memòria, comparacions, operacions aritmètiques, etc.

```python
import math
a = 5
b = 4
for i in range(3):
    a += math.sqrt(a+b)
```

Però si manipulem nombres molt grans (que ocupen més de 64 bits), aquestes operacions no són tan barates!

```python
import math
a = 1234585127527575235234982374598245
b = 8112387512759287512875851285789127
for i in range(327864287686868676876876876887986):
    a += math.sqrt(a+b)
```

Caldrà tenir en compte quina complexitat computacional té operar dos nombres d’aquestes característiques.

---
name:granO

## La notació Gran O

Aquesta notació és una convenció per no ser ni massa ni massa poc precisos a l’hora d’escriure la complexitat computacional d’un algorisme (= nombre de passos).

La regla principal és **comptar el nombre de passos computacionals aproximats en funció de la mida de l'entrada**.

> Nota: Fem la següent aproximació:  enlloc de dir que té una complexitat de `5 x n^3 + 4 x n + 3` direm que té una complexitat de `O(n^3)`

En general utilitzarem aquestes convencions:

+ Ometrem les constants multiplicatives: `14n^2 és n^2`.
+ `n^a` domina sobre `n^b` si `a>b`: `n^2` domina sobre `n`.
+ Qualsevol exponencial domina sobre un polinomi: `3^n` domina sobre `n^5` (i també sobre `2^n`).
+ Qualsevol polinomi domina sobre un logaritme: `n` domina sobre `log(n)^3` i `n^2` domina sobre `nlog(n)`.

---

## La notació Gran O

<center><img src="images/grano.png" width="650" alt="Es mostren les assimptotes, per ordre de més inclinada a menys: O(N!), O(N2), O(NlogN), O(N), O(logN), O(1)"></center>

---

## La notació Gran O

<center><img src="images/grano2.png" width="750"></center>

Observacions:
+ Qualsevol algorisme amb `n!` és inútil a partir de `n`=20
+ Els algorismes amb `2^n` són inútils a partir de `n`=40
+ Els algorismes quadràtics, `n^2` comencen a ser costosos a partir de `n`=10.000 i a ser inútils a partir de `n`=1.000.000
+ Els algorismes lineals i els `nlog(n)` poden arribar fins a `n`=1.000.000.000
+ Els algorismes sublineals, `log(n)`, són útils per qualsevol `n`.

---
## La notació Gran O


Les famílies més importants d’algorismes són les que tenen un ordre:

+ Constant, `O(n) = 1`, com `f(n) = min(n,1)`, que no depenen de `n`.
+ Logarítmic, `O(n) = log(n)`.
+ Lineals, `O(n) = n`.
+ Super-lineals, `O(n) = nlog(n)`.
+ Quadràtics, `O(n) = n^2`.
+ Cúbics, `O(n) = n^3`.
+ Exponencials, `O(n) = c^n` per `c`>1.
+ Factorials, `O(n) = n!`

---

## Magnitud dels nombres.

És important familiaritzar-se amb les magnituds dels nombres. Aquest video, "Powers of Ten", us pot ajudar a tenir una idea intuitiva de la magnitud de les potències de 10.

https://www.youtube.com/watch?time_continue=1&v=0fKBhvDjuy0

---


class: center, middle, inverse
name:tema2

**Aritmètica Bàsica**

---

## Aritmètica Bàsica: Preliminar