Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych
Koordynator przedmiotu:
dr inż. Jadwiga Chudzicka
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Zarządzanie i Inżynieria Produkcji
Grupa przedmiotów:
Technologie informatyczne
Kod przedmiotu:
ASDAN
Semestr nominalny:
2 / rok ak. 2010/2011
Liczba punktów ECTS:
3
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
algorytmika, programowanie komputerów, algorytm, typy danych, struktury danych, złożoność algorytmów, rekurencja, sortowanie danych, algorytmy numeryczne, kodowanie danych, kompresja danych, grafy.
Limit liczby studentów:
Cel przedmiotu:
Przedmiot składa się tylko z jednostki wykładowej. Wykłady oparte są na prezentacjach multimedialnych prezentowanych przez prowadzącego. Elementem pracy twórczej w ramach wykładu jest tworzenie projektów rozwiązań zagadnień zaproponowanych przez wykładowcę na bazie schematów przedstawianych na zajęciach. Rozwiązania mogą być prezentowane w postaci schematów graficznych lub w wybranym języku programowania.
Treści kształcenia:
2h - Wprowadzenie do metodologii programowania Geneza algorytmiki. Pojęcia podstawowe. Definicja i cechy charakterystyczne poprawnych i efektywnych algorytmów. Sposoby zapisu algorytmów. Poprawność algorytmów. Języki programowania. 2h – Typy i struktury danych Typy proste i złożone. Przetwarzanie liczb, wartości logicznych i tekstów. Struktury danych: listy i ich tablicowe implementacje, kolejki, pojęcie stosu i jego zastosowania, drzewa, zbiory. 2h – Analiza złożoności algorytmów Terminologia i definicje. Typy złożoności obliczeniowej. Techniki optymalizacji programów. Ilustracja metod na przykładach. 2h – Techniki rekurencyjne Pojęcie rekurencji. Ilustracja rekurencji na przykładach: wyznaczanie wartości funkcji silnia, ciąg Fibonacciego. Typy programów rekurencyjnych. Pułapki programów rekurencyjnych. Rekurencje i ich odpowiedniki iteracyjne. 2h – Techniki sortowania Prezentacja metod sortowania: sortowanie przez wstawianie, sortowanie bąbelkowe, szybkie sortowanie, sortowanie przez kopcowanie, sortowanie przez scalanie, sortowanie zewnętrzne. Klasy algorytmów sortowania. 2h – Techniki przeszukiwania Przeszukiwanie liniowe. Przeszukiwanie binarne. Metody transformacji kluczowej. Funkcje matematyczne używane do konstruowania funkcji stosowanych w transformacji kluczowej. Zastosowania transformacji kluczowej. 2h – Przeszukiwanie tekstów Algorytmy przeszukiwania tekstów: typu brute-force, K-M-P, Boyera i Moore’a, Rabina i Karpa. 2h – Pierwszy sprawdzian Sporządzenie schematu blokowego przedstawiającego rozwiązanie konkretnego problemu i 2 lub 3 pytania teoretyczne. 2h – Algorytmy numeryczne cz. I Metody iteracyjne rozwiązywania układów równań liniowych. Metoda eliminacji Gaussa rozwiązywania układów równań liniowych. Poszukiwanie miejsc zerowych funkcji. Iteracyjne obliczanie wartości funkcji. 2h – Algorytmy numeryczne cz. II Interpolacja funkcji metodą Lagrange’a. Ekstrapolacja funkcji. Różniczkowanie funkcji metodą Stirlinga. Całkowanie funkcji metodą Simpsona. 2h – Algorytmika grafów. Kodowanie i kompresja danych Pojęcia podstawowe. Sposoby reprezentacji grafów. Operacje na grafach. Algorytmy poszukiwania najkrótszych dróg w grafach. Podstawowe wiadomości na temat kodowania danych (szyfrowania wiadomości) i popularne metody łamania szyfrów. Omówienie wybranych metod kompresji danych. 2h – Optymalizacja algorytmów Optymalizacja poprzez transformację algorytmów rekurencyjnych na ich postać iteracyjną. Powody, dla których stosuje się derekursywację. Wykorzystanie stosu. Schematy derekursywacji. 2h – Inne techniki programowania Metody heurystyczne. Algorytmy genetyczne. Programowanie typu „dziel i zwyciężaj”. Przykłady algorytmów. Programowanie dynamiczne. 2h – Drugi sprawdzian Sprawdzian pisemny: konstrukcja algorytmu rozwiązującego konkretny problem i 2 lub 3 pytania teoretyczne. 2h – Końcowe zaliczenia. Wpisy do indeksów Poprawa ocen niedostatecznych w formie sprawdzianu pisemnego. Studenci, którzy uzyskali oceny pozytywne, ale niższe od 5 również mogą spróbować poprawić oceny. Natomiast studenci, którzy nie piszą kolokwium poprawkowego otrzymują w tym dniu wpis do indeksu.
Metody oceny:
Prace pisemne sprawdzające praktyczne umiejętności rozwiązywania typowych problemów spotykanych w praktyce inżynierskiej i pytania sprawdzające wiedzę teoretyczną.
Egzamin:
Literatura:
• Wróblewski P., Algorytmy: struktury danych i techniki programowania, Wyd. Helion, Gliwice 2010. • Czech Z., Deorowicz S., Fabian P., Algorytmy i struktury danych: wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice 2007. • Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych, Wydawnictwa Naukowo-Techniczne, Warszawa 2006. • Dańko A., Algorytmy i struktury danych: zadania, Wydawnictwo Polsko-Japońskiej Wyższej Szkoły Technik Komputerowych, Warszawa 2006.
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się