Introduction to Computation and Python Programming

Comprehensive vocabulary flashcards covering the Introduction to Computation lecture series, including computer history, Von Neumann architecture, data representation, hardware components, Python programming fundamentals, control structures, and algorithm complexity.

Pascaline (Pascal's Calculator)

A mechanical calculating machine designed in 1642 by Blaise Pascal using interconnected clockwork gear mechanisms and styluses, capable of performing 6-digit addition and subtraction.

Leibniz Wheel (Stepped Reckoner)

A mechanical computing device developed in 1673 by Gottfried Wilhelm Leibniz that introduced stepped gear cylinders to perform all four basic arithmetic operations (addition, subtraction, multiplication, and division).

Difference Engine

A mechanical calculator designed by Charles Babbage in 1823 containing over 4,000 components; it calculated polynomial tables by reducing complex expressions to simple finite additions with precision up to 6 decimal places.

Analytical Engine

A steam-driven general-purpose computer design conceived in 1834 by Charles Babbage and programmed by Ada Lovelace, incorporating a memory store (1,000 numbers of 50 digits), a processing mill, punched card sequence controllers (0s and 1s), and data transfer mechanisms.

Turing Machine

A theoretical model of computation introduced by Alan Turing in 1937 consisting of an infinite tape, a read/write head, and a finite state controller that executes actions defined by quintuples $\langle q_i, s_j, s_k, D, q_m \rangle$.

Church-Turing Thesis

The hypothesis stating that any function that can be computed by an effective procedure or algorithm can be computed by a Turing machine.

Shannon's Switching Theory (1938)

A master's thesis by Claude Shannon at MIT proving that Boolean algebra's two-valued logic operations could be realized using electrical relay and switching circuits, establishing the digital basis for electronic computers.

Von Neumann Architecture

A computer system architecture described in 1945 for the EDVAC, characterized by binary representation, the stored-program principle, and five functional units: Controller, Arithmetic Logic Unit (ALU), Memory, Input devices, and Output devices.

Stored-Program Principle

The architectural concept where program instructions and data are stored together in the same addressable internal memory, allowing instructions to be fetched and executed automatically in sequence.

Byte

The fundamental unit of digital data storage consisting of 8 consecutive binary digits (bits), where $1\,\text{KB} = 1024\,\text{B} = 2^{10}\,\text{B}$, $1\,\text{MB} = 2^{20}\,\text{B}$, $1\,\text{GB} = 2^{30}\,\text{B}$, and $1\,\text{TB} = 2^{40}\,\text{B}$.

Two's Complement (补码)

A binary encoding method for signed integers used by computers where positive numbers match their true sign-magnitude form, and negative numbers are formed by inverting all bits of their absolute value (one's complement) and adding 1.

ASCII

American Standard Code for Information Interchange; a 7-bit character encoding system representing 128 characters (including 95 printable characters such as letters, digits, and punctuation, plus 33 control characters), with extended ASCII using an 8th bit for 128 additional symbols.

Magnetic Disk Geometry

The physical organization of a hard drive platter consisting of platters/surfaces, concentric circular tracks, and radial divisions called sectors (the fundamental unit of disk storage).

1-Bit Full Adder

A digital circuit composed of AND, OR, and XOR logic gates that calculates the sum of two operand bits ($A$ and $B$) and a lower carry-in bit ($\text{CarryIn}$), outputting a sum bit ($\text{Sum}$) and a carry-out bit ($\text{CarryOut}$).

Operating System (OS)

Core system software that manages and schedules hardware and software resources, provides user interfaces, and performs five primary tasks: process management, memory management, storage/file management, device management, and user interface provision.

Compiler vs. Interpreter

A compiler translates entire high-level source code into a standalone machine-code executable before runtime, whereas an interpreter reads, translates, and executes source code line-by-line during runtime.

Python

An interpreted, high-level programming language created in late 1989 by Guido van Rossum, known for concise syntax, rich libraries, and glue-language capabilities.

Algorithm

A finite, ordered, unambiguous sequence of steps or computational procedures designed to solve a specific problem and produce a result from given inputs within a finite amount of time.

OpenJudge Status Verdicts

Evaluation outcomes returned by an automated testing platform, including Accepted (passed all test cases), Compile Error (syntax failure), Runtime Error (execution aborted), Presentation Error (formatting discrepancy), and Wrong Answer (logic error).

sep and end (in print())

Keyword parameters in Python's print() function: sep specifies the delimiter inserted between multiple outputs (default ' '), while end specifies the character appended after the last value (default '\n').

Banker's Rounding (round())

Python's rounding rule where numbers equidistant from two integers (ending in .5) round toward the nearest even integer, while other fractions round toward the nearest integer.

Floor Division (//)

An arithmetic operator that divides two operands and rounds the result downward to the nearest mathematical integer (e.g., $10 // 3 = 3$, $10 // -3 = -4$).

Modulo Operator (%)

An arithmetic operator that calculates the remainder of division defined mathematically as $x \% y = x - ((x // y) \times y)$.

String Slicing ([start:stop:step])

A syntax extracting a portion of a sequence from index start up to but not including stop, incrementing indices by step without altering the original string.

Formatted String Literal (f-string)

A Python string literal prefixed with f or F that allows replacement fields containing expressions, variables, and format specifications (e.g., {a:8.2f}) inside curly braces {} evaluated at runtime.

Truthiness (Logical Values in Python)

The inherent Boolean evaluation of non-Boolean data types in conditional contexts, where values such as 0, 0.0, and empty strings "" evaluate to False, while non-zero and non-empty values evaluate to True.

Short-Circuit Logical Operators (and / or)

Boolean operators in Python where x and y returns x if x evaluates to false, otherwise returns y; and x or y returns x if x evaluates to true, otherwise returns y.

Membership Operators (in / not in)

Operators used to test whether an element exists within a sequence such as a string, list, or tuple, returning True or False.

Identity Operators (is / is not)

Operators determining whether two identifiers refer to the exact same memory object address (id(x) == id(y)), in contrast to == which compares value equality.

range(start, end, step)

A built-in Python function generating an immutable sequence of integers from start (inclusive) to end (exclusive) with interval step.

Infinite Loop (Dead Loop)

A loop structure whose conditional expression evaluates permanently to true (e.g., while 1:), causing instructions to repeat endlessly unless terminated by an external signal or internal break statement.

break vs. continue

In loop control, break immediately terminates the innermost enclosing loop, whereas continue aborts only the current iteration and jumps to the next cycle.

Loop else Clause

A block of code attached to a for or while loop that executes strictly when the loop completes all iterations naturally, and is skipped if the loop is aborted via a break statement.

Time Complexity (O(f(n)))

An asymptotic metric describing the computational runtime required by an algorithm as a function of input size $n$, characterized by the order of growth $T(n) = O(f(n))$.

Enumeration Algorithm (Exhaustive Search)

A problem-solving strategy that checks every possible candidate solution systematically against explicit criteria within a finite search space to guarantee finding all valid solutions.

Mutable vs. Immutable Types

A distinction in Python where immutable types (numbers, strings, tuples) cannot be altered in memory without creating a new object at a different address, while mutable types (lists, dictionaries, sets) allow in-place modification.

List (in Python)

A mutable, ordered, dynamic collection of heterogeneous elements enclosed in square brackets [] that stores references to memory locations.

a.sort() vs. sorted(a)

The list method a.sort() modifies the existing list a in place and returns None, whereas the built-in function sorted(a) leaves a unchanged and returns a new sorted list.

List Comprehension

A concise Python syntactic construct used to generate a new list by applying an expression to each item across an iterable (e.g., [x**2 for x in range(10)]).

Tuple (in Python)

An immutable, ordered collection of heterogeneous elements enclosed in parentheses () (or separated by commas), which provides data write-protection and faster traversal compared to lists.

Single-Element Tuple

A tuple containing exactly one value, which syntactically requires a trailing comma (e.g., (42,)) to distinguish it from a parenthesized expression ((42)).

Flag Variable Pattern

A programming design pattern where a Boolean or sentinel variable (e.g., flag = False) tracks whether a searched condition has been met during an iteration before triggering subsequent conditional blocks.

print(…, sep=':')

Specifying a custom delimiter string (such as a colon) to be inserted between multiple printed arguments instead of the default single space.

print(…, end='')

Suppressing the automatic trailing newline character so that subsequent print statements continue outputting on the exact same line.