Problème du sac à dos – Algorithme en Python (knapsack problem)

Le problème du sac à dos en algorithmique (et son implémentation python) est intéressant et fait parti du programme de Sciences numériques et informatique de première.

Ce problème illustre les algorithmes gloutons qui énumèrent toutes les possibilités de résolution d’un problème pour trouver la meilleure solution.

Le problème du sac à dos algorithme python est un problème d’optimisation, c’est à dire une fonction que l’on doit maximiser ou minimiser et des contraintes qu’il faut satisfaire.

Le problème du sac à dos – algorithme Python

Pour un sac à dos de capacité maximale de P et N articles chacun avec son propre poids et une valeur définie, jetez les articles à l’intérieur du sac à dos de telle sorte que le contenu final ait la valeur maximale.

Le problème du sac à dos - algorithme Python

Exemple d’énoncé :

  • Capacité maximum du sac à dos : 11 unités
  • Nombre d’objet : 5
  • Valeurs des objets : {10,50,20,30,60}
  • Poids des objets : {1,5,3,2,4}

Quelles est la valeur maximum qu’il est possible de mettre dans le sac à dos en considérant la contrainte de capacité maximum du sac qui est de 11 ?

Algorithme glouton python

Une solution efficace consiste à utiliser un algorithme glouton. L’idée est de calculer le rapport valeur / poids pour chaque objet et de trier l’objet sur la base de ce rapport calculé .

On prends l’objet avec le ratio le plus élevé et on ajoute jusqu’à ce qu’on ne puisse plus en ajouter.

En version fractionnaire il est possible d’ajouter des fractions d’article au sac à dos.

Implémentation du problème du sac à dos Python – version non fractionnaire

Voici une implémentation du problème du sac à dos python en version non fractionnaire, c’est à dire qu’on ne peut pas ajouter de fraction d’un objet dans le sac. Seul des objets entiers peuvent être ajoutés.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 120

Implémentation du problème du sac à dos python – version fractionnaire

En version fractionnaire de l’agorithme du sac à dos python on peut ajouter des fractions d’objet au sac à dos.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
            else: 
                fraction = capacite / poidsCourant 
                compteurValeur += valeurCourante * fraction 
                capacite = int(capacite - (poidsCourant * fraction)) 
                break
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 140.0

Liens internes algorithme python :

https://128mots.com/index.php/category/python/

https://128mots.com/index.php/2021/01/21/algorithme-glouton-python/
https://128mots.com/index.php/2021/01/19/levenshtein-python/
https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

Liens externes algorithme python :

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 3

Cet article fait suite aux deux premiers articles sur le sujet :

Les 2 premiers articles permettent de mieux comprendre le concept de blockchain et d’application décentralisée.

Création du projet

On crée un répertoire pour le projet d’application de vote sur des chansons.

mkdir vote-chanson-dapp

Pour accélérer le développement on va utiliser une « truffle box » : https://www.trufflesuite.com/boxes

C’est en quelques sorte un modèle, un canevas d’application qui vous permet de vous focaliser sur la Dapp en ayant une structure déjà créée.

Je vais baser mon explication sur la pet-shop box disponible ici : https://www.trufflesuite.com/tutorials/pet-shop. C’est un des premiers tutos de truffle pour créer une Dapp.

Cette truffle box comprend la structure de base du projet ainsi que le code de l’interface utilisateur.

Utilisez la commande truffle unbox :

truffle unbox pet-shop

Pour rappel l’installation de truffle est possible via la commande :

npm install -g truffle

Si vous ouvrez le dossier vote-chason-dapp avec vscode vous obtenez alors l’arborescence suivante :

Arborescence du projet de l’application Dapp exemple (basée sur pet-shop de truffle)
  • contract : stockage du smart contract de l’application
  • migration : Les migrations permettent de transférer les smarts contracts vers la blockchain Ethereum (en local test ou mainnet). Les migrations permettent également de relier des smart contrats avec d’autres smarts contracts et de les initialiser.
  • node_modules : Le dossier node_modules contient les bibliothèques téléchargées depuis npm.
  • src : Répertoire de l’application front-end (client)
  • test : Stockage des tests pour l’application
  • truffle-config.js : fichier Javascript qui peut exécuter tout code nécessaire pour créer votre configuration.

Création du smart contract

