[卓越演講]Algorithm Design with Functional Programming (以英文演講)
- 講者Jeremy Gibbons 教授 (Department of Computer Science, University of Oxford, England)
邀請人:柯向上 - 時間2023-08-17 (Thu.) 10:00 ~ 12:00
- 地點資訊所106演講廳
線上串流
- 會議鏈結:
- https://asmeet.webex.com/asmeet/j.php?MTID=ma3081776130851e5db39162450100f1b
- 會議號:
- 2514 128 7597
- 密碼:
- p8EMiCabz28
摘要
Algorithm design is a core topic in computer science. It is traditionally taught using two distinct formalisms: some form of mathematics for the "algorithms", and some programming language for their "implementations". I will show that only one formalism is needed: the right choice of programming language - specifically, a functional programming language - can also serve as the mathematical notation. This simplification removes some sources of confusion and vagueness.
The talk is based on the book "Algorithm Design with Haskell" by Richard Bird and Jeremy Gibbons (CUP, 2020). The book is devoted to five main principles of algorithm design: divide and conquer, greedy algorithms, thinning, dynamic programming, and exhaustive search. These principles are presented using Haskell, leading to simpler explanations and shorter programs than would be obtained with imperative languages. Carefully selected examples, both new and standard, reveal the commonalities and highlight the differences between algorithms. The algorithm developments use equational reasoning where applicable, clarifying the applicability conditions and correctness arguments. I will describe the premise of the book, including in particular the small aspect in which Haskell is insufficient, and present an example.
The talk is based on the book "Algorithm Design with Haskell" by Richard Bird and Jeremy Gibbons (CUP, 2020). The book is devoted to five main principles of algorithm design: divide and conquer, greedy algorithms, thinning, dynamic programming, and exhaustive search. These principles are presented using Haskell, leading to simpler explanations and shorter programs than would be obtained with imperative languages. Carefully selected examples, both new and standard, reveal the commonalities and highlight the differences between algorithms. The algorithm developments use equational reasoning where applicable, clarifying the applicability conditions and correctness arguments. I will describe the premise of the book, including in particular the small aspect in which Haskell is insufficient, and present an example.
BIO
Jeremy Gibbons is Professor of Computing at the University of Oxford, where he leads the Algebra of Programming research group, and is Director of the part-time professional postgraduate master’s programme in Software Engineering. His research interests are in programming languages, especially functional programming and patterns in programming. He is Editor-in-Chief of the The Art, Science, and Engineering of Programming (and was until recently Editor-in-Chief of the Journal of Functional Programming), and a member of IFIP Working Group 2.1 on Algorithmic Languages and Calculi, and of IFIP Working Group 2.11 on Program Generation.