Đồ án, luận văn, do an, luan van

State Space Search
Define problem in form of a state space and use a search algorithm to find a solution
The problem space consists of:
a state space which is a set of states representing the possible configurations of the world
a set of operators which can change one state into another
The problem space can be viewed as a graph ...

8 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 743 | Lượt tải: 0

Data Compression
Data in memory have used fixed length for representation
For data transfer (in particular), this method is inefficient.
For speed and storage efficiencies, data symbols should use the minimum number of bits possible for representation.
Methods Used For Compression:
Encode high probability symbols with fewer bits ...

22 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 771 | Lượt tải: 0

Weighted Graph
We can add attributes to edges. We call the attributes weights.
For example if we are using the graph as a map where the vertices are the cites and the edges are highways between the cities.
Then if we want the shortest travel distance between cities an appropriate weight would be the road mileage.
If we are concerne...

7 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 790 | Lượt tải: 0

Connected graph
A graph is connected if and only if there exists a path between every pair of distinct vertices
Sub-graph
A graph with the vertex and edge set being subsets of the original graph
Connected Components
A connected component of a graph is a maximally connected subgraph of a graph
Cycle
A path in a graph that s...

12 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 848 | Lượt tải: 0

Depth-First Search 1. From the given vertex, visit one of its adjacent vertices and leave others; 2. Then visit one of the adjacent vertices of the previous vertex; 3. Continue the process, visit the graph as deep as possible until:
A visited vertex is reached;
An end vertex is reached Depth-First Traversal 1. Depth-first traversal of...

8 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 751 | Lượt tải: 0

We need also algorithm to traverse a graph like for a tree
Graph traversal may start at an arbitrary vertex. (Tree traversal generally starts at root vertex)
Two difficulties in graph traversal, but not in tree traversal: - The graph may contain cycles; - The graph may not be connected.
There are two important traversal methods: - Br...

6 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 727 | Lượt tải: 0

Undirected graphs
A graph G=(V, E) where V is a set of vertices connected pairwise by edges E.
Why study graph algorithms?
Interesting and broadly useful abstraction.
Challenging branch of computer science and discrete math.
Hundreds of graph algorithms known.
Thousands of practical applications.
Communication, circuits, tran...

11 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 802 | Lượt tải: 0

A B-Tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties :
Every node has <= m children.
Every node ( except root and leaves ) has >= m/2 children.
The root has at least 2 children.
All leaves appear in the same level
A non-leaf node with k children contains k – 1 keys

8 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 789 | Lượt tải: 0

Symbol table: key-value pair abstraction.
Insert a value with specified key.
Search for value given key.
Delete value with given key.
Different implementations
Array
Linked list
BST (binary search tree)

10 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 841 | Lượt tải: 0

Generic functions
In a generic function, data should be passed in a generic way (by address and size).
If the algorithm demands a specific function to manipulate data (e.g.., compare two values), such a function should be passed using a function pointer.
Example: A generic search function on an array.
How to pass data to this funct...

11 trang | Chia sẻ: candy98 | Ngày: 28/11/2020 | Lượt xem: 717 | Lượt tải: 0