Sylabus przedmiotu
Podstawy informatyki I
| Forma zajęć | Atrybuty formy | Godziny w semestrze | Godziny w tygodniu | Zaliczenie | Kompetencje | Waga | ||
|---|---|---|---|---|---|---|---|---|
| stacjonarne | niestacjonarne | stacjonarne | niestacjonarne | |||||
| Wykład | Forma mieszana, Kontakt bezpośredni: 100% | 30 | 18 | 2 | 1 | Zaliczenie na ocenę |
|
(50%)1 przez 2 |
| Laboratorium | Kontakt bezpośredni: 100% | 30 | 18 | 2 | 1 | Zaliczenie na ocenę |
|
(50%)1 przez 2 |
| Forma aktywności | Liczba godzin - stac. | Liczba godzin - niestac. |
|---|---|---|
| Przygotowanie do zajęć | 15 | 24 |
| Analiza wskazanej literatury | 15 | 18 |
| Przygotowanie do egzaminu / zaliczenia | 5 | 5 |
| Przygotowanie pracy pisemnej, raportu, prezentacji, demonstracji, itp. | 15 | 24 |
| Przygotowanie projektu | 15 | 18 |
| SUMA | 65 | 89 |
Cele przedmiotu: Celem przedmiotu jest przedstawienie własności algorytmów, zasad projektowania algorytmów, ograniczeń związanych z projektowaniem algorytmów, przedstawienie podstawowych struktur danych oraz algorytmów ich obsługi, ukształtowanie umiejętności projektowania algorytmów dla wybranych problemów algorytmicznych.
Wymagania wstępne:
Zakres tematyczny
| Rodzaj zajęć | Opis | Godz. stac. | Godz. niestac. |
|---|---|---|---|
| Wykład | 1. Algorytm i jego własności: pojęcie problemu algorytmicznego i algorytmu, własności algorytmów. Poprawność i częściowa poprawność algorytmu. Własność stopu. Złożoność obliczeniowa: pamięciowa, czasowa. | 3 | 2 |
| Wykład | 2. Schematy blokowe, opis bloków, graficzna reprezentacja bloków, struktury sterujące. | 3 | 1 |
| Wykład | 3. Techniki programowania: rekurencja i derekursywacja, programowanie typu „dziel i rządź”, algorytmy zachłanne, programowanie dynamiczne. | 3 | 2 |
| Wykład | 4. Struktury danych: pojęcie struktury danych, zbiory dynamiczne, zbiory liniowo uporządkowane, słownik, kolejki i stosy. | 3 | 2 |
| Wykład | 5. Sortowanie, model sortowania wewnętrznego, proste algorytmy sortowania, sortowanie stogowe, sortowanie szybkie. | 3 | 2 |
| Wykład | 6. Listy jedno- i dwukierunkowe, listy cykliczne, kolejki priorytetowe, mapy. | 3 | 2 |
| Wykład | 7. Drzewa, drzewa przeszukiwań binarnych BST, struktury samoorganizujące się, drzewa przeszukiwań pozycyjnych. | 3 | 2 |
| Wykład | 8. Tablice haszujące, funkcje haszujące, techniki zapobiegania konfliktom; B-drzewa. | 3 | 2 |
| Wykład | 9. Zbiory i grafy: zbiory, grafy skierowane i nieskierowane, reprezentacje grafów, przeszukiwanie grafów wszerz i w głąb, algorytmy teoriografowe i sieciowe. | 4 | 2 |
| Wykład | 10. Analiza wybranych problemów algorytmicznych: przeszukiwanie liniowe i binarne, wybór k-tego elementu, wyszukiwanie wzorca w tekście. | 2 | 1 |
| Laboratorium | 1. Przedstawienie tematyki, harmonogramu i zasad zaliczenia laboratorium. | 1 | 1 |
| Laboratorium | 2. Analiza własności algorytmów. | 2 | 1 |
| Laboratorium | 3. Schematy blokowe, graficzna reprezentacja bloków. Rysowanie schematów blokowych dla wybranych problemów algorytmicznych | 3 | 2 |
| Laboratorium | 4. Zastosowanie rekurencji, programowania typu „dziel i rządź” dla wybranych problemów algorytmicznych. | 3 | 2 |
| Laboratorium | 5. Tablice. Implementacja podstawowych i złożonych algorytmów sortowania tablic. Analiza złożoności obliczeniowej poszczególnych algorytmów. | 3 | 1 |
| Laboratorium | 6. Implementacja dynamicznych struktur danych: zbiory liniowo uporządkowane, kolejki i stosy. | 3 | 2 |
| Laboratorium | 7. Programowanie dynamicznych struktur danych: listy jedno- i dwukierunkowe, listy cykliczne, kolejki priorytetowe, mapy. | 4 | 3 |
| Laboratorium | 8. Implementacja podstawowych operacji dla struktury drzewa, drzewa przeszukiwań binarnych BST, B-drzewa. | 4 | 2 |
| Laboratorium | 9. Drzewa uporządkowane, implementacja wyważania drzewa w oparciu o procedury rekurencyjne. | 3 | 2 |
| Laboratorium | 10. Implementacja algorytmów przeszukiwania liniowego i binarnego, wyboru elementu, wyszukiwania wzorca w tekście. | 2 | 1 |
| Laboratorium | 11. Poprawa sprawdzianów. Podsumowanie i zaliczenie ćwiczeń. | 2 | 1 |
Metody dydaktyczne
| Opis |
|---|
| Wykład problemowy |
| Wykład konwencjonalny |
| Metoda przypadków |
| Dyskusja |
| Demonstracja |
| Ćwiczenia laboratoryjne |
Warunki zaliczenia:
bardzo dobry 5.0 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu bardzo dobrym dobry plus 4.5 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu ponad dobrym dobry 4.0 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu dobrym dostateczny plus 3.5 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu dość dobrym dostateczny 3.0 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu dostatecznym zaliczone zal student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce niezaliczone nzal student/ka nie zna, nie rozumie i nie wyjaśnia zakładanych efektów uczenia się i nie potrafi ich zastosować w praktyce
Literatura podstawowa: Piotr Wróblewski, Algorytmy, struktury danych i techniki programowania. Wydanie VI, Helion 2019. Stephen G. Kochan, Język C. Kompendium wiedzy, Wydanie IV, Helion 2015. Feliks Kurp, Algorytmy. Struktury danych i złożoność obliczeniowa, Helion 2022. Pks Prakash, Achyutuni Sri Krishna Rao, R Data Structures and Algorithms. Increase speed and performance of your applications with efficient data structures and algorithms, Packt Publishing 2016.
Literatura uzupełniająca:
| Symbole | Opis efektu | Metoda weryfikacji | Forma zajęć |
|---|---|---|---|
| Potrafi wyjaśnić zasadę działania algorytmów wstawiania, usuwania i wyszukiwania elementów w szerokiej klasie dynamicznych struktur danych, takich jak listy, drzewa binarne, Bdrzewa czy kolejki priorytetowe |
|
|
|
| Zna i potrafi opisać podstawowe algorytmy rozwiązujące wybrane zadania algorytmiczne (np. sortowanie, wyszukiwanie wzorca w tekście, itp.) |
|
|
|
| Potrafi zaproponować właściwie dobraną technikę algorytmiczną do konkretnego klasycznego zadania algorytmicznego (np. sortowanie, wyszukiwanie wzorca w tekście itp.) |
|
|
|
| Potrafi interpretować schematy blokowe algorytmów oraz opracować je dla prostych zadań algorytmicznych |
|
|