English |
ADT / ADS / DT / DS |
Svenska |
ADT |
Abstract Data Type: an ADS + a set of operations |
ADT |
ADS |
Abstract Data Structure: an abstract set, sequence, tree, graph |
ADS |
DT |
Data Type: a DS + a set of operations |
DT |
DS |
Data Structure: a programming language / user defined data structure
where the user defined data structures are
usually based on arrays and/or structures+pointers |
DS |
English |
General Terminology |
Svenska |
Recursion |
An entity partially defined in terms of itself |
rekursion |
Ordered |
A collection where the elements are accessible using position |
ordnad |
Sorted |
An ordered collection where the elements are arranged by value
according to some sorting relation e.g. > or < |
sorterad |
English |
Modelling |
Svenska |
Computer Model |
computer representation of some abstraction of a real life situation
- in this course ADTs
|
datamodell |
Entity |
A representation of an "object", abstracted from reality,
usually as a number of attributes
|
entitet |
Attribute |
A property of an entity
e.g. height, weight, address, personal number
|
attribut |
Relationship |
A property connecting 2 entities
e.g. distance, communication link, parent/child
|
relation |
Collection |
A number of entities having a common property |
samling |
English |
Graphs |
Svenska |
Graph |
In mathematics G = (V, E) where V is a collection (set) of nodes
and E a collection (set) of edges;
each edge connects two nodes (u, v) in V - in DS&A, used to represent an ADT
|
graf |
Node |
A representation of an entity
(additional properties: In-degree, Out-degree)
|
nod / hörn |
Edge |
A representation of a relationship between 2 entities |
kant / båg |
Subgraph |
A subgraph of a graph, G = (V, E) is a graph Gs = (Vs, Es) where Vs
is a subset of V and Es a subset of E such that the nodes describing
the edges in Es are members of Vs.
|
delgraf |
Induced Subgraph |
An induced subgraph of a graph, G = (V, E) is a graph Gs = (Vs, Es) where Vs
is a subset of V and Es a subset of E such that the edges (in G) connecting
the nodes in Vs are members of Es.
|
inducerad delgraf |
Directed Graph (Digraph) |
A graph where the relationships between nodes are unidirectional
e.g. parent => child
|
riktad graf (digraf) |
Undirected Graph |
A graph where the relationships between nodes are bidirectional
(represented by 2 directed edges)
e.g. distance between two points
|
oriktad graf |
Weighted Graph |
A graph where the edges have an associated value (weight)
|
viktad graf |
Dense graph |
Omega(|V|*|V|) edges - implementation is usually an adjacency matrix |
tät graf |
Sparse graph |
Omega(|V|) edges - implementation is usually an adjacency list |
gles graf |
Degree |
The number of edges arriving at and leaving from a node |
graden |
In-degree |
The number of directed edges arriving at a node |
ingraden |
Out-degree |
The number of directed edges leaving a node |
utgraden |
Path |
A sequence of vertices, V1, ... Vn, such that (V1,V2), ... (Vn-1, Vn) are edges |
väg / stig |
Path Length |
The number of edges in a path |
längd |
Simple Path |
A path where all vertices are distinct
(except possibly the first and the last) |
enkel väg / stig |
Cycle |
A path that begins and ends at the same vertex |
cykel |
Simple Cycle |
A simple path of length >= 1 that begins and ends at the same vertex |
enkel cykel |
Acyclic |
A graph with no cycles |
acyklisk |
Connected |
if there exists a path from every vertex to every other vertex |
sammanhängande |
Articulation Point |
If a node breaks the graph into more than one component
when removed then it is called an articulation point except if it is the root.
If the root has more than one child then it is an articulation point. |
skäringspunkt artikuleringspunkt |
Biconnected |
In a graph, in a selected component,
if you can go from one of the nodes to all other nodes
by an alternative path then the component is called biconnected component. |
bisammanhängande |
Strongly Connected |
A connected directed graph where exists a path from
every vertex to every other vertex |
starkt sammanhängande |
Weakly Connected |
A connected directed graph where the underlying graph
without distinction to the direction is connected |
svagt sammanhängande |
Complete |
If there is an edge between every pair of vertices |
fullständig |
Spanning Tree |
See MST algorithms (e.g. Prim, Kruskal) |
uppspänningsträd |
Free Tree |
An undirected graph with n nodes and n-1 edges.
Adding another edge will result in a cycle |
friträd |
English |
Graph Algorithms |
Svenska |
Depth First Search |
O(|V| + |E|) |
djupetförssökning |
Breadth First Search |
O(|V| + |E|) |
breddenförssökning |
Transitive Closure |
Warshall's algorithm: O(n*n*n) |
transitiva höljet |
English |
Graph Representations |
Svenska |
Adjacency Matrix |
Usually used for dense graphs |
grannmatris |
Adjacency List |
Usually used for sparse graphs |
grannlista |
English |
Set |
Svenska |
Set |
A (directed) graph, G = (V, E), where E is empty.
For each node (max) In-degree = 0 and (max) Out-degree = 0
I.e. a collection of nodes
where no relationships exist between nodes but where each node has
a common attribute (property).
e.g. the collection of all third year students
|
mängd (set) |
English |
Sequence |
Svenska |
Sequence |
A (directed) graph, G = (V, E)
For each node (max) In-degree = 1 and (max) Out-degree = 1
I.e. a collection of nodes where the relationship is successor.
or
An undirected graph, G = (V, E)
For each node (max) In-degree = 1 and (max) Out-degree = 1
I.e. a collection of nodes where the relationship is successor/predecessor.
|
sekvens |
Successor |
|
efterföljare |
Predecessor |
|
föregångare |
English |
(directed) Tree |
Svenska |
(directed) Tree |
A (directed) graph, G = (V, E)
For each node (max) In-degree = 1 and (max) Out-degree = n
A binary tree is a tree where (max) Out-degree = 2
I.e. a collection of nodes where the relationship is hierarchical.
|
(riktat) träd |
Note that the GRAPH is the general case where
(max) In-degree = n and (max) Out-degree = m
|
English |
Semantics |
Svenska |
Semantics |
The meaning of a given system or model.
Note that one difficulty of modelling is in matching
the semantics of the system being modelled and
the semantics of the model.
In this course we have Reality => ADT => Implementation
so that the question of the semantics of the implementation
language also arises.
|
semantik |
English |
Implementation |
Svenska |
primitive function |
A back-end function which operates directly on the implementation
structure (DS), or uses implementation defined constants and/or operations directly |
primitiv funktion |
basic function |
A back-end function written using primitive functions
(does not use the implementation structure (DS), constants or
operations directly) |
bas funktion |
abstract function |
A front-end function which is written (composed?)
only using primitive and/or basic functions |
abstrakt funktion |