Introduction to Computing - Teoria (2005/2006)

Learning outcomes

The course addresses some basic concepts in computer science, in which the scientific aspect is emphasized. It starts from the analysis of the notion of calculus that originates from the usual evaluation of algebraic expressions, and addresses the difference between symbolic and operational calculus.
By following the aforementioned perspective, algorithms, automata, programs, data structures and types, fundamental characteristics of the digital information, formal languages and other basic ideas that underlie the organization of computing (operating and network) systems are presented.

1. Operations and Algorithms
Classes, Sequences, Relations, Operations, Functions, Predicates.
Diagrams. Calculi and Algorithms.

2. Expressions and Commands
Operating expressions and evaluation calculi. Conditional expressions, Lambda expressions. Commands and control constructs.

3. Instructions and Programs
Data spaces. Symbolic and imperative calculus. Programs, Machines and Automata.
Register Machines. High-level procedural languages.

4 Circuits and Machines
Boolena functions and Combinatorial Circuits. Sequential Machines.
Transfer and Synchronization circuits. Structure of the Von Neumann machine.
Execution cycle.

5. Data and Types
Graphs. Trees. Strings. Arrays and Lists. Random Access and Sequential memories.
Files. Records. Pointers.

6. Symbols and Codes
Characteristics of the digital information. Information measures. Codes and code trees.
ASCII and UNICODE codes. Instantaneous codes. Information entropy.

7. Automata and Languages
Languages and operations on languages. Finite State Automata. Regular Expressions.
Computability, semidecidability and decidability. Turing machines. Church's thesis. Undecidability. Computational complexity.

8. Operating Systems
Programming levels. Functions and structure of an operating system. System kernel. Structure of a file system. Command-based languages. Basic applications. Graphical interfaces.

9. Networks and services
Network levels. Resources and addresses. Services and Protocols.
Client-Server model (HTTP, SMTP). Texts. Formats. Hypertexts. Service access and use. Authentication and security systems.

Questionnaire: 10 questions, two hours, books and notes cannot be used during the examination.

- 4 exercises: evaluation of lambda and combinatorial expressions; register machine program; automaton and/or regular expression; Turing machine;
- 2 definitions;
- 1 shell script.
- 3 questions about Linux.