Politechnika Krakowska - Wydział Inżynierii Elektrycznej i Komputerowej - Katedra Automatyki i Technik Informacyjnych

Metody Programowania/Programming Methods

Grupa/Group:
Wykładowca/Lecturer:
Informatyka/Computer Engineering
Semestr/Semester:
2
Wykład/Lecture:
poniedziałek/MON (tygodnie parzyste), godz. 9.15-10.45, WIEiK, s. A1
wtorek/THU, godz. 12.45-14.15, WIEiK, s. A4
+ distance learning (w czasie przerwy z zajęciach)
Laboratorium/Laboratory:
wg planu/according to schedule
+ distance learning (w czasie przerwy z zajęciach)
dr hab. inż. Zbigniew Kokosiński
Katedra Automatyki i Technik Informacyjnych, pokój 200
tel: +48-12-628-2693
email: zk na pk.edu.pl
Konsultacje/Office hours:
poniedziałek/MON (tygodnie parzyste), godz. 11.00-11.45, KAiTI, WIEiK, p. 200
wtorek/TUE, godz. 15.15-16.00, KAiTI, WIEiK, p. 200


KOMUNIKATY/Announcements
1. Ostatnia modyfikacja strony odbędzie się w dniu 13.04.2020 r. Od poniedziałku 16.03.2020 r. strona Metod Programowania zostanie przeniesiona na platformę Moodle . Proszę utworzyć konta i korzystać z tej formy komunikacji.
2. Arkusz z ocenami /Data spreadsheet będzie dostępny na platformie Moodle.
3. Arkusz z ocenami z laboratorium /LAB data spreadsheet (ZK) będzie dostępny na platformie Moodle.
4. Przypominam wszystkim studentom, którzy uzyskali zaliczenie w I i II terminie o wypełnieniu ankiet oceny przedmiotu - na stronie ANKIETY .


Program przedmiotu:

Wprowadzenie do programowania. Zagadnienie programowania a zagadnienia pokrewne. Problemy algorytmiczne i niealgorytmiczne. Pojęcie algorytmu i klasyfikacje algorytmów. Analiza złożoności czasowej i pamięciowej algorytmów. Złożoność asymptotyczna.

Style programowania. Programowanie strukturalne. Projektowanie programów. Zasada abstrakcji. Programowanie modularne. Podstawowe struktury danych. Implementacja. Testowanie. Wydajność i przenośność. Programowanie obiektowe.

Podstawowe techniki projektowania algorytmów. Technika "dziel i zwyciężaj". Metoda podziałów i ograniczeń. Rekurencja. Programowanie dynamiczne. Algorytmy zachłanne. Algorytmy z powracaniem. Wyszukiwanie lokalne. Wyszukiwanie wyczerpujące. Algorytmy aproksymacyjne. Algorytmy iteracyjne.


Wykłady/Lectures


Program laboratorium dla grup ZK w roku akad. 2019/2020 (tymczasowy/tentative):

Projektowanie programów w języku C/C++
L1: Generacja (n,k)-kombinacji, (n-k+1,)-kombinacji z powtórzeniami w porządku leksykograficznym (1<=k<=n) oraz wszystkich (n,k)-kombinacji algorytmem I. Semby (k={1,...,n}).
L2: Generacja co najwyżej n-blokowych podziałów zbioru n-elementowego.
------------- distance-learning ----------
L3 (13.03 e-learning): Generacja permutacji zbioru n-elementowego
L4-5 (20-27.03 e-learning): Generacja drzew t-narnych o n wierzchołkach wewnętrznych
L6 (3.04): Generacja grafów R-MAT o zadanych własnościach. PDF + JPG 1 + JPG 2 + JPG 3
--------end-of-distance-learning ---------
L7 (17.04): termin zaliczeniowy z lab 1-6
L8 (24.04): Programowanie dynamiczne.
L9 (: Algorytmy zachłanne : kodowanie Huffmana w kompresji danych.
L10: Algorytmy zachłanne : wyznaczanie minimalnej bazy macierzy binarnej.
L11: Wyszukiwanie lokalne. Problem SAT. Implementacja algorytmu WALKSAT lub GSAT.
L12-L13: Symetryczny problem stabilnych małżeństw (zbiory równoliczne). Wyznaczanie wszystkich rozwiązań dopuszczalnych. Wyszukiwanie rozwiązania optymalnego. Rozwiązanie przypadków asymetrycznych.
-------------------------------
L14-L15: Terminy zaliczeniowe.

Laboratoria w roku akad. 2019/2020 prowadzą dr hab. inż. Zbigniew Kokosiński i mgr inż. Grzegorz Nowakowski.


Oprogramowanie :


Użyteczne odnośniki: link


Literatura:

Literatura dodatkowa:


Forma zaliczenia przedmiotu:


oprac. ZK 2009-2020 śąź