University of London / MSc Computer Science: Fundamentals of computing（前半）

University of London / MSc Computer Science: Fundamentals of computing（前半）

February 15, 2025

ロンドン大学で MSc Computer Science: Fundamentals of computing モジュールを履修中。

講義内容に関して記録した個人的なスタディノートです。

全 12 週のうち 1〜5 週目の内容を記録します。（1 週目開始：2025 年 1 月 6 日 / 5 週目終了：2024 年 2 月 9 日）

モジュール概要 #

Aims

The aims of this module are to:

  • introduce the notation, terminology, concepts and techniques underpinning the discipline of computer science
  • promote the importance of formal notations as the necessary means of ensuring clarity, precision, and absence of ambiguity
  • provide an introduction to the concepts and manipulation of the basic finite structures as these arise in computer science, e.g. computer arithmetic, strings, - graphs, sets, digital circuits, lists, binary trees
  • introduce basic models of computation, such as finite automata and Turing machines
  • give students an understanding of the fundamentals of data structures and file organisation: their representation, algorithms for their operation, and the - relative merits of different structures and methods
  • introduce the design and analysis of algorithms, and their efficiency/complexity.

Weeks

講義は Week 10 まで。Week 11, 12 は最終課題を作成する期間。

  • Week 1: Numbers
  • Week 2: Arithmetic for computers
  • Week 3: Digital logic
  • Week 4: Sets and relations
  • Week 5: Graph theory
  • Week 6: Finite state machines
  • Week 7: Data structures: representations and operations
  • Week 8: Lists, trees, forests, binary trees
  • Week 9: Tree traversal and other operations; binary search trees
  • Week 10: Sorting and searching

参考文書 #

Essential reading

  • Blinder, S.M. Guide to essential math. (London: Elsevier, 2013) 2nd edition.
  • Null, L. and J. Lobur. Essentials of computer organization and architecture. (Burlington, MA: Jones & Bartlett Publishers, 2014) 5th edition.
  • Patterson, D. and J. Hennessy Computer organization and design: the hardware/software interface. (Burlington, MA: Morgan Kaufmann, 2008) 4th edition.
  • Ledin, J. Modern computer architecture and organization. (Birmingham: Packt Publishing, 2020).
  • Hua, D., A. Weiland and S. Drummond ‘Bits, bytes, and binary: the mathematics of computers’, Tech Directions 73(7) 2014, pp.18-23.
  • Koshy, T. Discrete mathematics with applications. (Burlington, MA: Elsevier, 2003).
  • Trefil, J. (ed) Discoveries in modern science: exploration, invention, technology (Vol. 3). (Cengage Learning, 2015).
  • Goodrich, M.T., R. Tamassia and M.H. Goldwasser. Data structures and algorithms in Python. (Hoboken, NJ: John Wiley & Sons Inc, 2013).

Further reading

  • Tarnoff, D. Computer organization and design fundamentals. (Lulu.com, 2006).

Week 1: Numbers #

キーコンセプト

This topic includes:

  • history of computing
  • computer architectures
  • number types
  • numeral systems
  • base conversion.

レクチャーリスト

  • Introduction to Fundamentals of Computing
    • Lecture 1: Introduction
  • History of computers: a very brief overview
    • Lecture 2: History of computers: a very brief overview – part 1
    • Lecture 3: History of computers: a very brief overview – part 2
  • Numeral systems
    • Lecture 4: Numbers and numeral systems
    • Lecture 5: Converting between bases

Lecture 1: Introduction #

詳細は省略。モジュール全体で学ぶ内容についての概要説明。

Lecture 2: History of computers: a very brief overview – part 1 #

A computer can control storage, processing and movement of data

  • store data
  • process data
  • move data

Ato the most basic level, a computer is a device consisting of:

  • a processor (CPU, or Central Processing Unit) to interpret and execute programs
  • a memory to store data and programs
  • a mechanism for transferring data to and from the outside world

Lecture 3: History of computers: a very brief overview – part 2 #

内容省略。

Lecture 4: Numbers and numeral systems #

内容省略。主には２進数、１０進数、１６進数についての説明。

Lecture 5: Converting between bases #

内容省略。主には２進数、１０進数、１６進数の変換手順についての説明。

Further material #

Week 2: Arithmetic for computers #

キーコンセプト

This topic includes:

  • binary arithmetic
  • signed representations
  • arithmetic logic unit
  • representation errors.

レクチャーリスト

  • Binary arithmetic
    • Lecture 1: Adding, subtracting and multiplying binary numbers
  • Signed arithmetic and floating-point representation
    • Lecture 2: Signed representations
    • Lecture 3: Floating point representations and precision
  • The Arithmetic Logic Unit (ALU)
    • Lecture 4: Overview of the ALU and example of Boolean circuit (adder)

Lecture 1: Adding, subtracting and multiplying binary numbers #

内容省略。２進数での四則演算について。

Lecture 2: Signed representations #

Suppose we are using 32-bit words

  • Reserve the most significant bit to represent the sign
  • Use the rest of the word to represent the number itself (that is, the magnitude)

Sign-magnitude representation

  • Treat the most significant (left-most) bit in the word as a sign: if it is 0, the number is positive; if the left-most bit is 1, the number is negative; the right-most 31 bits contain the magnitude of the integer
+18(10) = 0000 0000 0000 0000 0000 0000 0001 0010(2)
-18(10) = 1000 0000 0000 0000 0000 0000 0001 0010(2)

But this representation is not commonly used in computers.

Problems:

  • There are two representations of zero.
  • Adding +x and -x doesn’t give zero

One’s complement representation

  • The complement of a number is a way of changing the representation of a number in a given base in order to represent negative numbers or to perform usbtraction more easily
  • We use the radix or radix-minus-one complement
  • For deccimal numbers, that is the 10’s or 9’s complement
# The 9's complement of a decimal number is obtained by subtracting each digit from9:

Decimal:         4308
9's complement:  5691
10's complement: 5692

# We can subtract by adding the complement
6142 - 4816 = 1326

Decimal:        4816
9's complement: 5183

Decimal:        6142
9's complement: 5183
9's complement: 11325 -> 1 1325 -> 1325 + (1) = 1326

# We can subtract by adding the complement.

# 1's complement of a binary number: subtract each digit from 1 (which means, invert the bits)

+18(10) = 0000 0000 0000 0000 0000 0000 0001 0010(2)
-18(10) = 1111 1111 1111 1111 1111 1111 1110 1101(2)

# 2's complement of a binary number: subtract each digit from 1, and then add 1:

+18(10) = 0000 0000 0000 0000 0000 0000 0001 0010(2)
-18(10) = 1111 1111 1111 1111 1111 1111 1110 1101(2)

Lecture 3: Floating point representations and precision #

IEEE 754 floating-point standard

Every real number dirrerent from 0 can be represented in the form: (-1)s x (1+F) x 2E, 0 <= F < 1

  • S is the sign
  • F is the fraction (0 <= F < 1)
  • E is the exponent (determining the location of the binary point)
Single precision floating-point format: 8 bits for E and 23 bits for F

- S: 1 bit
- E: 8 bits
- F: 23 bits

Double precision floating-point format: 11 bits for E and 52 bits for F

- S: 1 bit
- E: 11 bits
- F: 52 bits

Overview of the ALU and example of Boolean circuit #

Alithmetic logic unit (ALU)

  • The ALU is the part of the computer that performs arithmetic and logical operations
  • It is the workhouse of the central processing unit (CPU), because it carries out all calculations
  • The hardware required to build an ALU is the basic gates AND, OR and NOT

Inputs and outputs of a single-bit adder

  • Two input for operands (the bits we want to add e.g. A and B)
  • A single-bit output for the Sum
  • A second output to pass on the carry - CarryOut
  • A third input is CarryIn - the CarryOut from the previous adder

Further material #

Week 3: Digital logic #

キーコンセプト

This topic includes:

  • Boolean logic
  • truth tables
  • Boolean functions
  • equivalence classes
  • digital circuits.

レクチャーリスト

  • Introduction to logic
    • Lecture 1: Digital logi
  • Boolean logic in computers
    • Lecture 2: Boolean circuits for computer
  • Equivalences and universal functions
    • Lecture 3: Boolean equivalence

Lecture 1: Introduction to logic #

  • George Boole (1815-1864) invented Boolean logic, an algebra of two values.
  • Forms the basis for all modern computer arithmetic

Lecture 2: Boolean circuits for computers #

（内容省略。AND, OR, NOT, XOR の回路について。）

Lecture 3: Boolean equivalence #

Universal sets of Boolean functions

  • Any Boolean function can be represented in disjunctive normal form using the connectives ¬, ^, v
  • We sa that {¬, ^, v} is a universal set of Boolean connectives, also known as functionally compete set
  • NAND alone forms a universal set

