Rozwiązywanie problemów za pomocą algorytmów i struktur danych¶
Bradley N. Miller, David L. Ranum
Tłumaczenie: Witold Ilewicz, Michał Lewecki, Łukasz Machura
Wstęp¶
- Cele rozdziału
- Wprowadzenie
- Czym jest Informatyka?
- Czym jest programowanie
- Struktury i abstrakcyjne typy danych
- Algorytmy
- Podstawy języka Python - przypomnienie
- Pierwsze kroki z danymi
- Funkcja Input i Output
- Struktury kontrolne
- Obsługa wyjątków
- Defining Functions
- Object-Oriented Programming in Python: Defining Classes
- Summary
- Key Terms
- Discussion Questions
- Programming Exercises
Analysis¶
Basic Data Structures¶
- Objectives
- What Are Linear Structures?
- What is a Stack?
- The Stack Abstract Data Type
- Implementing a Stack in Python
- Simple Balanced Parentheses
- Balanced Symbols (A General Case)
- Converting Decimal Numbers to Binary Numbers
- Infix, Prefix and Postfix Expressions
- What Is a Queue?
- The Queue Abstract Data Type
- Implementing a Queue in Python
- Simulation: Hot Potato
- Simulation: Printing Tasks
- What Is a Deque?
- The Deque Abstract Data Type
- Implementing a Deque in Python
- Palindrome-Checker
- Lists
- The Unordered List Abstract Data Type
- Implementing an Unordered List: Linked Lists
- The Ordered List Abstract Data Type
- Implementing an Ordered List
- Summary
- Key Terms
- Discussion Questions
- Programming Exercises
Recursion¶
- Objectives
- What Is Recursion?
- Calculating the Sum of a List of Numbers
- The Three Laws of Recursion
- Converting an Integer to a String in Any Base
- Stack Frames: Implementing Recursion
- Introduction: Visualizing Recursion
- Sierpinski Triangle
- Complex Recursive Problems
- Tower of Hanoi
- Exploring a Maze
- Dynamic Programming
- Summary
- Key Terms
- Discussion Questions
- Glossary
- Programming Exercises
Sorting and Searching¶
Trees and Tree Algorithms¶
- Objectives
- Examples of Trees
- Vocabulary and Definitions
- List of Lists Representation
- Nodes and References
- Parse Tree
- Tree Traversals
- Priority Queues with Binary Heaps
- Binary Heap Operations
- Binary Heap Implementation
- Binary Search Trees
- Search Tree Operations
- Search Tree Implementation
- Search Tree Analysis
- Balanced Binary Search Trees
- AVL Tree Performance
- AVL Tree Implementation
- Summary of Map ADT Implementations
- Summary
- Key Terms
- Discussion Questions
- Programming Exercises
Graphs and Graph Algorithms¶
- Objectives
- Vocabulary and Definitions
- The Graph Abstract Data Type
- An Adjacency Matrix
- An Adjacency List
- Implementation
- The Word Ladder Problem
- Building the Word Ladder Graph
- Implementing Breadth First Search
- Breadth First Search Analysis
- The Knight’s Tour Problem
- Building the Knight’s Tour Graph
- Implementing Knight’s Tour
- Knight’s Tour Analysis
- General Depth First Search
- Depth First Search Analysis
- Topological Sorting
- Strongly Connected Components
- Shortest Path Problems
- Dijkstra’s Algorithm
- Analysis of Dijkstra’s Algorithm
- Prim’s Spanning Tree Algorithm
- Summary
- Key Terms
- Discussion Questions
- Programming Exercises
Informacje o wydaniach¶
Problem Solving with Algorithms and Data Structures using Python
Copyright © 2005 Brad Miller, David Ranum
Wydanie 1, Franklin Beedle & Associates 2005, ISBN: 1590280539
Problem Solving with Algorithms and Data Structures using Python
Copyright © 2014 Brad Miller, David Ranum
Wersja interaktywna opracowana w ramach projektu Runestone Interactive realizowanego w Luther College.
Rozwiązywanie problemów za pomocą algorytmów i struktur danych
Copyright © 2015 Witold Ilewicz, Michał Lewecki, Łukasz Machura
Opracowanie w ramach projektu PWP Partnerstwo - Informatyka - Nanofizyka - PIN współfinansowanego przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.
Książka wydana na licencji Creative Commons BY-NC-SA 4.0.