Artificial Intelligence (AI) (Cambridge (CIE) A Level Computer Science): Flashcards

For dense graphs and fast lookup.

For sparse graphs. It is often used in AI search.

That the graph is undirected.

False.

A symmetric matrix confirms the graph is undirected. A non-symmetric matrix reflects the one-way nature of a directed graph.

A 1 indicates a connection exists between two nodes. A 0 means there is no direct connection.

Infinity.

In a weighted adjacency matrix, no connection between two nodes is shown as infinity.

Exploring environments with equal-cost connections, clustering in machine learning, and social network analysis where connections are mutual.

Depth-first and breadth-first search, and graph traversal algorithms that explore all reachable nodes.

Search algorithms such as A, BFS and DFS; expert systems and rule engines; planning and scheduling; and navigation* with one-way streets.

Pathfinding with A or Dijkstra, clustering and similarity graphs, recommendation engines, and robotics and navigation*.

A* and Dijkstra, route planning in robotics, search algorithms tracking transitions between states, reinforcement learning, and game AI with terrain costs.

They decide the best route or option when multiple paths are available.

Game boards, map-based navigation, and resource allocation networks.

An optimisation problem involves finding the most efficient solution to a problem: minimising cost, time or resource usage, or maximising output, efficiency or value.

Finding the shortest route between two locations, minimising resource usage, creating efficient timetables, and scheduling tasks and staff shifts.

An optimisation algorithm that calculates the shortest path from a starting node to all other nodes in a weighted graph.

False.

It calculates the shortest path from the start node to all other nodes in the graph.

Dijkstra's includes edge weights and ensures the lowest total cost to reach each destination node.

Nodes (vertices) and edges (arcs), where each edge has a weight.

Time, distance or cost.

The optimal path from the start node to every other node in the graph.

Set the start node's path weight to 0 and all other path weights to infinity.

At the start of Dijkstra's, all path weights except the start node are set to infinity.

Update all neighbouring nodes' path weights to the distance from that node plus the node's own path weight.

Choose the unvisited node with the lowest path weight.

Only if the old path weight is bigger than the new path weight, that is when the new path is shorter.

False.

It is updated only if the new path is shorter than the current path weight.

When all nodes have been visited.

By back tracking from the destination node.

previousNode as a dictionary, and visited and unvisited as lists.

It sets distance[node] to infinity for every node, then sets distance[start] to 0.

WHILE LENGTH(unvisited) > 0

It loops through unvisited and keeps the node with the smallest distance in min.

The algorithm exits the WHILE loop.

alt is set to distance[min] + cost. If alt < distance[neighbour], then distance[neighbour] is set to alt.

previousNode[neighbour] is set to min, so that the path can be rebuilt at the end.

After processing, min is removed from unvisited and added to visited.

Starting at the goal, follow previousNode back to the start, adding each node to path, then reverse the path.

A is a pathfinding algorithm that builds on Dijkstra's algorithm, introducing a heuristic function* to improve efficiency.

To find the shortest path from a starting node to a goal node in a graph.

Dijkstra's considers only the actual cost from the start node. A also estimates the remaining distance to the goal*.

It is more goal-oriented, which avoids inefficient detours.

A function that estimates the straight-line (Euclidean) distance from the current node to the goal.

f(x) = g(x) + h(x)

The actual cost from the start node to the current node.

The heuristic estimate to the goal node.

The total estimated cost of the cheapest solution through node x.

The node with the lowest f(x) value, so it explores paths that are both cheap and move closer to the goal.

It should never overestimate the true cost to the goal.

The heuristic should never overestimate the true cost to the goal.

This ensures A remains optimally efficient*.

The fewer nodes A* needs to explore.

That the algorithm is moving away from the goal, which helps it backtrack or choose a better path.

No. A is* goal-aware; Dijkstra's is not.

Dijkstra's uses g(x). A uses g(x) + h(x)*.

False.

Dijkstra's uses g(x) only. A uses g(x) + h(x)*.

A, because it moves more directly toward the goal. Dijkstra's is slower because it explores more*.

False.

Dijkstra's explores more. A* is more direct toward the goal.

When you need a full shortest path map to all nodes.

For the fastest route to a specific destination.

No. A uses one to estimate the distance to the goal*; Dijkstra's uses none.

g[node] and f[node], for every node in the graph.

g[start] is set to 0, and f[start] is set to h[start].

The list of nodes still to be considered. It begins containing only the start node.

It finds the node in openSet with the lowest f value.

tentativeG is set to g[min] + cost(min, neighbour). If tentativeG < g[neighbour], then g[neighbour] is updated to tentativeG.

In the A pseudocode, h[node] is your heuristic* table.

Machine learning is a type of AI that allows computers to learn patterns from data and improve performance without being explicitly programmed.

They analyse large amounts of data, identify patterns or trends, and make predictions or decisions based on that data.

Spam filters, voice assistants, recommendation systems and fraud detection.

An algorithm inspired by the structure of the human brain, made up of layers of nodes (neurons) connected by weighted links.

It receives input, processes it, and passes the result to the next layer.

It adjusts the weights based on errors in its output, using algorithms such as backpropagation.

They learn from experience even with complex or unstructured data, they improve accuracy with more data and training, and they can solve problems too complex for rule-based programming.

Deep learning is a subfield of machine learning that uses deep, multi-layered neural networks.

False.

Deep learning is a subfield of machine learning.

The more complex the patterns the network can learn.

Learning abstract features in images, text, audio and video.

A type of machine learning where an agent learns by interacting with an environment, receiving rewards for good actions and penalties for poor ones.

Reinforcement learning agents receive rewards for good actions and penalties for poor ones.

The optimal strategy an agent learns over time in order to maximise rewards.

Robotics, self-driving cars, game-playing AI and industrial automation.

Supervised learning is when the algorithm is trained on a labelled dataset, where the input data has known outputs.

To learn a function that maps inputs to the correct output, so the trained model can make predictions on unseen data.

Input is email text and output is spam or not spam. The model learns from thousands of pre-labelled emails.

Classification, such as face recognition or spam detection, and regression, such as predicting house prices.

Unsupervised learning is when the algorithm is given unlabelled data and must find patterns or groupings on its own.

False.

It uses unlabelled data. There are no correct answers, and the system explores the data structure itself.

Clusters, trends or anomalies, without any guidance.

Clustering, such as customer segmentation or social network analysis, and dimensionality reduction, such as simplifying complex data.

A training method used in artificial neural networks to improve accuracy by adjusting the weights of connections.

Back propagation is a key part of the supervised learning process.

Forward pass, error calculation, backward pass, and weight adjustment.

Input data passes through the network layer by layer, and the network produces an output, which is its prediction.

The difference between the network's output and the actual target value.

The error is propagated backwards through the network, and each layer calculates its contribution to the error.

Gradient descent.

Regression is a type of supervised learning used to predict continuous values rather than categories.

Linear regression, multiple linear regression and logistic regression.

Binary outcomes, such as yes or no, despite the name 'regression'.