不插电的计算机科学课件复习进程.ppt

《不插电的计算机科学课件复习进程.ppt》由会员分享，可在线阅读，更多相关《不插电的计算机科学课件复习进程.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、不插电的计算机科学课件COUNT THE DOTSData in computers is stored and transmitted as a series of zeros and ones.How can we represent words and numbers using just these two symbols?COUNT THE DOTSWhat numerical property do you see in the dots on the cards?Display the cards so the following number of dots are showi

2、ng:61521 COUNT THE DOTSWhen a binary number card is not showing,it is represented by a zero.When it is showing,it is represented by a one.This is the binary number system(base 2).What are the following binary numbers?010012100112COUNT THE DOTSWhat is the highest number we can represent using 5 cards

3、?111112=31What is the lowest number we can represent using 5 cards?000002=0Count from 0 to 31 in binary.COUNT THE DOTSLetters are represented in computers in binary also!blank0000002A1000012B2000102C3000112.Z26110102COUNT THE DOTS010010001100101000000001110010001010000101101ICE_CREAMblank0A1B2C3D4E5

4、F6G7H8I9J10K11L12M13N14O15P16Q17R18S19T20U21V22W23X24Y25Z26COUNT THE DOTSHAPPY BIRTHDAY,CARLOS SANTANA!Born July 20,1947COLOR BY NUMBERSComputer screens are divided up into a grid of small dots called pixels(picture elements).In a black and white picture,each pixel is either black or white.Computers

5、 store drawings,photographs and other pictures using only numbers.The following activity demonstrates how a computer image can be stored efficiently.COLOR BY NUMBERSThe letter a has been magnified to show the pixels.When a computer stores a picture,all that it needs to store is which dots are black

6、and which are white.1,34,11,40,1,3,10,1,3,11,4COLOR BY NUMBERS6,5,2,34,2,5,2,3,13,1,9,1,2,13,1,9,1,1,12,1,11,12,1,10,22,1,9,1,1,12,1,8,1,2,12,1,7,1,3,11,1,1,1,4,2,3,10,1,2,1,2,2,5,10,1,3,2,5,21,3,2,5COLOR BY NUMBERSThis technique is called run-length encoding.Fax transmissionCompression of images Co

7、lor encodingUse two numbers per runFirst number is how many pixels as beforeSecond number is what color(1=red,2=green,.)CARD FLIP MAGICWhen data is stored on a disk or transmitted from one computer to another,we usually assume that it doesnt get changed in the process.But sometimes things go wrong a

8、nd the data is changed accidentally.This activity uses a magic trick to show how to detect when data has been corrupted,and to correct it.CARD FLIP MAGICCARD FLIP MAGICThis exercise illustrates even parity.When computer data is transmitted to another computer,extra bits are added so that the number

9、of 1s is even.The receiving computer can detect if something gets messed up during the transmission and can correct it if there is one error.What happens if there are two errors?CARD FLIP MAGICHere is an example of parity in real life:1 X 10=104 X 9=362 X 8=165 X 7=359 X 6=543 X 5=157 X 4=286 X 3=18

10、7 X 2=14 226/11=20 remainder 6 Checksum Digit=11-6=5 CARD FLIP MAGICMore parity:YOU CAN SAY THAT AGAIN!Since computers only have a limited amount of space to hold information,they need to represent information as efficiently as possible.This is called compression.By coding data before it is stored,a

11、nd decoding it when it is retrieved,the computer can store more data,or send it faster through the Internet.This exercise illustrates how a childrens rhyme can be compressed.YOU CAN SAY THAT AGAIN!PITTER PATTERPITTER PATTERLISTEN TO THE RAINPITTER PATTERPITTER PATTERON THE WINDOW PANEYOU CAN SAY THA

12、T AGAIN!PITTER PATTERPITTER PATTERLISTEN TO THE RAINPITTER PATTERPITTER PATTERON THE WINDOW PANEBEFORE:78 lettersAFTER:29 lettersYOU CAN SAY THAT AGAIN!The arrows and boxes are presented with 2 numbers.PITTER PA(7,4)7:count back 7 positions4:copy 4 letters/spacesSometimes boxes point back to a box w

13、ith a blank inside.BANYOU CAN SAY THAT AGAIN!The storage capacity of computers is growing at an unbelievable rate.In the last 25 years,the amount of storage provided on a typical computer has grown about a million fold.We can compress the data so that it takes up less space.This exercise uses Ziv-Le

14、mpel coding,or LZ coding,invented by two Israeli professors in the 1970s.ZIP files,GIF imagesMARCHING ORDERSComputers are usually programmed using a language,which is a limited vocabulary of instructions that can be obeyed.One of the most frustrating things about programming is that computers always

15、 obey the instructions to the letter,even if they produce a crazy result.This activity gives kids some experience with this aspect of programming.MARCHING ORDERSMARCHING ORDERSBEAT THE CLOCKThis activity illustrates structures used in parallel sorting networks.Kids sort data by walking through a sor

16、ting network laid out on the floor.The network simulates how a parallel network would sort data.Kids find out that data can be sorted a lot faster in parallel!BEAT THE CLOCKBEAT THE CLOCKVIDEO csunplugged.org Search for“computer science unplugged”TWENTY GUESSESHow much information is there in a 1000

17、-page book?Is there more information in a 1000-page telephone book,or in Tolkiens Lord of the Rings?If we can measure this,we can estimate how much space is needed to store the information.This activity introduces a way of measuring information content.TWENTY GUESSESCan you read the following senten

18、ce?Ths sntnce hs th vwls mssng.You probably can,because there is not much information in the vowels.TWENTY GUESSESI am thinking of a number between1 and 100.I will start you off with 20 pieces of candy.You may only ask questions that have a yes or no answer.For each incorrect guess,you will lose one

19、 piece of candy.Once you guess correctly,you can keep whatever candy remains.42TWENTY GUESSESTo pick a number between 0 and 100,you only need 7 guesses.Always shoot for the middle number of the range and eliminate half the possibilities!This concept is called binary search.If the number was between

20、0 and 1000,you would only need 3 additional guesses.You can guess a number between 0 and 1 million in only 20 guesses!BATTLESHIPSComputers are often required to find information in large collections of data.Computer scientists study quick and efficient ways of doing this.This activity demonstrates t

21、hree different search methods so children can compare them.BATTLESHIPSBattleships are lined up at sea.Each battleship has a number that is hidden.How many guesses does it take for you to find a specific battleship?The number of guesses is the childs score.The lowest score wins.BATTLESHIPSGAME 1:Ship

22、s are randomly ordered.FIND SHIP#7171630 9263 4127 405 4429 7113 3176 4015 7976 88 3465 1571 86252587 7187 5258 8020 1919 141 4414 3056 9118 717 7021 3076 3336BATTLESHIPSGAME 2:Ships are in increasing order.FIND SHIP#5897 33 183 730 911 1927 1943 2200 2215 3451 3519 4055 5548 56555785 5897 5905 6118

23、 6296 6625 6771 6831 7151 7806 8077 9024 9328BATTLESHIPSGAME 3:Ships are ordered into 10 groupsbased on a mystery function.FIND SHIP#8417BATTLESHIPSThese three games illustratelinear searchbinary searchhashingWhat is the maximum number of guesses required for each of these search techniquesfor 26 ba

24、ttleships?for n battleships?POOR CARTOGRAPHERMany optimization problems involve situations where certain events cannot occur at the same time(e.g.scheduling meetings and classes).Coloring regions of a map with different colors is effectively the same problem as we will show in this exercise.POOR CAR

25、TOGRAPHERGiven a map,color each region with a color so that no two adjacent regions use the same color.If two region touch only at one point,they are not considered adjacent.Example:Arizona and ColoradoHow many colors are sufficientto color a map?How many colors are necessaryto color a map?POOR CART

26、OGRAPHERPOOR CARTOGRAPHERPOOR CARTOGRAPHERPOOR CARTOGRAPHERundirected graphAIHGBFECDJGABCDEFJHIPOOR CARTOGRAPHERSchedulingPOOR CARTOGRAPHERCan we color a map with 3 colors?This problem is intractable.The only way we know to solve this problem in general is to derive all possible colorings and see if

27、 we come across a valid coloring.How many colorings are there for a map with 25 regions?How long would it take to analyze all of these colorings if it takes 1 second to analyze one coloring?THE COOPERATION GAMEWhen you have a lot of people using one resource(such as cars using roads,or messages gett

28、ing through the Internet),there is the possibility of deadlock.A way of working cooperatively is needed to avoid this happening.This exercise illustrates cooperative problem solving and(potentially)deadlock.THE COOPERATION GAMEA shared resourcein Pittsburgh:THE COOPERATION GAMEA shared resourcein Ne

