Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Structures de données fonctionnelles : Collections et opérations

Dans cours

CS-214: Software construction

Learn how to design and implement reliable, maintainable, and efficient software using a mix of programming skills (declarative style, higher-order functions, inductive types, parallelism) and fundamental software construction concepts (reusability, abstr ...

Description

Cette séance de cours couvre les structures de données fonctionnelles, en se concentrant sur les relations entre les collections comme les listes, les ensembles, les sacs et les cartes. Il explique comment relier les collections, mettre en œuvre des séquences, des cartes et des sacs, et construire des arbres efficacement. La séance de cours traite également du partage de la structure, de l'analyse du temps de fonctionnement et des invariants des structures de données.

Enseignant·e·s (2)

Martin Odersky

Martin Odersky heads the programming research group at EPFL. His research interests cover fundamental as well as applied aspects of programming languages. They include semantics, type systems, programming language design, and compiler construction. The main focus if his work lies in the integration of object-oriented and functional programming. His research thesis is that the two paradigms are just two sides of the same coin and should be unified as much as possible. To prove this he has experimented a number of language designs, from Pizza to GJ to Functional Nets. He has also influenced the development of Java as a co-designer of Java generics and as the original author of the current javac reference compiler. His current work concentrates on the Scala programming language, which unifies FP and OOP, while staying completely interoperable with Java and .NET. Martin Odersky got his doctorate from ETHZ, in 1989. He held research positions at the IBM T.J. Watson Research Center from 1989 and at Yale University from 1991. He was then a professor at the University of Karlsruhe from 1993 and at the University of South Australia from 1997. He joined EPFL as full professor in 1999. He is associate editor of the Journal of Functional Programming and member of IFIP WG 2.8. He was conference chair for ICFP 2000, and program chair for ECOOP 2004 as well as ETAPS/CC 2007.

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Source officielle

Concepts associés (32)

Structure de données persistante

En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu'elle est modifiée ; une telle structure est immuable, car ses opérations ne la modifient pas en place (de manière visible) mais renvoient au contraire de nouvelles structures. Une structure est partiellement persistante si seule sa version la plus récente peut être modifiée, les autres n'étant accessibles qu'en lecture. La structure est dite totalement persistante si chacune de ses versions peut être lue ou modifiée.

Purely functional data structure

In computer science, a purely functional data structure is a data structure that can be directly implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) immutable. This restriction ensures the data structure possesses the advantages of immutable objects: (full) persistency, quick copy of objects, and thread safety. Efficient purely functional data structures may require the use of lazy evaluation and memoization.

Arbre binaire

En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.

Programmation purement fonctionnelle

En informatique, la programmation purement fonctionnelle est un paradigme de programmation qui considère toutes les opérations comme l'évaluation de fonctions mathématiques. L'état et les objets immuables sont généralement modélisés à l'aide d'une logique temporelle, en tant que variables explicites représentant l'état du programme à chaque étape de son exécution : l'état d'une variable est transmis en tant que paramètre d'entrée d'une fonction de transformation d'état, qui renvoie l'état mis à jour en tant que partie de sa valeur de retour.

Arbre

vignette|Les arbres sont notamment représentés par des espèces du groupe des plantes à fleurs comme ces jacarandas au Zimbabwe. vignette|Même les arbres les plus majestueux commencent leur existence sous forme de modestes plantules, comme celle-ci de hêtre (Fagus sylvatica). vignette|Les arbres contribuent significativement au bien-être et à la subsistance des sociétés humaines. De nombreuses espèces produisent des fruits comestibles, comme ici l'arbre à pain (Artocarpus altilis).

Afficher plus

Séances de cours associées (27)

Conc-Trees: Programmation parallèle en Scala

Couvre la mise en œuvre de Conc-Trees à Scala pour la programmation parallèle.

Mise en œuvre des mélangeurs

Couvre la mise en œuvre de combinaisons dans la programmation parallèle à Scala, y compris des méthodes de combinaison efficaces et des structures de données.

Programmation fonctionnelle: concepts et mise en œuvre

Couvre les concepts et la mise en œuvre de la programmation fonctionnelle dans Scala, mettant l'accent sur les fonctions, les données immuables et l'abstraction des données.

Mutation sans danger à Scala

Explore la mutation sûre dans Scala, en mettant l'accent sur la gestion de l'état mutable et son importance dans les interactions, la modélisation et l'efficacité de mise en œuvre.

Structures de données dynamiques : vecteurs et listes liées

Couvre la comparaison entre les vecteurs et les listes liées en programmation C++.

Afficher plus

Concepts associés (32)

Structure de données persistante

Purely functional data structure

Arbre binaire

Programmation purement fonctionnelle

Arbre

Afficher plus