Wprowadzenie do informatyki Flashcards
(8 cards)
Informatyka, informacja, zadanie algorytmiczne, algorytm i sposoby jego zapisu.
Informatyka to dziedzina nauki zajmująca się przetwarzaniem informacji za pomocą komputerów.
Informacja to zbiór danych, które są przetwarzane, przechowywane i przekazywane za pomocą różnych narzędzi i technologii.
Zadanie algorytmiczne to problem, który można rozwiązać za pomocą algorytmu, czyli serii logicznie uporządkowanych kroków do realizacji określonego celu.
Algorytm może być zapisany w różny sposób, np. jako lista kroków do wykonania, diagram blokowy lub kod programu komputerowego.
Jednym ze sposobów zapisu algorytmu jest pseudokod, czyli symboliczny zapis kroków algorytmu, który jest zrozumiały dla ludzi, ale nie jest językiem programowania. Innym sposobem jest użycie języka programowania, takiego jak C++, Python lub Java, do zapisania algorytmu w postaci kodu, który jest interpretowany przez komputer.
Podejście zstępujące i wstępujące w programowaniu. Procedury i funkcje. Rekurencja
w programowaniu. Problemy rozwiązywane z użyciem rekurencji. Modele danych.
> Podejście zstępujące, zwane również podejściem top-down, to podejście do projektowania programów, w którym najpierw szkicuje się ogólny plan rozwiązania problemu, a następnie rozwija go w szczegóły. Podejście to jest często używane do projektowania algorytmów, ponieważ pozwala na przejrzyste i uporządkowane myślenie o problemie.
Podejście wstępujące, zwane również podejściem bottom-up, to podejście do projektowania programów, w którym najpierw rozwija się szczegóły, a następnie łączy je w całość. Podejście to jest często używane, gdy istnieje już duża liczba istniejących elementów, które mogą być połączone w celu rozwiązania problemu.
Procedury to fragmenty kodu, które są wywoływane z innych miejsc w programie i wykonują określone zadania. Procedury nie zwracają żadnej wartości.
>
>
> Funkcje to również fragmenty kodu, które są wywoływane z innych miejsc w programie, ale oprócz tego zwracają wartość. Funkcje są często używane do wykonywania obliczeń lub przetwarzania danych i zwracania wyniku.
>
> Rekurencja to technika, w której funkcja lub procedura wywołuje sama siebie w celu rozwiązania problemu.
>
> Rekurencja jest często używana do rozwiązywania problemów, które mogą być rozwiązane poprzez podział na mniejsze podproblemy i rozwiązanie ich osobno. Przykładami problemów, które mogą być rozwiązywane za pomocą rekurencji, są: obliczanie silni, sortowanie listy, przechodzenie drzewa lub grafu.
>
> Modele danych to sposoby przedstawienia danych w programie. Istnieje wiele różnych modeli danych, takich jak modele relacyjne, obiektowe, hierarchiczne i inne. Modele danych są używane do określenia sposobu przechowywania i manipulowania danymi w programie.
>
Proste typy danych w językach programowania. Sposoby kodowania znaków. Liczby
stałopozycyjne i zmiennopozycyjne.
> Liczby całkowite (integer): reprezentują liczby całkowite, takie jak -1, 0, 1, 2 itd
Liczby zmiennoprzecinkowe (float): reprezentują liczby zmiennoprzecinkowe, takie jak 3.14, -0.01 itd.
Zmienne logiczne (boolean): przyjmują wartości prawda (true) lub fałsz (false).
Ciągi znaków (string): reprezentują ciągi znaków, takie jak “hello” lub “goodbye”.
Tablice (array): reprezentują kolekcje elementów, które mogą być różnych typów.W językach programowania istnieją również bardziej złożone typy danych, takie jak obiekty i struktury danych.Znaki są kodowane za pomocą różnych standardów, takich jak ASCII, Unicode lub UTF-8. ASCII to starszy standard, który koduje 128 znaków, natomiast Unicode i UTF-8 są nowszymi standardami, które kodują ponad 100 000 znaków z różnych języków i symboli.Liczby stałopozycyjne to liczby, które zawsze mają tę samą liczbę miejsc po przecinku. Przykładem liczb stałopozycyjnych są liczby dziesiętne, takie jak 3.14. Liczby zmiennopozycyjne, zwane również liczbami zmiennoprzecinkowymi, to liczby, które mogą mieć różną liczbę miejsc po przecinku. Przykładem liczb zmiennopozycyjnych są liczby zmiennoprzecinkowe, takie jak 3.14159265358979323846.
Język programowania, składnia, semantyka. Język proceduralny. Konstrukcje
strukturalne i ich realizacja.
Język programowania to specjalny język, który służy do tworzenia programów komputerowych.
Składnia języka programowania określa sposób, w jaki należy pisać konkretne komendy i instrukcje, tak aby były one poprawne według reguł danego języka.
Semantyka języka programowania opisuje znaczenie poszczególnych komend i instrukcji w danym języku.
Język proceduralny to język programowania, w którym algorytm jest opisywany przez serię kroków do wykonania. W językach proceduralnych program jest zwykle podzielony na procedury lub funkcje, które są wywoływane w określonym miejscu i służą do realizacji konkretnych zadań.
Konstrukcje strukturalne to elementy języków programowania, takie jak pętle i instrukcje warunkowe, które pozwalają na stworzenie bardziej złożonych algorytmów.
Realizacja konstrukcji strukturalnych oznacza wykonanie kodu, który został umieszczony w danej konstrukcji, w zależności od określonych warunków.
Strukturalne typy danych w językach programowania.
> Strukturalne typy danych to typy danych, które pozwalają na przechowywanie i organizowanie danych w bardziej złożonej strukturze niż pojedyncze wartości lub zmienne.Przykłady strukturalnych typów danych to:
- Krotki (tuple): krotki to niezmienne sekwencje elementów, które mogą być różnych typów. Krotki są często używane do przekazywania kilku wartości jako jednej zwracanej wartości z funkcji.
- Słowniki (dictionary): słowniki to kolekcje par klucz-wartość, gdzie klucze są unikalne i mogą być różnych typów, a wartości mogą być dowolnego typu. Słowniki są często używane do przechowywania danych w postaci par klucz-wartość, gdzie klucze są używane do szybkiego wyszukiwania wartości.
- Zbiory (set): zbiory to kolekcje unikalnych elementów, które nie są uporządkowane. Zbiory są często używane do przechowywania unikalnych elementów lub do wykonywania operacji na zbiorach, takich jak zbiory arytmetyczne (suma, różnica, iloczyn itd.).
- Listy (list): listy to uporządkowane sekwencje elementów, które mogą być różnych typów. Listy są podobne do krotek, ale są zmienne i można je modyfikować (dodawać lub usuwać elementy).
- Kolejki (queue): kolejki to struktury danych, w których elementy są dodawane do końca sekwencji i usuwane z początku. Kolejki są często używane do przechowywania danych w kolejce do przetworzenia.
- Stosy (stack): stosy to struktury danych, w których elementy są dodawane i usuwane z tego samego końca. Stosy są często używane do przechowywania danych w stosie lub do realizacji rekurenc
Podstawowe pojęcia ze złożoności obliczeniowej algorytmów. Złożoność
obliczeniowa, funkcja złożoności obliczeniowej, rząd złożoności obliczeniowej.
Złożoność obliczeniowa algorytmu to miernik jego wydajności, określający, ile operacji jest wykonywanych w zależności od rozmiaru danych wejściowych. Im mniej operacji jest wykonywanych, tym lepsza jest złożoność obliczeniowa algorytmu.
Funkcja złożoności obliczeniowej to wzór matematyczny, który opisuje złożoność obliczeniową algorytmu. Funkcja złożoności obliczeniowej jest zwykle zapisywana jako O(f(n)), gdzie n jest rozmiarem danych wejściowych, a f(n) jest funkcją opisującą ilość operacji wykonywanych przez algorytm.
Rząd złożoności obliczeniowej to największy wyraz w funkcji złożoności obliczeniowej algorytmu. Rząd złożoności obliczeniowej określa, jak szybko rośnie złożoność obliczeniowa algorytmu wraz ze wzrostem rozmiaru danych wejściowych. Algorytmy o niższym rzędzie złożoności obliczeniowej są zwykle bardziej wydajne niż algorytmy o wyższym rzędzie złożoności obliczeniowej, ponieważ wykonują mniej operacji.
Podstawowe pojęcia lingwistyki matematycznej. Wzorce, automaty, wyrażenia
regularne i gramatyki.
> Lingwistyka matematyczna to dziedzina informatyki, która zajmuje się badaniem języków formalnych i ich zastosowań w informatyce. Obejmuje ona takie pojęcia jak:
- Wzorce (patterns) - wzorce są używane do opisywania struktur danych lub ciągów znaków, takich jak ciągi znaków w językach programowania lub sekwencje baz danych.
- Automaty - automaty to modele matematyczne, które są używane do opisywania języków formalnych i ich akceptacji. Istnieją różne rodzaje automatów, takie jak automaty skończone, automaty stanów skończonych i automaty pushdown.
- Wyrażenia regularne - wyrażenia regularne to zapisy języków formalnych, które są używane do opisywania ciągów znaków, takich jak ciągi znaków w językach programowania lub adresy URL.
- Gramatyki - gramatyki to modele matematyczne, które są używane do opisywania struktur języków formalnych i ich generowania. Gramatyki są używane do opisywania języków programowania, języków naturalnych i innych języków formalnych.
Języki formalne, klasy P i NP, problemy NP-zupełne, teoria Turinga.
> Języki formalne to języki matematyczne, które są używane do opisywania struktur i zachowań różnych systemów. Języki formalne są używane w informatyce do opisywania języków programowania, struktur danych i innych systemów informatycznych.Klasy P i NP to dwie klasy problemów informatycznych, które są zdefiniowane na podstawie złożoności obliczeniowej. Klasa P obejmuje problemy, dla których istnieje algorytm o złożoności obliczeniowej liniowej lub logarytmicznej. Klasa NP obejmuje problemy, dla których istnieje algorytm o złożoności obliczeniowej wielomianowej, ale istnieje również szybsze rozwiązanie znajdujące się w klasie P.Problemy NP-zupełne to specjalny rodzaj problemów w klasie NP, które są szczególnie trudne do rozwiązania. Istnieje podejrzenie, że nie istnieje algorytm o złożoności obliczeniowej niższej niż wielomianowa dla tych problemów, ale nie jest to dowiedzione.Teoria Turinga to fundament informatyki, który zajmuje się badaniem możliwości i ograniczeń komputerów. Została ona zaproponowana przez Alana Turinga w latach 30. XX wieku i służy do opisywania, co komputery mogą i nie mogą zrobić. Teoria Turinga jest podstawą dla większości badań informatycznych i jest używana do badania złożoności obliczeniowej algorytmów i innych problemów informatycznych.
