Boolean functions and their representation. Minimization of Boolean formulas. Technology mapping using gates, multiplexors, decoders, memories. Typical combinational logic circuits used in digital computers, their design and implementation. Hazards in combinational circuits.
A finite state machine (FSM) as a model of sequential circuits, Mealy and Moore types. State minimization. Synchronous and asynchronous sequential circuits. Basic types of latches and flip-flops. Technology mapping using gates, flip-flops, memories, programmable logic structures (PLAs, FPGAs). Timing analysis, working frequency computations, metastability.
Fault models, test pattern generation for combinational circuits by sensitive-path method, fault detection and localization.
Von Neumann and Harvard architectures. The function of main units. Memory organization and data representation. The basic instruction cycle. Interrupts and exceptions, their types and handling, masking/disabling interrupts, priorities and their evaluation. Hardware interrupt handling.
Performance criteria, bandwidth and execution time (latency). Benchmarks and performance measurement. Amdahl's law and processor performance equation.
Basic types of instruction sets (accumulator-based, stack-based, with general-purpose registers), their properties and application domains. Instruction encoding, operation code. Machine instructions and assembly language. Arithmetic and logical operations in instruction sets. Addressing modes and representation of data in memory. Control instructions, subroutine call support. Taxonomy of ISAs with general-purpose registers. Characteristic features of CISC and RISC.
Number systems. Representation of signed numbers in binary codes. Basic operations in sign-and-magnitude and two's complement binary codes: addition, subtraction, arithmetic shifts. Floating point arithmetic: number representation and basic principles of arithmetic operations. Alphanumeric codes. The basic principles of error control codes and their use.
Basic memory parameters, memory access latency and memory cycle time. Memory taxonomy based on data addressing method (addressable memories, LIFO, FIFO, CAM), characterization of individual types, realization, use in computers. Memory hierarchy. Cache memory, its organization and addressing. Virtual memory, dynamic address translation, TLB. The main memory with interleaved cycles. Implementation methods for concurrent access to the memory.
Computer controller (control unit) and the data path, relations between them. Hardwired controllers and microprogrammed controllers: principles, structure, and design. Comparison of a controller without instruction pipelining and a controller with instruction pipelining.
Decomposition of a processor into pipelined stages (sections). Hazards in pipeline processing, their taxonomy, and their elimination. Pipeline stalls, instruction control flow between stages. Techniques for prevention of data and control hazards without stalls. Pipelined integer and floating-point arithmetic units. Pipeline execution of complex instructions. Advanced pipeline processing; superscalar, superpipeline and VLIW processors.
Taxonomies of parallel systems, Flynn classification. Vector computers. Architectures of multiprocessor systems with shared and distributed memory. cache memory coherence and memory consistency in shared memory multiprocessor systems. Instruction primitives for process synchronization.
I/O (peripheral) units and their devices - DMA, channels, and I/O processors. Busses - types, regimes, arbitration. Standard system and I/O buses. Methods and techniques for connecting peripheral devices to a bus.
Displays, printers, plotters. Keyboards, digitizers and tablets, scanners, controller function. Input of video and audio information for digital processing. Typical standard interfaces.
Magnetic and optical memories, organization, encoding; protection of records against errors. Typical standard interfaces to external memories.
Properties of transport channels, encoding and modulation methods. Metallic, optical, and radio connections (links). Transport networks, access networks, radio networks, ISDN networks, ATM.
Protection against communication errors, acknowledgement schemes. Algorithms and mechanisms of routing, flow control in routers and end devices. Transport, relation, presentation services. Data encryption in computer networks. Internet protocols.
Client-server technology, interface of UDP and TCP protocols.
Asymptotic complexity. Complexity classes P and NP. NP-completeness. Turing machines, their generalization. Undecidable problems.
Recursion, transformation of recursion into iteration. Backtracking technique. Dynamic programming. Sweep plane technique. Divide-and-conquer method.
Sorting by selection, insertion, exchange. CountingSort, HeapSort, MergeSort, ShellSort, RadixSort, QuickSort. Operational and memory complexity of the sorting algorithms in the best, average, and worst case.
Address searching (direct access, chaining and open hashing, hashing function). Associative searching (sequential, binary, binary search trees). Operational and memory complexity of the search algorithms in the best, average, and worst case.
Array, table, list, set, tree, queue, stack, heap. Basic properties, fundamental operations and their complexities.
Depth-first and breadth-first search of a graph. Directed graphs, topological ordering, strong connectivity. Minimum spanning tree of a graph, shortest path problem. Network flow problem. Greedy algorithms. Dynamic programming. Solving problem using state space search. Heuristic search.
Architecture of single-user and multi-user operating system (OS). OS kernel. Precesses, threads, process scheduling and context switching. Alocation of shared resources to processes. Deadlock - Coffman's conditions and solutions.
Race conditions. Critical sections, methods for mutual exclusion of processes and threads. Classical synchronization tasks and their solutions.
Memory management in single-task and multitask systems. Swapping. Virtual memory, paging, segmentation, combined techniques for memory management. Methods for translation of virtual addresses to physical ones. Page replacement algorithms.
File attributes, file types, operations with files. File implementations: methods for allocating data blocks, methods for storing attributes, management of free blocks. Directory implementation. Disk cache memory. File systems (FAT, UFS, NTFS). RAID.
Simple and structured data types, internal representation. Pointers and dynamic variables, dynamic memory management. Simple and structured statements. Procedures and functions, block structure, stack frames. Modular program structure. Exceptions. Object oriented features.
Lexical analyzer, regular grammars, finite state automata and relations among them. Software implementation. Top-down parsers, context-free grammars, push-down automata and relations among them. LL(1) grammars, transformation of grammars. SW implementation of an LL(1) parser.
Specification methods for syntax directed translation - translation grammars, attribute grammars, attribute translation grammars. LL-attribute translation grammars, recursive descent parsing with parameters. Internal form, stack machine language, abstract syntax tree, examples of translation of basic constructs.
Database management systems (DBMS), database, data dictionary, concurrency control, transaction processing, client-server architecture.
Conceptual data model, logical database models, physical database models, their relationship. Relational database model: relation, functional dependencies, relational scheme design algorithms, normalization, integrity constraints. Design of a relational scheme in the 3rd NF by decomposition from a universal relation.
Relation algebra, SQL (DDL, DML, DCL).
Conceptual data models. Abstract data types as definitions of attribute domains, ER-model, class model. Conceptual functional models. Behavior model, use cases scenario, communication diagrams, data flow diagrams, context diagrams, activity diagrams. Function hierarchy, minispecification of elementary functions, descriptions of operations. Description of dynamic dependencies by state diagrams, behavior scenarios, regular expressions, and relationships between them. UML - syntax and diagrams.
Design of logical data models from conceptual models. Relation logical model. Object logical model. Functional dependencies. Normal forms. Design of a relation scheme from conceptual data model. Design of logical functional models. Design by decomposition, design based on data structures, object-oriented design, design based on data flows. Design patterns. Component diagrams, deployments diagrams.