#!/usr/bin/env python
# coding: utf-8

# # Algorithmique et complexité :
# 
# <h2 class='fa fa-graduation-cap' style="color: MediumSeaGreen"> A faire vous même :</h2>
# 
# Lire la page [Introduction à l'algorithmique](https://pixees.fr/informatiquelycee/n_site/nsi_prem_intro_algo.html) proposée par David ROCHE puis répondre aux questions suivantes :

# - A qui attribue-t-on les premiers algorithmes :
# 
# ...

# - Qu'est-ce qu'un algorithme ? Proposez une définition :
# 
# ...

# - Dans quel langage exprime-t-on un algorithme :
# 
# ...

# - Rechercher sur le Web ce qu'est un algorigramme ? Proposez des synonymes puis collez ci-dessous un lien hypertexte, une image d'un exemple d'algorigramme :
# 
# ...

# - Que devez vous faire si on vous demande d'implémenter un algorithme ?
# 
# ...

# - Qu'est-ce que la complexité d'un algorithme ?
# 
# ...

# - Quels types de complexité distingue-t-on pour un algorithme ?
# 
# ...

# - Comment mesure-t-on la complexité d'un algorithme ?
# 
# ...

# - A quoi correspond la complexité du pire des cas ?
# 
# ...

# <h2 class='fa fa-code' style="color: darkorange"> A coder vous même :</h2>
# 
# ### Implémenter l'algorithme suivant dans une fonction en Python :
# 
# > /!\ en Python le premier élément d'un tableau a pour indice 0
# 
# ```pseudocode
# VARIABLE
# t : tableau d'entiers
# x : nombre entier
# tr : booléen (VRAI ou FAUX)
# i : nombre entier
# DEBUT
# tr ← FAUX
# i ← 1
# tant que i<=longueur(t) et que tr==FAUX:
#   si t[i]==x:
#     tr ← VRAI
#   fin si
#   i ← i+1
# fin tant que
# renvoyer la valeur de tr
# FIN
# ```

# In[ ]:


def maFonction(t, x) :
    tr = False
    
    
        
            
        
    return tr


# ### Vérifier le bon fonctionnement de votre fonction :

# In[ ]:


maFonction([5,8,15,53], 15)


# In[ ]:


maFonction([5,8,15,53], 12)


# ### Puis mesurer le temps d'exécution de votre programme avec `timeit` :

# In[ ]:


get_ipython().run_line_magic('timeit', 'maFonction([5,8,15,53], 15)')


# In[ ]:


get_ipython().run_line_magic('timeit', 'maFonction([5,8,15,53], 12)')


# In[ ]:


get_ipython().run_line_magic('timeit', 'maFonction([5,8,15,53], 5)')


# Est-ce que ces résultats sont logiques ? Expliquez pourquoi ?
# 
# ...

# Mesurez le temps d'exécution de votre programme pour des tableaux de plus grande dimension.
# 
# Est-ce que ces résultats vérifient l'ordre de grandeur de sa complexité ?
# 
# ...

# In[ ]:





# In[ ]:





# In[ ]:





# <h2 class='fa fa-cogs' style="color: tomato"> A faire vous même :</h2>

# Écrivez un algorithme permettant de trouver le plus grand entier présent dans un tableau.
# 
# ```pseudocode
# VARIABLE
# t : tableau d'entiers
# 
# ...
# 
# DEBUT
# 
# 
# 
# ...
# 
# 
# 
# renvoyer ...
# FIN
# ```
# 
# Vous ferez "tourner à la main" votre algorithme en utilisant le tableau `t = [3,5,1,8,4,2]`.
# 
# Vous déterminerez ensuite la complexité de votre algorithme.
# 
# Enfin programmez une fonction Python correspondante à votre algorithme puis mesurez son temps d'exécution et vérifiez sa complexité...

# <h2 class='fa fa-cogs' style="color: tomato"> A faire vous même :</h2>

# Écrivez un algorithme permettant de calculer la moyenne de tous les entiers présents dans un tableau.
# 
# ```pseudocode
# VARIABLE
# t : tableau d'entiers
# 
# ...
# 
# DEBUT
# 
# 
# 
# ...
# 
# 
# 
# renvoyer ...
# FIN
# ```
# 
# Vous ferez "tourner à la main" votre algorithme en utilisant le tableau `t = [3,5,1,8,4,2]`.
# 
# Vous déterminerez ensuite la complexité de votre algorithme.
# 
# Enfin programmez une fonction Python correspondante à votre algorithme puis mesurez son temps d'exécution et vérifiez sa complexité...

# ****
# ## Références aux programmes :
# 
# <style type="text/css">
# .tg  {border-collapse:collapse;border-spacing:0;}
# .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;}
# .tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;}
# .tg .tg-cv16{font-weight:bold;background-color:#dae8fc;border-color:inherit;text-align:center}
# .tg .tg-xldj{border-color:inherit;text-align:left}
# </style>
# 
# <table class="tg">
#   <tr>
#     <th class="tg-cv16">Contenus</th>
#     <th class="tg-cv16">Capacités attendues</th>
#     <th class="tg-cv16">Commentaires</th>
#   </tr>
#   
#   <tr>
#     <td class="tg-xldj">Parcours séquentiel d’un tableau</td>
#     <td class="tg-xldj">Écrire un algorithme de recherche d’une occurrence sur des valeurs de type quelconque.<br>Écrire un algorithme de recherche d’un extremum, de calcul d’une moyenne.</td>
#     <td class="tg-xldj">On montre que le coût est linéaire.</td>
#   </tr>
#     
# </table>

# ## Ressources :
# 
# Pour mesurer un temps d'exécution, Python dispose d'une bibliothèque dédiée : [timeit](https://docs.python.org/3.8/library/timeit)

# Dans jupyter :
# 
# ```python
# %timeit ma_fonction()
# ```
# 
# ou 
# 
# ```python
# %%timeit
# i,r = 0,1
# n = 5
# while i <= n:
#     i = i + 1
#     r = r*i
# ```
# 
# Afficher l'aide :

# In[ ]:


get_ipython().run_line_magic('pinfo', 'timeit')


# <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="Licence Creative Commons" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/88x31.png" /></a><br />Ce document, basé sur le travail de [David ROCHE](https://pixees.fr/informatiquelycee/n_site/nsi_prem.html), est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">Licence Creative Commons Attribution -  Partage dans les Mêmes Conditions 4.0 International</a>.
# 
# Pour toute question, suggestion ou commentaire : <a href="mailto:eric.madec@ecmorlaix.fr">eric.madec@ecmorlaix.fr</a>

# In[ ]: