Flashcards
What is Computer Software?
Cards in this deck (24)
- 1Briefly (and not too precisely) explain the difference between an algorithm and a program. Suppose we have an algorithm and wish to implement it in python. How many different implementations are there of this algorithm?Algorithms work on some input and produce an output according to precisely defined steps, and can work on some general range of inputs. A program is similar but is a way of translating an algorithm into something usable by a computer.
There may be many different implementations of an algorithm in any one language. - 2Give 4 different programming paradigms and briely explain the underlying principle for each paradigm.Imperative: statements change a program's (or computer's) state.
Declarative: programs say what we want rather than how we can get it
Assembly: Low-level programs that provide the interface between machine code and a high level programming language
Concurrent: provide facilities for doing tasks in parallel (threads, processes). May work by message sharing or using shared memory, or timesharing if only one processor. - 3Give 4 different drivers of the evolution of programming languages and briefly explain each of these driving motivations.Productivity - languages that speed up the software development process, reduce response times and costs
Reliability - language has features so that programs are more reliable eg type checking.
Security - ensuring that the language does not allow malicious code to be executed on your computer eg through the internet by restricting what activity it can undertake.
Execution speed - getting the results as quickly as possible - 4Give 3 general properties any programming language should haveBe easy to use (with programs easy to read, write and understand)
Support abstraction so new concepts and features can be added
Support testing, debugging and program verification - 5Explain very briefly how a Prolog program computes.Prolog programs have two parts: the program (or the database - the facts you know and the rules you can use to deduce new facts), and the query (the question you want answering, given what you know and what you can deduce).
- 6What is the fundamental principle of the research area known as ubiquitious programming?/Integration of computing and software into everyday items, so we can have control over remote aspects of our lives.
- 7What are the syntax and semantics of a programming language? Give 2 reasons why we should strive for a formal semantics for a programming language.Syntax: the rules that govern what makes a program "legitimately written".
Semantics: the rules that provide meaning to those statements.
1. So you can be absolutely (mathematically) sure that a program does what it says it will do
2. So there is no ambiguitiy which leads to errors, thus making writing programs take more time. - 8In order to execute a high-level program, we must first convert it into machine code so that the CPU can "understand" is. Briefly explain the difference between compilation and interpretation. How are Java programs executed?Compilers transform the high-levl code to machine code for the CPU to read before the program is run. The compiler is CPU-specific.
Interpreters translate one instruction at a time, as needed, into machine code, interspersing translations with program execution.
Java is compiled into bytecode, then interpreted into machine code by a Java virtual machine - so a CPU specific compiler is not neede. - 9Give an advantage of compilation over interpretation, and the other way around.Compiled programs run faster and are checked for bugs. Optimised, interpreted programs use memory better and allow for faster development.
- 10Outline a refined view of the phases of compilationA lexical analyzer reads a high level program as a string of symbols and converts it into basic syntactic components - ie tokens in a token stream.
A syntax analyser recognises the syntactic structure of the token stream and creates a parse tree.
The tree is them simplified and used to undertake various analysis operations, eg type checking.
The translation phase then flattens the parse tree into a linear sequence of intermediate code.
The final stage is code generation, wereby the intermediate code is translated to assembly and then machine code. - 11In compilation, over 50% of the time taken can be spent on lexical analysis - that is, character handling. In moving from a program as a string of symbols to a token stream, which algebraic construction is usually used to define tokens?Tokens are almost always defined using regular expressions.
- 12Define carefully what a regular expression is.
- 13Explain how a regular expression is used to denote a set of strings.To talk about regular expressions, you have to define an alphabet. See above.
So we can build up a vast collection of regexs by repeatedly applying the above constructions. Every regular expression denotes a set of strings over sigma.
a, ∅ and ε denote the sets of strings {a},{} (empty set of strings), and {ε} (the set containing just the empty string ε, respectively.
If w and w' represent the sets of strings R and S, then:
(ww') denotes {xy : x ∈ R, y ∈ S}
(w|w') denotes R U S
w* denotes {x1,x2,...xn : n >=0, i ∈ (1,...,n), xi ∈ R} - 14Give a regular expression that denotes the set of stirinigs over the alphabet {a,b,c} consisting of strings with the property that there is always at most one c.((a|b)*|c)(a|b)*
- 15Give a regular expression that denotes the set of strings over the alphabet {a,b} consisting of strings with the property that any a must always be followed by bb.(b|abb)*
- 16Definte carefully a finite state machine and explain how one is used to accept a set of strings.A FSM is defined as:
M = (Σ, Q, δ : Q × Σ → Q, q0 ∈ Q, F)
where:
Σ is some finite alphabet;
Q is some finite set of states with initial state q0 and set of final states F ⊆ Q;
δ : Q × Σ → Q is the transition function.
On input any string a1a2...an over the alphabet, M yields a sequence of states q0,q1,q2...qn via:
q1 = δ(q0,a1), q2 = δ(q1,a2), q3=δ(q2,a3)... etc
Our input string is accepted by our FSM M if the resulting sequence of states q0,q1,q2...qn ends in a final state, that is, is such that qn is a member of F. - 17Give a finite state machine that accepts the set of strings over the alphabet {a,b,c} consisting of strings with the property that there is always at most one c.Can terminate on double circles.
- 18Give a finite state machine that accepts the set of strings over the alphabet {a,b} consisting of strings with the property t hat any a must always be followed by bb.
- 19What is the relationship between regular expressions and finite state machines?A set of strings is represented by a regular expression iff it is accepted by a finite state machine.
- 20Define carefully a context-free grammar and explain how one is used to generate a set of strings.A context-free grammar is a four-tuple (N,T,s,R) where:
T and N are disjoint, finite sets of Terminal and Non-terminal symbols respectively
S ∈ N is a distinguishable start symbol
R is a finite set of rules:
R ⊆ (NUT)+ x (NUT)*
Productions are of the form X -> Y1Y2...Yn. X has to be a non-terminal, Y can be a terminal or a non-terminal, n has to be non negative. - 21Which restriction on a context-free grammar makes it a regular grammar, and how are regular grammars, regular expressions, and FSMs related?A regular expression or FSM can always be written in a context-free grammar, but not all context free grammars can be expressed by a regex or FSM. A regular grammar can always be written as a regular expression or a FSM.
- 22Define a regular grammar that generates the set of strings over the alphabet {a,b,c} consisting of strings with the property that there is always at most one c.N = {s,t} T = {a,b,c},s,R with R consisting of the productions
s-> ε|as|bs|ct
t->at|bt|ε - 23Define a regular grammar that generates the set of strings over the alphabet {a,b} constisting of strings with the property that any a must always be followed by bb.N = {s,t,u} T = {a,b},S,R with R consisting of the productions:
S -> bS|aT|ε
T -> bU
U -> bS - 24Which algebraic notation is normally used to specify the syntax of a programming language?Backus Naur form.
Information
- Description
- Flashcards on What is Computer Software?, created by SEZ McKelvey on 26/03/2018.
- Created by
- SEZ McKelvey
- Views
- 2
- Rating