The list of topics for the entry exam to the AGH Doctoral School in the discipline of Information and communication technology

  • Algorithmics - definition of the algorithm, time and space complexity, classes of complexity, examples of algorithms differ in complexity classes. Asymptotic notations, running time estimation. Sorting algorithms, BFS and DFS algorithm, a minimal spanning tree of a graph, the shortest path problem and algorithms. The concept of a data structure. Different types of data structures, i.e., single-linked and double-linked lists, hash tables, binary search trees (BST), red-black trees, representations of a directed/undirected graph, and their pros and cons
  • Programming languages – procedural, object-oriented, and functional languages. Popular control structures/phrases: if, for, while, do, return, break, new, delete, super, etc. Their meaning and use. The overall structure of a program providing in object-oriented and functional languages. Effective use of data structures in various programming languages. Object-oriented programming - concepts of inheritance, polymorphism, and projection. Throwing and handling exceptions.
  • Parallel processing - the concept of a thread and a process. The idea of shared memory, mutual exclusion, thread, and processes synchronization. Synchronization errors, deadlock, and livelock issues. Models of concurrent systems: dining philosophers' problem, readers and writers, producers and consumers, etc. Synchronization mechanisms: semaphore, monitor, and CAS (compare-and-swap) mechanism. Their meaning and implementations in the contemporary programming languages.
  • Formal languages - Chomsky's taxonomy of formal languages and automata corresponding to these languages. Turing machine as a computation model. Classes of computability: NP, NP-complete, NP-hard, and others. Examples of problems belonging to these classes. Halting problem. The relationship between formal languages and programming languages.
  • Databases - types of databases. The architecture of a relational database: tables, relations, keys, indexes, views, component procedures, etc. Basics of SQL, types of queries, and their syntax. Database normalization, normal forms. Effective use of databases. Integration of programming languages and DBs.
  • Software engineering - requirements engineering, product engineering. Acquisition and analysis of requirements. Models of the software development process. Structural software analysis and modeling. ERD, DFD, STD, FHD diagrams. Object-oriented design (OOD) and analysis (OOA). The concept of object, class, method, message, pattern, encapsulation, interface. UML language - basic diagrams. Software quality - evaluation methods, software metrics, quality management in the software development process.
  • General IT knowledge - computer architecture and design. Problems and challenges of AI, Turing test vs. the Chinese room idea. Computer-aided decision-making. The idea of heuristics. Examples of heuristic algorithms. Binary arithmetic. Basics of formal logic and discrete mathematics. Examples of computer applications.