Algorithms: A Functional Programming Approach (International Computer Science Series)

Note moyenne 4
( 13 avis fournis par Goodreads )
 
9780201596045: Algorithms: A Functional Programming Approach (International Computer Science Series)

The design of algorithms for problem-solving lies at the heart of computer science. Concise yet authoritative, Algorithms - A Functional Programming Approach teaches the skills needed to master this essential subject.

The authors challenge more traditional methods of teaching algorithms by using a functional programming context, with Haskell as the implementation language. This leads to smaller, clearer and more elegant programs which enable the programmer to understand the algorithm itself more quickly and to use that understanding to explore alternative solutions. Placing the emphasis on program development rather than the mathematical properties of algorithms, the book uses a succession of practical programming examples to develop in the reader problem-solving skills which can be easily transferred to other language paradigms.

Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.

About the Author :

Fethi Rabhi completed his PhD in 1990 at Sheffield University (UK). After a short stay at Allegheny College (USA) as a visiting professor, he is now a lecturer in Computer Science at the University of Hull (UK). His teaching and research interests include all aspects of parallel processing and functional languages.

Guy Lapalme is a professor of Computer Science at the University of Montreal in Canada. He has been interested in functional languages for many years, especially their implementation and use in other areas such as natural language semantics and bioinformatics.



0201596040AB04062001

Excerpt. © Reprinted by permission. All rights reserved. :

Purpose/goals

This book is primarily an introduction to the design of algorithms for problem solving. Its prominent feature is to use a functional language as an implementation language. Because of the high level of abstraction provided, functional programs tend to be shorter, clearer and faster to develop than their imperative counterparts. This contributes to a better understanding of the algorithm being implemented and makes it possible to explore alternative solutions more rapidly. Although we believe that this is true for a wide range of algorithms, the book also discusses the limitations of functional style in dealing with certain problems.

This book is not about a particular functional language. The material is arranged in the same way as in a classic algorithms book: it is a succession of chapters on 'traditional' topics such as sorting and searching algorithms. In addition, the choice of a functional language permits the introduction of algorithm design strategies such as divide-and-conquer and dynamic programming by means of higher-order functions. New concepts such as process networks and parallel algorithms can also be introduced in a non-conventional way. Due to this extra material, topics such as lower bound proofs and N-P completeness theory are not covered.

The emphasis of the book is on intuitive and pragmatic program development techniques. This is only a small step forward, as we believe that functional programming provides a link between the study of algorithms and the study of correctness proofs and systematic derivation from formal specifications. We are hoping that more publications covering this area will emerge in the near future.

Another aim of this book is to provide a useful reference of functional programs related to a variety of problems. Programmers will be able to choose (or adapt) a functional program that is relevant to their problem as they already do with other languages such as Fortran, Pascal or C. We are also hoping that this book will contribute towards making functional languages more viable as a programming tool.

Approach

Each chapter addresses a specific problem area by describing the associated algorithms. Each algorithm is specified using a trivial (but sometimes inefficient) functional program. In some cases, a more efficient (and often more obscure) version can be derived. Sections containing non-essential material are marked with a (t) symbol and can be safely skipped. Exercises are included at the end of each chapter. For an excellent companion book which provides further details about most of the algorithms presented in this book, we recommend Brassard and Bratley's Fundamentals of Algorithmics 19.

Another feature of the book is the use of Haskell, a newly proposed functional language standard, named after the logician Haskell B. Curry. Haskell is purely functional, uses lazy evaluation and incorporates most of the features of modern functional languages. It is free to use, has numerous implementations on almost all platforms, and is available from sites worldwide. Appendix A provides some information about these implementations.

The Haskell source code of the programs given in this book and the answers to selected exercises are available from the following WWW site:
http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html

Target audience

This book is primarily targeted at undergraduate students in computer science studying algorithms. Within a traditional course that uses imperative languages, only a fraction of the known algorithms can be completely implemented. By adopting a functional language, more prototypes can be developed; this contributes to a better understanding of the techniques involved, since implementing a particular algorithm requires a complete understanding of all the details related to this algorithm. This approach also allows experimentation with certain types of algorithms (such as process networks) which would be too difficult to program in an imperative language.

The prerequisites are:

  • Students must have had some programming experience in any language, preferably a functional language. Some notion of how functional languages are implemented is also desirable.

  • A minimum mathematical background (mostly summations) is required for the analysis of algorithms although these sections can safely be omitted by those who are not interested in complexity or efficiency analysis.

The book can also be used to support an advanced functional programming course in a variety of ways: (1) by presenting examples of implementing and using data structures such as queues, trees and graphs, (2) by introducing program design techniques, (3) by increasing the awareness concerning time and space efficiency, and (4) by presenting some advanced topics such as process networks and parallel algorithms.

As mentioned previously, the book is also a useful source of functional programs which can be regarded as executable specifications of the algorithms concerned.

Overview

The book is roughly divided into three parts. The first part contains all the background information needed before embarking on the main body of the book. Chapter I presents the basic concept of an algorithm and highlights key features of functional languages with a brief history of their evolution and role in recent years. Chapter 2 contains an introduction to the functional language Haskell. Chapter 3 is a review of evaluation mechanisms such as strict and lazy evaluation, with an overview of the graph reduction model. It defines what is meant by 'efficiency' and presents some simple transformations that increase the efficiency of programs. Chapter 4 examines simple concrete data structures (lists, trees, and arrays) and the efficiency of the operations used to manipulate these data structures.

The second part of the book considers some basic algorithms for a variety of purposes. Chapter 5 examines abstract data types (ADTs), using them to represent for example priority queues and binary search trees. Chapter 6 presents sorting techniques such as quicksort and heapsort and Chapter 7 discusses graphs and associated algorithms such as computing the minimum spanning tree and depth-first search.

The last part addresses some high-level methodologies used in the design of algorithms. Chapter 8 describes top-down design techniques such as divide-and-conquer and backtracking search. Chapter 9 explains some inefficiencies in top-down algorithms and how they can be solved by adopting a bottom-up approach, namely dynamic programming. Finally, Chapter 10 examines some advanced topics such as process networks, monads, and parallel algorithms through some extensions to the Haskell language.

Acknowledgments

The idea of the book came while the first author was a visiting lecturer at Allegheny College so our special thanks are due to Mike Holcombe, Bob Cupper and Ben Haytock for making it possible. We would like to thank Aster Thien, Marina Mahmood, Chris Meen, Len Bottaci and Rob Turner for their contribution to some of the programs presented in this book. We also thank Guy St-Denis for his many constructive suggestions on a preliminary version of this book, our editor Michael Strang for his continued support, and the anonymous reviewers who found many inaccuracies and gave constructive ideas on presentation. Finally, we are grateful to the (enthusiastic!) Haskell community for their efforts in designing a standard functional language and for providing the scientific community with free implementations.

Fethi Rabhi (F.A.Rabhi@dcs. hull. ac. uk)
Guy Lapalme (lapalme@iro. umontreal. ca)



0201596040P04062001

Les informations fournies dans la section « A propos du livre » peuvent faire référence à une autre édition de ce titre.

Meilleurs résultats de recherche sur AbeBooks

1.

Fethi A. Rabhi; Guy Lapalme
Edité par Addison Wesley (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 1
Vendeur
Ergodebooks
(RICHMOND, TX, Etats-Unis)
Evaluation vendeur
[?]

Description du livre Addison Wesley, 1999. Paperback. État : New. N° de réf. du libraire SONG0201596040

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 49,32
Autre devise

Ajouter au panier

Frais de port : EUR 3,43
Vers Etats-Unis
Destinations, frais et délais

2.

Rabhi, Fethi A., Lapalme, Guy
Edité par Addison-Wesley (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 2
Vendeur
Murray Media
(North Miami Beach, FL, Etats-Unis)
Evaluation vendeur
[?]

Description du livre Addison-Wesley, 1999. Paperback. État : New. N° de réf. du libraire P110201596040

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 51,01
Autre devise

Ajouter au panier

Frais de port : EUR 2,57
Vers Etats-Unis
Destinations, frais et délais

3.

Fethi Rahbi, Guy Lapalme
Edité par Pearson Education (US), United States (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 10
impression à la demande
Vendeur
The Book Depository US
(London, Royaume-Uni)
Evaluation vendeur
[?]

Description du livre Pearson Education (US), United States, 1999. Paperback. État : New. 2nd ed.. Language: English . Brand New Book ***** Print on Demand *****. The design of algorithms for problem-solving lies at the heart of computer science. Concise yet authoritative, Algorithms - A Functional Programming Approach teaches the skills needed to master this essential subject. The authors challenge more traditional methods of teaching algorithms by using a functional programming context, with Haskell as the implementation language. This leads to smaller, clearer and more elegant programs which enable the programmer to understand the algorithm itself more quickly and to use that understanding to explore alternative solutions. Placing the emphasis on program development rather than the mathematical properties of algorithms, the book uses a succession of practical programming examples to develop in the reader problem-solving skills which can be easily transferred to other language paradigms. N° de réf. du libraire AAV9780201596045

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 70,04
Autre devise

Ajouter au panier

Frais de port : Gratuit
De Royaume-Uni vers Etats-Unis
Destinations, frais et délais

4.

Fethi Rahbi, Guy Lapalme
Edité par Pearson Education (US), United States (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 10
impression à la demande
Vendeur
The Book Depository
(London, Royaume-Uni)
Evaluation vendeur
[?]

Description du livre Pearson Education (US), United States, 1999. Paperback. État : New. 2nd ed.. Language: English . Brand New Book ***** Print on Demand *****.The design of algorithms for problem-solving lies at the heart of computer science. Concise yet authoritative, Algorithms - A Functional Programming Approach teaches the skills needed to master this essential subject. The authors challenge more traditional methods of teaching algorithms by using a functional programming context, with Haskell as the implementation language. This leads to smaller, clearer and more elegant programs which enable the programmer to understand the algorithm itself more quickly and to use that understanding to explore alternative solutions. Placing the emphasis on program development rather than the mathematical properties of algorithms, the book uses a succession of practical programming examples to develop in the reader problem-solving skills which can be easily transferred to other language paradigms. N° de réf. du libraire AAV9780201596045

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 70,05
Autre devise

Ajouter au panier

Frais de port : Gratuit
De Royaume-Uni vers Etats-Unis
Destinations, frais et délais

5.

Rabhi, Fethi
Edité par Addison Wesley (2016)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 1
impression à la demande
Vendeur
Ria Christie Collections
(Uxbridge, Royaume-Uni)
Evaluation vendeur
[?]

Description du livre Addison Wesley, 2016. Paperback. État : New. PRINT ON DEMAND Book; New; Publication Year 2016; Not Signed; Fast Shipping from the UK. No. book. N° de réf. du libraire ria9780201596045_lsuk

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 69,28
Autre devise

Ajouter au panier

Frais de port : EUR 4,33
De Royaume-Uni vers Etats-Unis
Destinations, frais et délais

6.

Fethi A. Rabhi
Edité par Pearson Education (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Quantité : > 20
impression à la demande
Vendeur
Books2Anywhere
(Fairford, GLOS, Royaume-Uni)
Evaluation vendeur
[?]

Description du livre Pearson Education, 1999. PAP. État : New. New Book. Delivered from our UK warehouse in 3 to 5 business days. THIS BOOK IS PRINTED ON DEMAND. Established seller since 2000. N° de réf. du libraire LQ-9780201596045

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 64,09
Autre devise

Ajouter au panier

Frais de port : EUR 10,08
De Royaume-Uni vers Etats-Unis
Destinations, frais et délais

7.

Rahbi, Fethi/ Lapalme, Guy
Edité par Addison-Wesley (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 1
Vendeur
Revaluation Books
(Exeter, Royaume-Uni)
Evaluation vendeur
[?]

Description du livre Addison-Wesley, 1999. Paperback. État : Brand New. 2nd edition. 256 pages. 9.50x7.50x0.75 inches. In Stock. N° de réf. du libraire zk0201596040

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 76,05
Autre devise

Ajouter au panier

Frais de port : EUR 6,71
De Royaume-Uni vers Etats-Unis
Destinations, frais et délais

8.

Fethi A. Rabhi, Guy Lapalme
Edité par Addison-Wesley (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 1
Vendeur
Ergodebooks
(RICHMOND, TX, Etats-Unis)
Evaluation vendeur
[?]

Description du livre Addison-Wesley, 1999. Paperback. État : New. 1. N° de réf. du libraire DADAX0201596040

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 82,02
Autre devise

Ajouter au panier

Frais de port : EUR 3,43
Vers Etats-Unis
Destinations, frais et délais

9.

Fethi A. Rabhi; Guy Lapalme
Edité par Addison-Wesley (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Paperback Quantité : 1
Vendeur
Irish Booksellers
(Rumford, ME, Etats-Unis)
Evaluation vendeur
[?]

Description du livre Addison-Wesley, 1999. Paperback. État : New. book. N° de réf. du libraire 0201596040

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 95,65
Autre devise

Ajouter au panier

Frais de port : Gratuit
Vers Etats-Unis
Destinations, frais et délais

10.

Fethi Rabhi; Rabhi; Guy Lapalme
Edité par Addison Wesley (1999)
ISBN 10 : 0201596040 ISBN 13 : 9780201596045
Neuf(s) Couverture souple Quantité : 1
impression à la demande
Vendeur
European-Media-Service Mannheim
(Mannheim, Allemagne)
Evaluation vendeur
[?]

Description du livre Addison Wesley, 1999. État : New. This item is printed on demand for shipment within 3 working days. N° de réf. du libraire GM9780201596045

Plus d'informations sur ce vendeur | Poser une question au libraire

Acheter neuf
EUR 119,79
Autre devise

Ajouter au panier

Frais de port : EUR 3,99
De Allemagne vers Etats-Unis
Destinations, frais et délais