Terms : Hide Images
| 64729838 | Abstraction | Modelling of a complex system only including the essential details | |
| 64729839 | Automation | Turning an abstraction into a form that can be processed by a computer | |
| 64729840 | Polynomial Time | O(n^a) Eg. Bubble Sort - O(n²) | |
| 64729841 | Linear Time | O(n) Eg. Tree Traversal | |
| 64729842 | Exponential Time | O(aⁿ) where a > 1 Eg. Tower of Hanoi | |
| 64730718 | Syntax diagram | Graphical way of expressing the grammar of a language. Arrows indicate the different paths that may be taken through the diagram | |
| 64730719 | Extended Backus Naur form | | denotes OR, { } denotes ZERO OR MORE, [ ] denotes OPTIONAL | |
| 67499227 | A programming paradigm | an approach or a way of reasoning to solve a problem | |
| 67499228 | Procedural Programming | Write sequences of commands. Fairly efficient, easy to follow. Fine for pay roll | |
| 67499229 | Event driven programming | Nothing happens until the user clicks a mouse or a timer generates a signal | |
| 67499230 | Object Oriented programming | The programmer uses objects to represent real concepts. Suitable for simulations. | |
| 67499231 | OOP Object | a bundle of attributes and related methods that modify the attributes. | |
| 67499232 | OOP Object Class | a blueprint for an object. It represents the information and methods that a typical object has. Eg. the college is an object, being a member of the object class of FE colleges | |
| 67499233 | An object is known as | an instance of the class | |
| 67499234 | Instantiation | Creating an instance of a class | |
| 67499235 | Encapsulation | the bundling together of attributes and methods but making the attributes private and only allowing attributes to be changed using the methods | |
| 67499236 | Inheritance | passing attributes and methods to objects in a sub class | |
| 67499556 | List | a one-dimensional array | |
| 67499557 | Stack | a collection of items which can only be added or removed at one end. There is a pointer to the top which is incremented and decremented. Watch out for overflow and underflow. Simulate using a 1 dim array and a pointer. | |
| 67499558 | Queue | items are taken from the front and added to the rear. There is a pointer for each end. A circular queue wraps around from the bottom of memory to the top. Check for empty or full queue. Simulate with a 1 dim array | |
| 67499559 | Binary tree | represented using an array with 3 columns to store the left & right pointer and the data. Additions to a tree are easy and it can be accessed in alphabetical order. | |
| 67499560 | linked list | a dynamic data structure in which items are physically added to the end of the list. We can access sorted data as each item has a pointer to the next item in logical order. To add or remove an item simply change 2 pointers. Free space is also held in a linked list. | |
| 67499561 | Static Structure | size is specified at the start, eg. an array | |
| 67499562 | Dynamic Structure | can grow or shrink during execution | |
| 67499563 | Pointer data types | allow the creation of dynamic data structures in memory, using locations only when needed. | |
| 67499564 | When dynamic structure need more memory | It is pulled from a pool called a heap and is returned to the free memory heap when finished | |
| 67499612 | A Recursive algorithm | is very powerful producing lots of results with minimum coding but is hard to follow. It is used in quick sort, tree traversal & solving mazes. | |
| 67499613 | A recursive procedure | is defined in terms of itself. Eg. n! A stack is needed to store return addresses and different copies of the same variable | |
| 67499614 | Tree Traversal Algorithm | Inorder: traverse left subtree, visit root, traverse right subtree -gives Infix notation: A + B preorder: visit root, traverse left subtree, traverse right subtree postorder: traverse left subtree, traverse right subtree, visit root -gives Reverse Polish notation: A B + | |
| 67976972 | Graph | A data structure containing data items, called vertices that are connected by lines called edges or arcs | |
| 67976973 | Undirected graph | Connections are two way. An undirected graph is complete if every vertex is joined to every other vertex | |
| 67976974 | Directed graph or digraph | Has 1-way edges with arrows. | |
| 67976975 | 2 vertices are neighbours | If they form an edge | |
| 67976976 | A path | is a sequence of vertices in which each successive pair is an edge | |
| 67976977 | A closed path | starts and ends at the same vertex | |
| 67976978 | A cycle | is a closed path with all edges & vertices different | |
| 67976979 | An undirected graph is connected | if, for any pair of vertices, there is a path between them | |
| 67976980 | A tree | is a connected, undirected graph with no cycles | |
| 67976981 | A rooted tree | is a tree with one vertex designed as the root and every edge is directed away from the root | |
| 67976982 | Traversing a graph | is visiting each vertex once | |
| 67976983 | Graph Traversal Algorithm | Algorithm maintains 2 flags for each vertex: Have we encountered before?, Have we finished exploring it? Breadth-first or neighbours-first Output data at that vertex, Add new neighbours to queue Depth-first is similar but neighbours are added to a stack. Explorer traverses each road once and returns to start. Traveller visits each vertex once and returns to start | |
| 67977350 | Adjacency list representation | For each vertex keep a list of vertices we can reach Could use a linked list Suitable method for a graph with few connections | |
| 67977351 | Adjacency matrix representation | 2 dimensional array showing connections for each pair Suitable for dense graphs | |
| 67977352 | In a labelled graph | The edges are given a value called a weight eg the distance between 2 towns. This value is held in the adjacency matrix or as extra item in adjacency list. | |
| 68309231 | A binary search | The middle item is compared with the search item, discard the half of the list without the search item, this process continues until you find it or only one value remains and it is not the search item. Can only be used on sorted data | |
| 68309232 | Insertion sort | Gets the first 2 numbers in order and then, one at a time, merges each extra number into its correct place. It is a fast method on a small set and on a set that is nearly in order | |
| 68309233 | Computer simulations | Can represent real and imaginary situations. They allow users to study or try things that would be difficult or impossible in real life. Can be simulated over much shorter time than real life. Used in training as dangerous situations can be set up and repeated safely & cheaply | |
| 68309234 | A model | a mathematical representation of a process. A computer can quickly do calculations & display results. Limited by human understanding and the need to be simple enough to produce quick results | |
| 68309235 | Examples of Models and Simulations | Traffic flow can be modelled to investigate the route of a new road. Traffic can be increased and results observed. Weather forecasters use a computer simulation. Data is gathered from many sources and predictions are made | |
| 68309236 | Floating point | a representation that consists of 2 parts, a mantissa and an exponent | |
| 68309237 | Precision of a real number representation | depends on the number of bits used for the mantissa | |
| 68309238 | Range of a real number representation | depends on the size of the exponent | |
| 68309239 | Truncation of a real number | (or rounding) occurs when the mantissa is not sufficient to represent all the digits in the number | |
| 68416685 | Normalisation of a real number | gives a consistent representation with maximum precision. We shift positive numbers to the left to push out leading 0s. If negative we push out leading 1s | |
| 68416686 | Overflow in real number representation | occurs when a number is too large to be held | |
| 68416687 | Underflow in real number representation | A calculation results in a number which is too close to zero to be represented | |
| 68416688 | Virtual machine | hides the complexities of the hardware from the user. It manages the hardware resources in order to provide an orderly and controlled allocation of the processors, memories and I/O devices among the various processes competing for them | |
| 68416689 | Interactive OS | user gets immediate response and has two way communication with the computer. User interacts with main computer and has access to the main data files | |
| 68416690 | Real-Time OS | data is processed sufficiently quickly to influence what happens next | |
| 68416691 | Network OS | Controls Communication | |
| 68416692 | Client server systems | the server holds the data and runs the program, the client computer interfaces with the user | |
| 68416693 | Database | Data is held in a collection of tables. Each entity has its own table. | |
| 68416694 | Data relationships | are implemented by having a common field to link the related tables | |
| 68416695 | Attributes | items of information held about an entity | |
| 68416696 | Primary key field | Holds a unique value for each record | |
| 68416697 | Composite key | uses two or more attributes | |
| 68416698 | A secondary key | unique field other than primary key | |
| 68416699 | Foreign key | a field linked to a key field in another table | |
| 68416700 | Referential integrity | ensures that relationships between tables remain consistent. You may not add a record to the table that contains the foreign key unless there is a corresponding record in the linked table. | |
| 68416701 | Entity | an item to be represented in a database | |
| 68416702 | Entity relationship | a connection (relationship) between entities in a database | |
| 68416703 | First Normal Form | simplifies the structure by removing repeating attributes | |
| 68416704 | Third Normal Form | ensures that there is no redundant data in a table by creating additional tables | |
| 68416705 | DDL (Data Definition Language) | a way of specifying all the attributes and properties of a database: create tables and views with indexes and constraints | |
| 68416706 | SQL (Structured Query Language) | for users to define and manipulate data in a relational database | |
| 68416707 | Serial transmission | sends each bit down a single line | |
| 68416708 | Parallel transmission | sends many bits simultaneously along separate lines. This is faster than serial but only works over short distances and cable is expensive | |
| 68416709 | Baud rate | the number of voltage changes a second | |
| 68416710 | Bit rate | the number of bits transmitted per second | |
| 68416711 | Bandwidth | the range of frequencies that a line can transmit. Low for telephone wire, high for fibre optic. The higher the figure the greater the bit rate | |
| 68416712 | latency | refers to any of several kinds of delays typically incurred in processing of network data | |
| 68416713 | Ping test | measures latency by determining the time it takes a given network packet to travel from source to destination and back | |
| 68416714 | Asynchronous data | sent intermittently one character at a time with a start bit to alert receiver & a stop bit | |
| 68416715 | parity bit | is sent with 7 bit ASCII so that the number of 1s is always odd or always even | |
| 68416716 | Protocol | rules covering transmission speed & codes | |
| 68416717 | Handshaking | is sending signals between devices to test if device is ready to receive and to acknowledge receipt | |
| 68416718 | Baseband | carries one signal at a time. Fast, up to 300m | |
| 68416719 | Broadband | carries multiple signals, voice, video & data | |
| 68416720 | WAN | connects geographically remote computers using telecommunications | |
| 68416721 | LAN | confined to a small site, can share printer, programs, data files. Allows communication and centralises security and backups | |
| 68416722 | Topology | refers to the layout of connected devices | |
| 68416723 | Star Topology | directly linked to server, reliable, cable costly | |
| 68416724 | Bus Topology | one cable, cheap, degrades if highly loaded | |
| 68416725 | Segmenting a bus network | reduces the traffic in each segment and now each segment can cover 500m | |
| 68416726 | Bridge | hardware device that links segments, using same protocol, only passes packets destined for other segment | |
| 68416870 | Peer-to-peer Network | does not use a server but each computer can share the printer, hard drive or other hardware connected to another machine, which must be on. Suitable for a small network when users mostly do their own work but occasionally share data or communicate | |
| 68416871 | Server based network | user authentication, administration, resource allocation managed by servers | |
| 68416872 | Thin client | does little processing and accesses the server each time input data needs to be processed or validated | |
| 68416873 | Rich client | performs many functions without server | |
| 68416874 | AJAX | Asynchronous JavaScript and XML - technique for creating interactive web applications. Data is retrieved from the web server asynchronously in the background, without a page reload. Only the part of a page that needs updating is fetched from the web server. This reduces the number of bytes to transfer | |
| 68416875 | In a Classic web application | user interface events trigger an HTTP request to a web server to retrieve data, process and return an HTML page to the browser | |
| 68416876 | Inter-networking | two or more independent networks are connected yet function separately, as in Internet | |
| 68416877 | Routers | use IP addresses to route packets | |
| 68416878 | Gateways | connect networks of different protocols | |
| 68416879 | CGI | Common Gateway Interface is a standard protocol for interfacing application software with a web server | |
| 68416880 | Server-side scripting | runs a script directly on the web server to generate dynamic web pages that provide interactive web sites that interface to databases. This is different from client-side scripting where scripts are run by the viewing web browser | |
| 68416881 | Advantage of server-side scripting | the ability to highly customize the response based on the user's requirements or access rights | |
| 68416882 | Firewall | a security system intended to protect an organisation's network against external threats and prevent hackers. It decides which messages to let through | |
| 68416883 | A proxy server | acts as a go-between for requests from clients requesting some service, such as a file, connection, web page, or other resource, available from a different server. The proxy server evaluates the request according to its filtering rules. | |
| 68417183 | Main purposes of a proxy server | To keep machines behind it anonymous (for security) and to speed up access to a resource (via caching). It is commonly used to cache web pages from a web server. | |
| 68417184 | Encryption | the process of encoding data for transmission, protecting e-mail, credit card info & company data | |
| 68417185 | Governments | want access to all decryption keys | |
| 68417186 | Digital certificate | comes with a public key for encoding and a private key for decoding. Public key is freely given | |
| 68417187 | Digital signature | a mathematical calculation on the whole message, is generated and sent. A digital signature authenticates the sender, proves that the message has not been tampered with and the sender can not deny sending it | |
| 70428360 | Intractable problems: | Software and hardware present limitations to solving problems | |
| 70428361 | Halting problem | The unsolvable problem of determining whether any program will ever stop given particular input | |
| 70428362 | Turing Machine | Is a basic abstract symbol-manipulating devices that can be manipulated to simulate the logic of any computer algorithm | |
| 70428363 | Universal Machine | can simulate any Turing machine | |
| 70428364 | Automata | is a Finite State Machine with no output | |
| 70428520 | Hashing algorithm | Converts a key field into an integer that could be a record number. | |
| 70428521 | Collision | When a Hash function maps two keys to the same value | |
| 70428522 | Absolute error | difference between actual and nearest representation | |
| 70428523 | Relative error | absolute error divided by the actual number | |
| 70428524 | Embedded computer system | a dedicated computer system with a limited or non-existent user interface, designed to operate autonomously within machinery | |
| 70428525 | Desktop operating systems | manage many types of hardware and software. Written in layers for easy update They can provide a virtual machine so easier for user | |
| 70428526 | DDL - Create Table | CREATE TABLE Cars ( REGNO CHAR(7) PRIMARY KEY, REGISTERED DATE ) | |
| 70428527 | Bluetooth | supports a very short range, 10m and low bandwidth. Designed for low power network devices like handhelds- PDA, mobile phone. Lower manufacturing cost | |
| 70428528 | Authentication | way of identifying a user - username | |
| 70428529 | Authorisation | check user has permission to perform a certain task | |
| 70428530 | Accounting | records resources used and logs what done | |
| 70455908 | Advantage of Adjacency List Implementation | Only uses memory for links | |
| 70456024 | Advantage of Adjacency Matrix Implementation | Faster access to data (to check existence of link) | |
| 70460846 | Advantage of Reverse Polish | Easier to compute, unambiguous | |
| 73044794 | Information Hiding | Hiding design details behind a standard interface | |
| 73044795 | Interface | a boundary between the implementation of a system and the world that uses it | |
| 73044796 | Algorithm | A sequence of unambiguous instructions for solving a problem | |
| 73044797 | Finite State Machine | consists of a set of input symbols and a finite set of states and a transition function that maps a state-symbol pair to a state | |
| 73044798 | Deterministic FSM | has just one next state for each state-symbol pair | |
| 73044799 | Non-deterministic FSM | may have several possible next states for each state-symbol pair | |
| 73044800 | Tractable | a problem that has a reasonable (polynomial) time solution | |
| 73044801 | Regular Language | any language that a FSM will accept | |
| 73046027 | Regular Language | | Exclusive OR | |
| 73046028 | Regular Language ? | Zero or one of the preceding element | |
| 73046029 | Regular Language * | Zero or more of the preceding element | |
| 73046030 | Regular Language + | One or more of the preceding element | |
| 73046031 | Regular Language [ ] | encloses a list of characters, one of which is selected | |
| 73046032 | Regular Language [^a] | negates the enclosed list of characters (any letter other than a) | |
| 73046033 | Regular Language [a-z] | all 26 lower case letters | |
| 73046034 | Regular Language \d | any integer 0-9 | |
| 73046035 | Regular Language \w | a single alphanumeric character or an underscore _ | |
| 73046036 | Regular Language \W | a single non-alphanumeric character | |
| 73046037 | Regular Language \D | a single non-numeric character | |
| 73046038 | Regular Language \s | a space | |
| 73046039 | Regular Language \S | a single character other than a space |
