Prowadzony w
cyklach:
2022/23Z, 2023/24Z, 2024/25Z, 2025/26Z
Kod ISCED: 0613
Punkty ECTS:
6
Język:
polski
Organizowany przez:
Wydział Matematyki i Informatyki
Podstawy algorytmiki i programowania 1000-I1PAiP
- Algorytmy - wstęp. Pojęcie algorytmu. Specyfikacja algorytmu (programu). Języki zapisu algorytmów: schematy blokowe, pseudokod, języki programowania. Przykłady algorytmów rozwiązujących proste zadania.
- Język programowania. Podstawowe struktury sterujące (instrukcje: warunkowe, pętla repetycyjna i iteracyjna). Syntaktyka i semantyka instrukcji. Zapisywanie algorytmów za pomocą instrukcji. Struktura programu. Kompilacja programów. Obsługa wejścia i wyjścia. Środowiska programistyczne.
- Przegląd podstawowych typów prostych (typy całkowite, rzeczywiste, logiczny, znakowy). Zmienne i stałe. Reprezentacja liczb całkowitych i rzeczywistych w komputerze.
- Złożone typy danych: tablice, łańcuchy (napisy), struktury, typy wyliczeniowe. Przykłady użycia poszczególnych typów.
- Funkcje - definicja i deklaracja. Przekazywanie parametrów przez wartość i przez nazwę (referencję). Zmienne lokalne i globalne. Biblioteki.
- Rekurencja w programowaniu. Funkcje rekurencyjne. Wady i zalety stosowania rekurencji. Przykłady algorytmów rekurencyjnych.
- Złożoność obliczeniowa algorytmów. Funkcja kosztu - funkcja pesymistycznej czasowej złożoności algorytmu, jej rząd wielkości. Notacja asymptotyczna. Wyznaczanie pesymistycznej złożoności czasowej algorytmu.
- Wyjaśnienie poprawności własnej implementacji (bez narzędzi formalnych).
- Typowe metody algorytmiczne. Przegląd metod projektowania algorytmów: metoda zachłanna, metoda „dziel i zwyciężaj”, programowanie dynamiczne. Przegląd algorytmicznych rozwiązań wybranych problemów obliczeniowych (w tym, algorytmy wyszukujące oraz algorytmy sortowania).
- Praca z plikami i napisami. Strumienie.
- Wskaźniki i podstawowe dynamiczne struktury danych.
Całkowity nakład pracy studenta
30h - wykład,
4h - egzamin,
45h - laboratoria,
20h - praca własna - bieżące przygotowanie do zajęć, studiowanie literatury
55h - praca własna moderowana przez nauczycieli akademickich - implementacja programów w języku C++, udział w konsultacjach
20h - praca własna - przygotowanie do egzaminu
Razem 174h,
6pkt. ECTS
Efekty uczenia się - wiedza
Po zakończeniu przedmiotu student:
(W1) opisuje podstawowe pojęcia teorii algorytmów, ich złożoności i poprawności (por. K_W02),
(W2) zna podstawowe konstrukcje programistyczne (por. K_W03),
(W3) zna podstawową składnię języka C++, rozróżnia proste typy danych i typy złożone (por. K_W03, K_W10),
(W4) zna podstawowe metody i techniki projektowania, analizowania i programowania algorytmów (por. K_W04).
Efekty uczenia się - umiejętności
Po zakończeniu przedmiotu student:
(U1) projektuje algorytmy na rozwiązanie typowych zadań i implementuje je w języku C++ w wybranym środowisku programistycznym np. Code::Blocks (por. K_U05, K_U07, K_U03),
(U2) poprawnie wykorzystuje proste i złożone typy danych stosownie do sytuacji, pamiętając o ich ograniczeniach, np. związanych z arytmetyką komputera (por. K_U08),
(U3) ocenia rząd złożoności czasowej algorytmu (por. K_U07, K_U01, K_U06),
(U4) uzasadnia poprawność algorytmu oraz własnej implementacji (por. K_U07, K_U01),
(U5) umie czytać ze zrozumieniem schematy blokowe oraz programy zapisane w języku C++ (por. K_U06).
Efekty uczenia się - kompetencje społeczne
Po zakończeniu przedmiotu student:
(K1) służy swoją wiedzą i umiejętnościami, skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową w obrębie zagadnień związanych z podstawami programowania (por. K_K02),
(K2) jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny (por. K_K04),
(K3) krytycznie ocenia swoją wiedzę i doskonali ją z wykorzystaniem różnych źródeł informacji (por. K_K03).
Metody dydaktyczne
Zagadnienia dyskutowane na tym przedmiocie podawane są studentom w formie wykładów informacyjnych i problemowych przeplatanych pokazami działania algorytmów na konkretnych, reprezentatywnych danych wejściowych. Wykłady uzupełnione są zajęciami laboratoryjnymi poświęconymi zarówno implementacji poznawanych algorytmów i struktur danych jak i rozwiązywaniu teoretycznych ćwiczeń problemowych pozwalających pogłębić wiedzę przyswojoną w czasie wykładów.
Metody dydaktyczne eksponujące
- pokaz
Metody dydaktyczne podające
- wykład informacyjny (konwencjonalny)
- wykład konwersatoryjny
- wykład problemowy
- wykład konwersatoryjny
- wykład problemowy
Metody dydaktyczne poszukujące
- ćwiczeniowa
- laboratoryjna
- klasyczna metoda problemowa
- laboratoryjna
- klasyczna metoda problemowa
Rodzaj przedmiotu
kanon (atrybut wycofany)
Wymagania wstępne
Znajomość matematyki szkolnej na poziomie podstawowym. Podstawowa obsługa komputera (uruchomienie aplikacji, korzystanie z serwisów www, obsługa prostego edytora tekstowego).
Koordynatorzy przedmiotu
Kryteria oceniania
Zaliczenie ćwiczeń laboratoryjnych na ocenę oraz egzamin z wykładu.
Elementami składowymi zaliczenia ćwiczeń są:
- sprawdzian praktyczny „przy komputerze" weryfikujący umiejętność samodzielnego rozwiązywania problemów algorytmicznych i programowania w C/C++ (efekty W2-W4, U1, U2, K1, K2),
- sprawdzian teoretyczny weryfikujący przyswojenie wiedzy i umiejętności z zakresu złożoności algorytmów (efekty W1, W4, U3-U5, K1, K2),
- samodzielny projekt programistyczny (efekty W2-W4, U1, U2, K1-K3),
- aktywność na zajęciach i samodzielne przygotowanie rozwiązań prostych zadań programistycznych i teoretycznych (efekt W1-W4, U1-U5, K1-K3).
Warunkiem koniecznym jest uzyskanie pozytywnej oceny dla każdego z powyższych elementów. Zalecane jest równe traktowanie każdego z nich. Bardziej szczegółowe zasady zaliczenia ćwiczeń mogą znajdować się w informacjach dla zajęć w konkretnym cyklu.
Egzamin z wykładu:
Dopuszcza się jedną z dwóch poniższych form (preferowana będzie pierwsza z nich):
- Egzamin dwuczęściowy:
- Część I (teoretyczna/pisemna) - sprawdzający opanowanie zagadnień teoretycznych omawianych na wykładzie (efekty W1, W4, U1-U5, K1, K2).
- Część II (praktyczna/przy komputerze) - proste zadanie programistyczne sprawdzające umiejętność implementacji i omówienia podstawowych konstrukcji programistycznych (efekty W2, W3, U1-U5, K1-K3).
Warunkiem koniecznym zdania egzaminu jest pozytywne (minimum 50%) zaliczenie części teoretycznej, która stanowi główny czynnik kształtujący ocenę końcową oraz pozytywne zaliczenie części praktycznej (mogącej w nieznacznym stopniu zmodyfikować wynik uzyskany w części pisemnej: ±0,5 oceny).
lub - Egzamin pisemny jednoczęściowy:
- sprawdzający opanowanie zagadnień teoretycznych i praktycznych omawianych na wykładzie (efekty W1-W4, U1-U5, K1-K3).
Praktyki zawodowe
---
Literatura
Literatura podstawowa:
- N. Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa,
- M. Sysło, Algorytmy, WSiP, Warszawa,
- J. Grębosz, Symfonia C++ Standard, t.1, Edition 2000,
- J. Grębosz, Opus magnum C++11. Programowanie w języku C++, Gliwice, Helion 2018,
- Portal "Studia Informatyczne" - http://wazniak.mimuw.edu.pl/.
Literatura uzupełniająca:
- D. Harel, Rzecz o istocie informatyki: Algorytmika, WNT, Warszawa.
- L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Warszawa.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT, Warszawa.
Uwagi
|
W cyklu 2022/23Z:
Uwaga: W zależności od rozwoju epidemii koronawirusa oraz obowiązujących reżimów sanitarnych, dopuszcza się realizację części (lub całości) egzaminu w formie zdalnej. Zgodnie z obowiązującym na ten moment reżimem sanitarnym, egzamin odbędzie się w formie dwuczęściowej. |
W cyklu 2023/24Z:
Zgodnie z obowiązującym na ten moment reżimem sanitarnym, egzamin odbędzie się w formie dwuczęściowej. |
W cyklu 2024/25Z:
Zgodnie z obowiązującym na ten moment reżimem sanitarnym, egzamin odbędzie się w formie dwuczęściowej. |
W cyklu 2025/26Z:
Zgodnie z obowiązującym na ten moment reżimem sanitarnym, egzamin odbędzie się w formie dwuczęściowej. |
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: