Foundations of Computer Science

[Vincenzo1968]

http://www.hwupgrade.it/forum/showpost.php?p=39056427&postcount=23

by van9:

Alcuni libri utili per prepararsi (gli ultimi due sono molto impegnativi, ma li cito comunque):
- Algorithmics: the spirit of computing - Harel
- Matematica: questione di metodo - Bramanti
- How to think like a mathematician - Houston
- Che cos'è la matematica? - Courant
- Structure and interpretation of computer programs - Abelson, Sussman
Il miglior libro d'informatica mai scritto
- Foundations of Computer Science - Aho, Ullman
http://i.stanford.edu/~ullman/focs.html


Concordo al 101% sul fatto che il libro di Aho e Ullman sia uno dei migliori testi d'Informatica. Per me al primo posto c'è il Knuth (http://www-cs-faculty.stanford.edu/~uno/taocp.html) "The Art of Computer Programming", ma, subito dopo, viene Aho-Ullman(anzi, quasi quasi, direi a pari merito).

[airon]

http://www.hwupgrade.it/forum/showpost.php?p=39056427&postcount=23

by van9:


Concordo al 101% sul fatto che il libro di Aho e Ullman sia uno dei migliori testi d'Informatica. Per me al primo posto c'è il Knuth (http://www-cs-faculty.stanford.edu/~uno/taocp.html) "The Art of Computer Programming", ma, subito dopo, viene Aho-Ullman(anzi, quasi quasi, direi a pari merito).

Tutti i libri che un informatico dovrebbe avere in libreria e leggere prima di andare a dormire ;)

[Vincenzo1968]

Ohé l'indice:

1. Computer Science: The Mechanization of Abstraction
What This Book Is About 3
What This Chapter Is About 6
Data Models 6
The C Data Model 13
Algorithms and the Design of Programs 20
Some C Conventions Used Throughout the Book 22
Summary of Chapter 1 23
Bibliographic Notes for Chapter 1 24

Chapter 2. Iteration, Induction, and Recursion 25
2.1. What This Chapter Is About 27
2.2. Iteration 27
2.3. Inductive Proofs 34
2.4. Complete Induction 44
2.5. Proving Properties of Programs 52
2.6. Recursive Definitions 59
2.7. Recursive Functions 69
2.8. Merge Sort: A Recursive Sorting Algorithm 75
2.9. Proving Properties of Recursive Programs 84
2.10. Summary of Chapter 2 87
2.11. Bibliographic Notes for Chapter 2 88

Chapter 3. The Running Time of Programs 89
3.1. What This Chapter Is About 89
3.2. Choosing an Algorithm 90
3.3. Measuring Running Time 91
3.4. Big-Oh and Approximate Running Time 96
3.5. Simplifying Big-Oh Expressions 101
3.6. Analyzing the Running Time of a Program 109
3.7. A Recursive Rule for Bounding Running Time 116
3.8. Analyzing Programs with Function Calls 127
3.9. Analyzing Recursive Functions 132
3.10. Analysis of Merge Sort 136
3.11. Solving Recurrence Relations 144
3.12. Summary of Chapter 3 154
3.13. Bibliographic Notes for Chapter 3 155

Chapter 4. Combinatorics and Probability 156
4.1. What This Chapter Is About 156
4.2. Counting Assignments 157
4.3. Counting Permutations 160
4.4. Ordered Selections 167
4.5. Unordered Selections 170
4.6. Orderings With Identical Items 178
4.7. Distribution of Objects to Bins 181
4.8. Combining Counting Rules 184
4.9. Introduction to Probability Theory 187
4.10. Conditional Probability 193
4.11. Probabilistic Reasoning 203
4.12. Expected Value Calculations 212
4.13. Some Programming Applications of Probability
4.14. Summary of Chapter 4 220
4.15. Bibliographic Notes for Chapter 4 221

Chapter 5. The Tree Data Model 223
5.1. What This Chapter Is About 223
5.2. Basic Terminology 224
5.3. Data Structures for Trees 231
5.4. Recursions on Trees 239
5.5. Structural Induction 248
5.6. Binary Trees 253
5.7. Binary Search Trees 258
5.8. Efficiency of Binary Search Tree Operations 268
5.9. Priority Queues and Partially Ordered Trees 271
5.10. Heapsort: Sorting with Balanced POTs 280
5.11. Summary of Chapter 5 284
5.12. Bibliographic Notes for Chapter 5 285

Chapter 6. The List Data Model 286
6.1. What This Chapter Is About 286
6.2. Basic Terminology 287
6.3. Operations on Lists 291
6.4. The Linked-List Data Structure 293
6.5. Array-Based Implementation of Lists 301
6.6. Stacks 306
6.7. Implementing Function Calls Using a Stack
6.8. Queues 318
6.9. Longest Common Subsequences 321
6.10. Representing Character Strings 327
6.11. Summary of Chapter 6 334
6.12. Bibliographic Notes for Chapter 6 335

Chapter 7. The Set Data Model 337
7.1. What This Chapter Is About 337
7.2. Basic Definitions 338
7.3. Operations on Sets 342
7.4. List Implementation of Sets 351
7.5. Characteristic-Vector Implementation of Sets
7.6. Hashing 360
7.7. Relations and Functions 366
7.8. Implementing Functions as Data 373
7.9. Implementing Binary Relations 380
7.10. Some Special Properties of Binary Relations
7.11. Infinite Sets 396
7.12. Summary of Chapter 7 401
7.13. Bibliographic Notes for Chapter 7 402

Chapter 8. The Relational Data Model 403
8.1. What This Chapter Is About 403
8.2. Relations 404
8.3. Keys 411
8.4. Primary Storage Structures for Relations 414
8.5. Secondary Index Structures 419
8.6. Navigation among Relations 423
8.7. An Algebra of Relations 428
8.8. Implementing Relational Algebra Operations 436
8.9. Algebraic Laws for Relations 440
8.10. Summary of Chapter 8 449
8.11. Bibliographic Notes for Chapter 8 450

Chapter 9. The Graph Data Model 451
9.1. What This Chapter Is About 451
9.2. Basic Concepts 452
9.3. Implementation of Graphs 459
9.4. Connected Components of an Undirected Graph
9.5. Minimal Spanning Trees 478
9.6. Depth-First Search 484
9.7. Some Uses of Depth-First Search 495
9.8. Dijkstra’s Algorithm for Finding Shortest Paths
9.9. Floyd’s Algorithm for Shortest Paths 513
9.10. An Introduction to Graph Theory 521
9.11. Summary of Chapter 9 526
9.12. Bibliographic Notes for Chapter 9 527

Chapter 10. Patterns, Automata, and Regular Expressions 529
10.1. What This Chapter Is About 530
10.2. State Machines and Automata 530
10.3. Deterministic and Nondeterministic Automata 536
10.4. From Nondeterminism to Determinism 547
10.5. Regular Expressions 556
10.6. The UNIX Extensions to Regular Expressions 564
10.7. Algebraic Laws for Regular Expressions 568
10.8. From Regular Expressions to Automata 571
10.9. From Automata to Regular Expressions 582
10.10. Summary of Chapter 10 588
10.11. Bibliographic Notes for Chapter 10 589

Chapter 11. Recursive Description of Patterns
11.1. What This Chapter Is About 591
11.2. Context-Free Grammars 592
11.3. Languages from Grammars 599
11.4. Parse Trees 602
11.5. Ambiguity and the Design of Grammars 610
11.6. Constructing Parse Trees 617
11.7. A Table-Driven Parsing Algorithm 625
11.8. Grammars Versus Regular Expressions 634
11.9. Summary of Chapter 11 640
11.10. Bibliographic Notes for Chapter 11 641

Chapter 12. Propositional Logic 642
12.1. What This Chapter Is About 642
12.2. What Is Propositional Logic? 643
12.3. Logical Expressions 645
12.4. Truth Tables 649
12.5. From Boolean Functions to Logical Expressions 655
12.6. Designing Logical Expressions by Karnaugh Maps 660
12.7. Tautologies 669
12.8. Some Algebraic Laws for Logical Expressions 674
12.9. Tautologies and Methods of Proof 682
12.10. Deduction 686
12.11. Proofs by Resolution 692
12.12. Summary of Chapter 12 697
12.13. Bibliographic Notes for Chapter 12 698

Chapter 13. Using Logic to Design Computer Components
13.1. What This Chapter is About 699
13.2. Gates 700
13.3. Circuits 701
13.4. Logical Expressions and Circuits 705
13.5. Some Physical Constraints on Circuits 711
13.6. A Divide-and-Conquer Addition Circuit 716
13.7. Design of a Multiplexer 723
13.8. Memory Elements 730
13.9. Summary of Chapter 13 731
13.10. Bibliographic Notes for Chapter 13 732

Chapter 14. Predicate Logic 733
14.1. What This Chapter Is About 733
14.2. Predicates 734
14.3. Logical Expressions 736
14.4. Quantifiers 739
14.5. Interpretations 745
14.6. Tautologies 751
14.7. Tautologies Involving Quantifiers 753
14.8. Proofs in Predicate Logic 759
14.9. Proofs from Rules and Facts 762
14.10. Truth and Provability 768
14.11. Summary of Chapter 14 774
14.12. Bibliographic Notes for Chapter 14 775

[van9]

http://www.hwupgrade.it/forum/showpost.php?p=39056427&postcount=23

by van9:


Concordo al 101% sul fatto che il libro di Aho e Ullman sia uno dei migliori testi d'Informatica.

Il commento era ovviamente riferito all'Abelson & Sussman!

[Vincenzo1968]

Il commento era ovviamente riferito all'Abelson & Sussman!

Ah! Allora me lo consigli? Lo compro?

[Vincenzo1968]

Ordinato! :O

http://www.amazon.com/Algorithmics-Spirit-Computing-David-Harel/dp/0321117840
http://ecx.images-amazon.com/images/I/51I0ASeDceL._SY300_.jpg

L'Abelson & Sussman no perché c'è la versione online. :O

[Vincenzo1968]

Ohé, tutti commenti positivi da parte degli utenti su Amazon. Ne riporto solo uno:

A great book! April 24, 2003
By Scorn

This book is the most amazing book on algorithms I've read. The concepts are so well explained that moving to "An introduction to Algorithms by Cormen, Rivest" will be very easy.

I come from a non-computer science background. When I started my coursework in Computer Science I was intimidated with Cormen - (although that IS THE MOST AUTHORITATIVE and a complete text!) until I found Harel.

Harel covers ALL the key aspects of algorithms and quite a bit of Data Structs too. He explains all the concepts in a non-mathematical, yet intellectually stimulating manner.One can literally read through the book in single day and gain insight into the most difficult topics like, unsolvable problems, hard problems, NP and NP complete problems.

On a side note - I pity those reviewers who returned the masterpiece and took objection to Bible quotes. Please grow up and look at what the book has to offer instead of taking objection to such insignificant embellishments

EDIT: Anche questo:

5.0 out of 5 stars 'Theoretical Computer Science at 10,000 feet' November 5, 2001
By Optimistix

As the author says, the members of the research community of Computer
Science have done their discipline a disservice by not making any
special efforts to write accessible accounts of the field, as a result
of which the 'layman' still has little idea of what goes on 'under the
hood', so to say.

He has therefore undertaken the challenging task of presenting the basic
ideas underpinning Computer Science in a way that's easy for the general
reader to grasp. He sets out to present the essential notions of
Algorithms and data structures, Turing machines, Finite state machines,
Decidability, Computability, Complexity, NP-completeness, Correctness,
Parallel algorithms, Probabilistic algorithms, and more with a minimum
of mathematics and yet without sacrificing intellectual rigour - and
most admirably, succeeds in doing so.

:yeah: :winner: :yeah: