Fondamenti di Informatica

The test consists of creating a program capable of managing data (entered by users or already stored in files). The test may also include exercises regarding: the creation of a database and the execution of simple queries; design and management of spreadsheets.

Below is a (non-exhaustive) list of possible theoretical questions - written multiple-choice or open-ended.

2.1 Describe the reasons that lead to the choice of binary encoding.

2.2 How many bits are needed to binary encode numbers from 0 to 37?

2.3 Propose an encoding for the days of the week based on an alphabet of 3 symbols.

2.4 Encode the following base-ten numbers into binary: 139, 8.25.

2.5 Encode the following base-ten numbers into base 3: 139, 230.

2.6 Encode the following numbers in 8-bit two's complement: −19, −38.

2.7 Perform the following operations in binary between 8-bit encoded positive integers: 21 + 13, 35 + 18, 129 + 131, reporting any overflow conditions.

2.8 List the advantages and disadvantages of analog encoding and digital encoding.

2.9 Describe the main types of compression techniques.

2.10 Describe the advantages of hexadecimal notation.

2.11 Assume that approximately 20 million vehicles circulate in Italy; if the license plate of each vehicle were expressed by (a) a binary number or (b) a hexadecimal number, what would be the minimum length (number of digits) of each plate? Indicate the logical steps used to reach the answer, which can be derived without performing the binary conversion of the indicated number.

2.12 Indicate the meaning of the sequence of digits ‘1001001’ depending on whether it is interpreted (a) as a base-two number; (b) as a base-ten number and (c) as a base-sixteen number.

2.13 Perform the following operations using 8-bit two's complement binary encoding: 35 + 18, 35 − 18, 101 + 51, 101 − 51, reporting any overflow conditions.

2.14 To digitize an analog signal, it is necessary to perform the two operations of sampling and quantization. Indicate the parameters that characterize these operations and explain how these parameters can influence the quality of the final encoding.

2.15 Encode the numbers −191, −387 in two's complement using (a) the minimum number of bits necessary for encoding; (b) 16 bits. Then write the results obtained in octal and hexadecimal.

Chapter 3 – Information Processing and Structuring

3.1 Differences and common characteristics between an algorithm and a program.

3.2 Structure and operation of the Turing machine.

3.3 Importance of the Universal Turing Machine.

3.4 Design a Turing machine to add two integers.

3.5 Consequences of the Church–Turing thesis.

3.6 Von Neumann model and its evolution compared to the Turing machine.

3.7 Describe the data structures presented in the chapter.

3.8 Main constructs in flowcharts.

3.9 Differences between (static) arrays and FIFO queues (dynamic), examples, and use cases.

3.10 Differences between FIFO queues and LIFO stacks, examples, and use cases.

3.11 Combination of static and dynamic data structures (examples: queues of records, arrays of stacks).

3.12 Flowcharts for: (a) Reading a vector of n integers (with n provided by the user); (b) Reading a vector by reusing a subprogram; (c) Division between two integers (manual algorithm); (d) Counting and summing even numbers in a vector; (e) Counting zeros in an n×m matrix; (f) Counting even numbers in an n×m matrix (using the subprogram from point d); (g) Swapping two columns of a matrix (indices read from user).

3.13 Verify the equivalence of boolean expressions using truth tables.

3.14 Flowchart to find the minimum in a sequence of natural numbers (>0), terminating on input ≤0.

3.15 Flowchart for maximum, minimum, and average of a sequence of natural numbers (>0), terminating on input ≤0.

3.16 Flowchart for: (a) Reading N; (b) Reading N numbers; (c) Calculating and printing maximum, minimum, and average.

3.17 Flowchart for: (a) Reading day, month, year; (b) Calculating days elapsed since the beginning of the year; (c) Error handling for out-of-range values, days exceeding the month limit, and 29/02 in a non-leap year.

3.18 Derive a boolean expression equivalent to a given truth table (variables a, b, c).

Chapter 4 – Languages for Information Formalization

4.1 Classification criteria for programming languages (imperative, object-oriented, functional, declarative) and schematic characteristics.

4.2 Comparison between imperative and object-oriented languages: advantages/disadvantages, examples of preferred use, relationships between categories.

