Definicja problemu komputerowego to sposób formułowania problemu do rozwiązania. Problem obliczeniowy składa się ze zbioru dwóch elementów: wejścia i rozwiązania. Dane wejściowe i rozwiązanie są często podane parami i nazywane są instancją problemu. Instancja problemu to dany zbiór wejść i rozwiązań, a zbiór możliwych par nazywany jest językiem problemu. Aby zdefiniować problem, trzeba wiedzieć, jakiego typu wejścia i rozwiązania są wymagane.
Teoria złożoności obliczeniowej
Centralnym tematem teorii złożoności obliczeniowej jest badanie problemów decyzyjnych, które mają binarną odpowiedź tak lub nie. Problemy decyzyjne można traktować jako struktury języka formalnego, które mają instancje zwracające odpowiedź tak i instancje zwracające odpowiedź nie. Celem problemu jest określenie, czy dany ciąg informacji jest członkiem języka formalnego, a algorytm, który zwraca odpowiedź „tak”, mówi o przyjęciu lub odrzuceniu danych wejściowych.
Złożoność obliczeniowa problemu zależy od jego trudności. Mierzy się ją w kategoriach pamięci, miejsca i czasu potrzebnych do jego rozwiązania. Teoria złożoności ma zastosowanie w świecie rzeczywistym, zwłaszcza w projektowaniu algorytmów. Definiując algorytmy pod względem ich złożoności, inżynierowie komputerowi mogą projektować bardziej wydajne systemy i mniej zasobochłonne procesy. W praktyce teoria ta pomaga programistom zrozumieć, ile zasobów obliczeniowych będą potrzebować do rozwiązania problemu, a nawet może pomóc im wybrać odpowiedni algorytm.
Ponadto złożoność obliczeniowa może być scharakteryzowana przez zakres czasu. Podczas gdy niektóre problemy są trudne do rozwiązania za pomocą prostego algorytmu, inne wymagają rozwiązania w czasie wielomianowym, co może być niepraktyczne dla praktycznych zastosowań. Jednak dla większości problemów rozwiązanie w czasie wielomianowym może być praktyczne w przeciętnym przypadku, ponieważ wymaga dużej liczby zasobów do wykonania obliczeń.
Złożoność czasowa, która opisuje liczbę kroków potrzebnych do rozwiązania danego problemu, jest również znana jako „złożoność czasowa” problemu. Liczba kroków potrzebnych do rozwiązania instancji zależy od rozmiaru danych wejściowych. Najbardziej wydajny algorytm będzie w stanie rozwiązać instancję z zaledwie n kroków. Jednak dokładna liczba zależy od języka i maszyny użytej do stworzenia algorytmu. Problem ten jest często określany jako Big O, ponieważ ma wykładniczą skalę czasową.
Instancje problemu obliczeniowego
Instancja problemu obliczeniowego to konkretna wypowiedź, która jest wejściem do problemu. Instancja jest spełnialna, jeśli dane wejściowe pasują do rozwiązania problemu. W przeciwnym razie, instancja jest niezadowalająca. To samo dotyczy problemu decyzyjnego. W niektórych przypadkach instancje nazywane są podinstancjami, ponieważ mieszczą się w określonej niszy. Nisza ta może być wykorzystana algorytmicznie.
Instancje problemu obliczeniowego można scharakteryzować przez ich prawdopodobieństwo spełnienia. Na progu spełnialności występuje przejście fazowe w prawdopodobieństwie, co oznacza, że instancje znajdujące się bliżej progu są trudniejsze do rozwiązania niż te znajdujące się dalej. Średnia trudność instancji jest znana jako złożoność instancji i jest miarą trudności obliczeniowej poszczególnych instancji. Można ją obliczyć analizując cechy przestrzeni rozwiązań i problemu.
Złożoność instancji odnosi się do złożoności całego zbioru instancji i jest związana z trudnością problemu. Można ją wykorzystać do oceny twardości obliczeniowej danego problemu, jest też użytecznym narzędziem w badaniu ludzkiego poznania. Złożoność instancji mierzy odległość między progiem decyzyjnym a optymalną wartością możliwą do osiągnięcia. Klasycznym przykładem jest najkrótsza ścieżka pomiędzy wszystkimi miastami. Ten typ problemu był szeroko badany, ponieważ jest to klasyczny problem optymalizacji kombinatorycznej.
Jeśli x4 = 1, to zbiorem rozwiązań dla x4=1 jest punkt zamknięty i prosta afiniczna lub punkt zamknięty i okrąg. Problem ten można rozwiązać metodą k-SAT. Jeśli jednak zbiór rozwiązań dla x4=0, to problem k-SAT jest wielomianem n-tego stopnia. Wielomian n-tego stopnia to wielomian kwadratowy.
Iteracja rozwiązania
Iteracja to proces w programowaniu komputerowym, w którym sekwencja instrukcji jest powtarzana do momentu wystąpienia określonego zdarzenia lub określonej liczby powtórzeń. Na przykład kod HTML strony internetowej może nakazać komputerowi wielokrotne odświeżanie strony, aż użytkownik naciśnie przycisk. Algorytm może nakazać komputerowi zmienić układ liter w słowie, aż wszystkie będą miały taką samą pisownię.
Proces definiowania algorytmu komputerowego wymaga określonej liczby kroków, zwanych iteracjami. Jeśli algorytm składa się z nieskończonej liczby kroków, nie może być zapisany jako program komputerowy. Na szczęście większość języków programowania pozwala na powtarzanie czynności zwanych iteracjami. Pomaga to programiście napisać krótki opis algorytmu. Pozwala to również na kontrolowanie liczby kroków w zależności od danych wejściowych, dzięki czemu komputer może wykonywać te kroki tak często, jak to konieczne, nie powodując przy tym przejścia w nieskończoną pętlę.
Struktury i wskaźniki
W programie komputerowym wskaźniki pomagają zarządzać strukturami danych. Mogą być bezwzględne, być odwołaniem do adresu w pamięci wirtualnej lub przesunięciem od bezwzględnego adresu startowego. Wskaźniki są przydatne do przekazywania informacji do funkcji, zwracania wielu wartości z funkcji oraz wyświetlania zmian w danej strukturze danych. Wskaźniki są również używane do przekazywania parametrów przez odniesienie. Pointery są podstawowym elementem konstrukcyjnym w wielu językach programowania.
Wskaźniki są podstawowym elementem programów komputerowych. Obiekty te przechowują adresy pamięci i sterują przepływem programu. W programach komputerowych wskaźniki są często osadzone w wpisach tablicy, przechowującej punkty wejścia dla podprogramów. Służą one również jako środek do przemierzania algorytmów. Innym powszechnym zastosowaniem wskaźników są wtórne struktury danych. Struktury te przechowują adresy obiektów lub zmiennych. Poprzez dereferencję wskaźnika, komputer może pobrać wartość przechowywaną pod bazowym adresem pamięci.
Wskaźniki mogą wskazywać na dowolne typy. W zależności od platformy, na której uruchamiany jest program, mogą one wskazywać na nieskończoną liczbę typów danych. Częstym przykładem jest adres uzyskany za pomocą operatora &. Dziki wskaźnik jest niezainicjalizowanym wskaźnikiem. Może on uszkodzić inne części programu lub spowodować nieoczekiwane zachowanie. Jest to określane jako błąd segmentacji, naruszenie pamięci masowej lub dzikie rozgałęzienie.
Wskaźniki są używane do dynamicznej implementacji różnych struktur danych. Rozmiar wskaźnika zależy od architektury komputera. Wskaźniki są powszechnie stosowane we wszystkich językach komputerowych i każdy z nich wymaga wskaźnika do działania. Jeśli chcesz uzyskać dostęp do struktury danych, która ma wiele lokalizacji, wskaźniki są ważne. Możesz połączyć łańcuchowo wiele wskaźników, aby uzyskać określoną wartość.
Wejście i wyjście programu komputerowego
Wejście i wyjście programu komputerowego to dwa podstawowe pojęcia. Niektóre dane są bezpośrednio wprowadzane do komputera, np. kod kreskowy lub sygnał z mikrofonu. Inne dane przechodzą przez pośrednie przetwarzanie, takie jak kopiowanie z dokumentu i przekształcanie go na nośnik nadający się do odczytu maszynowego. W obu przypadkach dane wejściowe i wyjściowe są krytyczne dla funkcjonowania programu komputerowego. W tym artykule omówimy rolę wejścia i wyjścia w programach komputerowych oraz ich związek z użytkownikami.
Urządzenie wejściowe to urządzenie, którego użytkownik używa do wprowadzania danych do komputera. Przykładami urządzeń wejściowych są klawiatury i myszy. Do wprowadzania danych można również używać ekranu dotykowego, podobnie jak przenośnej klawiatury i myszy. Inne rodzaje urządzeń wejściowych to skanery, czujniki ruchu ciała i fale dźwiękowe. Wszystkie programy wymagają danych wejściowych i wyjściowych. Dane wejściowe są przechowywane w zmiennych, które są używane do uruchomienia programu. Wyjściem może być wydrukowany dokument, kartka papieru lub dźwięk.
Urządzenia wyjściowe to urządzenia, które przekształcają dane w formę inną niż ta, którą widzi komputer. Najczęściej jest to na ekranie komputera. Inne formy wyjścia obejmują dźwięk, wideo, mikrofilm i różne formy grafiki. Wejście i wyjście są niezbędne do funkcjonowania programu komputerowego. Istnieje wiele rodzajów urządzeń wejściowych i ich funkcji. Oto kilka popularnych przykładów:
W celu skoncentrowania się uczniów na nauce, możesz poprosić ich o przeprowadzenie burzy mózgów na temat przykładów wejścia i wyjścia z popularnych aplikacji komputerowych. Dla dodatkowego wyzwania możesz przeprowadzić burzę mózgów z wieloma przykładami wejścia i wyjścia w konkretnych zadaniach. Możesz nawet dać im bilet wyjściowy, jeśli wymyślą wiele przykładów wejścia i wyjścia. Kiedy mają już przykład, mogą porównać różne typy wejść i wyjść. Kiedy będą mieli kilka przykładów, mogą rozpocząć dyskusję na temat wejścia i wyjścia oraz jak te dwa różne typy wpływają na program komputerowy.
Podobne tematy