1DI1107 - Podstawy informatyki

Nazwa w drugim języku: 

Fundamentals of Computer Science

Przedmiot realizowany w planach wzorcowych:

• Informatyka Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: 12
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2017Z/2018L
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: 22
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2021Z/2022L
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2018Z/2019L
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2023Z/2024L
• Informatyka Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: 14
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: 21
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2024Z/2025L
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2016Z/2017L
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2022Z/2023L
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2019Z/2020L
• Informatyka Stosowana Semestr: 1 Etap: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Wersja programu studiów: WPS2020Z/2021L

Obieralny dla katalogów:

Znalazłem 0 pozycji. (Pokaż szczegóły)

Cel przedmiotu: 

Celem przedmiotu jest zapoznanie studentów z podstawami teoretycznymi niezbędnymi do studiowania informatyki.

Treści kształcenia: 

Wykład
1. Wprowadzenie (Łańcuch, alfabety i języki. Grafy i drzewa. Dowody przez indukcje. Oznaczenia dla zbiorów. Relacje.)
2. Automaty skończone i wyrażenia regularne (Systemy skończone stanowe. Podstawowe definicje. Niedeterministyczne automaty skończone. Wyrażenia regularne. Zastosowanie automatów skończonych: analizatory leksykalne, edytory tekstu).
3. Gramatyki bezkontekstowe (Wprowadzenie. Definicja. Wyprowadzenia i języki. Drzewa wyprowadzenia.)
4. Automaty ze stosem (Wprowadzenie. Definicje – ruchy, języki akceptowane.)
5. Maszyny Turinga (Wprowadzenie. Model maszyny Turinga. Języki i funkcje obliczalne. Techniki konstruowania maszyn Turinga, Modyfikacje maszyny Turinga. Maszyny Turinga jako generatory).
6. Nierozstrzygalność (Problemy rozstrzygalne i nierozstrzygalne. Własności języków rekurencyjnych i rekurencyjnie przeliczalnych. Uniwersalne maszyny Turinga i problem nierozstrzygalny. Kody maszyn Turinga. Język uniwersalny. Nierozstrzygalność problemu odpowiedniości posta)
7. Hierarchia Chomsky’ego Gramatyka regularna. Gramatyki nieograniczone. Języki kontekstowe.
8. Teoria złożoności obliczeniowej (Definicje, Złożoność pamięciowa, Złożoność czasowa, Klasy złożoności. Redukcja złożoności: Przyspieszenie liniowe. Kompresja taśmy. Zmniejszenie liczby taśm.)
9. Problemy niepodatne (Wielomianowy czas i pamięć: Wprowadzenie, Ograniczone redukowalności, Problemy zupełne. Przykład problemu NP-zupełnego: spełnialność).

Laboratorium
1. Wprowadzenie. Zasoby komputerowe.
2. System operacyjny UNIX – wyrażenia regularne.
3. Automaty skończone. Emulacja działania prostego automatu skończonego
4. Gramatyki bezkontekstowe. Generowanie łańcuchów opisanych za pomocą danej gramatyki
5. Maszyna Turinga. Emulacja działania maszyny Turinga.
6. Problem Odpowiedniości POSTa.
7. Rezerwowy termin odrabiania zajęć.

Bibliografia: 

1. J. E. Hopcroft, M. Rajeev, J. D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń. PWN, 2012.
2. M. Sipser, Wprowadzenie do teorii obliczeń. PWN, 2021.
3. A. V. Aho, J. D. Ullman, Wykłady z informatyki z przykładami w języku C. Helion, 2003.
4. T. H. Cormen, Ch. F. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów, PWN, 2022.
5. C. H. Papadimitriou, Złożoność obliczeniowa. Helion, 2012.
6. D. Brylow, J. Glenn Brookshear, Informatyka w ogólnym zarysie. PWN 2022.
7. D. Harel, Rzecz o istocie informatyki, WNT, 2008.

Metody oceny: 

Wykład jest zaliczany na podstawie pisemnego egzaminu. Laboratorium jest zaliczane w oparciu o zadania problemowe.

Uwagi: 

-

