Créer une présentation
Télécharger la présentation

Télécharger la présentation
## Algorithms, Programs, and Computers

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Algorithms, Programs, and Computers**CS 110 Fall 2005**Problem Solving**• You want to make money and you have some simpletons who are willing to help • Devise aplan that will make money (write a business plan for starting a restaurant) • Tell the simpletons to execute the business plan**Problem Solving**• The simpletons can make mistakes • Refine the communication of instructions to them • Use time cards, tables, flow charts, pictures • Develop a bullet proof “process”**Problem Solving**• You want to make money and you have a computer to help you • Devise an algorithm (plan) • Make the algorithm very detailed so a simpleton can do it (program) • Execute the program (computer)**Hardware / Software**• A program is a sequence of instructions that tell the computer what to do • What language do computers speak? • What language do people speak?**Computer Language**• Assembly Language • ADD R1, R2 • MOV [R5], R1 • IF (R4 < R2) JMP A: • Very sequential • Like a flow chart • Not the language of human users**It Gets Worse**• Computer logic is even more primitive • AND • OR • NOT • All programs (nearly every electronic device you use) operates with only these three logical operations**It Gets Much Better**• Computer software exists to create an abstraction between AND/OR/NOT and human language/logic • Programming Languages • C++, Java, C#, Perl**C++**void main (int argc, char **argv) { printf (“Hello, world\n”); }**Java**class program { public static void main(String args[]) { System.out.println("Hello World!"); } }**Why So Many Languages?**• Each has strengths and weaknesses • Error protection • Syntax in English vs. syntax in German • Expressiveness • Eskimo words for snow**Multipurpose Computers**• How can computers interpret so many different languages? • Translate them all into a common language (machine language) • Compilers!**Recap: Problem Solving**• Computers execute machine language • Programs are a sequence of instructions in some language • Compilers transform programs from one language to another, usually a simpler one**Algorithms**• The way one solves a problem • Divide and conquer • Top-down or bottom-up • Simplify • Deduction • Trial and error**Dealing Out Cards**• Poker: deal five cards to everyone at the table How? (step by step)**Recap: Algorithms**• An approach to solving a problem • A sequence of steps • Break a complex problem into simpler pieces The first step in making computers work for you!**Complexity**• There’s a danger here • Time is scarce • Simple algorithms may entail inordinate time and resources • Computers are simpletons • We must think about an algorithm’s complexity before using it**Complexity of Cards**• Consider dealing five cards • One second per deal • How long to finish dealing five cards to: 2 players**Complexity of Cards**• Consider dealing five cards • One second per deal • How long to finish dealing five cards to: 3 players**Complexity of Cards**• Consider dealing five cards • One second per deal • How long to finish dealing five cards to: 4 players**Complexity of Cards**• Consider dealing five cards • One second per deal • How long to finish dealing five cards to: 100 players**Complexity of Cards**• It takes 5 * num_players time A Linear Time Algorithm time Number of players**Complexity of Other Problems**• Many problems are polynomial (n2) • Execution time grows as the square of the problem size (sorting names) time Problem size**Complexity of Other Problems**• Many problems are exponential (2n) • Execution time grows as to the nth with increase in problem size (Traveling Salesperson Problem) time Problem size**Complexity of Other Problems**• Some problems are intractable • There are 1079 atoms in Universe • It would be impossible to solve an algorithm this complex**Complexity of Other Problems**• Some problems are not computable • Literally no end to computation to be donw**Recap: Algorithms**• Algorithms have different complexities • Complexity is important to understand • What is knowable? • How difficult is it to acquire?