Pour rappel nous développons une application qui permet d’élire la chanson préférée des électeurs.

Nous allons créer dans un premier temps la partie qui permet de créer un vote pour la meilleure chanson basée sur 3 chansons éligibles.

Le contrat écrit en solidity est le suivant :

contract TopChanson {
        struct Chanson {
        uint identifiant;
        string titre;
        uint compteur;
    }
    uint public compteurDeChansons;
    mapping(uint => Chanson) public chansons;

    function ajouterChansonElligible (string memory nomChanson) private {
        compteurDeChansons ++;
        chansons[compteurDeChansons] = Chanson(compteurDeChansons, nomChanson, 0);
    }

    function TopChansons() public {
        ajouterChansonElligible("Au clair de la lune");
        ajouterChansonElligible("Maman les p'tits bateaux");
        ajouterChansonElligible("Ah ! Les crocodiles");
    }

}

A noter l’utilisation de « mapping(uint => Chanson) public chansons; »

A lire : https://solidity.readthedocs.io/en/v0.6.6/types.html#mapping-types

Cette structure de donnée va nous permettre de stocker les titres des chansons éligibles à la façon d’une table de hachage. C’est à dire un tableau qui prend pour clé d’accès dans notre cas un uint qui est l’identifiant de la chanson et permet de récupérer la valeur qui est un type Chanson structuré.

Le type Chanson est structuré, voir la documentation solidity : https://solidity.readthedocs.io/en/v0.6.6/types.html#structs

Ici il y a un cas particulier sur la fonction ajouterChansonElligible, elle prends en argument le nom de la chanson qui est une chaine de caractère STRING. Si on ajoute pas le mot clé « memory » on obtient l’erreur suivante:

TypeError: Data location must be « storage » or « memory » for parameter in function, but none was given.

Pour les paramètres de fonction et les variables de retour, l’emplacement des données doit être explicité pour toutes les variables de type (struct, mapping, string).

La migration du contrat s’effectue via la commande :

truffle migrate --reset

On obtient alors :

Compiling your contracts...
===========================
> Compiling ./contracts/Migrations.sol
> Compiling ./contracts/TopChanson.sol

A suivre …

ANGULAR en moins de 128 mots – TypeScript – Angular Partie 8

Cet article fait suite aux sept premiers sur le sujet ANGULAR et porte sur le langage TypeScript :

Templates et interpolation

L’interpolation est l’incorporation d’expressions dans du texte balisé. Par défaut, l’interpolation utilise comme délimiteur les doubles accolades, {{ et }}.

<h3>Client n° : {{ numeroClient }}</h3>

Exemple de directive avec itération :

<li *ngFor="let client of listeClients">{{client.nom}}</li>

Services :

Les services permettent de découpler le composant de l’appel à un service, ils sont ainsi réutilisables.

ng generate service client
import { Injectable } from '@angular/core';

@Injectable({
  providedIn: 'root',
})
export class ClientService {

  constructor() { }

}

La logique est alors découplée du service qui est injectable via l’injection de dépendance.

Injection de dépendance

Exemple d’injection de la dépendance ClientService dans un composant ClientComponent

import { Component, OnInit } from '@angular/core';

import { Hero } from '../hero';
import { HeroService } from '../hero.service';
import { MessageService } from '../message.service';

@Component({
  selector: 'app-heroes',
  templateUrl: './heroes.component.html',
  styleUrls: ['./heroes.component.css']
})
export class ClientComponent implements OnInit {

...

  getClients(): void {
    this.clientService.getClients();
  }
}

Typescript Getter Setter ANGULAR

Cet article fait suite aux six premiers sur le sujet ANGULAR Typescript Getter Setter et porte sur le langage TypeScript :

typescript getter setter

Constructeur :

Le constructeur est la méthode appelée à la création de l’instance d’un objet

class Point {
    x: number;
    y: number;

    constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
    }
    ajouter(point: Point) {
        return new Point(this.x + point.x, this.y + point.y);
    }
}

var p1 = new Point(30, 5);
var p2 = new Point(14, 21);
var p3 = p1.ajouter(p2);

Paramètre optionnel :

Si un paramètre est déclaré optionnel alors tous les paramètres déclarés à sa droite sont optionnels. Exemple du paramètre name dans le constructeur.

class Point {
    x: number;
    y: number;
    name: string;

    constructor(x: number, y: number, name?:string) {
        this.x = x;
        this.y = y;
        this.name = name;
    }
}

Visibilité :

Par défaut la visibilité du paramètre est publique, on peut utiliser des « access modifier » pour la modifier.

class Point {
    private x: number;

Les modificateurs d’accès peuvent être positionnés sur les méthodes, les variables et les propriétés.

class Point {
...
     private ajouter(point: Point) {
        return new Point(this.x + point.x, this.y + point.y);
    }
}
class Point {
...
    constructor(private x: number, private y: number) {
...

L’ajout d’un modificateur d’accès (public / privé / protégé / en lecture seule) à un paramètre constructeur affectera automatiquement ce paramètre à un champ du même nom.

Typescript getter setter :

TypeScript prend en charge les getters / setters comme moyen d’intercepter les accès à un membre d’un objet.

Cela permet d’avoir un contrôle plus fin sur la façon dont un membre est accédé sur chaque objet.

const longueurMaxDuNom = 10;

class Salarie {
    private _nomComplet: string;

    get nomComplet(): string {
        return this._nomComplet;
    }

    set nomComplet(nouveauNom: string) {
        if (nouveauNom && nouveauNom.length > longueurMaxDuNom) {
            throw new Error("Erreur Longueur maxi du nom atteinte, longueur max autorisee = " + longueurMaxDuNom);
        }
        
        this._nomComplet = nouveauNom;
    }
}

let salarie = new Salarie();
salarie.nomComplet = "Toto Hello";
if (employee.nomComplet) {
    console.log(employee.nomComplet);
}

Références à lire :

Typescript getter setter : liens internes

https://128mots.com/index.php/category/graphes/

https://128mots.com/index.php/category/python/

Typescript getter setter Plus d’informations:

Le stockage des classes peut se faire dans des fichiers séparés, dans ce cas il s’agit d’une déclaration de module.

Les modules permettent de rendre accessible la classe en dehors du fichier. La classes doit dans un premier temps être exportée via « export » pour être visible exemple de personne.ts:

Utilisation des classes

Comme dans les autres langages une classe permet de créer des objets et regroupe des variables et des fonctions qui sont fortement liées « Highly Related »

TypeScript est un langage à typage fort typé, orienté objet et compilé. TypeScript est un sur-ensemble typé de JavaScript compilé en JavaScript. TypeScript est JavaScript et quelques fonctionnalités supplémentaires.

La documentation de typescript est disponible sur ce lien : https://www.typescriptlang.org/docs/home.html

Angular est un framework pour construire des applications clientes, il se base sur HTML/CSS et JavaScript/TypeScript.

Angular propose les avantages suivants :

  1. Revealing Module Pattern : permet d’organiser le code en un ou plusieurs modules et donne une meilleure structure.
  2. Architecture propre et structurée.
  3. Code réutilisable.
  4. Application plus facilement testable.

ANGULAR en moins de 128 mots – Composants Angular – Partie 6

Construction d’application par bloc

Les composants sont comme des blocs de construction dans une application Angular.

Les composants sont définis à l’aide du décorateur @component. Un composant possède un sélecteur, un modèle, un style et d’autres propriétés, à l’aide desquels il spécifie les métadonnées requises pour traiter le composant.

Exemple d’architecture en bloc de composant Angular

AppComponent est le composant racine de notre application. C’est la base de l’arborescence des composants de l’application Angular.

https://angular.io/guide/architecture-modules

Pour générer un composant la commande est :

ng g component MyComponent

Exemple de composant :

import { Component } from "@angular/core";

@Component({
  selector: "articles",
  template: "<h2>Article</h2>"
})
export class ArticlesComponent {
}

A noter que si vous n’avez pas utilisé la commande de génération de composant, il faut alors manuellement ajouter le composant dans le fichier src/app/app.module.ts dans les imports

import { BrowserModule } from "@angular/platform-browser";
import { NgModule } from "@angular/core";
import { AppComponent } from "./app.component";
import { ArticlesComponent } from "./articles.component";

@NgModule({
  declarations: [AppComponent, ArticlesComponent],
  imports: [BrowserModule, ArticlesComponent],
  providers: [],
  bootstrap: [AppComponent]
})
export class AppModule {}

ANGULAR en moins de 128 mots – TypeScript – Partie 5

Cet article fait suite aux quatre premiers sur le sujet ANGULAR et porte sur le langage TypeScript :

Utilisation des classes

Comme dans les autres langages une classe permet de créer des objets et regroupe des variables et des fonctions qui sont fortement liées « Highly Related »

Exemple de classe

class Personne {
  nom: string;
  prenom: string;

  sePresenter() {
    console.log('Mon nom est ' + this.nom + ' ' + this.prenom);
  }
}

Modules :

Le stockage des classes peut se faire dans des fichiers séparés, dans ce cas il s’agit d’une déclaration de module.

Les modules permettent de rendre accessible la classe en dehors du fichier. La classes doit dans un premier temps être exportée via « export » pour être visible exemple de personne.ts:

export class Personne {
  nom: string;
  prenom: string;

  sePresenter() {
    console.log('Mon nom est ' + this.nom + ' ' + this.prenom);
  }
}

exemple de fichier main.ts qui importe la classe Personne :

import { Personne } from "./personne";

let personne = new Personne();

A noter qu’il existe des modules Angular qui seront importés avec la mention @angular exemple :

import { Component } from '@angular/core';

A lire :

https://www.typescriptlang.org/docs/handbook/modules.html

https://www.angularchef.com/recette/50/

Algorithme KNN Python : k plus proches voisins

L’algorithme knn python d’apprentissage des k plus proches voisins (KNN) est utilisé pour effectuer de la classification de données.

algorithme knn python

Introduction

Pour prédire la classification d’une nouvelle donnée, l’algorithme se base sur les k enregistrements issus de l’ensemble de données d’apprentissage sont alors localisés les plus similaires à ce nouvel enregistrement.

La similitude entre les enregistrements peut être mesurée de différentes manières. Et généralement un bon point de départ est la distance euclidienne.

L’algorithme knn python :

Pour une entrée x quelle est sa classe y si je me base sur les k voisins les plus proches de x ?

  1. Trouver les k entrée partie les données d’entrainement qui sont les plus « proches » de mon entrée x (ici on utilisera par exemple la distance euclidienne)
  2. Faire voter chacune de ces données d’entrainement pour sa classe y.
  3. Retourner la classe majoritaire

Ainsi, Le succès de l’algorithme va reposer sur la quantité de donnée d’entrainement et sur la qualité de la mesure de la distance entre 2 vecteurs x.

Implémentation python de l’algorithme knn des k plus proches voisins.

Finalement, Voici un exemple d’utilisation et d’implémentation Python sur la base de données qui concerne l’accord d’un crédit en fonction de l’age et du montant demandé. La classe correspond à la réponse OUI ou NON.

from math import sqrt
 
# Faire une predicition de la classification
def predire_classification(donnee_test, entrainement, nombre_voisins_vote):
	voisins = recherche_voisins(entrainement, donnee_test, nombre_voisins_vote)
	sortie = [vecteur[-1] for vecteur in voisins]
	prediction = max(set(sortie), key=sortie.count)
	return prediction


 #Distance euclidienne de 2 vecteurs
def distance_euclidienne(vecteur1, vecteur2):
	distance = 0.0
	for i in range(len(vecteur1)-1):
		distance += (vecteur1[i] - vecteur2[i])**2
	return sqrt(distance)
 

# Recherche les voisins
def recherche_voisins(entrainement, donnee_test, nbVoisins):
	distances = list()
	for ligneEntrainement in entrainement:
		dist = distance_euclidienne(donnee_test, ligneEntrainement)
		distances.append((ligneEntrainement, dist))
	distances.sort(key=lambda tup: tup[1])
	kVoisins = list()
	for i in range(nbVoisins):
		kVoisins.append(distances[i][0])
	return kVoisins
 
 
# Données d'entrainement
donneesApprentissage = [[25,40000,'NON'],
		   [30,60000,'OUI'],
		   [35,80000,'NON'],
		   [45,50000,'NON'],
		   [20,60000,'NON'],
		   [60,15000,'NON'],
		   [70,5000,'OUI'],
		   [80,1000,'NON'],
		   [33,80000,'OUI'],
		   [32,10000,'NON']]

prediction = predire_classification(donneesApprentissage[1], donneesApprentissage, 3)
print('On devrait trouver %s, la prediction est : %s.' % (donneesApprentissage[1][-1], prediction))

Liens externes :

https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins

https://www.python.org/

Liens internes :

https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/
https://128mots.com/index.php/2020/10/09/pytorch-comment-charger-un-modele-pre-entraine/

https://128mots.com/index.php/category/python/

Implémentation Python du parcours en largeur dans les graphes (BFS)

Cet article fait suite à celui qui porte sur l’algorithme BFS ici : https://128mots.com/index.php/2020/02/11/parcours-en-largeur-dans-les-graphes-bfs/

L’implémentation Python de cet algorithme est la suivante :

from collections import deque

def bfs(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    pere = {vertex: None}
    while queue:
    	t = queue.popleft()
    	for voisin in graph[t]:
    		if voisin not in distance:
    			queue.append(voisin)
    			distance[voisin] = distance[t] + 1
    			pere[voisin] = t
    return distance, pere


#Liste d'ajacence du graphe
graph = {
	'A': ['B','C'],
	'B': ['A','C', 'D'],
	'C': ['D'],
	'D': ['C','A']
}

distance,pere = bfs(graph,'A')
print("Distances" + str(distance))
print("Pere = " + str(pere))

Tri fusion Python – implémentation de l’algorithme

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présente une implémentation du tri fusion python.

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présent une implémentation du tri fusion python.

Introduction

L’algorithme est le suivant :
Diviser en deux moitiés la liste à trier.
On trie chacune d’entre elles.
Fusionner les deux moitiés obtenues pour reconstituer la liste triée.

On applique récursivement cet algorithme c’est à dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.

tri fusion python
Tri fusion (source : wikipedia)
#Tri fusion fonction de division du tableau
def tri_fusion(tableau):
    if  len(tableau) <= 1: 
        return tableau
    pivot = len(tableau)//2
    tableau1 = tableau[:pivot]
    tableau2 = tableau[pivot:]
    gauche = tri_fusion(tableau1)
    droite = tri_fusion(tableau2)
    fusionne = fusion(gauche,droite)
    return fusionne


#Tri fusion fonction de fusion de 2 listes
def fusion(tableau1,tableau2):
    indice_tableau1 = 0
    indice_tableau2 = 0    
    taille_tableau1 = len(tableau1)
    taille_tableau2 = len(tableau2)
    tableau_fusionne = []
    while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
        if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
            tableau_fusionne.append(tableau1[indice_tableau1])
            indice_tableau1 += 1
        else:
            tableau_fusionne.append(tableau2[indice_tableau2])
            indice_tableau2 += 1
    while indice_tableau1<taille_tableau1:
        tableau_fusionne.append(tableau1[indice_tableau1])
        indice_tableau1+=1
    while indice_tableau2<taille_tableau2:
        tableau_fusionne.append(tableau2[indice_tableau2])
        indice_tableau2+=1
    return tableau_fusionne

tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
tableau_trie = tri_fusion(tableau)
print(tableau_trie)

A propos de tri fusion

Enfin, Le tri fusion fonctionne par comparaison. La complexité de l’algorithme pour n entrée est n log n, donc asymptotiquement optimal.

La technique est de diviser pour régner. Et l’algorithme fait principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire).

Tri fusion python : liens externes

https://www.geeksforgeeks.org/merge-sort/

http://lwh.free.fr/pages/algo/tri/tri_fusion.html

https://pixees.fr/informatiquelycee/n_site/isn_algo_diviser_pour_regner.html

https://fr.wikipedia.org/wiki/Tri_fusion

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

https://128mots.com/index.php/category/python/

https://128mots.com/index.php/category/graphes/

https://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.

Le langage Python en moins de 128 mots

Python est un langage de programmation qui est caractérisé par :

  • sa lisibilité : La syntaxe du langage est articulé sur la présentation (importance de l’indentation)
  • Pragmatique : L’objectif est de faire des programmes efficaces qui contiennent le moins de lignes de code possible.

Il est également facile d’accès, on peut ainsi facilement échanger avec d’autre programmeur.

La première version de python date de 1994, Python 3 date de 2008. Le langage est stable puisque les anciennes versions du langages continuent d’être maintenue (mise à jour).

Python est portable, il fonctionne sur la plupart des plateformes (mobile, PC, MAC, Linux …), il y a beaucoup de librairies disponibles.

Python est sous licence PSF, le débat sur les évolutions est démocratique et sont soumises au créateur du langage Guido Van Rossum.