<?xml version="1.0" encoding="UTF-8"?><lom xmlns="http://ltsc.ieee.org/xsd/LOM" xmlns:lomfr="http://www.lom-fr.fr/xsd/LOMFR" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://ltsc.ieee.org/xsd/LOM http://www.lom-fr.fr/xsd/lomfrv1.0/std/lomfr.xsd">
<general>
<identifier>
<catalog>Canal-U_Ocms</catalog>
<entry>6494</entry>
</identifier>
<title><string language="fre"><![CDATA[Quelques rudiments de calculabilité et de complexité]]></string></title>
<language>FRE</language>
<description>
<string language="fre"><![CDATA[Dans cet exposé, Paul Gastin, à travers des exemples concrets tel que le jeu du Sudoku, pose les deux problématiques fondamentales de l'algorithmique théorique que sont calculabilité et complexité, en définissant les notions et en donnant des jalons historiques de Hilbert à Gödel et Turing sur les grandes étapes des idées à ce sujet. Il définit les classes de complexité et donne quelques clés pour les évaluer.
Ce cours a été donné en juin 2010 lors des journées de formation à l'informatique organisées par l'INRIA à destination des professeurs de mathématiques d'Ile de France. Il est composé d'une présentation et d'une séance de questions-réponses.]]></string></description>
<keyword><string language="fre"><![CDATA[diagonalisation]]></string></keyword><keyword><string language="fre"><![CDATA[codage]]></string></keyword><keyword><string language="fre"><![CDATA[science informatique]]></string></keyword><keyword><string language="fre"><![CDATA[calculabilité]]></string></keyword><keyword><string language="fre"><![CDATA[programme]]></string></keyword><keyword><string language="fre"><![CDATA[complexité]]></string></keyword><keyword><string language="fre"><![CDATA[modèle de calcul]]></string></keyword><keyword><string language="fre"><![CDATA[réduction]]></string></keyword>
<lomfr:documentType>
<lomfr:source>LOMFRv1.0</lomfr:source>
<lomfr:value>image en mouvement</lomfr:value>
</lomfr:documentType>
</general><lifeCycle>
<contribute>
<role>
<source>LOMv1.0</source>
<value>author</value>
</role>
<entity><![CDATA[BEGIN:VCARD
VERSION:3.0
CLASS:PUBLIC
REV:2021-09-16 17:46:47
FN:Paul GASTIN
N:GASTIN;Paul;;;
URL;TYPE=work:Page personnelle de Paul Gastin
ROLE:author
NOTE:Paul Gastin est professeur des Universités et directeur du Département Informatique à l'ENS Cachan. 
TZ:+0200
END:VCARD
]]></entity>
<date><dateTime>2010-06-02</dateTime></date>
</contribute>
<contribute>
<role>
<source>LOMv1.0</source>
<value>content provider</value>
</role>
<entity><![CDATA[BEGIN:VCARD
VERSION:3.0
CLASS:PUBLIC
REV:2021-09-16 17:46:47
FN:INRIA (Institut national de recherche en informatique et automatique)
N:INRIA (Institut national de recherche en informatique et automatique);;;;
URL;TYPE=work:http://www.inria.fr/
ROLE:content provider
TZ:+0200
END:VCARD
]]></entity>
<date><dateTime>2010-06-02</dateTime></date>
</contribute>
</lifeCycle>
<metaMetadata>
<metadataSchema>LOMv1.0</metadataSchema>
<metadataSchema>LOMFRv1.0</metadataSchema>
</metaMetadata>
<technical>
<format>video/mp4</format>
<location><![CDATA[https://www.canal-u.tv/video/inria/quelques_rudiments_de_calculabilite_et_de_complexite.6494]]></location>
<location><![CDATA[https://streaming-canal-u.fmsh.fr/vod/media/canalu/videos/fuscia/p_gastin.mp4]]></location>
<size>490264229</size>
<duration><duration>PT1H21M10S</duration></duration>
</technical>
<educational>
<learningResourceType>
<source>LOMv1.0</source>
<value>lecture</value>
</learningResourceType>
<context>
<source>LOMv1.0</source>
<value>formation continue</value>
</context>
</educational>
<rights>
<cost>
<source>LOMv1.0</source>
<value>no</value>
</cost>
<copyrightAndOtherRestrictions>
<source>LOMv1.0</source>
<value>no</value>
</copyrightAndOtherRestrictions>
<description>
<string language="fre"><![CDATA[Droits réservés à l'éditeur et aux auteurs. 
]]></string>
</description>
</rights>
<relation>
<kind>
<source>LOMv1.0</source>
<value>ispartof</value>
</kind>
<resource>
<identifier>
<catalog>URI</catalog>
<entry>https://www.canal-u.tv/producteurs/inria/science_info_lycee_profs_conferences_de_formation_des_professeurs_du_secondaire_en_science_informatique</entry>
</identifier>
<description>
<string language="fre"><![CDATA[Science Info Lycée Profs : conférences de formation des professeurs du secondaire en science informatique.]]></string>
</description>
</resource>
</relation>
<classification>
<purpose>
<source>LOMv1.0</source>
<value>discipline</value>
</purpose>
<taxonPath>
<source>
<string language="fre"><![CDATA[Universités Numériques Thématiques 2009 http://www.universites-numeriques.fr]]></string>
</source>
<taxon>
<id/>
<entry>
<string language="fre"/>
</entry>
</taxon>
</taxonPath>
</classification>
<classification>
<purpose>
<source>LOMv1.0</source>
<value>discipline</value>
</purpose>
<taxonPath>
<source>
<string language="fre">CDD 22e éd.</string>
<string language="eng">DDC 22nd ed.</string>
</source>
<taxon>
<id>511.8</id>
<entry>
<string language="fre"><![CDATA[Modélisation mathématique]]></string>
</entry>
</taxon>
</taxonPath>
</classification> </lom>