CS1005

Chinese Abacus

Way of mechanising adding

Babbage's Difference Engine

Automatic mechanical calculator designed to tabulate polynomial functions

Babbage's Analytical Engine

Decimal computer with notion of sequential instructions

Ada Lovelace

Created the first algorithm intended to be carried out by such a machine

Analogue

Continuously varying value, as in analogue signal

Digital

Varies in discrete steps

What is a computer?

A device that can be instructed to carry out arbitrary sequences of arithmetic or logical operations automatically

Z3 (Zuse)

First working electromechanical programmable, fully automatic digital computer.

Z3 was Turing complete

Colossus

The first programmable, electronic, digital computer.

Not Turing complete

Functions

Is a correspondence between a collection of possible input values and a collection of possible output values so that each possible input is assigned a single output

Turing machine

-Theoretical model of computer hardware

-Exists only as a description 'on paper'

-Given any computer algorithm, a TM machine can be designed to simulate that algorithm

Computing a function

Determining the output value associated with a given set of input values

Components of a Turing machine

-Infinite tape

-Read-write head

-A State register

-A finite table of instructions

What can Turing machines calculate?

-Computable numbers

-Computable Functions

What can't a Turing machine do

-Halting problem

Halting problem

A function that returns true if it halts

Automata theory

-Deals with the logic of computation with respect to simple machines, f

Automatons

are abstract models of machines that perform computations on an input by moving through a series of states or configurations

Characteristics of Automated machines

-Inputs

-Outputs

-States

Types of Automated machines

-Turing machine

-Finite state machines

State Transition Diagram

A diagram that indicates the possible states of automaton and the allowable transitions between such states.

-circles(nodes) represent a state

-arrows represent state transitions

-each arrow also represents one instruction

Universal Turing Machine(UTM)

A Turing machine which can stimulate an arbitrary input

reads from its own tape

-The definition of the TM being simulated

Finite state machines

-They are the simplest model of computation

-Small computer or controller

-They have a start state

-They can be used to accept or generate strings

State machine for Turing

-It is a finite state machine

-it has an initial state

-Final states where we stop computation

-The machine may enter into a loop where we do not stop

-It is a deterministic machine: every state has one transition we can take

Compilers

-Program source code compiled to machine code all at one time before program executes

-Fast = Especially because loops are compiled once

-Compiled for specific machines (Have to make compilation for each platform)

-Machine code is sold(Don't give away source code)

Interpreter

-Program source code translated to machine code line by line as program executes

-Slow = Especially because loops have to be translated many times

-The source code is what is sold

AUB

Union

A n B

Intersection of A and B

Cardinality

The size of a set, number of elements (members in a set)

A'

Not A

|A|

cardinality of A

Set

Is a collection of definite

Alphabet

A finite set of fundamental units

Language

A set of strings of symbols from the alphabet, plus rules specific to the language

Words

Those (finite) strings that are permissible in the language

Two kinds of rule sets

-Test valid words

-Generate all the words in the language

Concatenation

Join together

Reversing strings

Same string of letters in reverse order. Just because you reverse a word, doesn't mean it will be in your language.

Palindromes

Same word forwards and backwards

Closure * Kleene star

Make all combinations possible out of given characters.

Search and find

-Given a regular expression

-Search through a set of strings

-Find all of the matching instances

-Report what has been found, optionally with their location

Regular grammars

A regular grammar is left or right regular grammar, and defines a regular languages.

Left grammar

In a left regular grammar is a format grammar

B ::= a

B ::= Ca

B ::= E

Right grammar

Is a formal grammar such that all the production rules in P are one of the following forms:

B ::= a

B ::= aC

B ::= E

Backus-Naur form

Proposed a meta language to describe the syntax of the new high-level programming language. terminals are in <> and ::= is an arrow

::=

Grammars

are defined by (N, E, P, s)

-N = Set of non-terminals (rule names)

-E = Set Of terminals (input character)

-N and E are disjoint (have no members in common)

-P is a set production rules

-S is a starting non-terminal, and is a member of N

Logic

Is the science of valid reasoning.

Reasoning

about situations means constructing argument about them, so that the arguments are valid whether certain conclusion follow from some given assumptions.

Application

-Deductive systems

-Expert systems

-Correctness of programs

Proposition logic

-Concerned with propositions

-A proposition is an atomic sentence that can be either true or false, but not both or neither

Representing propositions

To represent propositions, propositional variables are used e.g p,q,r,t

Logical connectives

Used to combine simple if it cannot be broken up into sub-propositions

logical expression trees

To capture ordering of statements we can use logical expression

Truth table

Can help us to express complicated proposition and also to combine them.

Tautology

a statement that is always true

Contradiction

Invalid truth table.

Argument

A sequence of statements (known as premises) ending in a conclusion.

Validity of arguments

-To test the validity of an argument we use truth tables.

- Argument = valid if all conclusions are true.

Fallacy

An error in reasoning that results in an invalid argument.

Converse error

p ->q p therefore p

Inverse error

p ->q 'p therefore 'q

Hypothetical syllogism

if p -> q

q ->r

------------

p ->r

Modustollens (method of denying)

if p -> q

'q

---------

'p

Predicate logic

To overcome two limitations that we have in proposition logic.

Predicates describe either a property of a thing or a relationship between things.

Predicate

-Is a statement that contains variables.

-It becomes a proposition when the individual variables are bound to specific values, resulting to either true or false.

Combining predications

Since predications evaluate to truth values they maybe combined together using the logical connectives that were introduced in the propositional logic lecture.

Predicate calculus

The result of combining predicates and logical connectives.

Universes

Our logic deals with classes of things. They are referred to as the universe of discourse or universe or the domain of discourse.

Quantifiers

-Existential

-Universal

Existential quantifier

There exists, meaning at least one member of the universe.

Universal quantifier

For all (∀) meaning all members of the universe.

Universal conditional statements (UCS)

Using quantifiers

∀

Inverse

If not p, then not q

Converse

If q, then p

Contrapositive

If not q, then not p

logically equivalent

is a universal conditional statement logically equivalent to its: inverse; converse; Contrapositive.

Computational modelling

Use of computers to stimulate and study the behaviour of complex systems using mathematics, physics and computer science.

Black box model

accurate, but no explaination

Glass box model

Less accurate, but explanation.

Petrinets

-Model of parallel & distributed systems

-Basic idea is to describe state changes in a system with transitions.

Types of petrinets

-Qualitative

-Quantitative

Bipartite graph

2 sets of nodes and 2 sets of arcs

Nodes

places(circles) and transitions (squares)

arcs

(arrows) from places to transitions, or from transitions to places.

-Arcs in both directions are permitted

-Arc weights by default are 1 but other values can be associated.

Discrete models

Where individuals are modelled using tokens

Continuous

results in smoothed behaviour

Stochastic

'Jumpy' curves based on random firing of transitions

Arithmetic progression

There is a constant difference between any two successive members of the sequence.

Geometric progression

Where there is a constant multiplier r to generate a new term. (common ratio)

Static linear data structures Advantages

Easy to create, easy to access items

Static linear data structures Disadvantages

Fixed size

-Need to set aside max space in memory that could be needed

-Can't extend/reduce size during computation

Dynamic data structure (list) Advantages

-Can increase/decrease size

-Can reclaim space

Dynamic data structure (list) Disadvantages

More complex and time consuming

Stacks

Special list where you can only insert and delete from one end. Items are added on a last-in-last-out basis.

Push (add)

Pop (remove & return)

Reverse Polish notation (RPN)

-Does not need any parenthesis as long as each operator has a fixed number of operands

RPN advantages

- Gets rid of need for brackets in expressions

- Speed advantages

- Faster than algebraic notation

- May be due to smaller number of key strokes

RPN Disadvantages

more difficult to learn

Queues

- First in, first out

- Items are inserted at one end (rear)

Enqueue

Insertion

Dequeue

Delete