Wprowadzenie do Algorytmów i Struktur Danych
24 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Jakie operatory arytmetyczne są wymienione w treści?

  • +, -, *, /, div, mod (correct)
  • +, -, avg, /, div, mod
  • +, *, /, sqrt, div, mod
  • +, -, *, div, floor, mod

    • Który z wymienionych typów danych nie istnieje w treści?

  • string
  • bool
  • float (correct)
  • char

    • Jak prawidłowo deklaruje się zmienną dla liczby całkowitej?

  • real i;
  • int i; (correct)
  • i:int;
  • i:=int;

    • Jakie są poprawne sposoby dostępu do elementów tablicy w treści?

    <p>K[1,1] (B)</p> Signup and view all the answers

    Co oznacza operator ':=' w kontekście instrukcji przypisania?

    <p>Instrukcja przypisania wartości (D)</p> Signup and view all the answers

    Który z poniższych operatorów jest operatorem logicznym?

    <p>AND (D)</p> Signup and view all the answers

    Jakie jest znaczenie zmiennej 'p' zadeklarowanej jako 'bool'?

    <p>Może być tylko prawdziwa lub fałszywa (A)</p> Signup and view all the answers

    Jak można zapisać pusty blok instrukcji?

    <p>; (D)</p> Signup and view all the answers

    Które z podanych cech nie są wymagane dla poprawnego działania algorytmu?

    <p>Złożoność (D)</p> Signup and view all the answers

    W kontekście algorytmów, co oznacza termin "rozstrzygalny"?

    <p>Algorytm może znaleźć rozwiązanie w skończonej liczbie kroków. (D)</p> Signup and view all the answers

    Które z poniższych nie jest prawidłowym sposobem zapisu algorytmu?

    <p>Pamięć masowa (B)</p> Signup and view all the answers

    Jaki jest główny argument za patentowaniem algorytmów?

    <p>Pozwala chronić prawa autorskie do oprogramowania. (B)</p> Signup and view all the answers

    Jaka jest główna różnica między algorytmem, który jest rozstrzygalny, a algorytmem, który nie jest rozstrzygalny?

    <p>Algorytm rozstrzygalny zawsze znajdzie rozwiązanie, a nierozstrzygalny niekoniecznie. (A)</p> Signup and view all the answers

    Co nie jest celem przedmiotu "Algorytmy i Struktury Danych" w pierwszym semestrze?

    <p>Nauka projektowania algorytmów o wyższym stopniu złożoności. (B)</p> Signup and view all the answers

    Które z poniższych nie jest zaletą algorytmów?

    <p>Zawsze gwarantowane poprawne wyniki. (A)</p> Signup and view all the answers

    Które z podanych nie jest ważnym aspektem przy ocenie algorytmu?

    <p>Liczba dostępnych algorytmów. (C)</p> Signup and view all the answers

    Jaki jest adres witryny internetowej wykładu?

    <p><a href="http://fenix.univ.rzeszow.pl/bazan/archiwum/">http://fenix.univ.rzeszow.pl/bazan/archiwum/</a> (A)</p> Signup and view all the answers

    Który z wymienionych autorów nie jest współautorem książki "Algorytmy i struktury danych - zadania"?

    <p>K. Diks (D)</p> Signup and view all the answers

    Z jakiego powodu niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki?

    <p>Ponieważ patenty utrudniają dostęp do kluczowych technologii i mogą prowadzić do powstania monopoli. (A)</p> Signup and view all the answers

    Które z poniższych operacji nie jest uważane za operację elementarną w kontekście algorytmów?

    <p>Wczytanie pliku z dysku (A)</p> Signup and view all the answers

    Która z wymienionych książek nie jest wymieniona jako literatura do przedmiotu "Algorytmy i struktury danych"?

    <p>Elementy analizy algorytmów, WNT (1989), autorzy: Banachowski, L., Kreczmar, A. (D)</p> Signup and view all the answers

    Który z podanych autorów jest współautorem książki "Algorytmy i struktury danych" z 2003 roku, wydanej przez Helion?

    <p>J.E. Hopcroft (A)</p> Signup and view all the answers

    Co rozumie się przez operację elementarną w kontekście algorytmów?

    <p>Operacja, która jest wykonywana w skończonym i akceptowalnym czasie. (A)</p> Signup and view all the answers

    Jaka jest główna różnica między algorytmem a algorytmiką?

    <p>Algorytm to opis rozwiązania problemu, a algorytmika to dziedzina informatyki zajmująca się projektowaniem i analizą algorytmów. (C)</p> Signup and view all the answers

    Flashcards

    Algorytm

    Opis metody rozwiązania problemu w skończonej liczbie kroków.

    Algorytmika

    Dział informatyki zajmujący się projektowaniem i analizą algorytmów.

    Operacja elementarna

    Niepodzielna czynność wykonywana w skończonym czasie.

    Patenty na algorytmy

    Możliwość opatentowania algorytmu, jeśli jest zastosowany praktycznie.

    Signup and view all the flashcards

    Przykład algorytmu

    Sposób ilustrowania działania algorytmu, np. sortowanie.

    Signup and view all the flashcards

    Muhammed ibn Musa Alchwarizmi

    Matematyk, po którym nazwano algorytm.

    Signup and view all the flashcards

    Literatura o algorytmach

    Książki i materiały dotyczące algorytmów i struktur danych.

    Signup and view all the flashcards

    Analiza algorytmów

    Badanie efektywności algorytmów i ich złożoności.

    Signup and view all the flashcards

    Operatory arytmetyczne

    Operacje matematyczne: +, -, *, /, div, mod.

    Signup and view all the flashcards

    Operatory logiczne

    Operacje na wartościach logicznych: NOT, AND, OR, XOR, ⇒, ⇔.

    Signup and view all the flashcards

    Typy podstawowe

    Podstawowe rodzaje zmiennych: int, real, char, bool, string.

    Signup and view all the flashcards

    Deklaracja zmiennych

    Tworzenie zmiennych z użyciem ; lub :=.

    Signup and view all the flashcards

    Zmienna tablicowa

    Zmienne, które przechowują wiele wartości, dostępne przez indeksy.

    Signup and view all the flashcards

    Blok instrukcji

    Sekwencja instrukcji oddzielonych średnikiem, może być pusta.

    Signup and view all the flashcards

    Instrukcja przypisania

    Przypisanie wartości zmiennej przy użyciu :=.

    Signup and view all the flashcards

    Dostęp do elementów typu string

    Dostęp do konkretnych znaków w łańcuchu z użyciem indeksu.

    Signup and view all the flashcards

    Prawo własności intelektualnej

    Prawo chroniące twórczość intelektualną, np. algorytmy.

    Signup and view all the flashcards

    Cechy algorytmu - Poprawność

    Algorytm daje dobre wyniki, które odzwierciedlają rzeczywistość.

    Signup and view all the flashcards

    Cechy algorytmu - Jednoznaczność

    Brak rozbieżności wyników przy tych samych danych.

    Signup and view all the flashcards

    Cechy algorytmu - Skończoność

    Algorytm wykonuje się w skończonej ilości kroków.

    Signup and view all the flashcards

    Cechy algorytmu - Sprawność

    Odnosi się do szybkości działania i zapotrzebowania na pamięć.

    Signup and view all the flashcards

    Cechy algorytmu - Prostota wykonania

    Operacje w algorytmie powinny być możliwie najprostsze.

    Signup and view all the flashcards

    Problem nierozstrzygalny

    Problem bez algorytmu rozwiązującego go w skończonej liczbie kroków.

    Signup and view all the flashcards

    Opis słowny algorytmu

    Logiczne przedstawienie kolejnych czynności do wykonania.

    Signup and view all the flashcards

    Study Notes

    Wprowadzenie do przedmiotu Algorytmy i struktury danych

    • Przedmiot: Algorytmy i struktury danych
    • Autor: Jan G. Bazan
    • Witryna internetowa wykładu: http://fenix.univ.rzeszow.pl/bazan/archiwum/
    • Dostęp wymaga autoryzacji:
      • Konto: asd
      • Hasło: algosys
    • Witryna zawierać będzie prezentacje wykładowe, materiały pomocnicze do ćwiczeń, przykłady programów, pytania do egzaminu itp.

    Literatura

    • Elementy analizy algorytmów (1989), WNT, Banachowski, L., Kreczmar, A.
    • Algorytmy i struktury danych - zadania (2006), PJWSTK, Dańko, A, Truong Lan Le, Mirkowska, G., Rembelski, P., Smyk, A., Sydow, M.
    • Zbiór zadań z propedeutyki informatyki (1996), PWN, Cichy M., Nomańczuk J., Szpakowicz S.
    • Algorytmy i struktury danych (2003), Helion, Aho, A., V., Hopcroft, J., E., Ullman, J., D.
    • Algorytmy i struktury danych (1996), WNT, Banachowski, L., Diks, K., Rytter, W.
    • Wprowadzenie do algorytmów (2012), WNT, Cormen, T., H., Leiserson, C. E, Rivest, R., L., Stein, C.

    Algorytm i algorytmika

    • Algorytm to opis metody rozwiązania problemu w skończonej liczbie kroków (operacje elementarne).
    • Operacja elementarna to operacja, która z punktu widzenia użytkownika jest całością i realizowana w skończonym czasie.
    • Przykłady operacji elementarnych: przypisanie wartości do zmiennej, porównanie dwóch wartości, wczytanie danych z wejścia, wypisanie danych na wyjściu.
    • Algorytmika to dział informatyki zajmujący się własnościami algorytmów, ich projektowaniem i analizą.
    • Określenie algorytm wywodzi się od nazwiska matematyka perskiego Muhammeda ibn Mūsā al-Chwarizmi (około 800 r. n.e.)

    Przykład algorytmu

    • Wypranie ubrań w pralce automatycznej:
      • Włączenie pralki, załadowanie ubrań, nasypanie proszku
      • Ustalenie odpowiedniego programu (w zależności od stopnia zabrudzenia)
      • Odkręcenie zaworu doprowadzającego wodę
      • Naciśnięcie przycisku START
      • Czekanie na sygnał zakończenia pracy (kontrolka KONIEC)
      • Zakręcenie zaworu doprowadzającego wodę
      • Wyjęcie ubrań, wyłączenie pralki

    Patenty na algorytmy

    • W niektórych krajach (np. USA) algorytmy mogą być opatentowane, jeśli są zaimplementowane w konkretnym, praktycznym celu.
    • Prowadzi to do sporów prawnych pomiędzy koncernami komputerowymi.
    • Argumentacja za patentowaniem algorytmów opiera się na prawie własności intelektualnej, traktując oprogramowanie jako wytwór intelektu i pracy jego twórców.

    Oczekiwane cechy algorytmów

    • Poprawność (algorytm daje dobre wyniki, odzwierciedlające rzeczywistość)
    • Jednoznaczność (identyczne dane dają taki sam wynik)
    • Skończoność (algorytm kończy się po skończonej ilości kroków)
    • Sprawność (czasowa - szybkość wykonania, pamięciowa - zużycie zasobów)
    • Prostota (operacje powinny być jak najprostsze)

    Cel przedmiotu w pierwszym semestrze

    • Nauka projektowania prostych algorytmów
    • Nauka analizy algorytmów pod kątem złożoności (efektywności) i poprawności
    • Analiza algorytmów bez rekurencji i rekurencyjnych

    Algorytm i zagadnienia towarzyszące

    • Znajomość problemu
    • Podejście do definicji algorytmu
    • Rozwijanie algorytmów
    • Poprawność
    • Złożoność
    • Optymalność

    Problemy nierozstrzygalne

    • Problem decyzyjny jest rozstrzygalny, jeśli istnieje algorytm, który dla dowolnych danych po skończonej liczbie kroków daje rozwiązanie problemu.
    • W przeciwnym razie problem jest nierozstrzygalny.
    • Przykładem problemu nierozstrzygalnego jest problem domina.

    Sposoby zapisu algorytmów

    • Opis słowny (opis kolejnych czynności)
    • Schemat blokowy (symbole graficzne)
    • Pseudokod (umowny język programowania)
    • Język programowania (języki programowania)

    Aspekty różnych metodologii tworzenia algorytmów

    • Proceduralność (podzielenie na procedury)
    • Praca sekwencyjna (kolejne wykonywanie czynności)
    • Praca wielowątkowa (konkurencyjne wykonywanie czynności)
    • Praca równoległa i współbieżna (współpraca procesów)
    • Rekurencja (procedura wywołująca sama siebie)
    • Obiektowość (połączenie danych i czynności w obiekty)
    • Algorytm probabilistyczny (algorytm z wysokim prawdopodobieństwem daje poprawny wynik)

    Podstawy pseudokodu

    • Książka Algorytmy i struktury danych – zadania, Dańko, A, Truong Lan Le, Mirkowska, G., Rembelski, P., Smyk, A., Sydow, M. (2006), PJWSTK

    Elementy składni pseudokodu

    • Omówienie składni pseudokodu (elementy instrukcji).

    Operatory i relacje

    • Operatory arytmetyczne (+, -, *, / ,div, mod)
    • Operatory logiczne (NOT, AND, OR, XOR, ⇒, ⇔)
    • Relacje (=, <, >, <=, >=)

    Typy podstawowe

    • int (liczby całkowite)
    • real (liczby rzeczywiste)
    • char (znaki)
    • bool (wartości logiczne)
    • string (łańcuchy znaków)

    Deklaracja zmiennych

    • Deklarowanie zmiennych (z typami)
    • Przykłady
    • Dostęp do elementów tablicy

    Deklaracja zmiennych tablicowych

    • Deklaracja zmiennych tablicowych dla różnego typu danych
    • Dostęp za pomocą operatorów tablicowych [] dla elementów tablicy.
    • Wartość tablic przy inicjalizacji.

    Blok instrukcji

    • Bloki instrukcji – pogrupowane grupy instrukcji.
    • Separacja instrukcji w blokach instrukcji.
    • Wprowadzenie przykładów bloków instrukcji.

    Instrukcja przypisania

    • Instrukcja przypisania – przypisanie wartości wyrażenia do zmiennej.
    • Przykłady instrukcji przypisania

    Instrukcja warunkowa

    • Instrukcja if-then-else – rozgałęzienie algorytmu w zależności od warunku.
    • Zasady tworzenia i stosowania instrukcji warunkowych.
    • Własne przykłady instrukcji warunkowych

    Przykłady instrukcji warunkowych

    • Rozmiarowy przykład if-then-else z różnymi warunkami.
    • Przykład w programowaniu

    Instrukcja pętli while

    • Instrukcja pętli while – iterowanie przez blok instrukcji tak długo, jak warunek jest spełniony.
    • Wprowadzenie przykładów

    Instrukcja pętli for

    • Instrukcja pętli for – iterowanie przez blok instrukcji określony zakres iteracji.
    • Formy pętli for – do, downto.
    • Przykłady instrukcji pętli for

    Definicja funkcji

    • Definiowanie funkcji, procedur w pseudokodzie.
    • Parametry formalne i aktualne w funkcjach.
    • Deklaracja zmiennych.

    Przykład funkcji

    • Definicja funkcji obliczającej silnię.
    • Wywołanie funkcji

    Definicja procedury

    • Definicja procedury.
    • Parametry procedury.
    • Deklaracja zmiennych proceduralnych

    Przykład procedury

    • Definicja procedury obliczającej sumę elementów tablicy.
    • Wywołanie procedury.

    Trzy predefiniowane funkcje i procedury

    • Funkcja i procedura Print (wypisuje dane)
    • Funkcja Read (Odczytuje dane)
    • Funkcja Length (zwraca długość stringa lub tablicy)

    Podstawowe funkcje matematyczne

    • Funkcje matematyczne (sqr, sqrt, pow, log, abs, min, max, floor, ceil)

    Ręczne śledzenie działania programu metoda tabelkowa

    • Jak śledzić ręcznie wartości zmiennych podczas działania programu.
    • Tabela do śledzenia wykonania programu.
    • Celem śledzenia jest odnalezienie potencjalnych błędów w programie.
    • Przykład algorytmu i jego śledzenia.

    Notacje asymptotyczne

    • Wprowadzenie i definicje notacji asymptotycznych.

    Mniejszy, równy i większy rząd funkcji

    • porównanie funkcji z punktu widzenia asymptotycznego
    • notacje f = Ω(g), f = 0(g), f = Ɵ(g).

    Wniosek o rzędach funkcji

    • Wnioski na temat rzędów funkcji w oparciu o ich definicje.

    Porównanie różnych funkcji z punktu widzenia ich rzędów

    • Porównanie funkcji i ich rzędów.
    • Poszczególne funkcje jako przykłady.

    Ograniczenie funkcji z dołu

    • Określenie i uzasadnienie warunków ograniczenia funkcji z dołu.
    • Definicje oraz przykłady.

    Ograniczenie funkcji z góry

    • Określenie i uzasadnienie warunków ograniczenia funkcji z góry.

    Ograniczenie funkcji z dołu i z góry

    • Zestawienie zasad ograniczeń z dołu i z góry dla funkcji.
    • Przykładowa tabelka porównawcza.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Wprowadzenie do Algorytmów i Struktur Danych PDF

    Description

    Ten quiz dotyczy wprowadzenia do przedmiotu 'Algorytmy i struktury danych', omówionych przez Jana G. Bazana. Znajdziesz w nim pytania dotyczące ważnych koncepcji oraz literatury związanej z tematem. Przygotuj się na egzaminy i sprawdź swoją wiedzę na temat algorytmów.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser