Home

Slides

1. Consistent Each break out must be the same kind Orderly All blocks at the same level must be separate or independent Refined Each box of a given level must be break out of a box at the previous level Cohesive All of the items within a breakout box must fit together Mistakes and corrections nn Learning nouns Incorrect BOD a Learning Learning words English 5 Learning grammar Correct BOD a Learning Learning words English 5 Learning grammar Learning nouns Learning other words Mistakes and corrections Incorrect BOD Correct BOD Pre coffee Pre coffee Coffee break Coffee break Post coffee Post coffee AM NY __Lunch Soup 4 Main course S _ ME Pre Tea Time Pre Tea Time y Evening B Tea Time Teas time Diner time N Snack time Diner time Snack time 44 Mistakes and corrections Incorrect BOD Get out of bed ae Morning A Shower Pa l een e Drink coffee routine Eat Eat cereal Go to work Read news Correct BOD num Get out of bed Morning gad Ma In Breakfast Q8 a MA routine A x Drink coffee G k Eat sa MAC to wor Eu sg Eat cereal Read news E 45 Exercises and examples Draw BODs of the following things Computer architecture Human body Surface of Earth Phone number Starting a car Set up a TV set Using computer Your plan for tomorrow Solution refinement Algorithms Algorit
2. Leap year Exercises and examples How do the values of x y and s change during the process if x 5 and y 4 What is the output in this case How many times will the condition evaluated What does this algorithm do How can you modify it to calculate the product of x and y Exercises and examples How do the values of x and y change during the process if the input is 10 What is the output if the input is 60 What does this algorithm do y 2 i if x 1 Is it work if x 1 T false If the input is 24 how D many iterations will ue ay false C End gt be executed ir 7 How can it faster Exercises and examples Day of year Searching in ordered binary tree Raising to power Conversion of decimal number to binary Addition of binary numbers Solving second degree equation Calculating factorial Exercises and examples This flowchart describes the algorithm of a calculation of the remain of a division Complete it af false e Start true a lt b EC lt 0 WZA e dn SEK gt A 0 a a du d ASL oro ELTE TEL out error PET 7 e out a Gn e End Pseudocode Sequence Selection Iteration statement1 if condition then while condition do statement2 statementl statementl statement3 else enddo statement2 endif Exercises and examples input a e What is the output if a 10 if a 0 then e What is the output if a 4 i ra What does the algorithm do else b a e Wha
3. Maintenance Documentation Complete the documentation e Always document everything during the program development e What is the solution method e What are the solved subproblems e What are the necessary inputs and the output e How does the implemented algorithm work e What are the meaning of the variables comments How to use the program user manual e What are the discovered errors and their solutions Maintenance Maintenance the program e f the users need correct extend and update you application e Make documentation about all changes This is the END
4. work Programmer developes computer applications writes programs Problem solving Polya s problem solving steps Understanding the problem What is the task What is the unknown required result What is the relationship between the given information and the unknown Is the given information enough to solve the problem Creating a plan General techniques e Finding known similar problems if exists e Reshaping the original problem to a similar known problem Devide the problem to shorter solvable problems Generalizing a restricted problem e Finding existing work that can help in the search for a solution Executing the plan Follow the steps of the plan Each element of the plan should be checked as it is applied If a part of the plan is unsatisfactory the plan should be revised Evaluating The result should be examined s it correct e s it full s it valid Hasthe problem been solved An example What is the sum of 110010110 and 101110101 in binary notation See Number systems slides Software Life Cycle Software Life Cycle 1 Problem definition Similar to P lya s first step The description of the problem must be precise User and programmer must work together It leads to complete specitications of the problem the input datas and the desired output 2 Solution design Definition of the outline of solution Division of the original problem i
5. Collection of software that manages hardware resources and provides services for other programs User interface supports human interaction shell GUI Program scheduler decides which program can run now for how long time which will the next File management handles the files and directories of volume based on a file system Operating system Memory management provides ways to dynamically allocate portions of memory to programs at their request Device drivers software developed to allow interaction with hardware devices Security protect against illegal operation and access to datas Others Networking Interrupt management Utilities User applications File manager Windows Explorer Midnight commander Office application Microsoft Word Excel OpenOffice Write Calc Web browser Internet Explorer Firefox Crome Database manager Microsoft Access MySQL DB2 Graphical program Microsoft Paint GIMP Photoshop User applications Media player Windows Media Player Flash Player QuickTime Computer game Minesweeper Solitaire NFS CoD FIFA Anti virus program Virus Buster NOD32 AVG Integrated Development Environment IDE BorlandC Netbeans CodeBlocks Dev C Other User Human agent who uses computer Root Superuser system addministrator has high privilege e Simple user computer is just a tool not the purpose of
6. Introduction to Introduction to programming Imre Varga University of Debrecen Faculty of Informatics For internal use only 04 May 2014 General informations Teacher Dr Varga Imre University of Debrecen Faculty of Informatics Depertment of Informatics Systems and Networks email varga imre inf unideb hu www irh inf unideb hu user vargai room IF13 building of Faculty of Informatics General informations Requirements conditions Maximum number of absences is 3 Maximum late from classes is 20 minutes More than 20 minutes late means absent from class There will be two tests during the semester There is only one chance to retake Activity during class means plus score Furter readings Adrian Kingsley Hughes Beginning Programming Wiley 2005 Metrowerks CodeWarrior Principles of Programming Topics What are the basics of Informatics How does a computer built up How does a computer work What is software application program How to describe problems and its solution What is algorithmic thinking What does program writing mean Many more things Computer systems Computer System User Hardware Software Computer architecture hardware ROM System Unit 7 System Unit Central Processing Unit CPU The brain of computers Memory Contains datas and instructions ata ta Input Output Interface Surface between computer and outer wor
7. Syntax and semantics Syntax Formal rules of the program text Semantics Does it describe the desired algorithm Example absolute value input a Semantic error if a gt 0 then a l a enidf output a Syntax error Syntax of programing languages Fortran REAL FUNCTION FAKT I FAKT 1 TE I EQ O OR I EO 1 RETURN DO 20 K 2 I 20 FAKT FAKT K RETURN END Pascal FUNCTION FAKT 1 INTEGER REAL BEGIN IF I 0 THEN FARKT 1 ELSE FAKT FAKT I 1 I C END long fakt long n if n lt 1 return 1 else return n fakt n 1 Units and elements of the code Character set ESES We use different characters symbols special keywords expressions and rules in each language Syntactic units Instructions Program units aseaJ2ul AJIX2 dLUOJ Compiling units Program C programming language Solving second degree equation include lt stdio h gt include lt math h gt int main float 8 D C d x1 zx2 printf Give the coefficients n scanf f Sf f amp a amp b amp c if a 0 0 first degree if b 0 0 printf Error An else x1 c b printf x fNn x1l else second degree d b b 4 a c if d gt 0 0 two solution x1 b sqrt d 2 a x1 b sqrt d 2 a printf x1 f nx2 f n x1 x2 else if d 0 0 one solution xl b 2 a printf x fWMn x1 else no solution printf Error n 97 return 0 Documentation amp
8. e lift 2 Get in oF 4 5 Push 5 button Wait If the door opens get out Problems not complet e If the list goes downward e f the lift stops on 3rd floor for somebody Wrong algorithms How to make fried chicken Puc the chicken into the oven 2 Set the temperature 3 Wait until it is done 4 Serve it Problems ambiguity What is the optimal temperature 50 C or 200 C e Is the chicken frosen or alive e When is it done Wrong algorithms How to be a millionaire l Buy a lottery 2 Choose numbers 3 Wait for prize or be sad Problems stochastic not deterministic e In most of the cases we won t be a millionaire Not allways works Wrong algorithms How to use a bus i Walt for the bus 2 Get on the bus SM 4 D Buy a ticket Sit down Get out of the bus Problems infinite e f we are not in a bus stop bus won t stop If we are in a building bus will never arrive Using public coin phone CStart gt Problems e Not complete Ambiguous Modification Generalizing e Extending Foolproofing Completing put down receiver Avoiding misunderstans Using public coin phone true false Exercises and examples Buying shoes Watching TV Using microwave oven Paying at cash desk Making a call with mobile phone Going trough a road on foot Driving through a crossroads
9. hm Plan for performing a sequence of well understood actions to achieve the result Precise definition of the actions to be performed to accomplish each task of solution design Some properties e precise unambiguous e specified for all possible cases e finite sequence of actions achieves the result e efficiency elegance easy to use Representation of algorithms Algebraic Data flow diagram Flowblocks Flowchart Graphs or plots Hierarchical Pseudocode Tabular Verbal Example Function y sign x What is it What does it mean What is the result How is it work How can we determine its value If x is 4 what is the value of y y sign x Verbal representation 1 If x 0 set the result to y 0 2 Otherwise if x gt 0 let the value of this function 1 3 Else if x O give the function 1 y sign x Graph representation y sign x Algebraic like representation xe R ye 1 0 1 Vx x gt 0 gt y 1 Vx X lt 0 gt y 1 x 0 gt y 0 y sign x Flowchart representation y sign x Pseudocode representation if x 0 then y 0 else if y 0 then y 1 else y 1 endif endif Base structures of algorithms Sequence Selection Iteration CStart gt lt lt condition gt Task Gtop gt Modifying algorithms Algorithms often go through many changes to be better Generalizing making them apply to more cases e Extending to include ne
10. ld Bus system Connects together Central Processing Unit Control Unit CU Says what to do controls the parts of the CPU Arithmetic Logic Unit ALU Performs operations does calculations Registers Some tinny but very fast memory Cache small but fast memory Addressing Unit AU Deals with memory addresses at read write operation Memory Random Access Memory RAM Readable writeable operative memory Read Only Memory ROM Not rewritable eg BIOS ROM Memory hierarchy Register Cache Memory Hard disk drive HDD poods SuiseaJ aq DZIS 3uiseoJou Bus system Connects the CPU the Memory and the I O interfaces Data bus Transports the datas from to CPU Address bus Contains memory address of reading writing Control bus Carries control informations Input Output Interfaces It makes the system accessible to periferials world Connection to e Input devices e Output devices Storage devices e Network devices printer network ee 5 TES 0 EEG lt microphone A dL NN m keyboard REK ol Fol m m 14 9 speaker monitor projector USB drive Peripherials Input e Keyboard Mouse e Scanner Storage Winchester HDD CD DVD Blu ray drive e USB drive Memory Card Output e Monitor e Printer e Projektor Network e Ethernet e Wi Fi Other Software Applications user programs Software Hardware 14 Operating system
11. nto a number of subproblems Subproblems are smaller and easier to solve Their solution will be the components of our solution Devide and conquer Finally the problem will be converted to a plan of well known steps 3 Solution refinement Previous step is in very high level no indication given how subtasks are to be accomplished Refinement is necessary by adding more details Avoid any misunderstandings A precise method consists of a sequence of well defined steps called an algorithm Representation pseudocode flowchart etc 4 Testing strategy development It is necessary to try the algorithm with several different combinations of input data to make sure that it will give correct results in all cases These different combinations of input data are called test case It covers not only normal input values but also extreme input values to test the limits Complete test cases can be used to check the algorithm 5 Program coding and testing Description of algorithm in previous level cannot be executed directly by computer Translation needed to a programming language After coding program must be tested using our testing strategy If an error has been discovered appropriate revision must be made and than the test rerun until the program gives correct solution under all circumstances Process of coding and testing called implementation 6 Documentation completion Documentation begins with the first step of de
12. t does this algorithm do endif output b a if a lt 0 then a l a endif output a Exercises and examples input a Do the pseudocode and the flowchart input b describe the same algorithm c a if b gt O then b b 1 c c 1 else output c endif Exercises and examples input a input b c a while b gt 0 do b b 1 c c 1 enddo output c How do the values of a b and c change during the process if a 7 and b 3 What is the output in this case How many times will the condition evaluated What does this algorithm do Exercises and examples e Describe this flowchart by pseudocode Exercises and examples Describe this flowchart by pseudocode Exercises and examples Describe this flowchart by pseudocode Exercises and examples Verbal represented algorithm 1 Give a number Check that it is larger then one or not If it is larger substract two and continue with Step 2 Otherwise check it zero or not If it is zero write even 225 12 0 Te Else write odd Write this algorithm in pseudocode Exercises and examples Absolute value Raising to power Calculating factorial Prime or not Prime factorization Solution of first degree equation Sum of numbers from 10 to 20 Exercises and examples Average of an array Minimum maximum search Finding a value in ordered list Replacement of two values Selection sort Insertion sort Bubble sort Testing stra
13. tegy development Example of testing strategy e Solving second degree equation e General form ax bx c 0 e Input parameters a b c b Vb 4ac Solution X12 2a x b d 2 2a X b d 2 2a Does it work for all input e What is the output ifa 1 b 2 and c 1 e What is the output if a 1 b 2 and c 2 Example of testing strategy Does it work for all input e What is the output if a 0 b 2 and c 6 Example of testing strategy Does it work for all input e What is the output if a 0 b 0 and c 1 Example of testing strategy Example of testing strategy Good solution in pseudocode It works for all input To reach this state we have had to test the algorithm with more different input combination and then we have had to modify the algorithm We have used testing strategy input a b c if a 0 then if b 0 then output error else x c b output x endif else deb b 4 a c if d gt 0 then xl D sgrt d x2 b sqrt d output xl x2 else if d 0 then x b 2 a output X else output error endif endif endif The used testing strategy a b c reason X OK ol 2 3 aseo itdegee 7 3 0 semer V al 2 ol eso 7 0 0 1 more zeros not equation 7 3 1 9 d otnosoton v 0 83 ka Ed 2 4 2 d 0 only one solution Fa 2 3 negative inputs Program coding Creating source code in real programming language
14. velopment and continues throughout the whole lifetime of the program It contains Explanations of all steps Design dicisions that were made Occured problems Program list User instructions etc 7 Program maintenance The program can t wear out Sometimes the program may fail The reason of a program fail is that it was never tested for this circumstance Elimination of newly deteceted error is necessary Sometimes the users need new features to the program Update of documentations is needed Solution design by Break Out Diagrams Break Out Diagrams e Useful way to make the problem solving manageable Tree like hierarchical skeleton of problems e For viewing problems in levels e n Vertical P P WN Horizontal CDU nn Subproblem2 SUE Subsubproblem2 1 Subsubproblem2 2 i Subproblem1 Subproblem2 SUbproblem3 37 Ti BOD Human life d p LL Childhood Adulthood 7 RES Little childhood School years Work years Retirement d H x Elementary school High school Space BOD City areas Private areas Public areas Homes Companies Outdoors Indoors 1 I 1 I d I 1 I H k 1 1 I i Parks hi Flats Houses 1 1 1 1 1 1 1 Streets Action BOD Getting information Taking exams Visiting courses Learning 40 Data BOD Street name House number in house datas 41 Properties of BODs
15. w cases Foolproofing making an algorithm more reliable failsafe or robust e Embedding re using that algorithm within another algorithm Generalizing algoritms Original Generalized Input net VAT gross net 100 VAT Input net gross net 100 25 Extending algorithms Original Extended salary hours rate Out salary Out salary Foolproofing algorithms Original Foolproofed CStart gt CStart gt Out child Original Embeddig algorithms Embedded y sign x Alternative algorithms There are often many ways to achieve the same thing Algorithms can be different in structure but they can be equivalent in behavior It means for identical input data they will produce identical results Sometimes there is serious reason to prefer one algorithm over the other while sometimes there isn t In some cases one algorithm may be considerably smaller faster simpler or more reliable than another Alternative algorithms y sign x Properties of algorithms Complete all of actions must be exactly defined Unambiguous there is only one possible way of interpreting actions Deterministic if the instructions are followed it is certain that the desired result will always be achieved Finite the instructions must terminate after a limited number of steps Wrong algorithms How to get to the 5th floor from 2nd by elevator i Call th

Slides

Contents

Download Pdf Manuals

Related Search

Related Contents