Foundations of Computer Scienc
Foundations of Computer Scienc CPSC 125
Christopher Newport University
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 55 page Class Notes was uploaded by Ansley Hessel on Monday October 5, 2015. The Class Notes belongs to CPSC 125 at Christopher Newport University taught by Lonnie Cheney in Fall. Since its upload, it has received 64 views. For similar materials see /class/219475/cpsc-125-christopher-newport-university in ComputerScienence at Christopher Newport University.
Reviews for Foundations of Computer Scienc
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/05/15
H Department of Physics Computer Science 8 Engineering Foundations of Computer Science Operating Systems Dr Lonnie Cheney Ou i39line El Evolution of Operafing Sysfems El Operafing Sysfem Archifecfur e El Coordinafing file Machine39s Ac vifies El UNIX snde 2 Ou i39line El Evolufion of Operafing Sysfems El Operafing Sysfem Archifecfure El Coordinafing le Machine39s Acfivifies El UNIX sndes Evolu i39ion 39 mulfimillion dollar machines should nof be idle anamze hardware cass across many users batch processing inferucfivereuIfime processing mulfifusk rig nefwork disr bured processing snde Ba39l39ch Processing job the set of tasks programs one user wants to run user submits a job to operator OS job gets placed into a QUEUE FIFO after all jobs ahead of it are done the job is run Slide 5 Batch Processing Jobs Program data Results and directions User domain Machine Job Slide 6 Interactive some applications need immediate response example airline reservation system text editor nterac rive systems make it look like user has en r re machine some applications need rea7 39me response example robot control systems fly byw re Slide 7 Interactive Programs data directions and results User domain Machine domain Program execution Slide 8 Multi tasking Outline El Evolution of Operating Systems nstead of finish ng one job or task before doing the next one do part of the job El Operating System Architecture t meslic ng give each job n the queue a short t me using El coordina ng le MOChlne39s Ac39l39lVl es the CPU El UNIX CPU works so fast it appears that more than one job is being done at the same time Slide 9 Slide 10 Software Overview Interface between Users and 05 User Software f Application System User f 3 k User l r Kernel Utility Operating l system I 1 K Shell Kernel K User User Slide 11 Slide 12 05 Functions El control computer 6t its peripherals ighlevelease of use points of view enduser system programmer El window management ll data and file management El dev ce control El resource management El access control Sllde13 Control Computer mach ne language is too low level 10A0 MM 5001 30A2 6000 higher level commands cp publicfooc booc user view how to make computer do what I want systems view how to manage computer resources Sllde 14 Window Management provide graphical user interface GUI manage layout of w ndows stacking min miz ng max miz ng can range from very simple to very complex Sllde 5 Data and File Management datadt programs as files on secondary memory save open load provide file manipulation capabilit es copy rename delete move control file access permissions for owners world read write execute Sllde 6 Device Control provide communication paths to devices device drivers provide higherlevel instructions example instead of specifying what sector and track to store bytes onjust give bytes to device driver it will write the bytes appropriately device drivers encapsulation if new disk drive no need to change our program only the device driver Sllde 7 Resource Management memory allocation to different programs virtual memory communication 6i sharing of peripherals many users printing to the single printer sharing executable programs many people using the directory command Access Control user accounts user id39s log n names passwords disk quotas Sllde 9 OS utilities programs commands gt file management explorer cp mv rm ls cd gt text editing vi emacs textedit gt compilers gH gt special tools email print ng networking gt l braries collection of program p eces viii cli can be l nked into user programs Sllde 2n Virtual Machine OS insTrucTions def ne The compuTer OS TranslaTes user commands inTo machine commands basis s mulaTe a characTerisTic n sofTware simulaTed in software NOT The real machine There may noT be a REAL mach ne design of new compuTers Bootstrapping OS is loaded inTo memory Program CounTer poinTs To first 05 insTrucTion mach ne cycle sTarTs BUT WHAT LOADS OS INTO MEMORY simple fixed program called The booTsTrap loader Slide 21 Slide 22 Power on Sequence The Booting Process PC is iniTialized To a predeTerm ned value Main memory Main memory I Disk storage IT post To locaTIon In memory of The loader ROM Borotstrap ROM Bootstrap Disksmage 9 a program machine cycle is sTarTed Operating i39 Volatile Volatile e emo loader Is execuTed which Then 39y Operating Operating loads 05 from disk To memory Step 1 Machine stars by executing the bootstrap 5t 2 B t d 01 th t f f seTs PC To locaTIon of 05 In memory amalready m memorv peranng ep 023515 giraslgm39i ms fans em s IStem is Stored in mass sm39age and then transfers control to it conTInues machine cycle Slide 23 Slide 24 ROM bootstrap program must be permanent part of computer system must be stored in memory this memory must be non voiatiie Read Only Memory ROM Outline El Evolution of Operating Systems El Operating System Architecture El Coordinating the Machines Actnn ies El UNIX Concept of a Process Process Admll39llS39i39f O i39IOI39I li d t 39 d f note difference between program and process 5 5 mu quot39quotS 2 quot2555 P d f process table contains nrormation about all active processes t t t t d process activity of execut ng a program dynamic mmwmq Pm Y39 5 quot5 wa39 39quot939 m y d39 f It th t t d processsme current status of the actiVity includes quotPa 5 gram u Pmesses are execquot e cumm Fashion in 2 Program assigns t me slices to processes I CPU d H switches from one process to another processcontext switch n regs man nenoryce s e snapshot of the program execution activity TimeSharing lntetrupt Interrupt Interrupt Interrupt Interrupt I I I I I I I I E Process 3 E Process B i I I g I E f E i Process Process 1 I sw39Itch swnch I I I I I 1 I I 4 Advancing I time I I I l I I I 39I39Imesiice meslice TImeslice 39 meslice Slide 29 05 Architecture command processor scheduler 39 file manager resource aocator dispatcher Slide 30 How a command is executed print footxt gt Slide 31 Scheduler sets up task queue Slide 32 Dispatcher Timeslices Tasks PrinT Task being served Shae 33 Shae 34 PrinT Task waiTing Shae 35 PrinT Task done quotform user That Task is done inform CP That Tas is done Shae 36 Outline El Evolution of Operating Systems El Operating System Architecture El Coordinating the Machine39s Activities El UNIX UNIX Background operating system popular especially for servers developed by Bell Labs n 1969 several different quotflavorsquot ex isl today Solaris FreeBSD OpenBSD a wellknown UNIXlike operating sysiem is Linux a for sieriers check oui Ubuniu wwwubuniucom ii39s free and preiiy straight forward io in tall you can even run ii from CD no nsiuiiuiion required slides sliaeaa UNIX Commands cd eniered in a ierm nalsliell command line nierfucequot change directory Cd dlrectory typically contain three parts Exam Ies commend neme deienn nes ihe exoci command io b2 execuied P examples cd 15 cp nsn ed change direciory io home directory p ns 39ndicahz which variation ofacommand shouid be execuied ed m1 chmgedimpopypodpl opiions are opiionei ihere is always a dereuii 52H rig opiions are specifed using a hyphen v ed M change d rectory 0 Wmquoti d rectory 2xamp25ls ems es 15 eel rgunienis specify ihe objects or iergeis of a command noi all commands need orgumeni in command descripiions opiionei orgumenis are nd ceied wiih quot1quot examplescp fllel f11e2mkd1r newdlr sliaeas sliaean 10 Is More UNIX Commands list the files in the current d rectory ls 7 aF fllename l dlrectory Examples 15 list files using default format names only ls 1 list us rig long format all file info 15 s list all file includ rig hidden files 15 er list files show rig which are 2x2cutab2or dirsl diay file contents ca fllename print on screen without pausing n more fllename print one screenful at a time copy a file cp flleToCopy dupllcateFlle example Cp aBlgFlle anotherBlgFlle rename a file mv oldName newName example mV foo txt oldfootxt rename footxt to oldfootxt erase a file same as delete or remove rm fllename example rm fllel SlideA Slide42 More UNIX Commands Hierarchical File System mm quot dimquot7quot a file system can contain files and d rectories mdlr dlrname example rmdlr dlrl deletes the directory dir1 a directory is a file that contains other files or other directories display help from user manual for comand man rk keyword command the contained directories are called children the example man ls display info on how to use is command contain rig d rectory is called the paren display todaYs date and time the file system is descr bed as a tree every HFS has a date single topmost d rectory called the root directory designated by root is the ancestor of ALL files display list of users and what they are doing w Sllde43 SlideAA 11 HFS HFS home directory usr home bl usr etc home bin xf01 yppasswd xf01 yppasswd public xfOlOl Xf0102 Xf0103 public Xf0101 Xf0102 Xf0103 Iabl foodat bootxt Iabl foodat bootxt current directory indicated by p current directory homexf01xf0101 here is always a current directory When you log n the current directory is set to your home directory HFS path HFS going up to parent hb hb usr etc ome i usr etc ome i xf01 yppasswd xf01 yppasswd public xfOlOl Xf0102 Xf0103 Iabl foodat bootxt current directory homexf01xf0101 path name The path refers to the sequence of directories from root to the current directory Sllde47 public xfOlOl Xf0102 Xf0103 Iabl foodat bootxt current directory homexf01xf0101 The parent of the current dir is represented by so Cd will result in xfOl us the new current dir SlldeAE 12 Department of Physics Computer Science 8 Engineering Introduction to Computer Science Data Manipulation Dr Lonnie Cheney Outline El Computer Architecture El Machine Language El Program Execution El ArithmeticLogic Instructions El Communication with other Devices CI Other Architectures slide 2 Outline El Computer Architecture El Machine Language El Program Execution El ArithmeticLogic Instructions El Communication with other Devices CI Other Architectures slide 3 Computer Architecture Central processing unit Main memory Register unit Arithmeticlogic El unit ll ll ll ll Control unit Registers slide 4 von Neumann Architecture Registers data and instructions kept in memory special processor memory for temporary storage of results CPU fetches and executes instructions very fast access time compared to primary memory CPU connected to memory via data and address bus example add two numbers from memory one instruction executed at a time one register holds first number another holds second number third holds the answer special registers program counter instruction states states Outline Machine Instructions El Computer Architecture El Machine Language El Program Execution CPU has several circuits which perform different functions identify each function command instruction with aunique bit pattern just as ASCII code represents each character with a unique bit pattern El ArithmeticLogic Instructions types of instructions El Communication with other Devices dummnsfer El Other Architectures arithmeticlogic controlbranching state statett Data Transfer copy da139a from memory To regis rers or vice versa copy da139a from inpu r devices To memory Transfer is described rela139ive To CPU LOAD means copy from memory To regis rer STORE means copy from regis rer To memory Slide 9 Load vs Store Central processing unit Main memory Registers STORE Address Cell El 0 Program count 0 7 I 1 Bus 01 iii Instruction register LOAD Slide 10 ArithmeticLogic add sub rrac r mulfiply divide AND OR exclusive or XOR shiff rofafe Slide 11 Control branching ins139ruc139ions are execu red in sequence fefch firs r ins rruc rion execu re if fefch second ins rruc rion execu re if fefch Third ins rruc rion execu re i r and so on finally s139op execu rion ins rruc rions which modify This sequence are con rrol ins139ruc139ions s139op is a con rrol ins139ruc139ion jump or branch To anofher ins139ruc139ion go To Slide 12 Example of control flow How it works inside The PC sample program to add two numbers 1 load register one with first number from memory 2 load register two with second number from memory 3 add contents of registers one and two leave answer in register 3 4 if contents of register 3 are negative jump to step 6 5 store contents of register 3 to a location in memory 6 stop identify the data transfer arithmeticlogic and control instructions above Sllde13 CPU MEMORY Stored program Opcodes amp Operands instructions can be represented by bit patterns 39 P de 5 Pmerquot quotPresemmg iquot5 rquot quot b Patterns can be Stored in memory operand bit pattern representing object of instruction instead of building in programs in CPU store programs exumP39e LOAD REM ADD in memory a instruction ioad objects of instruction reg1 and addr CPU then interprets patterns as instructions or data 39 quot P39e e iquot5 quot de quotd Pequot quot Sllde 6 Opcode examples the LOAD instruction has opcode 0001 appendix C computer will load a specified register with contents of some memory location need to indicate which register to load and what memory location to access use more bits after the 0001 to indicate this info Slide 17 CISC vs RISC CISC Complex Instruction Set Computer many powerful instructions ex expon sqrt more CPU silicon devoted to instruction circuits programs are shorter RISC Reduced Instruction Set Computer few simple instructions ex add mov more registers on CPU rather than instruction circuits programs are longer Slide 18 A simple machine Architecture of simple machine CPU has 16 registers each 8 bit wide Centralprocessing unit Main memory registers identified as O to F Registers Address Cell El 0 Program counter 00 iii memory has 256 cells words each 8 bits wide I 1 01 l l memory address ranges from 00 to FF 02 4 El 2 Instruction register each instruction is 16 bits two words with 39 03 l l first 4 bits the opcode and remaining 12 the operand F FIF Slide 19 Slide 20 LOAD example load register 0 with the contents of address A7 is represented by the instruction 10A7 hex 0001 0000 10100111 1 0 A 7 1 is the opcode for the load instruction the next hex digit 0 represents which register to load the next 2 hex digits A7 represent memory location to access Slide 21 What does it mean 0011 0101 1010 0111 ActualbitpatternHGbits Slide 22 What does it mean Op code Operand 0011 0101 1010 0111 Actual bitpattern16bits l 3 5 A 7 Hexadecimal form 4 digits Slide 23 What does it mean Instruction 3 5 A 7 Opcode 3 means to store the contents This part of the operand identifies of a register in a the address of the memory cell memory cell that is to receive data This part of the operand identifies the register whose contents are to be stored Slide 24 And this Encoded instructions Translation 1 56C 1 BED 5056 306E 0000 And this Encoded instructions Translation 1560 Load register 5 with the bit pattern found in the memory cell at address 6C 166D Load register 6 with the bit pattern found in the memory cell at address 6D 5056 Add the contents of register 5 and 6 as though they were two s complement representation and leave the result in register 0 306E Store the contents of register 0 in the memory cell at address BE GOOD Haltt Slide 25 Slide 26 Outline Program Execution D compu rer ArCthedure 39 Fetchdecodeexecute cycle D MOChme Language Program counter PC register CI Program Execution points to next instruction in memory to execute El ArithmeticLogic Instructions Instruction register holds instruction to be decoded and executed El Communication With other DeVIces El Other Architectures Slide 27 Slide 28 FeTchdecodeexecuTe cycle seT The PC To The locaTion of The fir39sT insTr39ucTion copy insTr39ucTion from memory To The insTr39ucTion r39egisTer39 PC r39egisTer39 sTaTes which memory locaTion To copy from incremenT PC To poinT To nexT insTr39ucTion in memory decode and execuTe biT paTTer39n in insTr39ucTion regisTer39 when insTr39ucTion is done sTar39T fr39om sTep 2 above FeTchdecodeexecuTe cycle 1 Retrieve the next instruction from memory as indicated by the program counter and then increment the program counter 2 Decode the bit pattern in the instruction register 3 Perform the action required by the instruction in the instruction register Slide 29 Slide 30 Program counter contains address of first instructions CPU Main memory CPU Main memory Address calls Program counter Registers Address Cells Program counter A0 ll l A0 1 0 5 Bus A1 Csci P l l A2 7339767 Program is 39 l 6c M 6D stored in Instruction register quot main memory 2 E A4 1 beginning at 156C A2 l 16 l 7 address A0 A5 l 56 l A3 LGJL Instruction register A6 l A7 lEJ a At the beginning of the fetch step the instruction starting at address A0 is A8 r601 retrieved from memory and placed in the instruction register F I A9 00 1 Slide 31 Slide 32 CPU Main memory Program counter Address Cells 7 Bus A0 15 i A1 El Instruction register 156C A2 A3 h Then the program counter is incremented so that it points to the next instruction Slide 33 Characteristics computer does not get tired or bored mechanical pumping of data and instructions change PC to modify sequence of instructions can JUMP to data can modify programs viruses AI Slide 34 Outline El Computer Architecture El Machine Language El Program Execution El ArithmeticLogic Instructions El Communication with other Devices El Other Architectures Slide 35 Example for Rotate The original bit pattern 1 g 1 The bits move one position to the right The rightmost bit quotfalls offquot the end and is placed in the hole at the other en l 9 l l 9 0 1 Q Thefinalbitpattern Slide 36 Outline El Computer Architecture CI Machine Language El Program Execution El ArithmeticLogic Instructions El Communication with other Devices El Other Architectures Peripherals communication with external devices via controllers example printers disk drivers monitors modems different devices have different processing speeds need to synchronize communications should not keep CPU waiting for IO to finish serialparallel communication Slide 37 Slide 38 Peripherals Peripherals E CD drive Modem 8 0 Controller Controller E E U CPU BUS Main 5 memory 3 3 Controller Controller g 8 U Monitor Disk drive Slide 39 Slide 40 10 Memory Mapped IO replace a memory cell with a port send data To device by storing data To That memory cell no need for special IO instructions lose a memory cell for every por r Bus Main memory Direct Memory Access DMA simple specialized computer To control peripherals controller channel share memory with CPU Basic me rhod output CPU s rores data in memory at given location CPU signals controller To start IO Controller reads memory at The given location Controller performs IO Controller Peripheral device CPU doesn39f waif for IO Specialized IO instructions required Slide 41 CPU s139ores da39l39a CPU signals controller printer MEMORY controller slide 43 printer MEMORY controller slide 44 Controller reads da ra Controller ou rpu rs da ra printer MEMORY printer MEMORY SlideAS SlideA Buffers and Caches Serial vs Parallel memory reserved for data transfer across systems of different spee s example CPU and printer CPU can generate data much faster than printer can pr39n 39 CPU writes to buffer prinier reads from buffer also used in secondary storage systems Slide47 Serial one wire one hit at a time Parallel several wires several hits at a time stmeu 12 Outline Speed El Computer Architecture El Machine Language El Program Execution El ArithmeticLogic Instructions El Communication with other Devices El Other Architectures clock allows synchronization of processes directly affects rate of fetchexecute cycle word size data bus width von Neumann Bottleneck bench marks Speed of Light Limit Pipeline 300000 kmsec 30 cmnanosecond machine cycle has 3 phases fetchdecodeexecute 1ns 10399 sec consider this as a pipequot with 3 segments 39 electrons cannot travel faster than this each segment can hold one instruction directly affects rate of fetchexecute cycle when pipe is fulthere are 3 instructions in various electrons must travel through the address and phases of execution data busses memory circuits etc also known as prefetch Throughput measure of work done Execution speed time to execute an instruction 13 Department of Physics Computer Science 8 Engineering Illtl I L to r l B I Artificial Intel igence Dr Lonnie Cheney Outline El Intelligence and Machines El Understanding Images El Reasoning El Artificial Neural Networks El Other Areas of Research Delnltmem oi Plymi olllpultr intnu a tuglnctrlng slide 2 Outline El Intell gence and Mac El Understanding Images El Reasoning El Arti al Neural Networks El Other Areas of Research lxptrtnwltt oi l iysics wnlmtat Smelli st illglllecl ills slide a What is AI what is intelligence peroeptionreasoning In unexpected 5 Nations natural language understanding problem solving knowledge computers execute algorithms w tn speed and aocumcy predefined tasks ONLY h u m a n5 reason about unexpected events understand interpret and oomprenend results Urparlltlcnl at lntucs Cnmpuler stianra 2k glittering slide Psychology o in order to design machines with AI we need to understand more how human mind works 0 CS goal is a better machine PSYC goal is better understanding of human mind 0 intelligence as performance 0 intelligence as human like 0 example tic tac toe poker H Department of Physics Problem of Intelligence o no clean defin tion not a matter of yesnoquot o operational definition Turing test 0 if a human when conversing with another entity can t tell if the other entity is machine or human the entity is said to be intelligent ELIZA DOCTOR PARRY ALICE Department of Physics Computer Science amp Engineering Slide 6 Computer Science 84 Engineering Slide 5 The EightPuzzle Department of Physics Computer Science amp Engineering Slide 7 A Model AI Machine ocamera used for image processing ogripper and tool used for manipulation oproblem domain 8 puzzle solving Department of Physics Computer Science amp Engineering Slide 8 Outline Perception El Intelligence and Machines o extracting information form visual data character recogn tion El Understand 9 Images o pixelbased match bitmap templates D Reasonlng interpret b is as an image D ArtifiCial Neural Natworks o featureextraction detect standard shapes El Other Areas of Research halfcircle horizontal line unaniman 0139 l39 yslcs Ui pmlmcnl of rims ciiiiipnm SUCHU ii liigincurirrg siaa 9 ciiiiinnm kieiint a tilgintcnng snaa Pixelbased Pixelbased Problems o uniformity of style of characters required 0 templates must be of same size to match 0 characters must be oriented the same way array of pixels mmmciir ol i39iwsics urmrimmi or Physics iiinpuler mm it l llginte irs snaa 1 limpulci39 mm x tngiiieanng snaa 12 Feature Extraction C two horizontal bars one vertical vertical joins horizontal at left edges of horizontals Department of Physics Computer Science 8 Engineering Slide 13 Outline El Intelligence and Machines El Understanding Images El Artificial Neural Networks El Other Areas of Research Department of Physics Computer Science amp Engineering Slide 14 Reasoning 0 give machine a goal and a start posit on let it figure out how to get there 0 production system 0 states set of all values in the system at a certain point start state state system is initially in goal state state when problem is solved 0 product ons rules for how to change states 0 control system mechanism for choosing which product on to apply Department ol Physics Computer Science amp Engineering Slide 15 State Graph Department of Physics Computer Science as Engineering Slide 16 Control Systems o finding the right path picking the right productions 0 general methods for finding paths in a graph 0 will work on ANY problem expressible as a graph 0 bruteforce method try everything 0 heuristics use rule of thumb Department of Physics Computer Science 14 Engineering slide 17 Bruteforce Search Trees o in the state graph start at start state and list all states reachable using only one production 0 repeat above for each new state reached until the goal state is found 0 problem of combinatorial explosion o eliminate redundant states Department of Physics Computer Science 8 Engineering Slide 18 Sample Search Tree 135 4 2 776 1 5 135 135 432 42 482 1 1 135 35 135 135 432 432 742 142 482 482 786 786 8 6 7T 7 76 415 152 13 5 135 135 415 415152152135135 345 35 135 3513513 3 27324 34367 2 74212142 8 21824 8485 786 86786 78 846 86 786 786 476 476 762 762 Department ul Physics Computer Science ll Engineering Slide 19 Sample Search Tree 13 425 786 1 3 425 786 123 13 4 5 425 786 786 123 123 123 413 45 485 45 25 786 7 6 786 786 123 2312312312312 413 413 745 145 485 485456 453 725 2 5 86 786 76 7678 786 86 786 Goal Department of Plpsics Computer Seience amp Engineering Slide 20 Combinatorial Explosion the eightpuzzle has over 300000 states 0 each state is represented by a 9tuple goal 12345s7s95 where B is the blank 0 there are 9 different permutat ons ie 9x8x7x6x5x4x3x2x1362880 0 but there are many paths to any single state so in building the tree might repeata state Dupmmcnl oil39qusl s Costbased Elimination o attach a cost to Ed arc in the tree 0 when a redundantstate is found retain only the state whose path is cheaper o if cost is length of path then we retain only stats w th shortEt paths c Cuwpultr SUCHU x lngincwing shoe 2 vamlmcnl of I39lwms Cuillpuzd Sueth amp higlnrcnng Slide 22 Heu ristics o a mle of thumb 0 identify problem characterist cs which humans look for example move tile towards if home pos tion 0 definea cost funct on for stats in the system example count the number of posit ons between a tile and if home posit on Do this for each tile The sum for all tiles is the cost of transforming that state into the goal state mmmm oi l iwsl Characteristics of Cost Function 0 shows amount of work needed to move from given state to the goal state basis for decis ans 0 must be easy to calculate must not spend too much time calculating cosls cs chlupmer Uc k amp ingintenhs Slide 23 mmch of l hyslts llm ulcf wtmtx tngllltcflng Slide 24 Applying Heuristics Example for 8Puzzle 1 3 5 o from the start state lrst all reachable states 4 2 7 8 6 o for each reachable state calculate the cost function 0 select the state with lowest cost and list all states 1 a 5 1 3 5 1 3 reachable from t 4 2 a 4 2 4 2 5 7 8 7 8 6 7 8 6 0 repeat the cost calculations and selections until the 6 goal state is reached 1 3 5 1 3 0 see textbook pp 418 4 2 6 4 2 5 7 5 Heuristic values 7 3 6 Si l3l Department of Physics Department olquot Physics Computer Science 8 Engineering slide 25 Computer Science amp Engineering slide 26 Outline Neural Networks El Intelligence and Machines El Understanding Images El Reasoning El Artificial Neural Networks El Other Areas of Research Department of Physics Computer Science 8 Engineering Slide 27 The real thing a neuron in a living biological system Axonsfrom its neurons Dendrites fL Cell body Synapses Human brain 1011 neurons with about 104 synapses per neuron Department of Physics Computer Science 84 Engineering slide 28 Neural Networks 0 set of simple processing elements connected in layers 0 each unit maps a set of inputs to one output based on input weights and a threshold 0 multiply each input by ts weight if the sum of these products exceeds the threshold output a 1 else 0 V1 Processing unit Compute effective input Compare effective Produce output input to threshold of 0 or 1 v7w1v2w2v3w3 s 5 see Department of Physics Computer Science amp Engineering Slide 29 Example Neural Net input 1 1 15 2 1 gt Output b input 35 r 0 ll 35 gt Output Department of Physics Computer Science amp Engineering Slide 30 OCR and Neural Nets 0 problem is to detect C or T 0 net has two levels lower level has 9 inputs per unit while upper level has 1 input for each lower level 0 each lower level un t scans a 3X3 area of the field of view hence the 9 inputs 0 an active pixel in the field of view produces an input of 1 Department of Physics Computer Science amp Engineering Slide 31 Problem Recognize Department of Physics Computer Science 84 Engineering Slide 32 Net Structure Output Final processing unit First level of processing units Field of view containingsensors lIl VlI l Department of Physics Computer Science amp Engineering Slide 33 Letter C in the field Output Final processing unit First level of processing units H WW Sherlfal ihlg svensors l IllZIJ I J1 J1 Department of Physics Computer Science amp Engineering Slide 34 Letter T in the field Output First level of processing units H Field of view containing sensors Department of Physics Computer Science 8 Engineering Slide 35 Problems 0 number of processing units 0 number of levels 0 weights Department of Physics Computer Science amp Engineering Slide 36 Outline El Intelligence and Machines El Understanding Images El Reasoning ial Neural Networks Applications of AI 0 natural language understanding 0 robotics 0 database systems 0 expert systems El Arti El Other Areas of Resea Dupamucnl or l39 yslcs vamlmcnl of Him unupum Same x lnginctring Shae 37 Culupuzd imam a tugmtcnng Shae as Natural Language Stages o requirs understanding the meaning of the sentence compilers work with welldefined semantics o humans frequentlydon39t say literally what they mEn do you know what time it is o humans don 39t strictly obey correct syntax 0 human language changes over time o requirs general knowledge of the world mmmtut ol l iwslcs Cumpukr Uc k rt higineerurs Shae 39 o syntactic analysisparsing a pencn Jlmrecewed a pencll from John 0 semantic analysis mea mg the pencll that was a e n Wlth John l5 now Wlth 3er Both statements are equw nt 0 contextual analysis I The bat ew from hrs hand meamng depends on context Urmrrmmr of Physics limping Xltmt l tngmenng sluaean Robotics o mechanical operations in a controlled environment 0 example packing operations 0 not really intelligent but precise timing and movement Dupmmcnl oI l39 ysics Clllllpultr Sucncr x inginc lng Robotics and AI 0 in uncontrolled environmenttiming doesn39t work 0 example sorting operat ons 0 items arrive all jumbled up in a box 0 robot must p ck out items from the box and place them into different bins 0 must plan moves perceiverecognize shapes of items vamlmcnl of I39lwms sum Cumpum Sum z tnglnrcnng sum Database Systems DB and AI 0 DBMS query languages are not natural query language selectall records where me smithquotand 0 end users should not have to know a complicated l f tl the have no time to learn name 10hquot or ue an ua e re uen CL 7 g g q y y fname jimquotand t at anguage yearsEmpon gt 9 0 use A1 to produce a natural language query system for such end users natural language do we have any senior executivs by 0 be able to retrieve or INFER information the name of J Smith mmmm 0 Physics Urparmmnr of Physics Cumpuler mm a higineeruvs sum mmm uznu x langllrecnng sum M Department of Physics Computer Science 8 Engineering Introduction to Computer Science Algorithms Dr Lonnie Cheney Outline The Concept of an Algorithm Algorithm Representation Iterative Structures CI CI El Algorithm Discovery CI El Recursive Structures CI Efficiency shag 2 Outline CI The Concept of an Algorithm El Algorithm Representation CI CI CI CI Efficiency Algorithm Discovery Iterative Structures Recursive Structures sham Definition of an Algorithm An algorithm is an ordered set of unambiguous executable steps that defines a terminating process shag Example 1 Example 2 task find iargest positive nteger step 1 make a list of all the positive ntegers step2 arrange this list n order step3 copy the first integer n this list step4 stop NOT an algorithm because step 2 is ambiguous what order 1 is not executable 9 although it has f nite steps it does not terminatedi siiaes task take exam step 1 read unanswered question step2 if you know the answer write it down step3 go back to step 1 if there are still unanswered questions step4 stop Is this an algorithm Sllde Abstract Nature of Algorithms Outline Distinction between algorithm and its quotrepresentationquot algorithm mnderiying concept representation way of commun cating the algorithm Further distinction program formal representation of an algorithm process activityof executing the program Shae El The Concept of an Algorithm El Algorithm Discovery El Iterative Structures El Recursive Structures El Efficiency Sllde Representation algorithm is an abstraction of a process need to be able to tell other people or a computer how to do it Write it down syntax rules for how to write it down semant cs rules for determining meaning Slide 9 Example Folding a bird Slide 10 Example Folding a bird ijfj L ltllh7hg 3 w 4 4 Slide 11 Example Euclidean Algorithm Algorithm to find the greatest common divisor gcd of two positive integers 1 Assign M amp N the value of the larger and the smaller of the two input values respectively 2 Divide M by N and call the remainder R 3 If R is not zero then assign M the value of N assign N the value of R and return to step 2 otherwise the gcd is the value assigned to N Slide 12 Primitives welldefined set of building blocks must be unambiguous appropriate level of detail can be comb ned with other primitives to form higherlevelquot primitives mach ne language pr mitives will work however level of detail is inappropriate for most problems Origami Primitives Syntax Semantics Turn paper over 77 as T Q Shade one Side Distinguishes between different sides of paper of paper as in G G G Represents a valley fold sothat represents Q Slide 13 Slide 14 Representations Pseudocode programming languages ex C mplement Sequential statements execute statements from top to bottom pseudocode ie Englishlike statements with a assignment special simple syntax design name 9 eXPJTESSiOU conditional statements selection If it is cold wear a jacket otherwise a Tshirt is f ne if condition then activity 1 Depending on the temperature wear a Jacket or not I I else actiVity 2 if temp less than 70 then wear jacket else wear Tshirt iteration statements loops while condition do activity Like writing an outline or taking notes use it to develop understanding of problem Slide 15 Slide 16 Modular Design Procedures ease of comprehension and modif cation organize structure the algorithm into major sections or modules similar in concept to us ng an outline to write a paper each module can be considered an algorithm as well modules provide different levels of detail Slide 7 how to represent a module define the module give a module a name refer to the module nstead of writing out all steps of that module just give the name of the module pseudocode procedure nameOfModule Slide 5 Example Definition of Procedure refer to module brusliTeetli from 2 other modules procedure ge tReadyForSchool wakeUp eatBreakfast brushTeeth procedure getReadyForBed eatDlnner brushTeeth turn off hghts Slide 9 procedure brushTeeth O to athroom grab toothbrush open toothpaste tube put brush brlstles under tube openmg while not enough paste on brush do 5 whlle 2 mmutes not past o move brush up and down Slde to Slde rlnseMouth Slide 2n Considerations How to write pseudocode Two things you can do to a module use it defineit You can use a module before it39s def ned but the algorithm is NOT COMPLETE until the module is defined Modules can be used several times without having to def ne them over and over Sllde 21 what are our primitives in pseudocode a anything we need we just make it up so I can write brushHair and that39s my algorithm only if brushHair is executable on your target machine if it39s notyou need to treat brushHair like a procedure and define it in more specific terms Sllde 22 Outline The Art of Problem Solving El The Concept of an Algorithm El Algorithm Representation El Iterative Structures El Recursive Structures El Efficiency Sllde 23 an algorithm is a precise specification of how to solve a problem but how do I solve problems problem solvng is a skill that is developed and learned there is NO step by step recipe for solving problems the key is PRACTICE Sllde 24 Polya39s Phases Phases NOT Steps Understand the problem ll Get an idea about what kind of algorithm is needed Create the algorithm and implement it program Evaluate the program for accuracy and general use Sllde 25 not carried out in sequence typically depend on our exper ence creativity and imagination to understand a problem sometimes we need to implement an algorithm prototype problem solving is part of software engineer ng Sllde 25 Getting 0 Foot in the Doorquot Outline the desk drawer approach solve only part of a problem first work backwards from a solution study solutions to similar problems solve specific cases first then generalize stepwise refinement modular approach Sllde 27 El The Concept of an Algorithm El Algorithm Representation El Algorithm Discovery El Recursive Structures El Efficiency Sllde 2E Iteration Iteration and Search iteration involves repeat ng some action but how often or for how long should action be repeated 9 as long as a certa n condition is given while some condition is given do thisquot 9 until some eventcondition occurs repeat doing this until condition occursquot slide 29 searching is a process of examining objects from a list of objects until you f nd the one that you are looking for keep on searching 9 iteration is uppl cable to the search process slide 3n Sequential Search Pseudocode of Sequential Search oblem given a list of objects and an object to search for determine if the named object is in the list of objects this is the WHAT one method is to examine each object n the list sequentially until either we find the object we39re looking for or we loo through everything and see that the object is not there thisis the HOW slide 3 leen a 11 and an object select the flrst element 1n the 11st while selected element 1s not the Object do select the next element 1n the 11st problem does this terminate what happens if we run out of elements how do we handle the case where the object is NOT in the list slide 32 RefinemenT 1 procedure sequentialSearchobject list select first object in list while there are unselected objects in list AND selected element is not the object do select the next element in the list if we found object then printquotfound itquot else printquotnot therequot RefinemenT 2 procedure sequentialSearchobject list item firstObjectInlist while not isLastitem and item 1 object do item neXtObjectInlist if item object then printquotfound itquot else printquotnot there Does it work for all possible cases Slide 33 Slide 34 ComponenTs of a Loop while Loop InITIalIze seT up The condITIons whlch The loop TesTs Condition TesT39 compare cur39r39enT loop condiTion To The sTopping colSEEM false condiTion and Term naTe if They maTch modify change The condiTions so ThaT The loop will Condition whi 1e condition do evenTually TerminaTe true activity Activity Slide 36 Slide 35 repeat Loop i Activity l repeat activity until condition Te Condition condltlon false Condition true Slide 37 Outline CI The Concept of an Algorithm El Algorithm Representation El Algorithm Discovery El Iterative Structures El Recursive Structures El Efficiency Slide 38 Binary Search A Binary Search algorithm searches 0 sorted list by examining the middle item If the item is not found the appropriate half of the list is searched again using the Binary Search algorithm Each time only half of the remaining list is searched until the item is found Slide 39 Binary Search Algorithm procedure Search List TargetValue if List empty then Report that the search failed else Select the middle entry in List to be the TestEntry Execute the block of instructions below that is associated with the appropriate case case i TargetValue TestEnt Report that the search succeeded case 2 TargetVaIue lt TestEntry Apply the procedure Search to see if TargetVaIue is in the portion of the List preceding TestEntry and report the result of that search case 3 TargetValue gt TestEntry Apply the procedure Search to see if TargetValue is in the portion of List following TestEntry and report the result of that search end if Slide 40 10 Binary Search Example Search n9 for quotJohnquot Original list Firstsublist Second sublist Alice Bob Carol David Elaine Fred George Harw Irene Irene Irene John John John Kelly Kelly Kelly L quoty Larry Mary Mary Nancy Nancy Oliver OliVer Outline CI The Concept of an Algorithm El Algorithm Representation El Algorithm Discovery El Iterative Structures El Recursive Structures El Efficiency Slide 42 Slide 41 Algorithm EffICIency If an algorithm does not process information efficiently CPU resources are wasted Poor response time may result Possibly the problem cannot be solved in your lifetime Slide 43 Sequential Search For the sequential search previously discussed the time to find an item n the list is proportional to the size of the list divided by 2 This makes sense because some items close to the front of the list are found quickly but other items near the end of the list take more time to find So on average time NZ where N is the number of items in the list Slide 44 11 Binary Search A B nary Search algoriThm searches a sorTed isT by exam ning The middle iTem If The iTem is noT found The appropriaTe half of The isT is searched again using The Binary Search algoriThm Each Time only half of The remaining isT is searched unTil The iTem is found The T me To perform a binary search is proporTional To The logariThm of The size of The isT Time log2N where N is The number of iTems in The isT GrowTh RaTes b 100 2n n3 n2 n logzn 7539 5039 Value of growthrate function 2539 logzn Slide 46 Slide 45 ImporTance of EffICIency Towers of Hanoi 64 Golden Rings on 3 diamond pegs PriesTs n India musT move The rings from one peg To anoTher buT They can move only one ring aT a Time and They cannoT puT a larger ring on Top of a smaller one Legend has iT when all The disks have been moved The world will end This problem has a soluTion ThaT grows exponenTially Time 2quot Slide 47 When will The world end Assuming The priesT can move one ring per second IT will Take 264 18446744073709551616 seconds or approximaTely 585 Billion years For perSpecTive The universe is only 15 Billion years old Slide 48 12 Department of Physics Computer Science 8 Engineering Foundations of Computer Science Networking and the Internet Dr Lonnie Cheney Outline CI Network Fundamentals CI The Internet CI The World Wide Web CI Network Protocols El Security shag 2 Outline CI Network Fundamentals CI The Internet CI The World Wide Web CI Network Protocols El Security slide Classification of Networks Geomhkd scope Local Area Networks LAN e Wide Area Networks WAN awnship closed proprietary networks 69 open networks uponquot a different topologies possible shag Network Topologies a Ring b Bus Network Topologies c Star d Irregular meshed Topology Slide 6 Slide 5 Routers connecting Networks off 9 Wi Fi network f N AP Q Router Router lr V l A 7 L L Router Ethernet network AP GS Wi Fi network Slide 7 ClientServer vs PeertoPeer Server 3 Server must be prepared to serve multiple clients at any time Peer 4 Peer b Peers communicate as equals on a onetoone basis Slide 8 Outline CI Network Fundamentals CI The Internet CI The World Wide Web CI Network Protocols El Security Slide 9 Internet Architecture Tierrl ISPs Tier2 ISPs Access ISPs 3 End svmems Slide 10 Internet Architecture interconnection of many diverse communication networks all based on the Internet Protocol IP Slide 11 Internet Addressing Addresses 39 32 bits length gt 232 2 4109 different addresses 39 written in form XXXX with 0 g X g 255 eg 1371552 49 dotted decimal notation 39 addresses contain lnetworkidentifierl subnet I hostaddress I Nam es 39 better readable for humans 39 administrated through Domain Name Service DNS 39 Names reflect hierarchy levels of the Internet eg wwwpcsrnuedu 39 top level domains com edu org Slide 12 Addressing Example 12XXX domain verizoncom 137155XX domaincnuedu 195127XX domain eunetde Slide 13 Addressing Example pcscnuedu 1371552X 137155XX domaincnuedu MW 137155144X 1371554X Slide 14 Addressing Example wwwpcscnuedu 137155249 1371552X E pcscnuu keg a 137155227 defenderpcscnuedu 1quot Slide 15 Internet Applications email 39 FTP file transfer protocol telnet ssh secure shell Voice over IP VoIP World Wide Web Slide 16 Outline CI Network Fundamentals CI The Internet CI The World Wide Web CI Network Protocols El Security Slide 17 Implementation of the World Wide Web World Wide Web collection of linked documents and media documents are called quothypertextquot quothypermediaquot browser user interface to the WWW client HTTP Hypertext Transfer Protocol URL Uniform Resource Locator HTML Hypertext Markup Language Slide 18 Typical URL http 39 aw t mt h L JuliusCaesarhtml l Mnemonic name of host holding the document Document name Protocol required Directory path indicating the location ofthe document within hypertext transfer the host39s protocol http file system Slide 19 Simple Web page in HTML Tag indicating beginning of document Preliminaries The part of the document that will be displayed by a browser Tag indicating end of document lthtmlgt ltheadgt lttit1egtdemonstration pagelttitlegt ltheadgt ltbodygt lth1gtMy Web Pageltlh1gt ltpgtclick here for another pageltpgt ltbodygt lthtmlgt Slide 20 Web page with Link lthtmlgt ltheadgt lttitlegtdemon5tration pageltltitlegt ltheadgt ltbodygt lthlgtMy Web Pagelthlgt Anchor tag p uiCK containing 439 lta hrefquothttpcraftycomdemoihtmlquotgt pa re mote r here Go ng anchor tag 4 ltagt for another pageltpgt ltbadygt lthtm1gt Slide 21 Outline CI Network Fundamentals CI The Internet CI The World Wide Web CI Network Protocols El Security Slide 22 Issues of Network Protocols CI Synchronization of Communication CI Fair and efficient allocation of communication resources CI Enable quotunderstandingquot between hosts Slide 23 Communication over Ring Computer Computer Messages m Ve Computer In only one direction Computer Computer Slide 24 Communication over Bus Computer Computer Computer l V lv Iv Computer Computer Layered Approach Origin Pepares package for shipping Places package in container for airline Shipping company Intermediate stops Places container in airplane Airline Airline Transfers container to another airplane gt Airline gt Airline Final destination F end Shipping company Receives and opens package Removes package from container and delivers it to addressee Sends container to shipping company Slide 26 Slide 25 Internet Software Layers App39ication eg ftp telnet ssh SMTP HTTP Transport Transmission Control Protocol TCP User Datagram Protocol UDP Network Internet Protocol IP Link eg Token Ring CSMACD Ethernet Slide 27 Message through the Internet At each intermediate stop the network layer assigns a new intermediate address to the packet and returns it to the link layer for transmission across another network Prepares message Application and attaches destination address JL Chops message into packets Transport Pplica on message Receives A A 7 Collects packets Transport and reassembles A message Assigns I Detects that intermediate Network Network I Network Network packet has address to A A reached its each packet final destination Tra nsfe rs packet toits V V Link Link H Link address Origin Intermediate stops H Link Receives packet Final destination Slide 28
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'