Institute of Computer Science

Staff and structure

• Director of the Institute: Leszek Pacholski, Ph.D. Prof.
• vice Director for Teaching Affairs: Paweł Rychlikowski, Ph.D.
• vice Director for Financial Affairs: Marcin Młotkowski, Ph.D.
• vice Director for Scientific Matters: Emanuel Kieroński, Ph.D.

Councils and Boards

• Council of the Institute
• Board of Teaching Affairs
• Board of Financial Affairs
• Council of the Institute Library
• Council of the Computer Network

Superior authorities

• Ministry of Education and Science
• University of Wrocław
  pl. Uniwersytecki 1, PL-50-137 Wrocław
  Chancellor: Marek Bojarski, Ph.D. Prof. (e-mail: rektor@adm.uni.wroc.pl)
  Chancellor's Office: phone +48 71 3436847, +48 71 3752212
• Department of Mathematics and Computer Science
  pl. Grunwaldzki 2/4, PL-50-384 Wrocław
  Dean: Piotr Biler, Ph.D. Prof. (e-mail: dziekan@math.uni.wroc.pl)
  Dean's Office
  phone +48 71 3757895, +48 71 3757890, +48 71 3757892;
  +48 71 3757893, +48 71 3757894, fax +48 71 3757895

Research groups

Research groups in the Institute

Group of Programming Languages Head:Jerzy Marcinkowski, Ph.D., Professor of University of Wrocław Group of Numerical Methods Head:Stanisław Lewanowicz, Ph.D., Professor Group of Programming Methods Acting head: Helena Krupicka, Ph.D. Group of Computational Complexity and Analysis of Algorithms Head: Krzysztof Loryś, Ph.D., Professor of University of Wrocław
• Research interest: approximation, probabilistic and on-line algorithms; parallel, distributed and mobile computations; cryptology, computational complexity, formal languages, and theory of automata.
• Popularization of informatics: Polish Olympiad in Informatics, Programming Contest "Wielka Przesmycka".

Working group information

People

Faculty staff

PhD students

Others

Faculty staff

	Sebastian	Bala, Ph.D.
	Anna	Bartkowiak, Ph.D. habil.
	Marcin	Bieńkowski, Ph.D.
	Małgorzata	Biernacka, Ph.D.
	Dariusz	Biernacki, Ph.D.
	Witold	Charatonik, Ph.D. habil.
	Monika	Demichowicz, M.Sc.
	Leszek	Grocholski, Ph.D., Eng.
	Ewa	Gurbiel, Ph.D.
	Tomasz	Jurdziński, Ph.D. habil.
	Przemysława	Kanarek, Ph.D.
	Witold	Karczewski, Ph.D.
	Paweł	Keller, Ph.D.
	Emanuel	Kieroński, Ph.D.
	Ewa	Kołczyk, Ph.D.
	Antoni	Kościelski, Ph.D.
	Helena	Krupicka, Ph.D.
	Stanisław	Lewanowicz, Ph.D. Prof.
	Maciej	Liśkiewicz, Ph.D. habil.
	Krzysztof	Loryś, Ph.D. Prof.
	Andrzej	Łukaszewski, Ph.D.
	Jerzy	Marcinkowski, Ph.D. habil.
	Marcin	Młotkowski, Ph.D.
	Michał	Moskal, Ph.D.
	Jean-Marie	de Nivelle, Ph.D. habil.
	Rafał	Nowak, M.Sc.
	Leszek	Pacholski, Ph.D. Prof.
	Katarzyna	Paluch, Ph.D.
	Marek	Piotrów, Ph.D. habil.
	Łukasz	Piwowar, Ph.D.
	Zdzisław	Płoski, M.Sc.
	Paweł	Rychlikowski, Ph.D.
	Paweł	Rzechonek, M.Sc.
	Grzegorz	Stachowiak, Ph.D.
	Maciej M.	Sysło, Ph.D. Prof.
	Adam	Szustalewicz, Ph.D.
	Tomasz	Truderung, Ph.D.
	Piotr	Wieczorek, Ph.D.
	Tomasz	Wierzbicki, M.Sc., Eng.
	Piotr	Wnuk-Lipiński, Ph.D.
	Mieczysław	Wodecki, Ph.D.
	Paweł	Woźny, Ph.D.
	Michał	Wrona, Ph.D.
	Paweł	Zalewski, M.Sc.
	Wiktor	Zychla, Ph.D.

PhD students

	Krystian	Bacławski, M.Sc.
	Digvijay	Bharat, M.Sc.
	Tomasz	Cichocki, M.Sc.
	Paweł	Gawrychowski, M.Sc.
	Zbigniew	Gołębiewski, M.Sc.
	Łukasz	Jeż, M.Sc.
	Artur	Jeż , M.Sc.
	Michalis	Kamburelis, M.Sc.
	Kornel	Kisielewicz, M.Sc.
	Jakub	Łopuszański, M.Sc.
	Jakub	Michaliszyn, M.Sc.
	Jan	Otop, M.Sc.
	Marcin	Skórzewski, M.Sc.
	Łukasz	Stafiniak, M.Sc.
	Piotr	Witkowski, M.Sc.

Other employees

	Rashad	Al-Yawir, M.Sc., Eng.
	Harish	Batra, M.Sc., Eng.
	Urszula	Gładysz
	Elżbieta	Jakubczak
	Anna	Jędrzychowska, Ph.D.
	Janusz	Marciniak
	Marcin	Motykiewicz, Eng.
	Beata	Rusiecka, M.Sc., Eng.
	Anna	Smolińska, Eng.
	Katarzyna	Wodzyńska, M.Sc.
	Maria	Woźniak, Eng.

Library

Catalog: on-line catalog of the Institute Library

Working hours: 11 am - 5 pm (Monday - Friday)

Library staff:

• Ewa Marek
• Martyna Błaszczuk

Journals: the list of journals available in the library

University of Wrocław Library:

• home page
• on-line access

Other libraries:

• Library of the Institute of Mathematics
• Library of the Technical University of Wrocław
• On-line catalog of Wrocław libraries

Teaching

Bachelor and Master Degree Studies

Since 1997 the system of studies is based on credit points similar to ECTS (European Community Course-Credit Transfer System). It was designed to fulfill the following conditions:

• All students should learn basics and foundations useful in different areas of computer science. Therefore there are eight lectures obligatory for all students, for example Logic in Computer Science, Algorithms and Data Structures, Discrete Mathematics.
• It should be possible for students to choose lectures from as large number of possibilities as possible. In particular, there should be different advanced lectures each given only to a small fraction of all students.
• The evolution of the taught material should keep up with the evolution of computer science. For example, it should be possible for the students at the fifth year to study subjects which did not exist when they were at the first year.
• Each student should be allowed to choose his or her individual track of studies, as in computer science the set of possible specializations is numerous and diverse ranging from computer scientists, through programmers to system administrators.
• Students should be enabled to finish the process of studies earlier with the degree of a Bachelor if for some reasons they cannot or do not want to finish the whole 5 years Master track.
• Economy should be taken into consideration. For example, optional lectures can be given every two or three years and be visited by students at different stages of their studies.

Holding to the above guidelines, our institute offers several programmes in computer science.

• 5-year programme - Master Degree in Computer Science,
• 3-year programme - Bachelor Degree in Computer Science,
• 2-year complementary programme - Master Degree in Computer Science for graduates of Bachelor Degree studies.

Most of the courses are in Polish but we are starting to teach in English too. For possibilities of studying in Wrocław see information at the WWW page of the University of Wrocław.

Exchange studies

We are a member of the Socrates-Erasmus Programme and welcome students from Europe and all over the world to take lectures in English in our Institute.

Ph.D. Studies

We offer a Ph.D. programme in Computer Science to foreign students.

Postgraduate programmes

We also teach teachers and offer the following courses (in Polish) for them:

• in Education in Informatics,
• in Informatics for teachers.

Bachelor Degree - 3-year programme

Admission	Preparation	Basic Rules	Courses	Contact

Admission

Foreign candidates willing to study at the University of Wrocław should first visit the website, especially designed for their needs. There, they will find:
• recruitment rules,
• fees and accomodation,
• information regarding English academic programs and School of Polish Language
and many more useful details about our University, city, country etc.

What knowledge and skills you need if you want to choose our faculty

Mathematics? First of all, we expect scientific minds. Therefore, a profound mathematical background is inevitable. It may appear that the elements of mathematics required during the studies at our faculty scarcely correspond to the knowledge a student acquired at school. However, what might prove necessary are the skills that you have developed during your previous education, particularly critical problem analysis, creativity in finding solutions and flexible thinking. Computer studies? Secondary schools tend to have different approaches towards teaching computer studies, usually putting too much emphasis on computer skills. Hence, it is not required that the candidates show advanced skills in that field, as we provide them with opportunities to improve them during studies. We appreciate if the candidates are familiar with computer studies, though. English language skills? Obviously, candidates are supposed to know English at a good level, since it will be the language used during the classes. Nevertheless, if need be, the candidates will be given a chance to improve their language skills already in Wrocław. For further details, go to English academic programs. Anything else? Computer studies will enable the candidates to utilize the knowledge of subjects they were particularly fond of in a secondary school, be it biology, chemistry, physics, astronomy, etc. Computers make life easier nowadays in many areas of life, nevertheless, they can be used most efficiently only when information technology knowledge is combined with other fields of science. Thus, broad-minded students will find it easier to explore the fields of knowledge, inaccessible to others.

Basic rules

Freedom of choice and responsibility. Only 8 courses in the program of the undergraduate studies are obligatory. The remaining courses each student chooses by her/himself from a didactic offer. She/He is just required to collect sufficient number of credits to complete a semester. The offer of available courses is quite rich, but only some of them are taught in English. So international students have mostly prescribed programme, unless they speak Polish. Didactic offer. The list of available courses is varying each year - some new courses may be introduced and some out-of-date ones removed. The purpose of this process is to keep in touch with current achievements of computer science and requirements of employees. But some courses, covering basic subjects in computer science and engineering, are offered each year - althoug they are not obligatory. We call them guaranted. We propose for international students all quaranted courses suitable for undergraduate level. Despite them, one should expect to find some other courses in English. Frequency of courses. Courses can be offered once a year or every other year. This system allows us to broaden the spectrum of the offered subjects. But this means that in some cases it is not fixed, at which year of her/his studies the student has an opportunity to attend the course. It must be taken into account while planning a profile of the studies. Types of courses. There are several levels/types of courses in the didactic offer of our studies:
• obligatory courses - there are only seven such courses in the undergraduate programme and only one in the graduate programme; students are obliged to accomplish each of these courses before the prescribed term. The contents of these courses comprise of basics of computer science and it is required for most of other courses.
• courses in computer science - courses comprising subjects in computer science in general manner; usually supported by some projects or courses of programming tools, but not necessary;
• courses of programming tools and projects - typically practical courses - their purpose is usually to give students good knowledge and ability of using a specific programming tool like a programming language, an operating system, a database management system etc.
• seminars - courses where students are required to prepare and present given subject by themselves and take part in discussion on subjects presented by their colleagues.
ECTS. Each course is prescribed a number of credits (ECTS). A student obtains these credits after completing the course succesfuly. Usually a course incomputer science consisting of 30 hours of lectures and 30 hours of excercises with final examination is given 6 ECTS. Courses of tools (same number of hours but without examination) are given 5 ECTS. Seminars and non-informatic courses are prescribed 2-4 credits and obligatory courses are prescribed a number of credits adequate to the number of teaching hours (it may be even 10). Example study plan

Semester	Course	Type of course	Hours/semester	ECTS
1	Calculus (with rep.)	obl.	135	10
1	Logic in Comp. Sci. (with rep.)	obl.	90	7
1	Introduction to Comp. Sci.	opt.	60	6
1	Course of Programming in ANSI C	opt.	60	5
1	Polish Language	opt.	60	2
	1st semester in total		405	30
2	Algebra (with rep.)	obl.	105	7
2	Programming (with rep.)	obl.	120	9
2	Object-Oriented Programming	opt.	60	6
2	Course of Programming in C++	opt.	60	5
2	Polish Language	opt.	60	3
	2nd semester in total		405	30
3	Discrete Math.	obl.	60	6
3	Elements of Probability Theory	obl.	30	3
3	Numerical Analysis	obl.	75	8
3	Operating Systems	opt.	60	6
3	Course of Programming in Java	opt.	60	5
3	Polish Language	opt.	60	3
	3rd semester in total		345	31
4	Algorithms and Data Struct.	obl.	90	9
4	Computer Networks	opt.	60	6
4	Databases	opt.	60	6
4	Course of Programming in Windows	opt.	60	5
4	Non-informatic course 1	opt.	30	3
4	Physical training	opt.	30	1
	4th semester in total		330	30
5	Software Engineering	opt.	60	6
5	Functional Programming	opt.	60	6
5	Intr. to Comp. Graphics	opt.	60	6
5	Course of Database Systems	opt.	60	5
5	Seminar	opt.	30	3
5	Programming Project	opt.	30	4
5	Physical training	opt.	30	1
	5th semester in total		330	32
6	Course in Comp.Sci. 1	opt.	60	6
6	Course in Comp.Sci. 2	opt.	60	6
6	Course of tools 2	opt.	60	5
6	Programming project	opt.	30	4
6	Seminar	opt.	30	3
6	Non-informatic course 1	opt.	30	3
	6th semester in total		270	27

List of available courses

Obligatory courses

• Algebra
• Algorithms and Data Structures
• Calculus
• Discrete Mathematics
• Elements of Probability Theory
• Logic for Computer Science
• Numerical Analysis
• Programming

Courses in computer science

• Approximation Algorithms
• Artificial Intelligence I
• Automated Verification
• Compiler Design I
• Computational Goemetry
• Computer Networks
• Convergence Acceleration Methods
• Cryptography
• Databases
• Data Compression
• Distributed Algorithms
• Formal Languages and Computational Complexity
• Functional Programming
• Introduction to Computer Graphics
• Introduction to Computer Science
• Logic Programming
• Mathematical Methods of Computer Graphics
• Modelling of Natural Problems
• Natural Language Processing
• Neural Networks
• Neural Networks in Pattern Recognition
• Object-Oriented Programming
• Online Algorithms
• Operating Systems
• Randomized Algorithms
• Realistic Computer Graphics
• Software Engineering
• Text Algorithms
• Theoretical Foundations of Communication in Networks
• Theoretical Foundations of Programming Languages

Seminars

Each semester there are several seminars given. Some of them are regular - appear each year or each two years and strongly reference to a given advanced course (e.g. Randomized Algorithms, Online Algorithms, Text Algorithms, Cryptography, Neural Networks, Data Warehauses and Data Mining, Problems in Logic, Problems in Graphics, Distributed Systems). There are also occassional seminars (e.g. Algorithms in Computational Biology, Veryfication of Cryptographic Protocols, 3D Computer Vision) - the list of their subjects is proposed before the semester.
• Seminar: 3D Computer Vision
• Seminar: Hot Topics in Computer Graphics
• Seminar: Online Algorithms

Courses of Tools

Each year there are courses of basic tools offered (like programming in C/C++, Java, operating systems Windows and/or Unix/Linux, DBMS, Internet Tools). There are also occasional courses of other tools and systems like ASP.NET + ADO.NET, Open-Source Programming, Unix: Environment and Tools for Programming, UML and Other Basic Object Standards, Maple and Matlab, Computer Security, Haskell, Python, Assembler, XML, Nemerle.
• Course of Database Systems
• Course of Programming in ANSI C
• Course of Programming in C++
• Course of Programming in Java
• Course of Programming in Maple and Matlab
• Course of Programming in Windows

Non-informatic courses

To be announced later.

Contact

In case of any questions concerning studying Computer Science in English in our Institute, you may write to Paweł Woźny.

Computer Networks

Type: optional course ECTS: 6 credits Hours: 30h lectures, 30h exercises and lab. Assessment: written examination Semester: summer

Prerequisites:

• algebra,
• discrete mathematics.

Objective of the course:

This lecture is an introduction to the vast area of computer networks. We will present the basics of computer networks, particularly of these based on TCP/IP protocol, and we review network applications commonly met in the Internet. We will emphasize the mechanisms and algorithmic foundations of network communication problems, as well as the practical use of elements of this knowledge.

Contents of the course:

1. Basic concepts, kinds of communications, mathematical model of network (congestion, dilation). ISO/OSI reference model, RFC, brief history of computer networks.
2. Physical layer, cables, switches, hubs, repeaters. Medium access control layer, LAN networks, Ethernet frames, broadcast and colision domains, CSMA/CD algorithm and its analysis, MAC addresses, Manchester encoding, CRC sums.
3. IP protocol, IP header, bridging vs. routing. Fragmentation, MTU discovery. IP addresses, IP classes, CIDR. Routing tables, aggregation. Cooperation with the second layer (ARP/RARP/DHCP), ping and traceroute.
4. Dynamic routing. Creating routing tables using distance vector (RIP) and link state (OSPF) algorithms. Routing loops, split horizon, route poisoing. Information about Internet routing (BGP), hierarchical routing.
5. Transport layer protocols: UDP, TCP, similarities and differences, ports, header options. Client-server model. TCP states, sequential numbers and acknowledgements, types of segments. Basics of socket programming.
6. TCP algorithms: three-way handshaking, delayed acknowledgements, Nagle's algorithm, sliding window, MSS. Flow control: congestion window, slow start, AIMD: congestion avoidance algorithm and its analysis. Fast retransmit and fast recovery.
7. Application layer. DNS protocol: name hierarchy, TLD, delegations, iterative and recursive queries, reverse domain. FTP protocol, passive and active mode. HTTP protocol: URLs, HTTP headers, MIME types, information about basic WWW technologies (HTML, javascript, css).
8. Proxy servers, hierarchies. Proxy server algorithms: consistent hashing, web caching.
9. Basics of network security, types of attacks, intrusion detection systems, sniffers, spoofing. Firewalls and their configuration, information about NAT. Denial-of-Service attacks, detecting sources of attacks (ICMP traceback).
10. Web graph, social networks, random graphs, Pareto distribution. Searching in WWW, crawlers, content indexing, PageRank algorithm and its analysis.
11. Emails, headers, SMTP and POP3 protocols, MIME formats. Anti-spam filters, Bayesian algorithms. Digital signatures.
12. Theoretical foundations of routing. Routing algorithms in different network topologies. Ring, mesh, hypercube topologies, permutation network. Adaptive and oblivious routing. Selfish routing, price of anarchy.
13. Peer-to-peer networks, practice (Napster, Gnutella, Kazaa) and theory (distributed hash tables: Chord).
14. Worms and viruses, types of dangers. Epidemic models, rumour spreading models.
15. Mobile and ad-hoc networks. Radio networks, interferences. Topology control, stretching graphs.

Recommended reading:

• Andrew S. Tanenbaum, Computer Networks, 3rd ed., Prentice-Hall, 1996.
• Douglas E. Comer, Internetworking with TCP/IP, vol. 1 and 2, 5th ed., 2006.
• W. Richard Stevens, UNIX Network Programming, vol. 1 and 2, 2nd ed., Prentice Hall, 1998.
• Christian Schindelhauer, Algorithmic foundations of the Internet (script in German, available from the author's webpage).

Course of Programming in ANSI C

Type: course of programming tools ECTS: 5 credits Hours: 30h lectures, 30h labs Assessment: programming assignments and a small final project Semester: winter 2008/2009

Prerequisites:

None, some programming experience will be helpful.

Objective of the course:

The goal is to provide a comprehensive introduction to the programming in the ANSI C language with many examples and supervised practical sessions in computer labs. No previous programming experience is assumed, but students with no experience will need to do more homework to keep in line with others. The language is introduced in a structural manner, beginning with the simple constructs and working up to more complex issues, for example, pointers and dynamic data structures, file manipulations or recursive functions. The last lectures are devoted to some aspects of the C++ language. Learning effective programming and the good programming practice are the main objectives of the course.

Contents of the course:

1. Basic programming constructs: statements and declarations.
2. Standard data types and expressions.
3. Standard input/output, filters.
4. Functions and the structure of programs.
5. Arrays and pointers, aggregate structures and unions.
6. Dynamic memory allocation and the C runtime library.
7. Sequential and random file manipulation.
8. Classes, objects and streams in C++.

Recommended reading:

• Brian W. Kernighan and Dennis M. Ritche, The C Programming Language, second edition, Prentice Hall Software Series.
• Herbert Schildt, C - The Complete Reference, Osborne McGraw-Hill.
• ISO/IEC 9899 - Programming languages - C (the current ISO standard).

Course of Programming in C++

Coming soon.

Course of Programming in Java

Coming soon.

Course of Programming in Windows

Type: course of programming tools ECTS: 5 credits Hours: 30h lectures, 30h exercises Semester: summer

Prerequisites

Required:
• knowledge of ANSI C language,
• knowledge of any object-oriented language.

Objective of the course

The objective of the course is to present broad range of technologies used in modern enterprise applications for Microsoft Windows.

Contents of the course

The course consists of two major parts. The objective of the first part is to present the Win32 Application Programming Interface, a legacy API which lays the base for any high-level programming interfaces for Windows. The Component Object Model (COM) technology is also presented as well as other minor technologies used prior to the .NET. The objective of the second part of the course is to present the .NET Framework, starting with the introduction of the C# language and its features (generics, LINQ) and ending with the review of all major .NET technologies: collections, serialization, XML, Windows.Forms, ADO.NET, ASP.NET and WebServices.

Recommended reading

• Charles Petzold, Programming Windows 5th edition.
• Bruce Eckel, Thinking in C#, Release Candidate.
• Charles Petzold, Programming Microsoft WIndows with C#.
• Douglas Reilly, Desiging Microsoft ASP.NET Applications.

Databases

Type: optional course
ECTS: 6 credits
Hours: 30h lectures, 30h exercises and lab.
Assessment: written examination
Semester: summer

Prerequisites:

Some knowledge of logic (writing and understanding logical formulas) and basic algorithms and data structures (simple sorting algorithms and tree structures) are required. It is also necessary to know one of the popular programing languages, like C++, PHP or Java, to write an application part of the database project. Courses in the program of our studies that cover these topics (and much more) are:

• Logic For Computer Science,
• Introduction To Computer Science
or
Algorithms And Data Structures,
• Course of Programming in C++ or Course of Programming in Java.

Objective of the course:

The lecture is an introduction to the huge area of databases. Our goal is to present some general database mechanisms and study relational database systems in practice. Besides the lecture contains some ideas of object databases and general information on database management systems.

Contents of the course:

1. Basic concepts of databases: database, database management systems, data model. Historical database models.
2. Relational database model- concept of relation, integrity constraints (keys, foreign keys). Queries in relational algebra.
3. SQL data definition language - creating tables, views, users. Defining keys and other constraints.
4. SQL query language - simple one-table queries, joins and multi table queries, subqueries, grouping and aggregate functions.
5. SQL object elements - triggers, functions, structural data types.
6. SQL in applications - embedded SQL, elements of PL/SQL or other programmatic SQL, API for database applications.
7. Database management systems basics-
   1. The concept of transaction. Levels of independence in SQL.
   2. Database file organization and storage structure. Indexes (ISAM and B-trees). Hashing.
   3. Processing database queries. Optimization rules. Analyzing query execution plans.
   4. Data security - logs and recovery procedures.

Excercises and laboratory:

• SQL - quering database; we will train finding arbitrary information in a given database;
• SQL - definition language; we will create database according to a given model
• conceptual modelling - we will learn, how to create a good and effective database model of a real problem;
• writing database application;

Recommended reading:

• H.Garcia-Molina, J.Ullman, J.Widom Database Systems - The Complete Book (selected chapters), 2nd ed., Prentice-Hall, 2009.
• T.Connolly, C.Begg Database Systems (selected chapters), 4th ed., Addison Wesley, 2005

Introduction to Computer Science

Coming soon.

Object-Oriented Programming

Coming soon.

Operating Systems

Coming soon.

Software Engineering

Type: optional course ECTS: 6 credits Hours: 30h lectures, 30h exercises and lab. Assessment: written examination Semester: summer

Lecture

Lecture presents a general introduction to general process actions and gives familiarity with software development methods. It includes supporting examples and case studies. Some lectures are given by the representatives of leading world and polish information technologies companies: Siemens, VOLVO IT, Cup Gemini. The lectures is divided into fourteen parts:
1. Software engineering discipline (2h).
Software:
1. requirements (4h),
2. design (2h),
3. construction (2h),
4. testing (4h),
5. maintenance (2h),
6. configuration management (2h),
7. engineering management (2h),
8. engineering process (2h),
9. engineering tools and methods (2h),
10. quality (2h).
Software development methods:
1. SRUM (1h),
2. MSF (1h),
3. RUP (2h).

Practical exercise

During practical exercise software development practitioners obtain a good and practical understanding of software engineering process. Students participate in real and complete software development project. They create system vision, define requirements and then develop detail artifacts and put it together in a real project.

Recommended reading:

• SWEBOK Software Engineering Body of Knowledge, www.swebok.org.
• R. S. Pressman, Software Engineering: a Practitioner’s Approach, Seventh ed: Prentice-Hall, Inc., 2006.
• I. Sommerville, Software Engineering, Seventh ed.: Addison-Wesley, 2005.
• ISO 9001:2000.
• P. Kruchten, Rational Unified Process an theoretical approach, Addison-Wesley, 2004.
• P. Troll, P. Kruchten, Rational Unified Process an practical approach, Addison-Wesley, 2004.

Master and Bachelor Studies

Since 1997 the system of studies is based on credit points similar to ECTS (European Community Course-Credit Transfer System). It was designed to fulfill the following conditions:

• All students should learn basics and foundations useful in different areas of computer science. Therefore there are eight lectures obligatory for all students, for example Logic in Computer Science, Algorithms and Data Structures, Discrete Mathematics.
• It should be possible for students to choose lectures from as large number of possibilities as possible. In particular, there should be different advanced lectures each given only to a small fraction of all students.
• The evolution of the taught material should keep up with the evolution of computer science. For example, it should be possible for the students at the fifth year to study subjects which did not exist when they were at the first year.
• Each student should be allowed to choose his or her individual track of studies, as in computer science the set of possible specializations numerous and diverse ranging from computer scientists, through programmers to system administrators.
• Students should be enabled to finish the process of studies earlier with the degree of a Bachelor if for some reasons they cannot or do not want to finish the whole 5 years Master track.
• Economy should be taken into consideration. For example, optional lectures can be given every two or three years and be visited by students at different stages of their studies.

Holding to the above guidelines, our institute offers several programmes in computer science.

• 5-year programme - Master Degree in Computer Science;
• 3-year programme - Bachelor Degree in Computer Science;
• 2-year complementary programme - Master Degree in Computer Science for graduates of Bachelor Degree studies;

Most of the courses are in Polish but we are starting to teach in English too. For possibilities of studying in Poland see information at the WWW page of the University of Wrocław

Master Degree - 2-year programme

Preparation	Basic Rules	Courses	Contact

Preparation

Formally, to access our graduate studies in computer science a candidate is required to have a bachelor degree in computer science (or informatics). It is expected that she/he knows basic concepts of programming and computer systems. To make more precise required preparation for courses offered during the graduate studies we present below programs of courses obligatory during our undergraduate studies in computer science. These courses are not available for foreigners (taught only in Polish) and students can not obtain credits for them during the graduate studies. They are described here for information purpose only, as they are often referred as prerequisites for courses occurring in the program of the graduate studies.
• Algebra
• Algorithms and Data Structures
• Calculus
• Discrete Mathematics
• Logic for Computer Science
• Numerical Analysis
• Programming

Basic rules

Freedom of choice and responsibility. Almost all (except one) courses in the program of the graduate studies are optional. Each student is free to choose any of the available courses and it is her/his responsibility to decide if her/his knowledge is sufficient to take advantage of the course. While making their choice students are encouraged to take advice of their tutors and read carefully programs of the courses of subject and their prerequisites. Didactic offer. The list of courses available is very flexible. Each year some new courses may be introduced and some out-of-date ones removed. The purpose of this process is to keep in touch with current achievements of computer science and requirements of employees. The students have an opportunity to express their opinion in this subject voting for courses presented to them before the academic year starts. Frequency of courses. Courses can be offered once a year or every other year. This system allows us to broaden the spectrum of the offered subjects. But this means that in some cases it is not fixed, at which year of her/his studies the student has an opportunity to attend the course. It must be taken into account while planning a profile of the studies. Levels of courses. There are several levels/types of courses in the didactic offer of our studies:
• obligatory courses - there are only seven such courses in the undergraduate programme and only one in the graduate programme; students are obliged to accomplish each of these courses before the prescribed term. The contents of these courses comprise of basics of computer science and it is required for most of other courses.
• elementary courses - courses comprising of rather simple subjects and ideas, not requiring much preparation; typically students accomplish them during the undergraduate studies, so not many of them are offered in English for the graduate studies. Their programs are presented here mainly in purpose to give the idea of the preparation required for some more advanced courses referring to them. Still, if they are available in English, foreign students of the graduate studies may attend them.
• advanced courses - these courses are typical for the graduate studies and there is a fairly large number of them offered in English.
• courses of programming tools and projects - typically practical courses - their purpose is usually to give students good knowledge and ability of using a specific programming tool like a programming language, an operating system, a database management system etc.
• seminars - courses where students are required to prepare and present given subject by themselves and take part in discussion on subjects presented by their colleagues.
ECTS. At the moment the system of credits prescribed to different courses is under modification. It will be available in a final version in a few months. One can expect that elementary and advanced courses will be prescribed 6-8 credits, seminars and courses will be prescribed 3-4 credits and obligatory courses will be prescribed a number of credits adequate to the number of teaching hours (it maybe even 10). Assessment. Obligatory, elementary and advanced courses are finished with an exam (usually written). To accomplish a course of tools it is usually required to present a project, and to pass a seminar it is usually required to have a presentation. More detailed requirements for each course are presented at the beginning of each semester.

List of available courses

Bellow there is a list of elementary and advanced courses available for graduate students ordered according to the semester they occure. The offer covers two main areas: Algorithmics (AL) and Programing Languages (PL) and the student can find enough courses to get involved, specialized knowledge in these subjects. There are also several courses belonging to the areas of Data Processing (DP) and Graphics (GR) (and Others (OTH)), which may serve as a suplementary object of studies to the main course. An offer of seminars and courses of tools is described further. It should be stressed, that the final offer for each semester is arranged after voting of students, so (in case of lack of interest) it may happen that some of the courses listed below will be postponed to later semesters while some new ones will appear in their place. Still one can expect that each semester there will be enough courses in areas which are specialties of our institute (Algorithmics, Programming Languages, Data Processing) to arrange full time studies.

Winter 2007/2008

Summer 2007/2008

Winter 2008/2009

Summer 2008/2009

Advanced and elementary courses in winter 2007/2008 (October 2007 - January 2008)

• Compiler Design I (PL)
• Data Bases 2 (DP)
• Data Warehauses and Business Intelligence (DP)
• Distributed Algorithms (AL)
• Distributed Systems (OTH)
• Functional Programming (PL)
• Introduction to Computer Graphics (GR)
• Logic Programming (PL)
• Neural Networks (DP)
• Parallel Algorithms in Artificial Intelligence (AL, DP)
• Text Algorithms (AL)

Advanced and elementary courses in summer 2007/2008 (March 2007 - June 2008)

• Formal Languages and Computational Complexity (obligatory)
• Artificial Intelligence 1 (DP)
• Cryptography (OTH)
• Data Compression (AL)
• Data Warehauses and Data Mining (DP)
• Mathematical Methods of Computer Graphics (GR)
• Modelling of Natural Problems (OTH)
• Online Algorithms (AL)
• Parallel and Distributed Computations (OTH)
• Realistic Computer Graphics (GR)
• Theoretical Foundations of Communication in Networks (AL)

Advanced and elementary courses in winter 2008/2009 (October 2008 - January 2009)

• Approximation Algorithms (AL)
• Computational Complexity (OTH)
• Computational Geometry (AL, GR)
• Distributed Systems (OTH)
• Evolutionary Algorithms (DP, AL)
• Functional Programming (PL)
• Introduction to Computer Graphics (GR)
• Modal and Temporal Logic (PL, OTH)
• Natural Language Processing (DP)
• Parameterized Complexity (OTH)
• Parallel Algorithms in Artificial Intelligence (AL, DP)

Advanced and elementary courses in summer 2007/2008 (March 2009 - June 2009)

• Formal Languages and Computational Complexity (obligatory)
• Artificial Intelligence 1 (DP)
• Automated Verification (PL)
• Convergence Acceleration Methods (OTH)
• Cryptography (OT)
• Image Processing (DP, GR)
• Neural Networks in Pattern Recognition (DP)
• Parallel and Distributed Computations (DP)
• Randomized Algorithms (AL)
• Intelligent Agent Systems (DP)
• Theoretical Foundations of Programming Languages (PL)

Seminars

Each semester there are several seminars given. Some of them are regular - appear each year or each two years and strongly reference to a given advanced course (e.g. Randomized Algorithms, Online Algorithms, Text Algorithms, Cryptography, Neural Networks, Data Warehauses and Data Mining, Problems in Logic, Problems in Graphics, Distributed Systems). There are also occassional seminars (e.g. Algorithms in Computational Biology, Veryfication of Cryptographic Protocols, 3D Computer Vision) - the list of their subjects is proposed before the semester.

Courses of Tools

Each year there are courses of basic tools offered (like programming in C/C++, Java, operating systems Windows and/or Unix/Linux, DBMS, Internet Tools). There are also occasional courses of other tools and systems like ASP.NET + ADO.NET, Open-Source Programming, Unix: Environment and Tools for Programming, UML and Other Basic Object Standards, Maple and Matlab, Computer Security, Haskell, Python, Assembler, XML, Nemerle.

Contact

In case of any questions concerning studying Computer Science in English in our Institute, you may write to Paweł Woźny.

Algebra

Prerequisites:

High school course in mathematics

Contents of the course:

1. Matrices and vectors. Linear space, its dimension and base. Subspaces and layers.
2. Systems of linear equations, the Kronecker-Capelli Theorem. The elimination method.
3. Linear transformations, the matrix of the transformation. The determinant.
4. Bilinear and quadratic forms. The matrix of the form.
5. The orthogonal base. Orthogonalization.
6. Groups and their properties. Quotient groups. The construction of Z_n. The Lagrange Theorem. The Small Fermat Theorem.
7. Orbits and stabilizers.
8. Rings and fields: definitions and basic examples.

Algorithms and Data Structures

Prerequisites:

It is recommended that candidates accomplish the courses in Programming and Discrete Mathematics.

Objective of the course:

The purpose of the course is to present ideas of algorithms analysis, basic methods of constructing algorithms, basic data structures and their implementations. The course also contains the review of algorithmic solutions in main areas like: sorting and searching, graphs, dictionaries and priority queues.

Contents of the course:

1. Techniques of constructing effective algorithms: divide and conquer, dynamic programming and greedy methods.
2. Computational complexity of algorithms (worst case, expected, amortized). Examples of the cost analysis.
3. Sorting: Heapsort, Quicksort. Decision trees model and a lower bound for sorting. Sorting in linear time: Countsort, Radixsort, Bucketsort.
4. Selection: Hoare algorithm and Magic fives.
5. Priority queues: binary heaps, binomial and Fibonacci heaps. Applying presented structures in solutions for problems of shortest paths and minimal spanning tree.
6. Merging. Tournament trees. External sorting.
7. Data structures for dictionaries: binary search trees, balanced binary search trees (e.g. AVL-trees, 2-3-4-trees, black-red trees), optimal binary search trees. hashing, radix search.
8. External searching - B-trees.
9. The union problem for disjoint sets and its applications.
10. Graph algorithms: flows in networks, matching.
11. Text algorithms. Pattern matching. Suffix trees.
12. Computational geometry. Point localization. Convex hull. Sweeping.
13. Algorithms in algebra and number theory. FFT. Fast multiplying of numbers and polynomials.
14. NP-completeness. Approximation algorithms for intractable problems. Heuristics for difficult problems (genetic algorithms, simulated annealing).
15. Parallel computing models: PRAMs, meshes, hypercubes. Parallel algorithms. Class NC and P-complete problems.
16. Special computing models: comparator networks, logic circuits.
17. Randomized algorithms. Sample solutions from areas of data structures, computational geometry, graph algorithms, parallel algorithms.

Recommended reading:

• A.V.  Aho, J.E.  Hopcroft, J.D.  Ullman, The Desing and Analysis of Computer Algorithms,
• G.Brassard, P.Bratley, Algorithmics. Theory & Practice,
• T.H.  Cormen, C.E.  Leiserson, R.L.  Rivest, Introduction to Algorithms.

Approximation Algorithms

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written and/or oral examination
Semester: winter, 2008/2009

Prerequisites:

It is recommended that candidates accomplish courses in Discrete Mathematics and Algorithms and Data Structures.

Contents of the course:

Many optimization problems of practical interest are NP-hard. This means, that assuming widely believed hypothesis P≠NP, there do not exists polynomial time algorithms for solving these problems. The subject of the course is constructing approximation algorithms, i.e. algorithms working in polynomial time and finding solutions close to optimal ones. Different techniques of construction of approximation algorithms will be presented, e.g. combinatorial methods, linear programming methods, semi-defined programming methods. Searching for approximate solutions, we will consider problems like: minimal Steiner tree, TSP, set cover, k-center, knapsack problem, optimal packing, shortest superstring problem, minimal multiple cut and many others. We will also discuss criteria of difficulty of approximation, like approximation schema, bounds of approximity. There will be also many open problems presented.

Recommended reading:

• V.Vazirani, Approximation Algorithms,
• D.H.Hochbaum, Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997.

Artificial Intelligence I

Type: elementary, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h laboratory
Assessment: written examination
Semester: summer

Prerequisites:

It is recommended that candidates accomplish the courses in Algorithms and Data Structures, Discrete Mathematics and have some knowledge in Logic Programming

Objective of the course:

The course introduces into artificial intelligence topics, such as: knowledge representation, heuristics, reasoning, action planning, decision making, learning, and acting under uncertainty. First some basic techniques and algorithms for: searching, heuristics, logic and theorem proving, rule and semantic representations, as well as probabilistic apporoaches such as Bayesian networks methods will be presented. In the second part, basic concepts and techniques of machine learning will be covered. Finally, some selected practical application areas will be discussed, such as: expert systems, natural language understanding, vision and robotics.

Contents of the course:

1. State space representation, searching, greedy strategies, heuristic information, graph searching, constraint satisfaction searching, and searching for games.
2. First order logic representation, theorem proving and reasoning. Reasoning under uncertainty, non-monotonic logics, truth maintenance systems.
3. Action planning basic concepts and algorithms, conditional planning, plan execution monitoring.
4. Probabilistic represenations, conditional probability, probabilistic belief networks. Decision making basics: utility functions, value of information. Sequential decision problems: dynamic programming, value iteration, policy iteration. Complex decision making, Markov decision problems.
5. Machine learning: concept learning, version space method, decision trees. Reinforcement learning. Computational learning theory.
6. Applications.

Recommended reading:

• S.J.Russell, P.Norvig, Artificial Intelligence. A Modern Approach, Prentice-Hall, 1995
• T.Mitchell, Machine learning, McGraw Hill, 1997
• Internet resources.

Automated Verification

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written and/or oral examination
Semester: summer, 2008/2009

Preequisites:

Logic for Computer Science, Formal Languages and Computational Complexity.

Contents fo the course:

The course gives an introduction to automated verification techniques, particularly model checking. We will discuss temporal logics (CTL, LTL), binary decision diagrams (OBDD) and symbolic model checking, automata-theoretic approach to model checking, bounded model checking, infinite-state model checking (real-time systems, abstraction) and tools (SMV, SPIN, UPPAAL).

Calculus

Prerequisites:

High school course in mathematics

Contents of the course:

1. Real and complex numbers: supremum and infimum, continuity axiom, complex numbers as point on a plane, polar form of a complex number.
2. Sequences and series of real and complex numbers: converging sequences, Cauchy's condition, sequences defined by recursion (examples), Bolzano-Weierstrass theorem, series convergence criteria, power series.
3. Functions of one argument: limit of a function at a point, one side limits, continuity of a function (Cauchy and Heine definition), properties of functions continuous on closed interval, Intermediate value theorem.
4. Derivative of a function: geometric interpretation of a derivative, derivative of a composite function and an inverse function, Intermediate value theorem for derivatives, derivatives of higher orders, Taylor's theorem, function extrema.
5. Integrating: definite integrals (geometric interpretation of an integral), Riemann integral.
6. Function sequences and series: uniform convergence (uniform norm), power series, Taylor series, analytic functions (polynomials, exponential functions etc.).
7. Functions of many arguments: partial derivatives, directional derivatives, Taylor's theorem, extrema of many arguments functions, partial derivatives of a composite functions, multiple integrals, change of variables (Jacobian matrix).

Compiler Design I

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 15h exercises, 15h laboratory
Assessment: written examination
Semester: winter, 2007/2008

Prerequisites:

Programming

Contents of the course:

This course provides an introduction to compiler construction. It goes
through all phases of a compiler from lexical analysis via syntax
analysis, semantic analysis, storage organization to code generation
and optimization.

During the course students implement a complete compiler for a simple
but nontrivial imperative language.

Recommended reading:

• A.V. Aho, R. Sethi, J.D. Ullman, Compilers - Principles. Techniques, and Tools, Addison-Wesley, 1986.
• A.W. Appel, Modern Compiler Implementation in Java, Cambridge University Press, 1998.
• R. Wilhelm, D. Mauer, Compiler Design, Addison-Wesley, 1995.

Computational Goemetry

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written and/or oral examination
Semester: winter, 2008/2009

Prerequisites:

It is recommended that candidates accomplish the course in Algorithms and Data Structures.

Objective of the course:

The course is focused on basic geometric problems for 2D and 3D geometry. Deterministic and randomized algorithms are presented and analyzed. Techniques addressing degenerate cases are discussed as well.
Some applications of the presented algorithms in computer graphics, geographic information systems, robotics and other areas are also presented.

Contents of the course:

1. Basic data structures for geometric problems.
2. Segment intersection problem.
3. Polygon triangulation.
4. Convex hulls.
5. Point location.
6. Orthogonal range queries.
7. Voronoi diagrams.
8. Discrepancy problem.
9. Delaunay triangulation.
10. Robot motion planning.
11. Binary space partitions.

Recommended reading:

• M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Algorithms and Applications, Springer, 1997.
• F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.
• J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1994.
• H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.

Convergence Acceleration Methods

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written and/or oral examination
Semester: summer, 2008/2009

Prerequisites:

It is recommended that candidates accomplish the courses in Calculus and Numerical Analysis.

Objective of the course:

Sequences and series occur frequently in computational problems. However, it happens quite often that we have to do with so slowly convergent sequences or series that using them is impractical. For that reason methods of convergence acceleration are proposed which enable to solve some problems considered as hard or even unsolvable in practice.
We start with a short introduction of theoretical character. Next we discuss the most efficient methods and algorithms, as Epsilon algorithm and its generalizations, Richardson process (remember its application leading to the Romberg method of numerical integration), Levin transformations, Overholt process, iterated Delta Square method.
In the remaining part of the course, we give examples of applications of the algorithms in summing series, solving linear systems, computing zeros of functions, numerical integration and differentiation.
There will be a large portion of assignments related to practical implementation of algorithms and doing computational experiments.

Contents of the course:

1. Linear recurrence equations
   Difference operators. First-order recurrences. General theory of higher-order recurrences. Numerical solutions of recurrence equations.
2. Continued fractions
   Introduction. Equivalence transformations. Convergence.
3. Introduction to extrapolation methods
4. Extrapolation algorithms
   The Havie-Brezinski algorithm, or E-algorithm. Richardson extrapolation. Shanks transformation (epsilon algorithm). Overholt transformation. Theta transformation. Iterated Delta Square process.
5. Applications
   Sequences and series. Continued fractions. Numerical integration. Solving differential equations.

Recommended reading:

• C. Brezinski, M. Redivo Zaglia, Extrapolation methods, North-Holland, 1991.
• L. Lorentzen, H. Waadeland, Continued fractions with applications, North-Holland, 1992.
• J. Wimp, Sequence transformations and their applications, Academic Press, 1981.
• J. Wimp, Computation with recurrence relations, Pitman Publ., 1984.

Course of programming in Maple and Matlab

Type: course of programming tools ECTS: 5 credits Hours: 15h lectures, 45h labs Assessment: programming projects Semester: summer

Prerequisites:

• Algebra
• Calculus

Objective of the course:

Nowadays, every programmer is facing lots of mathematical problems. Solving them on a paper takes time and puts us in danger of making mistakes and getting wrong solutions. The material of this course covers two popular mathematics computation systems, namely Maple and Matlab. Maple contains advanced symbolic computation tools, which makes solving problems from the area of discrete mathematics and calculus fast and simple. Matlab was created mainly for algebra, it has been optimized for handling problems involving matrices. Both these languages are easy to learn, their syntax is very intuitive, which allows to concentrate on the mathematical side of the problem and avoid dealing with programming intricacies. Moreover, variety of graphical tools in both systems enables fast and attractive visualization of computed solutions.

Contents of the course:

1. Maple system,
2. Matlab system.

Recommended reading:

• Maple 11 language reference manual.
• Martha L. Abell, James Braselton, Maple V by example, Boston 1994.
• First Leaves: a tutorial introduction to Maple, Waterloo Maple Publ.
• Desmond J. Higham, Nicholas J. Higham, Matlab guide, Philadelphia 2000.
• Patrick Marchand, Graphics and GUIs with Matlab, CRC Press 1999.

Cryptography

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written examination
Semester: summer

Objective of the course:

The aim of the course is presenting modern cryptographic techniques used for encryption, authentication, secure communication and more complex protocols. The focus of the course will be both on practical methods currently used in computer systems and mathematical foundations of these methods.

Contents of the course:

1. Basic cryptographic functions, symmetric cyphers, asymmetric cyphers, hashing etc.
2. Basic cryptographic protocols, secret sharing, bit commitment, e-cash, e-voting.
3. Symmetric algorithms, AES, DES and extensions, IDEA, RC5.
4. Encryption modes, ECB, CBC, CFB, OFB.
5. Differential cryptanalysis, linear cryptanalysis, side channel attacks.
6. Asymmetric algorithms, RSA, ElGamal.
7. Hashing functions, based on discrete logarithm, MD5.
8. Message authentication codes (MAC).
9. Pseudorandom generators, LFSR, BBS, A5 and stream ciphers.
10. Digital signatures, ElGamal, DSA, blind signatures, subliminal channel, undeniable signatures.
11. Authentication, challenge and response, interactive proofs, zero knowledge proofs, Shnorr protocol, digital signatures by authentication.
12. Key management, key agreement, Diffie-Helman and similar protocols.
13. Smartcards, PIN.
14. Secure communication, Kerberos, SSH, SSL, VoIP.
15. Encryption of file systems.
16. Elliptic curves cryptography.

Recommended reading:

• D.R. Stinson, Cryptography. Theory and Practice, 3rd Edition, 2005
• A.J. Menezes, P.C van Oorschot, S.A. Vanstone , Handbook of Applied Cryptography, 1996
• W. Stallings, Cryptography and Network Security, 4th Edition, 2006
• O. Goldreich, Foundations of Cryptography, vol. 1 (2001), vol. 2, (2004)
• B. Schneier, Practical Cryptography, 2003

Data Compression

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written examination
Semester: summer, 2007/2008

Prerequisites:

It is recommended that candidates accomplish the courses in Calculus, Algebra, Discrete Mathematics and Algorithms and Data Structures.

Objective of the course:

The course covers main lossless and lossy compression techniques and algorithms. Some of the methods are analyzed formally, efficiency of compression and implementations are discussed. Specific standards and algorithms such as zip, gzip, GIF, JPEG, MPEG, mp3, etc. will also be presented.

Contents of the course:

1. Data modeling, introduction to information theory, Kolmogorov complexity.
2. Huffman coding, extended and dynamic Huffman codes.
3. Arithmetic coding, standard JBIG.
4. Dictionary techniques (LZ77, LZ78) and their applications (GIF, TIFF, zip).
5. Predictive coding (ppm, Burrows-Wheeler coding, JPEG-LS)
6. Scalar and vector quantization.
7. Lossless audio and image compression: differential encoding (DPCM), transform and wavelet coding (JPEG, JPEG2000), subband coding.
8. Video compression (MPEG-1, MPEG-2, MPEG-4, MPEG-7).

Recommended reading:

• D. Salomon, Data Compression, The Complete Reference, Springer, 3rd Edition, 2004.
• K. Sayood, Introduction to Data Compression, 2nd Edition, Morgan-Kaufman, 2000.
  

Discrete Mathematics

Prerequisites:

High school course in mathematics and the course in Calculus

Objective of the course:

Presenting elements of mathematics necessary in analysis of algorithms.

Contents of the course:

Elements of Algebra and Number Theory

1. Integer valued functions, modular arithmetic, rounding of numbers - ceiling and floor operations, mergesort algorithm.
2. Asymptotic behaviour of functions, applications to estimation of time complexity of algorithms.
3. Division of numbers, Euclid algorithm.
4. Fibonacci numbers.
5. Prime numbers and relatively prime numbers. Factorization. Euler function. Latin squares. Chinese reminder theorem. Euler's theorem.

Combinatorics

1. Permutations, combinations, partitions (of a set, of a number), Burnside's lemma.
2. Methods of generating simple combinatorial objects.
3. Examples of simple problems defined by recursion.
4. Solving recurrence equations. Generating functions.
5. Catalan numbers.
6. Inclusion-exclusion principle.

Graph theory and poset theory

1. Relations of order and equivalence, examples.
2. Linear extensions of ordered sets - application to constructions of sorting algorithms.
3. Definition and examples of lattices, distributive lattices and Boolean algebras.
4. Definition and examples of graphs, full graphs (cliques), bipartite graphs, directed graphs, degree of a vertex.
5. Paths and cycles in graphs: connected graphs and bipartite graphs.
6. Trees - equivalence of different definitions.
7. Computer representations of graphs.
8. BFS and DFS algorithms of graphs search.
9. Minimal spanning trees (MST) - Kruskal and Prim-Dijkstra algorithms.
10. Transitive closure of graphs: Dijkstra algorithm and Warshall algorithm. Complexity of problem.
11. Eulerian paths and cycles.
12. Hamiltonian paths and cycles. Ore's theorem and polynomial reduction of path problem to cycle problem and vice-versa.
13. Planar graphs. Kuratowski's Theorem, Wagner's Theorem and Euler's formula.
14. Graph colouring: applications - planning an examination session. Sequential algorithm and 5-colour theorem.

Elements of probability theory

1. Sample space, elementary events, probability in discrete probability spaces.
2. Conditional probability. Bayes' theorem.
3. Independent events. Bernoulli trial.
4. Random variables, expected value and variance. Laws of great numbers.
5. Probability in continuous sample spaces. Normal distribution.

Recommended reading:

• W. Feller, An Introduction to Probability Theory,
• M.Ch. Klin, R. Poeschel, K. Rosenbaum, Applied Algebra for Mathematicians and Information Scientists,
• R.L.&nbsp Graham, D.E.&nbsp Knuth, O.&nbsp Patashnik, Concrete Mathematics,
• J.L. Kulikowski, Zarys teorii grafów (in Polish),
• W. Lipski, Kombinatoryka dla programistów (in Polish),
• E.M. Reingold, J. Deo, N. Nievergelt, Combinatorial Algorithms,
• K.A.&nbsp Ross, Ch.B.&nbsp Wright, Discrete Mathematics,
• M.M. Sysło, N. Deo, J. S. Kowalik, Discrete Optimization Algorithms,
• R.J.&nbsp Wilson, Introduction to Graph Theory,
• M. Zakrzewski, T. Żak, Kombinatoryka, prawdopodobieństwo i zdrowy rozsądek (in Polish).

Distributed Algorithms

Type: advanced, optional course
ECTS: 6
Hours: 30h lectures, 30h exercises
Assessment: written examination
Semester: winter, 2007/2008

Prerequisites:

Algorithms and data structures

Objective of the course:

The goal of this course is to introduce the students to the fundamental
algorithms and protocols that are commonly used in distributed
computing. Both synchronous and asynchronous models are considered and
generally it is assumed that there is no access to a shared memory. The
main inter-process communication mechanism is message passing

Contents of the course:

1. Synchronous and asynchronous models of distributed computing.
2. Leader election and distributed consensus algorithms
3. Basic graph algorithms in distributed protocols:
   finding a spanning tree and breadth-first search.
4. Failure tolerant algorithms in distributed computing
5. Network resource allocation.

Recommended reading:

• N.A. Lynch, Distributed Algorithms,
  Morgan-Kaufmann Publishers, 1996.
• G. Tel, Introduction to Distributed Algorithms,
  Cambridge University Press, 1994
• H. Attiya, J. Welch, Distributed Computing, McGraw-Hill, 1998

Formal Languages and Computational Complexity

The course is obligatory for the 2nd stage studies (M.Sc. degree) but also available and recommended for the 1st stage studies (Bachelor degree). Due to this fact the main course is in Polish, but classes and tutor assistance or tutorials in English are available. The contents of the course states background for most of theoretic subjects in computer science, hence for many advanced courses.

Prerequisites:

It is recommended that candidates accomplish the courses in Logic for Computer Science and Discrete Mathematics.

Contents of the course:

1. Regular expressions and languages. Finite automata. Equivalence of deterministic finite automata, nondeterministic finite automata and regular expressions.
2. Pumping lemma. Myhill-Nerode theorem and automata minimization.
3. Context-free grammars and languages. Greibach and Chomsky normal forms. Pushdown automata. Equivalence of context-free grammars and pushdown automata.
4. Pumping lemma and Ogden's lemma.
5. Deterministic and unambiguous languages.
6. Theoretical models of computing machines. Sequential computation model: Turing machine and its modifications, random-access machine. Nondeterministic Turing machine. Sample reductions among different models. Kleene's definition. Church's thesis.
7. Notion of recursive and recursively enumerable sets. Encoding and enumeration of Turing machines, Universal Turing machine. Undecidability of the Halting problem. Other examples of undecidable problems. Rice's theorem.
8. Undecidability of the Post Correspondence Problem and the Word Problem for semigroups. Notes on undecidability of arithmetics.
9. Time and space computational complexity of Turing machines. Dependencies between time and space in computations. Notion of complexity class and major examples (LOGSPACE, NLOGSPACE, PTIME, UP, NP, PSPACE, EXPTIME). Examples of problems requiring exponential time and space.
10. NP-completeness, the idea of this notion, examples, Cook's theorem, reductions among problems, the P versus NP problem.
11. Notion of complexity for parallel models, PSPACE as the upper-bound of the complexity of parallel computations in polynomial time, information about NC class, its subclasses and structure.

Recommended reading:

• Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Series in Computer Science and Information Processing (1974).
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley (1979).
• Neil D. Jones, Computability and Complexity From a Programming Perspective, MIT press (1997).

Functional Programming

Type: elementary, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h laboratory
Assessment: written examination
Semester: winter

Prerequisites:

It is recommended that candidates accomplish the course in Programming.

Objective of the course:

The main goal is to acquaint students with different programming paradigm and pointing out situations where it may be preferable.

Contents of the course:

Functional style of programming is based on expression evaluation in opposition to imperative programming which explicitly uses program state modified by instructions. Students will be taught basic notions and techniques of functional programming using one of ML family programming languages (SML, Ocaml or Haskell). Topics covered include:

• type systems with parametric polymorphism,
• higher order functions,
• tail recursion,
• pattern matching,
• signatures,
• structures and functors,
• evaluation strategies.

Recommended reading:

Introduction to Computer Graphics

Type: elementary, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h laboratory
Assessment: programming tasks and theoretical examination
Semester: winter

Prerequisites:

It is recommended that candidates accomplish the courses in Algebra, Algorithms and Data Structures and have C/C++ programming ability.

Contents of the course:

1. Rasterization algorithms.
2. Antialiasing solutions.
3. Clipping and filling algorithms.
4. Geometrical transformations in homogenous coordinates.
5. View systems.
6. Model and scene representations.
7. Human visual system and colour models.
8. Shading.
9. Hidden surface removal.
10. Basic ray tracing and texturing

Recommended reading:

• J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Computer Graphics Principles and Practice , 2nd edition, Addison-Wesley, Reading, Massachusetts 1992.
• P.Shirley, Fundamentals of Computer Graphics, A.K. Peters 2002.

Logic for Computer Science

Prerequisites:

High school course in mathematics

Contents of the course:

1. Basic notions in set theory and operations on sets: union, intersection, Cartesian product, power set, relation, function, equivalence relation, quotient set.
2. Cardinalities of sets, finite and infinite sets, countable sets, Cantor's theorem, Cantor-Bernstein theorem.
3. Partial orderings, least and minimal elements, least upper bounds, linear orderings, well-founded orderings, fixed-point theorems.
4. Syntax and semantics of propositional and first-order logic, satisfiability, validity, consistency.
5. Unification and resolution.
6. Theorem proving; notes on Hilbert, natural deduction and sequent calculi.

Logic Programming

Type: elementary, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 15h exercises, 15h laboratory
Assessment: written examination
Semester: winter, 2007/2008

Prerequisites:

It is recommended that candidates accomplish the course in Logic for Computer Science and have quite high programming skill, preferably in functional programming (e.g. accomplished the course in Programming).

Contents of the course:

1. Programming in pure Prolog (with arithmetic).
2. Advanced Prolog features (cuts, asserts, second order predicates, all solutions predicates, negation, ...).
3. Prolog programming techniques.
4. The relation between Prolog and logic programming.
5. Operational, fixedpoint and model semantics for logic programs.
6. Constraint logic programming (theory and practice).
7. Writing constraint solvers (using Constraint Handling Rules).
8. The ways of combining logic programming paradigm with other programming paradigms (functional and object oriented, Curry and Logtalk).

Mathematical Methods of Computer Graphics

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written examination
Semester: summer, 2007/2008

Prerequisites:

It is recommended that candidates accomplish the courses in Calculus, Numerical Analysis and Introduction to Computer Graphics .

Objective of the course:

The aim is to present the main mathematical tools used in the computer graphics for description of curves and surfaces. One possible application of these tools will be given later in the course Realistic Computer Graphics.
Some well-known methods, as, e.g., polynomial or spline interpolation of functions of one variable, will be discussed from a new point of view. Also, some other modern techniques of curve modelling will be described. A vast part of the course is devoted to surface modelling. Some efficient interpolation and approximation algorithms will be discussed.

Contents of the course:

1. Introduction
   Basic notions. Types of curve and surface representation.
2. Curve modelling using interpolation
   Polynomial and spline interpolation. Bezier curves. B-spline curves.
3. Approximation of curves
   Types of approximation. Approximation using B-splines. B-splines with free knots. Application of curve approximation in graphics.
4. Surface modelling
   Tensor product representation of surfaces. Bezier surfaces. B-spline surfaces. Coons and Gordon surfaces.

Recommended reading:

• P. Dierckx, Curve and Surface Fitting with Splines, Clarendon Press, Oxford 1993.
• G. Farin, Curves and Surfaces for CAGD. A Practical Guide, Morgan-Kaufmann, 2002.
• J.Hoschek, D.Lasser, Fundamentals of Computer Aided Geometric Design, AK Peters, Wellesley (Ma) 1993.

Modelling of Natural Problems

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises/laboratory
Assessment: written examination
Semester: summer, 2007/2008

Prerequisites:

Calculus, Numerical Analysis.

Contents of the course:

The lecture is an introduction to the computer modeling of the surrounding nature like:

• epidemiological problems,
• predator–prey model,
• gravitational motion – pendulum, spring oscillations, ballistic problems with the environmental resistance or without,…

All considered problems are usually described by ordinary differential equations, which in most cases have no solutions in closed formulas. For getting to know the approximate solutions of considered problems the numerical methods must be applied.

Another interesting and beautiful way for modeling forms familiar in nature (snowflake, lightning, cloud, fern,…) is generation of fractals. Some basic features of fractals and elementary algorithms for their generation are described.

The purpose of the lecture is to present some selected numerical methods for determining approximate solutions of ordinary differential equations. The basic form of this presentation is animation. A very comfortable numerical computing environment and programming language is MATLAB which allows easy plotting of functions and producing two- or three-dimensional graphics as well.

Natural Language Processing

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises/laboratory
Assessment: written and/or oral examination
Semester: winter, 2008/2009

Prerequisites:

It is recommended that candidates accomplish the courses in Programming, Discrete Mathematics and be able to use any higher higher level programming language.

Contents of the course:

1. Objectives of computational linguistics (CL), the relations between CL and other areas of artificial intelligence.
2. Basic linguistics concepts (sentence, discourse, word, part of speech, parse tree, etc, corpora).
3. Collocations.
4. N-Gram based language analysis.
5. Word sense disambiguation.
6. Part of speech tagging.
7. Using context free grammars (with features) to describe natural languages.
8. Chart parsing for context free languages.
9. Probabilistic context free grammars (and their lexicalised versions and variations).
10. Mildly Context Sensitive Languages (tree adjoining grammars, linear indexed grammars, categorial grammars, head grammars): properties, parsing algorithms, the way of using in natural language modeling.
11. Head-driven phrase structure grammar (HPSG): properties, parsing algorithms, the way of using in natural language modeling.
12. Language pragmatics: discourse structure, conversational agents, natural language generation, machine translation.

Neural Networks

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h laboratory
Assessment: written examination
Semester: winter, 2007/2008

Prerequisites:

Required knowlege obtains contents of the course Numerical Analysis, a knowlegde of ideas of probability and statistics and Matlab programming is also necessary.

Objective of the course:

Students should obtain not only theoretical background how various artificial neural networks work, but also acquire the ability of dealing with practical problems of contemporain data analysis.
Durig lab classes assisting the course sudents obtain problems from the domain of Pattern Recognition, based on real data, in particular from the domain of discriminant analysis and clustering (medical data, images, MNIST base). Available software in Matlab: Neural Network Toolbox, Netlab, Som Toolbox.

Contents of the course:

1. Feedforward neural networks,
2. Multilayer perceptron,
3. Hebbian learning,
4. Self-organizing maps,
5. Radial basis networks,
6. Visualization of multivariate data: survey of methods available in the Netlab package.

Recommended reading:

• Ch. M. Bishop, Neural Networks for Pattern Recognition. Clarendon Press, Oxford, 1996
• Rosaria Silipo, Neural Networks, Chapter 7 from: M. Bertold, D.J. Hand (eds.) Intelligent Data Analysis, Springer Berlin 1999, pp. 217-268.
• Ian Nabney, Netlab: Algorithms for Pattern Recognition. Springer 2001.
• J. Vesanto, J. Himberg, E. Alhoniemi, J. Parhankangas, SOM Toolbox for Matlab 5. Som Toolbox Team, Helsinki University of Technology, Finland, Libella Oy, Espoo 2000, 1-54.
• R. O. Duda, P.E. Hart, David G. Stork, Pattern Classification, 2nd Edition, Wiley 2001.
• S. Osowski, Sieci neuronowe w ujęciu algorytmicznym. WNT Warszawa 1996. (in Polish)
• A. Bartkowiak, Sieci neuronowe 2005/2006 – Notatki, Instytut Informatyki UWr. http://www.ii.uni.wroc.pl/~aba/teach/ (in Polish)
.

Neural Networks in Pattern Recognition

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h laboratory
Assessment: written and/or oral examination
Semester: summer, 2008/2009

Prerequisites:

The knowledge of neural networks, principles of statistics and Matlab programming are required.

Contents of the course:

1. Patterns in data,
2. Similarity and dissimilarity,
3. Finding decision boundaries,
4. Sensivity and specificity,
5. ROC curves,
6. Parzen windows and kernel methods,
7. Support vector machines,
8. Boosting and bagging,
9. Image analysis,
10. Problems with large data,
11. One class classifier,
12. Outliers.

A part of the course are laboratory classes where students obtain advanced problems from the domain of Pattern Recognition. The problems concern real data, and are formulated in terms of discriminant analysis and Clustering (medical data, recognition of persons on the base of their palm scans or faces).
Available software in Matlab: Neural Network Toolbox, Netlab, and some specialistic Matlab software developed in Western Research Centers.

Recommended reading:

• R. O. Duda, P.E. Hart, David G. Stork: Pattern Classification, 2nd Edition, Wiley 2001.
• A. Webb, Statistical Pattern Recognition, 2nd Edition. Wiley 2002, Reprint September 2004.
• D. G. Stork and Elad Yom-Tov, Computer Manual in MATLAB to accompany Pattern Classifcation, Wiley Interscience, 2004,
• Elżbieta Pękalska, Robert P.W. Duin, The Dissimilarity Representation for Pattern Recognition. Foundations and Applications. Word Scientific 2005,
• Steve Gunn, Support Vector Machines for Classifcation and Regression. ISIS Technical Report. 14 May 1998. Image, Speech and Intelligent Systems Group, Univ. of Southampton.
• Francesco Camastra. Kernel Methods for Computer Vision. Theory and Applications, (citeseer.ist.psu.edu/483015.html)
• Alessandro Verri, Support Vector Machines for Classifcation.
Slides 1 - 32.
• Massimiliano Pontil and Alessandro Verri, Support Vector Machines for 3-D Object Reconition. IEEE Trans. on Pattern Analysis and Machine Intelligence, V. 20, Nb. 6, 637-646, 1998. (citeseer.ist.psu.edu/pontil98support.html)
• A. Bartkowiak, Neural Networks and Pattern Recognition. Lecture notes Fall 2004. Institute of Computer Science, University of Wrocław, pp. 1-56, http://www.ii.uni.wroc.pl/~aba/teach/roadmap.pdf

Numerical Analysis

Prerequisites:

It is recommended that candidates accomplish the courses in Calculus.

Contents of the course:

1. Error analysis
   Floating-point arithmetic. Conditioning. Numerically stable algorithms.
2. Solving nonlinear equations
   Fixed point iteration. The bisection method. Newton's method. Method of false position. Secant Method. Algebraic equations - Laguerre's method. Deflation process. Bairstow's method.
3. Interpolation
   Polynomial interpolation problem - Lagrange formula. Error analysis. Newton's interpolation formula. Hermite interpolation. Spline interpolation.
4. Approximation
   Least squares polynomial approximation - Orthogonal polynomials. Best approximation polynomial. Uniform approximation - Chebyshev's alternation theorem. The Remez algorithm for constructing the best polynomial.
5. Numerical integration
   Linear quadratures. Error and order of the quadrature. Convergence of quadratures, Interpolatory quadratures. Newton-Cotes quadratures. Trapezoid and Simpson's quadrature rules. Romberg's algorithm. Gaussian quadratures.
6. Solving systems of linear equations
   Condition number of the problem. LU decomposition. Gaussian elimination method. Numerical stability of elimination with pivoting. Iterative methods for solving systems of linear equations.

Recomended reading:

• D. Kincaid, W. Cheney, Numerical Analysis, 3rd Edition., Brooks/Cole, 2002,
• W. Gautschi, Numerical Analysis. An Introduction, Springer-Verlag, 1997,
• A. Quarteroni, R. Sacco, F. Saleri, Numerical Mathematics, Springer-Verlag, 2000.

Online Algorithms

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written examination
Semester: summer, 2007/2008

Prerequisites:

It is recommended that candidates accomplish the courses in Algorithms and Data Structures and Discrete Mathematics.

Objective of the course:

Many algorithms for real-life problems, like routing in networks, processor or web caching, or scheduling, have to work in online fashion and make decisions without knowing the future. This lecture covers the design and analysis of such algorithms.
We will be interested in approximating the optimal solution and show how to prove concrete guarantees on the quality of such approximations. The presented material is based on the books (listed below), current scientific papers and materials from similar lectures from other universities in the world.

Contents of the course

1. Introduction to online algorithms, Ski Rental Problem as an example of rent-or-buy class of problems. Foundations of competitive analysis, notion of k-competitiveness.
2. Amortized analysis and potential functions -- examples.
3. Paging algorithms in managing the cache memory of the processor. LFD (Least-Recently-Used) and FIFO (First-In-First-Out) algorithms, their analysis.
4. Randomized paging. Random Marking algorithm.
5. Comparison of adaptive and oblivious adversaries. Yao min-max principle in proving lower bounds for competitiveness of randomized algorithms.
6. Page migration and page replication in networks, randomized and deterministic algorithms. Generalization to File Allocation problem, randomized algorithm for File Allocation.
7. K-server problem, algorithms, k-sever hypothesis.
8. List update problem. Algorithms: Move-to-Front, BIT, and Timestamp.
9. Scheduling algorithms. Scheduling on identical machines (Graham's algorithm). Scheduling on on-identical machines.

Recommended reading:

• Alan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press, 1998.
• Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms. Cambridge University Press, 1995.
  

Programming

Prerequisites:

It is recommended that a candidate has accomplished the course Logic for Computer Science

Contents of the course:

1. Elements of software engineering.
2. Inductive definitions, recursion and proofs by structural induction.
3. Regular and context-free grammars. Lexical analysis and parsing. Lexer. Parser. Concrete and abstract syntax trees.
4. Semantics of programming languages. Structural operational semantic. Denotational semantic. Recursive definitions and partial functions.
5. Hoare logic and proving program correctness. Loop invariants. Bottom-up and top-down program synthesis.
6. Structure of modern programming languages. Names, memory cells and values; control constructs; functions and procedures; dynamic data structures; exceptions. Types, strong typing, type reconstruction.
7. Compilation. Scope of variables, function invocation and memory management. Block-structured languages, activation records, memory allocation for local and global variables. Higher-order functions, funarg problem. Automatic memory management and garbage collection.
8. Algebraic specification of data types. Inductive types (lists, trees, stacks, queues etc.). Inductive proofs of their properties.
9. Modules, generics and data abstraction. Data encapsulation. Solutions in modern languages. Generics (functors in SML, generic packages in Ada, templates in C++).
10. Functional programming. Declarative vs. imperative programming. Side effects. Reduction orders.
11. Object-oriented programming, OO methodology, objects and classes, abstract data types vs. classes, subtyping vs. inheritance, classless languages, Smalltalk. Object-oriented programming style in C++. Java.
12. Concurrency. Basic synchronization methods: semaphores, monitors, conditional critical regions. CSP. CCS. Asynchronous model. Distributed programming. Channels, threads, coroutines. Concurrency in Ada and other programming languages. The five philosophers problem. Flow-based programming.
13. Logic programming. Prolog.

Randomized Algorithms

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written and/or oral examination
Semester: summer, 2008/2009

Prerequisites:

It is recommended that candidates accomplish the courses in Algorithms and Data Structures and Discrete Mathematics.

Objective of the course:

During the first part of the lecture an overview of basic randomized techniques in algorithms construction is given. In the second part these techniques are applied to solve some selected classical algorithmic problems.

Contents of the course:

1. The basic notions of probabilistic theory, randomized algorithms and complexity classes.
2. Probabilistic method.
3. Markov chains and random walks.
4. Algebraic techniques in verifying problems and interactive proofs.
5. Applications of randomized techniques to graph algorithms, linear programming, computational geometry and number theory.

Recommended reading:

• R. Motvani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

Realistic Computer Graphics

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h laboratory
Assessment: writing a global illumination rendering system and theoretical examination
Semester: summer, 2007/2008

Prerequisites:

It is recommended that candidates accomplish the courses in Algebra, Introduction to Computer Graphics and have C/C++ programming ability.

Contents of the course:

1. Basics of ray tracing.
2. Accelerating the ray tracing method.
3. How to improve the ray tracing method.
4. Theory of light transport.
5. Different BRDF functions.
6. Theory of Monte Carlo methods.
7. Stochastic ray tracing.
8. Path tracing.
9. Photon tracing and photon maps.
10. Bidirectional path tracing.
11. Radiosity methods.

Recommended reading:

• A.Glassner, Principles of Digital Image Synthesis, Morgan Kaufmann Publ., San Francisco 1995.
• A.Glassner, Introduction to Ray Tracing, Morgan Kaufmann Publ. 1989.
• P.Shirley, Realistic Ray Tracing, A.K. Peters 2000.
• F.Sillion, C.Puech, Radiosity and Global Illumination, Morgan Kaufmann Publ. 1994.
• Various source materials: PhD theses, conference publications.

Seminar: 3D Computer Vision

Prerequisities:

It is recommended that candidates accomplish the courses in Algebra and Fundamentals of Computer Graphics.

Contents of the seminar:

Recovering 3D geometry and scene from photographs.
Through the semester we start with epipolar geometry and feature extraction basics to formulate the eight point algorithm which extracts the translation and rotation between two views of a three dimensional scene. Next we consider calibrated and uncalibrated cases, moving objects and multiple views.

Recommended reading:

• Yi Ma, S. Soatto, J. Kosecka, S.Shankar Sastry, An Invitation to 3D Vision, Springer Verlag 2004.

Seminar: Hot Topics in Computer Graphics

Type: optional course
ECTS: 3-4 credits
Hours: 30h seminar
Assessment: presentation
Semester: summer, 2007/2008

Prerequisites:

Knowledge of principles of 2D/3D computer graphics

Contents of the seminar:

Talks based on the latest Siggraph and Eurographics conference publications. The range of subjects includes rendering algorithms, geometrical modeling, texturing and computational photography.

Recommended reading:

Papers from Siggraph and Eurographics conferences and workshops.

Seminar: Online Algorithms

Prerequisites:

It is recommended that candidates accomplish the course in Discrete Mathematics, Algorithms and Data Structures. Basic knowledge of online algorithms is helpful.

Objective of the seminar:

During this seminar, we present classical and/or interesting online algorithms, which were not presented on the Online Algorithms lecture. Contributions from the area of approximation algorithms are also welcomed. Seminar will be based on papers from top theoretical computer science conferences and on the book by Borodin and El-Yaniv (see below).

Recommended reading:

• A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.

Text Algorithms

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written and/or oral examination
Semester: winter, 2007/2008

Prerequisites:

It is recommended that candidates accomplish the course in Algorithms and Data Structures.

Objective of the course:

The subject of the course are current problems and latest solutions in the area of processing and searching textual data. In the area one can find both difficult and involved ideas and simple but brilliant algorithmic constructions.

Contents of the course:

1. Analysis and applications of pattern matching algorithms: searching in compressed data, filtering, approximate searching.
2. Text similarity (common substrings, superstrings, edit distance, alignment).
3. Data structures for texts: suffix trees and arrays, inverted files.
4. Textual databases: data structures, storing and searching.

Recommended reading:

• M.Crochemore, W.Rytter Jewels of Stringology,
• ed. A.Appostolico, Z.Galil Pattern matching algorithms
• D.Gusfield Algorithms on Strings, Trees and Sequences

Theoretical Foundations of Communication in Networks

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h exercises
Assessment: written examination
Semester: summer, 2007/2008

Prerequisites:

It is recommended that candidates accomplish the courses in Algorithms and Data Structures and Discrete Mathematics.

Contents of the course

1. Formal definition of the problem of routing in a network. Path selection and packet switching. Congestion and dilation.
2. Analysis of routing in a ring network. Backward analysis.
3. Sample networks. Permutation networks. Butterfly, hipercube and mesh networks.
4. Adaptive routing algorithms. Chosing a system of paths in a permutation network. The Hall Theorem.
5. Oblivious routing algorithms. Permutation routing in a hypercube. Note on a lower bound on congestion (Borodin and Hopcroft). Valiant's Trick.
6. Time complexity of a packet routing. Offline switching. Almost optimal algorithm of Leighton, Maggs and Rao - the probabilistic method and Lovas Local Lemma.
7. Online switching. Random rank protocol.
8. Routing in continuous model. Adverasial queing. Stability of the packet routing algorithm. Stability of the SIS algorithm (Shortest in System) and unstability of the FIFO algorithm (First In First Out).
9. Virtual circuit routing. The best routong algorithm for a mesh. Note on the Raecke Algorithm for routing in universal networks.

Recommended reading:

• F.T.Leighton, Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. Morgan Kaufmann Publishers, Inc., 1992.

Theoretical Foundations of Programming Languages

Type: advanced, optional course
ECTS: 6-8 credits
Hours: 30h lectures, 30h excercises
Semester: summer

Prerequisites:

It is recommended that candidates accomplish the courses in Logic for Computer Science, Programming.

Contents of the course:

Programs and programming languages will be considered as mathematical objects, whose properties can be precisely formulated and proved. Following topics will be covered:

1. formal semantics,
2. type systems,
3. polymorphism,
4. subtyping,
5. theoretical foundations of object-oriented languages.

Recommended reading:

• Abadi M., Cardelli L., A Theory of Objects. Springer-Verlag, 1996
• Bruce K.B., Foundations of Object-Oriented Languages. Types and Semantics. MIT Press, 2002.
• Castagna G., Object-Oriented Programming. A Unified Foundation. Birkhauser, 1997.
• Goguen J., Malcolm G., Algebraic Semantics of Imperative Programs. MIT Press 1996.
• Mitchell J.C., Foundations of Programming Languages. MIT Press, 1996.
• Pierce B., Types and Programming Languages. MIT Press, 2002.
• Reynolds J.C., Theories of Programming Languages. Cambridge University Press, 1998.

Exchange Studies

We are a member of the Socrates-Erasmus Programme and welcome students from Europe and all over the world to take lectures in English in our Institute.

Research

Research groups in the Institute

Group of Programming Languages Head:Jerzy Marcinkowski, Ph.D., Professor of University of Wrocław Group of Numerical Methods Head:Stanisław Lewanowicz, Ph.D., Professor Group of Programming Methods Acting head: Helena Krupicka, Ph.D. Group of Computational Complexity and Analysis of Algorithms Head: Krzysztof Loryś, Ph.D., Professor of University of Wrocław

• Research interest: approximation, probabilistic and on-line algorithms; parallel, distributed and mobile computations; cryptology, computational complexity, formal languages, and theory of automata.
• Popularization of informatics: Polish Olympiad in Informatics, Programming Contest "Wielka Przesmycka".

previous

next

up

Staff and structure

Teaching
admin  2006-03-20 12:42   

Publications

Publications by years 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
Publications by the Research Groups of the Institute
• Group of Programming Languages: 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
• Group of Numerical Analysis: do 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
• Group of Programming Methods: 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
• Group of Theoretical Computer Science (later divided into group of Programming Languages and group of Computational Complexity and Algorithms: till 1996
• Group of Computational Complexity and Algorithms: 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008

Research projects

Research projects financed by Ministry of Science and Higher Education:

1. Conjunctive grammars and language equations
   Leader: prof. dr hab. Krzysztof Loryś
   Duration: 2008-2010
2. Combinatorial Analysis of Distributed Algorithms
   Leader: Mirosław Kutyłowski, Ph.D. Prof. (Faculty of Fundamental Problems of Technology, Wroclaw University of Technology)
   Duration: 2008-2010
3. Approximation and online algorithms
   Leader: Krzysztof Loryś, Ph.D. Prof.
   Duration: 2007-2010
4. Security of computer programs
   Leader: Leszek Pacholski, Ph.D. Prof.
   Duration: 2006-2009
5. Decidability of some logical theories motivated by problems in computer science
   Leader: Jerzy Marcinkowski, Ph.D.
   Duration: 2006-2009
6. Dynamic networks: exploration and data management
   Leader: Marcin Bieńkowski, Ph.D.
   Duration: 2006-2008
7. Construction and analysis of approximation algorithms for graph problems
   Leader: Krzysztof Loryś, Ph.D. Prof.
   Duration: 2006-2008
8. Automata theory and formal languages' techniques in pattern matching,
   security, computational complexity, and natural language processing
   Leader: Tomasz Jurdziński, Ph. D.
   Duration: 2006-2008
9. Applications of the notion of type to verification and certification of computer programs
   Leader: Leszek Pacholski, Ph. D. Prof.
   Duration: 2000-2003
10. Parallel and sequential approximation algorithms for combinatorial and geometric problems
    Kierownik: Krzysztof Loryś, Ph. D. Prof.
    Duration: 2000-2002
11. Informatics Education in Polish School System
    Leader: Maciej M. Sysło, Ph. D. Prof.
    Duration: 2001-2002
12. Cost reduction of Monte Carlo image synthesis using Minkowski operators and offsets
    Leader: Leszek Pacholski, Ph. D. Prof.
    Duration: 2000-2001
13. Applications of recurrence relations in the theory of orthogonal series
    Leader: Stanisław Lewanowicz, Ph. D. Prof.
    Duration: 1999-2001

Habilitations and PhD Dissertations

Habilitations (since 1981)

Tomasz Jurdziński Automaty skracające i inne uogólnienia hierarchii Chomsky'ego (17.03.2009) Lidia Tendera Problem spełnialności i skończonej spełnialności pewnych wariantów fragmentu strzeżonego (13.05.2008) Hans de Nivelle Using resolution as decision procedure (2008) Witold Charatonik Więzy mnogościowe (12.11.2002) Wiesław Szwast Złożoność obliczeniowa problemu spełnialności dla pewnych rozszerzeń słabych logik (11.12.2001) Marek Piotrów Konstrukcja asymptotycznie optymalnych sieci sortujących odpornych na błędne działanie komparatorów (20.11.2001) Krzysztof Loryś Złożoność obliczeniowa kompakcji w równoległych modelach obliczeń (12.12.2000) Maciej Liśkiewicz Złożoność obliczeniowa pamięciowo ograniczonych interakcyjnych systemów "dowodzących" (7.03.2000) Jerzy Marcinkowski Achilles, Turtle, and Undecidable Boundedness Programs for Small Datalog Programs (7.12.1999) Mirosław Kutyłowski Złożoność obliczeniowa wielogłowicowych automatów jednostronnych (1992) Krystyna Ziętak Aproksymacja macierzy i związane z nią równania macierzowe (1990) Stanisław Lewanowicz Związki rekurencyjne dla współczynników i momentów Jacobiego (1988) Jerzy Kucharczyk Algorytmy analizy skupień w języku ALGOL 60 (1986) Edward Neuman Metody funkcji sklejanych w analizie numerycznej (1985) Maciej M. Sysło Struktura cykli w grafach i grafy zewnętrznie płaskie, teoria i algorytmy (1981)

PhD Disertations (since 1973)

Piotr Wieczorek Modulo Constraints and Typechecking XML Views of Relational Databases Promotor: dr hab. J. Marcinkowski (16.12.2008) Wiktor Zychla eXtensible Multi Security: Security Framework for .NET Promotor: prof. L. Pacholski (21.10.2008) Przemysław Skibiński Reversible data transforms that improve effectiveness of universal lossless data compression Promotor: dr hab. M. Piotrów (3.10.2006) Mirosław Korzeniowski Dynamic Load Balancing in Peer-to-Peer Networks Promotor: prof. Friedhelm Meyer auf der Heide Praca pisana i obroniona w International Graduate School of Dynamic Intelligent Systems, Uniwersytet w Paderborn, Niemcy (5.05.2006) Sebastian Bala Decision Problems on Regular Expressions Promotor: prof. L. Pacholski (21.02.2006) Marcin Bieńkowski Page Migration in Dynamic Networks Promotor: prof. Friedhelm Meyer auf der Heide Praca pisana i obroniona w International Graduate School of Dynamic Intelligent Systems, Uniwersytet w Paderborn, Niemcy (16.09.2005) Katarzyna Paluch Approximation Algorithms for Rectangle Tiling Promotor: prof. K. Loryś (22.02.2005) Paweł Woźny Własności współczynników Fouriera względem semiklasycznych wielomianów ortogonalnych Promotor: prof. S. Lewanowicz (4.01.2005) Piotr Lipiński Evolutionary Data-Mining Methods in Discovering Stock Market Expertise from Financial Time Series Promotorzy: prof. J. Korczak i prof. A. Bartkowiak (18.10.2004) Paweł Keller Obliczanie całek nieoznaczonych funkcji osobliwych lub oscylujących Promotor: prof. S. Lewanowicz (10.06.2003) Emanuel Kieroński O złożoności logiki ze strażnikami z dwiema zmiennymi i z relacjami tranzytywnymi Promotor: prof. L. Pacholski (13.05.2003) Andrzej Łukaszewski Offsets and Minkowski operators for speeding up global illumination methods Promotor: prof. L. Pacholski (11.06.2002) Maciej Gębala Rekonstrukcja poliomin wypukłych Promotor: prof. L. Pacholski (14.05.2002) Ewa Kołczyk Edukacja informatyczna w polskim systemie szkolnym Promotor: prof. M.M. Sysło (Instytut Badań Edukacyjnych w Warszawie, 9.04.2002) Marcin Młotkowski Specification and optimization of the Smalltalk programs Promotor: prof. L. Pacholski (23.10.2001) Tomasz Truderung Polimorficzne typy kierunkowe dla języków programowania logicznego Promotor: prof. L. Pacholski (13.06.2000) Paweł Rychlikowski Polimorficzne typy kierunkowe dla języków programowania logicznego Promotor: prof. L. Pacholski (13.06.2000) Marcin Kik Efektywne sieci komparatorów Promotor: prof. M. Kutyłowski (13.06.2000) Tomasz Jurdziński Aspekty komunikacyjne obliczeń systemów automatów skończonych Promotor: prof. M. Kutyłowski (4.04.2000) Lidia Tendera Problem spełnialności dla rozszerzeń logiki pierwszego rzędu z ograniczoną liczbą zmiennych Promotor: prof. L. Pacholski (20.10.1998) Przemysława Kanarek Realizacja permutacji na sieciach ograniczonego stopnia Promotor: prof. M. Kutyłowski (1997) Zdzisław Spławski Proof-Theoretic Approach to Inductive Definitions in ML-like Programming Language versus Second-Order Lambda Calculus Promotor: prof. L. Pacholski (1996) Grzegorz Stachowiak Generowanie wybranych klas obiektów kombinatorycznych algorytmami minimalnych zmian Promotor: prof. M.M. Sysło (9.03.1995) Witold Charatonik Set constraints in some equational theories Promotor: prof. L. Pacholski (Polska Akademia Nauk, 1995) Jerzy Marcinkowski Decidability problems of Horn clause implications Promotor: prof. L. Pacholski (1993) Witold Karczewski Pewne uogólnienia arytmetycznych ułamków łańcuchowych Promotor: prof. S. Paszkowski (wrzesień 1992) Maciej Liśkiewicz On one-tape Turing machines Promotor: prof. L. Pacholski (1990) Marek Piotrów Counting and the polynomial time hierarchy Promotor: prof. L. Pacholski (1989) Krzysztof Loryś Reversal bounded alternating Turing machines Promotor: doc. L. Pacholski (1989) Mieczysław Wodecki Algorytmy szeregowania zadań w pewnym elastycznym systemie produkcyjnym Promotor: doc. J. Grabowski (1987) Wiesław Szwast Spektra hornowskie Promotor: prof. L. Pacholski (1985) Mirosław Kutyłowski Small Grzegorczyk classes and relations defined by simultaneous recursion and iteration Promotor: prof. L. Pacholski (1985) Andrzej Olejniczak Aproksymacja okresowych w czasie rozwiązań równania parabolicznego drugiego rzędu Promotor: doc. H. Marcinkowska (1984) Mieczysław Szyszkowicz Wyznaczanie kroku całkowania dla metod jednokrokowych rozwiązywania równań różniczkowych zwyczajnych Promotor: doc. R. Zuber (1983) Kostas Skandalis Programowalne funkcje rzeczywiste Promotor: prof. L. Pacholski (1981) Antoni Kościelski Aksjomat determinacji w arytmetyce drugiego rzędu Promotor: prof. L. Pacholski (IMPAN, 10.11.1981) Ewa Gurbiel System programowania przekształceń algebraicznych AMAL Promotor: prof. S. Paszkowski (1979) Helena Krupicka System programowania przekształceń algebraicznych AMAL Promotor: prof. S. Paszkowski (1979) Aleksander Janicki Rozwiązanie i numeryczna aproksymacja zagadnienia Stefano za pomocą nierówności wariacyjnych Promotor: doc. R. Zuber (1978) Jerzy Tomasik Nasycone produkty zredukowane Promotor: prof. L. Pacholski (1977) Adam Szustalewicz Różnicowe aproksymacje operatorów gradientu i dywergencji oraz związane z nimi twierdzenia Weyla o ortogonalnym rozkładzie dla dyskretnych dwuwymiarowych okresowych pól wektorowych Promotor: prof. A. Krzywicki (1977) Stanisław Lewanowicz Konstrukcja związku rekurencyjnego najmniejszego rzędu dla współczynników szeregu Gegenbauera Promotor: prof. S. Paszkowski (1975) Maciej M. Sysło Odwracalność digrafów ogólnych i jej realizacja Promotor: doc. dr L. Szamkołowicz (1973)

Conferences, Schools, and Workshops

18th International Workshop: Computer Science Logic 2004 – Karpacz 2004

ACM Schools

• Internet Security – Duszniki Zdrój 2002
• ACM Workshop on Functional and Object Oriented Programming – Jadwisin 1997
• ACM State of the Art Summer School Functional and Object Oriented Programming – Sobótka 1996

Forum of Theoretical Computer Science

• 20th Forum of Theoretical Computer Science – Karpacz 2006
• 19th Forum of Theoretical Computer Science – Karpacz 2005
• 18th Forum of Theoretical Computer Science – Karpacz 2004
• Forums of Theoretical Computer Science (1993 – 2000)

Informatics at Schools

• XX Conference „Informatics at Schools” – Wrocław 2004
• XIX Conference „Informatics at Schools” – Szczecin 2003
• XVIII Conference „Informatics at Schools” – Toruń 2002
• XVII Conference „Informatics at Schools” – Mielec 2001

The 24th International Symposium of Mathematical Foundations of Computer Science – Szklarska Poręba 1999

Useful links

Institute Library (page contains list of printed journals and links to other libraries)

Research associations

• Polish chapter of ACM
• Polish chapter of ACM SIGACT

Consortia

• Science Direct
• SIAM Journals Online
• Springer LINK
• IIC - ILAS
• The ACM Digital Library

Home pages of selected publishers in computer science

• ACM Press
• AMS
• Addison-Wesley Higher Education
• Birkhäuser Boston Scientific and Technical Publishing
• Cambridge University Press
• CRC Press
• Elsevier Science
• John Wiley&Sons, Inc.
• IEEE Computer Society Press
• MIT Press
• Kluwer Academic Publishers
• Oxford University Press
• Prentice Hall
• Springer-Verlag

Selected printed journals in computer science

• BIT
• IMA Journal of Numerical Analysis
• INFORMATICA An International Journal of Computing and Informatics
• Information and Computation
• Journal of Approximation Theory
• Journal of Functional Programming
• Mathematics of Computation
• Numerical Algorithms

Competitions

Our students take part in diverse computer science competitions. Below is a list of our most important successes

2007

• participation at the 31th Annual ACM-ICPC World Finals, Tokyo 15.03.2007
• the first place for Paweł Gawrychowski and the third place for Przemysław Uznański at the Jagiellonian Programming League (March 2007)
• the first place for Paweł Gawrychowski at Potyczki Algorytmiczne finals

2006

• the fourth and the eight place at the ACM Central Europe Programming Contest (Budapest, 19.11.2006) and promotion to world finals (Tokio 2007)
• the third and the fifth place at the XI Polish Collegiate Programming Competition
• The Google Summer of Code stipend for Piotr Wolny
• the first place for Tomasz Wawrzyniak at Potyczki Algorytmiczne finals
• the fourth and fifth place at the Poznan Open 2006. Team programming Championship, Poznań, 2.12.2006

2005

• the second and the sixth place at the III Collegiate Programming Contest of Wielkopolska, Poznań, 03.12.2005 (140 teams participated in the competition)
• the first place in the internet programming competition OPSSession of Algorithms - 580 participants took part
• the fifth place and a silver medal at the 29th Annual ACM-ICPC World Finals, Shanghai 06.04.2005
• the fourth and the tenth place at the 2005 ACM Central Europe Programming Contest, Budapest, 18.11.2004
• the third and the sixth place at the X Polish Collegiate Programming Competition, Kraków, 29.10.2005
• the seventh place in the wolrd finals of the 2005 TopCoder Open, Santa Clara, 12-14.10.2005 - accepted to the finals after 5 rounds; in the second round there were 750 participants from all over the world
• two participants in the finals of the Google Code Jam 2005, Mountain View, 23.09.2005 - accepted to the finals after three rounds; in the second round there were 500 participants
• the first place in the Internet Problem Solving Contest 2005, 13.05.2005

2004

• the fourth and the sixth place at the II Collegiate Programming Contest of Wielkopolska, Poznań, 04.12.2004 (more than 100 teams took part)
• the third and the sixth place at the 2004 ACM Central Europe Programming Contest, Budapest, 21.11.2004

2003

• the third and the fourth place at the I Collegiate Programming Contest of Wielkopolska, Poznań, 06.12.2003