Przedmioty na których bazuje dany przedmiot (prerekwizyty):

• Efekty Kształcenia dla kierunku Informatyka Stosowana:
• Wiedza

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  I1_W04	Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu informatyki, w szczególności: a) podstaw programowania, b) algorytmów i złożoności, c) architektury systemów komputerowych, d) systemów operacyjnych, e) technologii sieciowych, f) języków i paradygmatów programowania, g) grafiki i komunikacji człowiek-komputer, h) sztucznej inteligencji, i) baz danych, j) inżynierii oprogramowania, k) systemów wbudowanych, l) wybranych podstawowych zastosowań informatyki.	+ (33%)	Zna i rozumie modele matematyczne stosowane do opisu automatów, a w szczególności automat skończony, automat ze stosem i maszynę Turinga Zna i rozumie modele opisu języków o ich wzajemne zależności Zna podstawy złożoności obliczeniowej Zna i rozumie pojęcie nierozstrzygalności i jego znaczenie w informatyce	egzamin, zadania problemowe
  I1_W04b	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu algorytmów i złożoności		-	-

• Umiejętności

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  I1_U01	Potrafi pozyskiwać informacje z literatury, baz danych oraz innych właściwie dobranych źródeł w wersji drukowanej i elektronicznej, w tym w Internecie, także w języku angielskim albo francuskim lub niemieckim w zakresie informatyki, potrafi integrować uzyskane informacje, dokonywać ich interpretacji, a także wyciągać wnioski, formułować i uzasadniać opinie.	+ (33%)	Potrafi na podstawie dostępnych źródeł uzyskać informację niezbędne do przygotowania symulacji komputerowych	sprawdzenie poprawności rozwiązania zadań problemowych, egzamin
  I1_U05	Potrafi planować własne uczenie się, ma umiejętności samokształcenia.	+ (33%)	Potrafi uzyskać wiedzę niezbędną do rozwiązania prostych problemów informatycznych	zadania problemowe
  I1_U08	Potrafi planować i przeprowadzać eksperymenty, w tym pomiary, symulacje komputerowe, interpretować uzyskane wyniki i wyciągać wnioski.	+ (33%)	Potrafi przeprowadzić symulacje komputerowe z wykorzystaniem modeli matematycznych	zadania problemowe
  I1_U08b	potrafi planować i przeprowadzać eksperymenty, w tym symulacje komputerowe	+ (33%)	Potrafi przeprowadzić symulacje komputerowe z wykorzystaniem modeli matematycznych	zadania problemowe

• Kompetencje społeczne

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  I1_K01	Jest przygotowany do przeprowadzenie krytycznej analizy posiadanej wiedzy, ma świadomość posiadanych kompetencji i umie pozyskać informacje potrzebne do realizacji postawionych przed nim zadań.	+ (33%)	Jest przygotowany do przeprowadzenie krytycznej analizy posiadanej wiedzy, ma świadomość posiadanych kompetencji i umie pozyskać informacje potrzebne do realizacji postawionych przed nim zadań w zakresie teoretycznych podstaw informatyki	dyskusje z prowadzącym zajęcia
  I1_K02	Jest przygotowany do współpracy z mentorem dla osiągnięcia postawionych celów.	+ (33%)	Jest przygotowany do współpracy z mentorem przy rozwiązaniu postawionych zadań	dyskusje zadania problemowe

• • Punkty ECTS za zajęcia kontaktowe z nauczycielem: 2,4 
  • Punkty ECTS za zajęcia praktyczne łącznie; kontaktowe i bez kontaktu z nauczycielem: 4,1 
• • Uzasadnienie punktów ECTS:

  • Zajęcia kontaktowe z nauczycielem: 

    Wykład - 30
    Laboratorium - 30

  • Zajęcia bez kontaktu z nauczycielem: 

    Studia podręczników, innych źródeł - 35 Przygotowania do egzaminu – 20
    Opracowanie koncepcji i realizacja symulacji komputerowych - 18

  • • Sumaryczna liczba godzin pracy studenta: 133 
  • Łączna liczba punktów ECTS wynika z sumarycznej liczby godzin pracy studenta.