4.3 Comparison between functional and declarative languages: advantages/disadvantages, examples of preferred use, relationships between categories.

4.4 Data organization in relational databases.

4.5 Principles of entity–relationship models.

4.6 Concept of hypertext and main aspects of HTML.

4.7 General concepts on which XML is based.

4.8 Describe in pseudocode the algorithm examples presented in Chapter 3.

Chapter 5 – Information Transmission

5.1 Factors limiting the capacity of a transmission channel.

5.2 Advantages and disadvantages of digital transmission compared to analog.

5.3 Definition of bandwidth.

5.4 Definition of modulation.

5.5 Definition of a signal and three examples different from those cited in the text.

5.6 Definition of redundancy in a message.

5.7 Describe and justify the use of the parity bit.

5.8 Calculate the number of symbols per second with a 6-bit alphabet and 2 parity bits on a 10 kbit/s channel.

5.9 Calculate the minimum bandwidth (kbit/s) for 10 ksymbols/s with 8 bits/symbol and error detection.

5.10 Calculate channel bandwidth and source speed for a multimedia stream: 100 kbit/s, 100-bit blocks, 2% of blocks corrupted and retransmitted.

Chapter 6 – Hardware Infrastructures

6.1 Von Neumann architecture.

6.2 Organization of the processor's fundamental cycle (fetch-decode-execute).

6.3 Structure of the processor's data path.

6.4 Main elements of the processor's control unit.

6.5 Execution phases of the instruction OR R01, R02, R03 and active elements in the diagram.

6.6 5-stage pipeline (IF 10 ns, ID 5 ns, EX 10 ns, MEM 10 ns, WB 5 ns): improvement compared to execution without pipeline and sequence length necessary to triple the average speed.

6.7 Parameters characterizing memories.

6.8 Comparison of cache solutions: (a) L1 2 ns, 90% hit rate; (b) L1 2 ns (80%) + L2 4 ns (80%); (c) L1 2 ns (80%) + L2 5 ns (x%).

6.9 Same as 6.8 but with main memory at 8 ns.

6.10 Main technological advancements in modern processors.

6.11 Organization of mass storage.

6.12 Operation of the computer–peripheral interfacing mechanism.

Chapter 7 – Software Infrastructures

7.1 Fundamental components of the operating system.

7.2 Organizational models of operating systems.

7.3 Process scheduling mechanism.

7.4 Process life cycle.

7.5 Analysis of a process state diagram in time-sharing: eliminate impossible or useless transitions and clarify events.

7.6 Analysis of state transitions between running/ready/waiting processes; explain virtual memory.

7.7 Calculate the page table size for 2 GB physical memory, 512 KB page size, 1/2/4 GB virtual memory.

7.8 Organization and functions of the file system.

7.9 Principles of the client–server model.

7.10 Concept of resource virtualization.

7.11 Process protection mechanism.

7.12 Definition of system call and invocation modes.

Chapter 8 – Network Infrastructures

8.1 Classify computer networks (connection type, extension/scale, topology).

8.2 Describe transmission media (guided and unguided) and their characteristics.

8.3 Compare circuit switching and packet switching.

8.4 Characteristics of ADSL and Wi-Fi.

8.5 Advantages and disadvantages of main network topologies.

8.6 Main network devices (repeater, hub, switch, bridge, router, gateway).

8.7 ISO/OSI and TCP/IP protocol stacks: layers and functions.

8.8 Define what distributed systems are and describe their advantages.

Chapter 9 – Applications

9.1 Describe the three components of an application (User Interface, Application Logic, Data Management).

9.2 Comment on the phases of the software life cycle.

9.3 Classify types of user interfaces.

9.4 Describe and discuss the organization of web-oriented software architectures.

9.5 Describe software architectures for mobile devices.

9.6 Describe service-oriented software architectures (SOA).

9.7 Discuss main security issues regarding network communications.

9.8 Describe the operation of the HTTP protocol.

9.9 Define what a DBMS is.

9.10 Advantages and disadvantages of a DBMS compared to traditional files.

9.11 Difference between a web server and an application server.