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

# ## Éléments de syntaxe Python

# Les variables ne sont pas **typées**

# In[1]:


x = 13
x


# In[2]:


x = "toto"
x


# In[3]:


type(x)


# In[4]:


x = 10


# ### Le bloc `if`
# 
# Pas d'accolades `{` en Python : c'est l'**indentation** (espaceement à gauche) qui délimite les blocs. La convention veut que chaque nouveau bloc imbriqué ajoute 4 espaces d'indentation.

# In[5]:


if x <= 14:
    print "Hello"
    x += 5
    print x
elif x == 15:
    print x
else:
    print x - 20


# Une condition plus complexe avec des connecteurs logiques et des multi-comparaisons

# In[6]:


if x is not None and 5 < x < 100 and (True or False):
    print "Oui"


# ### Boucle `while`

# In[7]:


x = 75
while x < 100:
    x += 1
    print x


# Les variables de la boucle `while` ne sont pas locales à la boucle

# In[8]:


x


# ### *Listes* et boucle `for`

# In[9]:


L = [1, 2, 10, 15]
for a in L:
    b = a + 10
    print b


# Encore une preuve du fait que les variables des boucles ne sont pas locales

# In[10]:


a, b


# On peut imbrique les blocs, bien sûr

# In[11]:


for x in L:
    if x > 10:
        print x - 10
    else:
        print x


# ### Fonctions

# In[12]:


def tot(a, b):
    c = a + b
    return c


# In[13]:


x = tot(14, 5)


# In[14]:


x


# Les variables d'une fonction sont (généralement) locales à la fonction

# In[15]:


c


# Puisque l'opérateur `+` est *polymorphique* (il fonctionne sur plusieurs types), la fonction `tot` l'est aussi

# In[16]:


tot(5.2, 4.1)


# In[17]:


tot("Hello ", 'world')


# Mais cela ne veut pas dire qu'on peut additionner tout et n'importe quoi: les conversions de type ne sont pas implicite en Python (mais elle le sont parfois en Sage)

# In[18]:


tot("Hello", 13)


# In[19]:


tot("Hello", str(13))


# In[20]:


tot("Hello", '13')


# ### Plus sur les listes

# In[21]:


A = [1, 2, 3] + [100, 11, 5]


# In[22]:


A


# In[23]:


A[3]


# In[24]:


A.index(100)


# In[25]:


A[3]


# In[26]:


A.append(354)


# In[27]:


A


# In[28]:


A[2:4]


# In[29]:


A[1:5:2]


# In[30]:


A[-1]


# In[31]:


A[:-2]


# ### Classes
# 
# La méthode spéciale `__init__` est le *constructeur* de la classe

# In[32]:


class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def montrer(self):
        print "(" + str(self.x) + "," + str(self.y) + ")" 


# Le constructeur est appelé implicitement à la création d'un objet

# In[33]:


p = Point(10, 15)


# In[34]:


p.x


# In[35]:


p.y


# In[36]:


p.montrer()


# Les champs des classes sont *dynamiques*: on peut en ajouter à souhait

# In[37]:


p.c = 56


# In[38]:


p.c


# In[39]:


p.montrer()


# In[40]:


p


# On peut ajouter aussi des méthodes à une classe déjà définie

# In[41]:


def affichage(self):
    print "Dans __repr__"
    # L'opérateur % sur les chaines de caractères est simlaire au printf en C
    return "(%d, %d)" % (self.x, self.y)
Point.__repr__ = affichage


# In[42]:


p = Point(10, 15)


# La méthode spéciale `__repr__` modifie la façon dont les objets s'affichent

# In[43]:


p


# ### Exercice 6.1

# In[44]:


def euclidepol (A,B):
    A0 = A; A1 = B
    S0 = 1; S1 = 0
    T0 = 0; T1 = 1
    while A1 != 0:
        Q = A0//A1
        U = A1; A1 = A0 - Q*A1; A0 = U
        U = S1; S1 = S0 - Q*S1; S0 = U
        U = T1; T1 = T0 - Q*T1; T0 = U
    return (A0,S0,T0)


# In[45]:


A.<X> = QQ[]


# In[46]:


a, b = X^2-1, (X-1)^2
g, u, v = euclidepol(a, b)


# In[47]:


g


# In[48]:


u, v


# In[49]:


u*a + v*b == g


# ### Exercice 6.2

# In[50]:


def irreducible(k, n):
    A.<x> = k[]
    p = x^n
    while not p.is_irreducible():
        p = A.random_element(n)
    return p.monic()


# In[51]:


irreducible(QQ, 3)


# In[52]:


irreducible(GF(7), 100)


# ### Exercice 6.3

# In[53]:


def lexico_irred(p, n):
    A.<x> = GF(p)[]
    P = x^n
    while not P.is_irreducible():
        # print P
        for i in range(n):
            if P[i] != p-1:
                P += x^i
                break
        for j in range(i):
            P -= P[j] * x^j
    return P


# In[54]:


lexico_irred(3, 10)


# In[55]:


lexico_irred(101, 21)