-
Alphanumeric Data
- - refers to charachters that can be displayed or printed including numerals and symbols ( $, &, #....)
- -excludes control characters ( tab, carriage return, form feed...)
- - all symbolic data must be represented by binary code.
-
Coding
- Refers to the manner in which alphanumeric data and control characters are represented by a sequence of bits.
-
ASCII
- - American Standard Code for Information Interchange
- - a seven-bit code permitting 128 ( 27) different combinations
- - the use of the high order eighth bit is not commonly used in microcomputers.
- - ASCII -coded magnetic tape and disk files are used to transfer data and documents between computers of all sizes that would not otherwise share data structures
-
EBCDIC
- - Extended Binary Coded Decimal Interchange Code
- - is in widespread use in SuperComputers
- - It uses eight bits ( a byte) for each charachter, allowing a max of 256 (28) different charachters.
-
Hexadecimal
- - or "packed" format is used to simplicity working with EBCDIC data since strings of binary digits (bits) are difficult to read.
- - Each byte is converted into two strings are then converted to hexadecimal. Since (1111)2 = (15)10 = (F)16 the largest possible EBCDIC characters is coded FF in hexadecimal.
-
What is 11110111 in EBCDIC?
- 1111 = (15)10 or (F)16
- 0111 = (7)10 or (7)16
-
Program
- - a sequence of computer instructions that performs some function
- - a program is designed to implement an algorithm.
-
Algorythm
- - a procedure consisting of a finited set of well-defined steps
- - each step in the algorithm usually is implemented by one or more instructions ( eg, Read, GOTO, OPEN ...) entered by the programmer.
- - These original "human-readable" instructions are known as "source code statements".
-
Source Code Statements
- - Original "human-readable" insturctions
- - Except in rare cases, a computer will not understand source code statements.
- - Therefore, the source code is translated into machine-readable object code and absolute memory locations.
- - Eventually, an executable program is produced.
-
Software vs. Firmware vs, Hardware
- Software - if the executable program is kept on disk or tape.
- Firmware - if the program is placed in ROM or EPROM
- Hardware - the computer mechanism itself.
-
Internal Subprograms
- - those subprograms written by the programmer.
- - external subprograms are supplied in a library by another source.
-
Structured Program II
- - Ideally, the main line program will consist entirely of a series of calls ( references ) to these subprograms.
- - Liberal use is made of FOR/NEXT, DO/WHILE, and DO/UNTIL. commands.
- - Labels and GOTO commands are avoided as much as possible.
-
Structured Program II
- - Ideally, the main line program will consist entirely of a series of calls (references ) to these subprograms
- -Liberal use is made of FOR/NEXT, DO/WHILE and DO/UNTIL commands.
- - Labels and GOTO commands are avoided as much as possible.
-
Recursive Calls
- - Very efficient programs can be constructed in language that support recursive calls ( ie permit a subprogram to call itself )
- - Some languages permit recursion, others do not.
-
Local vs. Global Variables
- - Variables whose values are accessible strictly within the subprogram are Local Variables.
- - Global Variables can be refered to by the main program and all other subprograms.
-
Loop
- - If <conditions> THEN <action1> ELSE <action2>
- - DO WHILE <condition> ...set of instructions ENDWHILE
- -DO UNTIL <condition> ....set of instructions ... END UNTIL
- - FOR <counter range> ...instructions NEXT <counter>
- - GOTO operation avoided, fallen from favor
-
Fields, Records, and File Types
- - Record - a collection of Fields.
- - Field - ie name, age and address
- - File - group of records stored in
- - Sequential File structures - magnetic tape
- - Indexed Sequential Files - a separate index file is used to locate records
- - Random (direct access) file structure
-
File Indexing
- - It is more efficient to keep the names in the order of entry than to sort the list each time names are added or deleted.
- - An index ( key or keyword) file is analogous to the index at the end of a book.
- - One field in the record is selected as the key filed ( record index )
- - More than one field can be indexed, however, each field will required its onwn index file.
- - The sorted keys are usually kept in a file separate from the data file.
-
Successive Minima Sort
- - a list is searched sequentially until the smallest element is fround and brought to the top of the list
- - that element is then skipped and the remainig elements are searched for the smallest element which is placed after the previous minima
- - comparisons required - n ( n-1 ) / 2
- - comparisons required when n is large - n2 / 2
-
Random Secondary Storage Devices
- - Also known as mass storage devices
- - Random access (direct access) storage devices
- - Magnetic disk drives ( hard drives ) have several "platters" each with one or more read/write heads.
- - "Tracks" are concentric storage areas
- - "Sectors" are pie-shaped subdivisions of each track
- -"cylinders" are the same numbered track on each platter
- - some platters and "disk packs" are removable but most are not.
-
Flow Chart
- a step-by-step drawing representing a specific procedure or algorithm.
-
Terminal - (flowchart
- _________________
- (_________________)
-
Input/Output ( Flowchart )
- _____________
- / /
- /____________/
-
Processing ( Flowchart)
- ____________
- l........................1
- 1___________1
- refer to caluculations or data manipulation ( along with the predefined process symbol )
-
Predefined Process (flowchart)
- _______________
- ll..........................ll
- ll_____________ll
- refer to calculations or data manipulation ( along with the processing symbol.
-
Decision (flowchart)
- ............./\
- .........../...\
- ..........\..../
- ...........\./
- - indicates a point where a decision must be made or where two items compared.
-
-
Connector (flowchart)
- .........O
- - indicates that the flowchart continues elsewere.
-
Off- Page
- ________
- l..............l
- l..............l
- \............./
- ..\........./
- ....\..../
- Indicates flowchart continues on another page.
-
Annotation (flowchart)
- ...................___________
- _________l
- ..................l___________
- Note: Comments can be written in an annotation symbol
-
Low-Level Languages
- Two general types of specific languages
- 1. Low- Level
- 2. High -Level
- Low-Level languages include:
- 1. machine language
- 2. assembly language
-
Machine Language Instructions
- - intrinsically compatable with and understood by the computers CPU
- - they are the CPUs native language
- - an insturction normally consists of two ports:
- ...1.the operation to be performed (op-code)
- ...2. the operand expressed as a storage location
- - Each instruction ultimately must be expressed as a series of bits, a form known as intrinsic machine code.
- - However, octal and hexidecimal coding are more convenient.
- -In either case, coding a machine language program is tedious and seldom done by hand.
-
Assembly Language
- - more sophisticated ( ie is more symbolic)
- than machine language
- - Mneumonic codes are used to specify the operations.
- - The operations are refered to by variable names rather than by the addresses.
-
Macros ( macro instructions )
- - Blocks of code that are to be repeated verbatim at multiple locations in the program.
- - They are written once and refered to by a symbolic name in the source code.
-
Assembly Language Code
- - is translated into machine language code by an assembler (macro-assembler) if macros are supported
- - after assembly, portions of other programs or function libraries may be combined by a linker.
- In order to run, the program mjust be placed in the computers memory by a loader.
- - Assembly language programs are preffered for highly efficient programs.
- - However, the coding inconvenience outweighs the advantage for most applications.
-
Language Type Examples
- Language Instruction
- Intrinsic Machine Code.....11110001
- Machine Language.............1A
- Assembly Language...........+
-
High- Levle Languages
- - easier to use than low-level languages because the instructions resemble english.
- - High level statements are translated into machine language by either an interpreter or compiler.
-
Compiler
- - performs the checking and conversations on all instructions only when the compiler is invoked.
- - Then a true stand-alone executable program is created.
-
Interpreter
- An interpreter differs from a compiler in that it checks the instructions and converts then line-by-line into machine code during execution but produces no stand-alone program capable of being used without the interpreter.
-
Interpreters vs. Compilers Continued
- - Some interpreters check syntax as the statement is entered by the programmer.
- - some languages and implementations of other languages blur the distinction between interpreters and compilers.
- - Terms such as pseudo-compiler and incremental compiler are used in these cases.
-
Relative Computational Speed
- 1. Assembly language programs._____Fastest v
- 2. Compiled
- 3. Pseudo-compiled
- 4. Interpreted_______________Slowest v
- Most Efficient Program Structures
- 1. Simple equations - in repetitive opeartions__Fast v
- 2. Stand - alone loop
- 3. Loop withing a subroutine ________Slow v
- Overhead: Incrementing the loop variables and managing the exit and entry points - these take time.
-
Structured Language
- - It is structured if subroutines and other procedures each have one specific entry point and one specific return point.
- - Contrast this with BASIC with :
- __1) GOSUB - to a specific subroutine with a return from anywhere in subroutine
- __2) GOTO statements to anywhere in the main program.
-
Strong Data Types
- A languages has "Strong Data Types" if integer and real numbers cannot be combined in arithmentic statements.
-
Portable Language
- - A "Portable" Language can be implemented on different machines.
- - Most portable languages are either (1) sufficiently rigidly defined ( as in "ADA" or "C" ) to eliminate variants and extensions or (2) (as in the case of "Pascal") are compiled into an intermediate machine independent form called pseudocode (p-code)
-
Pseudocode (p-code)
- - neither source nor object code
- - The language is said to have been "ported" to a new machine when an interpreter is written that converts p-code to the appropriate machine code and supplies specific drivers for input, output, printers and disk use.
- - Some companies have produced Pascal engines that run p-code directly.
-
Structured Programming
- - Also known as " top-down programming", "procedure-oriented programming", and "GOTO-less programming.
- - Devides a procedure or algorithm into parts known as subprogramms, subroutines, modules, blocks or procedures.
- - The format and readability of source code do not define structured programming.
-
Bubble Sort
- - In a bubble sort, each element in the list is compared with the element immediately following it.
- - If the first element is larger, the positions of the two elements are reversed (swapped)
- - The smaller element thus "bubbles" to the top
- - If no swapps are made in a pass, list is sorted n2/2 comparisons are needed on average to sort list. Same as successive minima but more resources.
-
Insertion Sort
- - In an insertion sort, the elements are ordered by rewriting them in the proper sequence.
- - After the proper position of an element is found, all elements below that position are bumped down one place in the sequence Vacancy filled by insertion.
- - At worst n2/2 comparisons required
- - On average, approximately n2/4 comparisons.
-
Quicksort
- - more complex but reduces the average number of comparisons to nx log(n) / log (2) which is much less than the other sorts on the order of n2 for succesive minima, bubble, and insertion (in order of n x log(n) )
- - The quick sort falters in speed when the elements are in near perfect order.
-
Heap Sort
- The maximum number of comparisons for a heap sort is n x log(n)/log(2) but it is likely that even fewer comparisons will be needed.
-
Searching (Probing)
- - In a randomly organized group of records, a particular element in the list can be found only by a linear (sequential ) search.
- - 1 comparison at best, n comparisons at worst, n/2 on average comparisons ( of order n )
- - If the records are in ascending or decending order, the binary sort will be superior.
- - The search begins by looking at the middle element in the list.
- - If the middle element is the one sought-for the search is over.
- - Otherwise, half of the list will be disregarded as too large or small.
- - Then we look at the middle element of that list and so on.
- - The number of required comparisons if in ascending or decending order is Log(n)/ Log(2) of order Log(n)
-
Hashing
- - An Index File is not needed if the record number (i.e. storage location for a read or write operation ) can be calculated directly from the key.
- - This technique is called "hasing".
-
Hashing function or algorithm
- - The procedure by which a numeric or non-numeric key ( eg a last name ) is converted into a record number.
- - Most hashing algorithms use a remaindering modululs (remainder after deviding the key by the number of records, n, in the list.
- - Excellent results if n is a prime number and poor results occur if n is a power of 2.
- - (finding a record in this manner requires it to have been written in a location determined by the same hashing routine.
- - Not all hashed record numbers will be correct.
-
a "Collision" ( in hashing )
- - a collision occurs when an attempt is made to use a record number that is already in use.
- - chaining, linear probing, and double hashing are techniques used to resolve such collisions.
-
Database Structures
- - Databases can be implemented as indexed files, linked lists, and tree structures.
- - in all three cases, the records are written and remain in the order of entry.
-
Flat File
- - has only one key field by which records can be located.
- - "searching " techniques are used to locate a particular record.
-
Linked (Threaded ) List
- - each record has an associated "pointer" (usually a record number or memory address) to the next record in key sequence.
- - Only two pointers are changed when a record is added or deleted.
- - Generally, a linear search following the links through the records are used.
- Key and Data Files
- Key File
- Adams ......3
- Jones.........2
- Smith........1
- Thomas....4
- Data File
- 1.....Smith .............John............27
- 2.....Jones.............Wanda.........39
- 3....Adams...........Henry..........58
- 4....Thomas.........Susan...........18
-
Tree Structures
- - Pointers are also used Tree structures
- - Each record has one or more pointers to other records that meet certain criteria.
- - In a binary tree structure, each record has two pointers - usually to records that are lower and higher, respectively, in key sequence.
- - In general, records are in a tree structure are refered to as nodes.
-
Tree Structure ( How records are found )
- - Records are found in a tree by starting at the root node and moving sequentially according to the tree structure.
- - The number of comparisons required to find a particular element is 1+(log(n))/log(2)) which is on the order of log (n)
-
Root Node ( in tree structures )
- - The first record in a file is called the root node.
- - A particular node will have one node above it ( the parent or ancestor ) and one or more nodes below it ( the daughters or )
- .......................................[ Root Node ]
- .................................................l.........................
- ....._____James__.................................____Smith_____
- Adams.........Kensington................Rogers.....................Thomas
-
Hierarchical Database
- - contains records in an organized, structured format.
- - Records are organized according to one or more of the indexing schemes.
- However, each field within a record is not normally accessible.
- ......................................................................................
- ..............l...................................l............................l
- ..........Smith........................Jones.....................Thomas....
- John................27.....Wanda.............39.....Susan................18
-
Relational Database
- - Stores all information in the equivalent of a matrix
- - Nothing else ( no index files, pointers, etc,) is needed to find, read, edit, or select information.
- - Any information can be accessed directly by refering to the field name or field value.
- ...._________________________________________
- ...l Rec. no ....l....Last......l....First....l....Age....l
- ...l......1..........l....Smith...l....John....l....27.......l
-
Artificial Inteligence (AI)
- - in a machine, implies that the machine is capable of absorbing and organizing new data, learning new concepts, reasoning logically and responding to inquires.
- - AI is implemented in a category of programs known as expert systems that "learn" rules from sets of events that are entered whenever they occur.
- - Once the rules are learned, an expert system can participate in a dialogue to give advice, make predictions, and diagnoses or draw conclusions.
-
|
|