29、w York:THE COOPERATION GAMESet up:Each child is assigned a color.Give two color cards to each child except one child,who gets only one.Each child should not hold his or her own color initially.The children form a circle.Goal:Each child must end up with the card(s)of his or her own color.THE COOPERAT

30、ION GAMEPassing Rules:1.Only one card may be held in each hand.2.A card can only be passed to an empty hand of an immediate neighbor in the circle.(A child can pass either of their two cards to their neighbor.)3.(optional)No talking.THE COOPERATION GAMEAlternate ConfigurationsTHE COOPERATION GAMERou

31、ting and deadlock are problems in many networks,such as road systems,telephone and computer systems.Engineers spend a lot of time figuring out how to solve these problems-and how to design networks that make the problems easier to solve.TREASURE HUNTComputer programs often need to process a sequence

32、 of symbols such as words in a document or even the text of another program.Computer scientists use a Finite State Automaton(FSA),a set of instructions to see if the sequence is acceptable or not.This exercise uses the FSA idea using treasure maps!TREASURE HUNTGoal:Find Treasure Island,starting from

33、 Pirates Island.Friendly pirate ships sail along fixed routes between islands offering rides to travelers.Each island has two departing ships,A and B.Determine all possible sequences of ships that a traveler can take to arrive at Treasure Island.Use your map to record all the ship routes.TREASURE HU

34、NTABTREASURE HUNTABTREASURE HUNTABTREASURE HUNTABTREASURE HUNTABTREASURE HUNTABTREASURE HUNTPLAY AGAINTREASURE HUNTWhat is thequickestroute?directed graphLIGHTEST&HEAVIESTComputers are often used to put lists into some sort of order(e.g.names into alphabetical order,appointments or e-mail by date,et

35、c.)If you use the wrong method,it can take a long time to sort a large list into order,even on a fast computer.In this activity children will discover different methods for sorting,and see how a clever method can perform the task much more quickly than a simple one.LIGHTEST&HEAVIESTStart with 8 cont

36、ainers with different amounts of sand or water inside.Seal tightly.Children are only allowed to use the scales to compare the relative weights of two containers.Only two containers can be compared at a time.LIGHTEST&HEAVIESTMETHOD 1Weigh first two containers.Keep the lighter container and weigh it a

37、gainst the third container.Keep the lighter container and weigh it against the fourth container.continue.Keep the lighter container and weigh it against the eighth container.Keep the lighter container.This must be the lightest container.LIGHTEST&HEAVIESTMETHOD 1(contd)Repeat this process again using

38、 the 7 remaining containers to get the next lightest container.Repeat this process again using the 6 remaining containers to get the next lightest container.Continue until all containers are sorted by weight.How may weight comparisons do we have to do to sort the containers?7+6+5+4+3+2+1=28LIGHTEST&

39、HEAVIESTMETHOD 2Take a random container and weigh it against every other container one at a time.Every container that is lighter is put into one group to the left.Every container that is heavier is put into another group to the right.Put the initially selected container between the two groups.Now so

40、rt the two groups in the same way.LIGHTEST&HEAVIESTMETHOD 1 is called Selection Sort.METHOD 2 is called Quick Sort.Generally,quick sort is a lot faster than selection sort is.For 8 containers,quick sort can reduce the number of weight comparisons to 13.CS UNPLUGGEDThe basic edition of Computer Scien

41、ce Unplugged has 12 classroom exercises for you to use with your students.Each exercise has a number of extensions,activities and background information.All activities can be done without the use of computers,but they all demonstrate fundamental principles used in computers today.CS UNPLUGGEDThe tea

42、chers version of Computer Science Unplugged is available online at http:/www.csunplugged.orgThe book is FREE to download and use!Additional material will be published soon to add even more activities,including video to demonstrate how to use these activities effectively in your classroom.Computer Science Unplugged10100 01000 00001 01110 0101111001 01111 10101(THANK YOU!)此此课课件下件下载载可自行可自行编辑编辑修改，修改，仅仅供参考！供参考！感感谢谢您的支持，我您的支持，我们们努力做得更好！努力做得更好！谢谢谢谢