Useful equivalences (x and y are arbitrary Boolean formulas)

  • The law of double negation:
    • ¬¬x = x
  • The law of the excluded middle:
    • ¬x v x = 1
  • The law of contradiction:
    • ¬x ^ x = 0
  • Distributive law:
    • x ^ (y v z) = (x ^ y) v (x ^ z)
    • x v (y ^ z) = (x v y) ^ (x v z)
  • De Morgan’s lows:
    • ¬(x ^ y) = ¬x v ¬y
    • ¬(x v y) = ¬x ^ ¬y

Further material #

Week 4: Sets and relations #

キーコンセプト

This topic includes:

  • sets
  • set operations.

レクチャーリスト

  • Sets: definitions and notation
    • Lecture 1: Basic set theory
  • Set operations
    • Lecture 2: Set operations
  • Relations and functions
    • Lecture 3: Relations and functions

Lecture 1: Basic set theory #

Notation

A = {Monday, Tuesday, Wednesday}
A = {a, e, i, o, u}
A = {2, 4, 6, 8}

A = {x | x is an even positive number}
A = {x : x is an even positive number}

Some specific sets representation

φ = {} empty set, the set with no elements
N = {0, 1, 2, 3, ...} natural numbers
N+ = {1, 2, 3, ...} positive natural numbers
Z = {0, 1, -1, 2, -2, 3, ...} integer numbers
R = {decimals} real numbers
  • All elements of a aset are distinct. That is no element may occur more than once in a set
  • We do not distinguish between {3, 2, 4} and {2, 3, 4}
  • Principle of Extension: two sets A and B are equal if and only if they have the same members

Lecture 2: Set operations #

Subsets

  • Set B is a subset of set A if every element of B is an element of A
  • Two sets A and B are equal if they have exactly the same elements

Union

  • The set of all elements which belong to A or to B
  • A = {1, 2, 3} B = {2, 4, 6} then Union = {1, 2, 3, 4, 6}

Intersection

  • The set of all elements which belong to A and to B
  • A = {1, 2, 3} B = {2, 4, 6} then Intersection = {2}

Complement

  • U = {1, 2, 3, 4, 5, 6} A = {1, 2, 3} B = {2, 4, 6} then
    • Complement of A = {4, 5, 6}
    • Complement of B = {1, 3, 5}

Lecture 3: Relations and functions #

（内容省略）

Further material #

Week 5: Graph theory #

キーコンセプト

This topic includes:

  • graphs
  • types of graphs
  • adjacency matrixes
  • paths
  • cycles
  • subgraphs
  • components
  • connectedness
  • trees
  • graph isomorphism.

レクチャーリスト

  • Introduction to graph theory
    • Lecture 1: Introduction to graph theory
  • Graph – adjacency matrices, paths, cycles
    • Lecture 2: Adjacency matrices and types of graphs
  • Subgraphs, components, connectedness, trees, graph isomorphism
    • Lecture 3: Graph algorithms

Lecture 1: Introduction to graph theory #

  • Graphs are drawings with dots and lines (not necessarily straight) or arrows
  • The dots are called “vertices” (or “nodes”, or “points”)
  • The lines, or arrows, are called “edges”

Undirected graphs - basic terminology

  • If there is an edge e between vertices u and v, we say that:
    • u and v are adjacent, and
    • e is incident with u and v.
  • The degree of a vertex is the number of edges incident with it:
    • a vertex of degree zero is called isolated
    • so, an isolated vertex is not adjacent ot any vertex.
  • The sum of the degrees of the vertices of a graph is equal to twice the number of edges
  • (Sometimes called the “handshaking theorem”)

Directed graphs - basic terminology

  • If there is an edge e going from vertex u to vertex v, we say that:
    • u is adjacent to v
    • u is the initial or start vertex of e, and
    • v is the terminal or end vertex of e.
  • The in-degree of a vetex v is the number of edges with v as their terminal vertex
  • The out-degree of a vertex v is the number of edges with v as their initial vertex. (A loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex)
  • Number of edges = sum of the in-degree of vertices = sum of the out-degree of vertices

Lecture 2: Adjacency matrices and types of graphs #

Representing graphs

  • How do we represent graphs in a computer?
  • Edge list: list the edges
    • [(6,4), (4,5), (4,3), (3,2), (5,2), (5,1), (1,2)]
  • Adjacency matrix: record the edges in a matrix
    • It is common to represent a graph using a matrix
    • An array is an collection (e.g. a set) whose elements are indexed by one or more subscripts
    • A vector is a list of numbers (a one-dimensional array)
    • A matrix is a rectangular array of numbers, with row vectors and column vectors

Lecture 3: Graph algorithms #

（内容省略）