Informatyka teoretyczna - Theoretical computer science

Ten artykuł dotyczy dziedziny informatyki i matematyki. Czasopismo, patrz Informatyka teoretyczna (czasopismo) .
Artystyczne przedstawienie maszyny Turinga . Maszyny Turinga służą do modelowania ogólnych urządzeń obliczeniowych.

Informatyka teoretyczna ( TCS ) to podzbiór ogólnej informatyki i matematyki, który koncentruje się na matematycznych aspektach informatyki, takich jak teoria obliczeń , rachunek lambda i teoria typów .

Trudno precyzyjnie określić obszary teoretyczne. ACM „s Special Interest Group na algorytmach i Systemów Theory (SIGACT) przewiduje następujący opis:

TCS obejmuje szeroki zakres tematów, w tym algorytmów , struktur danych , złożoności obliczeniowej , równolegle i rozproszonych obliczeń, probabilistyczny obliczeń , obliczeń kwantowych , teorii automatów , teorii informacji , kryptografii , semantyki programowych i weryfikacji , uczenia maszynowego , biologii obliczeniowej , obliczeniowych ekonomii , obliczeniowych geometria oraz obliczeniowa teoria liczb i algebra . Praca w tej dziedzinie wyróżnia się często naciskiem na technikę matematyczną i rygoryzm .

Historia

Główny artykuł: Historia informatyki

Podczas gdy wnioskowanie logiczne i dowód matematyczny istniały wcześniej, w 1931 Kurt Gödel udowodnił swoim twierdzeniem o niezupełności, że istnieją fundamentalne ograniczenia dotyczące tego, jakie twierdzenia można udowodnić lub obalić.

Te osiągnięcia doprowadziły do ​​nowoczesnych badań nad logiką i obliczalnością , a także w całej dziedzinie informatyki teoretycznej. Teoria informacji została dodana do dziedziny matematycznej teorii komunikacji Claude'a Shannona z 1948 roku . W tej samej dekadzie Donald Hebb wprowadził matematyczny model uczenia się w mózgu. Wraz z gromadzeniem danych biologicznych wspierających tę hipotezę z pewnymi modyfikacjami, ustanowiono dziedziny sieci neuronowych i równoległego przetwarzania rozproszonego . W 1971 roku Stephen Cook i pracujący niezależnie Leonid Levin udowodnili, że istnieją praktycznie istotne problemy, które są NP-zupełne – przełomowy wynik w teorii złożoności obliczeniowej .

Wraz z rozwojem mechaniki kwantowej na początku XX wieku pojawiła się koncepcja, że ​​operacje matematyczne mogą być wykonywane na całej funkcji falowej cząstki. Innymi słowy, można obliczyć funkcje w wielu stanach jednocześnie. Doprowadziło to do powstania koncepcji komputera kwantowego w drugiej połowie XX wieku, która pojawiła się w latach 90., kiedy Peter Shor pokazał, że takie metody mogą być stosowane do rozkładania dużych liczb w czasie wielomianowym , co, jeśli zostanie zaimplementowane, spowoduje, że niektóre nowoczesne algorytmy kryptografii klucza publicznego , takie jak RSA_ (kryptosystem) są niepewne.

Współczesne badania w zakresie informatyki teoretycznej opierają się na tych podstawowych osiągnięciach, ale obejmują wiele innych problemów matematycznych i interdyscyplinarnych, które zostały postawione, jak pokazano poniżej:

DFAprzyklad.svg Krzywa eliptyczna simple.png 6n-graf.svg Wang płytki.svg P = NP  ?
Logika matematyczna Teoria automatów Teoria liczb Teoria grafów Teoria obliczalności Teoria złożoności obliczeniowej
GNITIRW-TERCES Diagram przemienny dla morfizmu.svg SimplexRangeSearching.svg TSP Polska 3.png Blochsphere.svg
Kryptografia Teoria typów Teoria kategorii Geometria obliczeniowa Optymalizacja kombinatoryczna Teoria obliczeń kwantowych

Tematy

Algorytmy

Główny artykuł: algorytm

Algorytm jest procedura krok po kroku do obliczeń. Algorytmy są wykorzystywane do obliczeń , przetwarzania danych i automatycznego wnioskowania .

Algorytm to skuteczna metoda wyrażona jako skończona lista dobrze zdefiniowanych instrukcji obliczania funkcji . Zaczynając od stanu początkowego i początkowego wejścia (być może pustego ), instrukcje opisują obliczenia, które po wykonaniu przebiegają przez skończoną liczbę dobrze zdefiniowanych kolejnych stanów, ostatecznie wytwarzając „wyjście” i kończąc w końcowym stanie końcowym. Przejście z jednego stanu do drugiego niekoniecznie jest deterministyczne ; niektóre algorytmy, znane jako algorytmy randomizowane , zawierają losowe dane wejściowe.

Teoria automatów

Główny artykuł: Teoria automatów

Teoria automatów to nauka o abstrakcyjnych maszynach i automatach , a także o problemach obliczeniowych, które można za ich pomocą rozwiązać. Jest to teoria informatyki teoretycznej, w ramach matematyki dyskretnej (dział matematyki, a także informatyki ). Automata pochodzi od greckiego słowa αὐτόματα oznaczającego „samoczynne”.

Teoria automatów to nauka o samoczynnie działających maszynach wirtualnych, która pomaga w logicznym zrozumieniu procesu wejścia i wyjścia, bez lub z pośrednimi etapami obliczeń (lub dowolnej funkcji /procesu).

Teoria kodowania

Główny artykuł: Teoria kodowania

Teoria kodowania to nauka o właściwościach kodów i ich przydatności do konkretnego zastosowania. Kody są używane do kompresji danych , kryptografii , korekcji błędów, a od niedawna także do kodowania sieciowego . Kody są badane przez różne dyscypliny naukowe — takie jak teoria informacji , elektrotechnika , matematyka i informatyka — w celu projektowania wydajnych i niezawodnych metod transmisji danych . Zwykle wiąże się to z usunięciem nadmiarowości i korektą (lub wykryciem) błędów w przesyłanych danych.

Biologia obliczeniowa

Główny artykuł: Biologia obliczeniowa

Biologia obliczeniowa obejmuje rozwój i zastosowanie metod analitycznych i teoretycznych, modelowania matematycznego i technik symulacji obliczeniowej do badania systemów biologicznych, behawioralnych i społecznych. Dziedzina jest szeroko zdefiniowana i obejmuje podstawy informatyki, matematyki stosowanej , animacji , statystyki , biochemii , chemii , biofizyki , biologii molekularnej , genetyki , genomiki , ekologii , ewolucji , anatomii , neuronauki i wizualizacji .

Biologia obliczeniowa różni się od obliczeń biologicznych , które są poddziedziną informatyki i inżynierii komputerowej wykorzystującej bioinżynierię i biologię do budowy komputerów , ale jest podobna do bioinformatyki , która jest nauką interdyscyplinarną wykorzystującą komputery do przechowywania i przetwarzania danych biologicznych.

Teoria złożoności obliczeniowej

Główny artykuł: Teoria złożoności obliczeniowej

Teoria złożoności obliczeniowej jest gałęzią teorii obliczeń, która koncentruje się na klasyfikowaniu problemów obliczeniowych według ich wrodzonej trudności i powiązaniu tych klas ze sobą. Przez problem obliczeniowy rozumie się zadanie, które w zasadzie może być rozwiązane przez komputer, co jest równoznaczne ze stwierdzeniem, że problem można rozwiązać przez mechaniczne zastosowanie kroków matematycznych, takich jak algorytm .

Problem jest uważany za z natury trudny, jeśli jego rozwiązanie wymaga znacznych zasobów, niezależnie od zastosowanego algorytmu . Teoria formalizuje tę intuicję, wprowadzając matematyczne modele obliczeniowe do badania tych problemów i ilościowego określania ilości zasobów potrzebnych do ich rozwiązania, takich jak czas i przechowywanie. Stosowane są również inne miary złożoności , takie jak ilość komunikacji (używana w złożoności komunikacji ), liczba bramek w obwodzie (używana w złożoności obwodu ) i liczba procesorów (używana w obliczeniach równoległych ). Jedną z ról teorii złożoności obliczeniowej jest określenie praktycznych ograniczeń tego, co komputery mogą, a czego nie mogą zrobić.

Geometria obliczeniowa

Główny artykuł: Geometria obliczeniowa

Geometria obliczeniowa to dział informatyki poświęcony badaniu algorytmów, które można określić w kategoriach geometrii . Niektóre czysto geometryczne problemy wynikają z badania obliczeniowych algorytmów geometrycznych i takie problemy są również uważane za część geometrii obliczeniowej. Podczas gdy współczesna geometria obliczeniowa jest najnowszym osiągnięciem, jest jedną z najstarszych dziedzin informatyki, której historia sięga starożytności. Starożytnym prekursorem jest sanskrycki traktat Shulba Sutras , czyli „Zasady akordu”, czyli księga algorytmów napisana w 800 roku p.n.e. Książka opisuje krok po kroku procedury konstruowania obiektów geometrycznych, takich jak ołtarze, za pomocą kołka i cięciwy.

Głównym impulsem do rozwoju geometrii obliczeniowej jako dyscypliny był postęp w grafice komputerowej oraz komputerowym wspomaganiu projektowania i wytwarzania ( CAD / CAM ), ale wiele problemów w geometrii obliczeniowej ma charakter klasyczny i może pochodzić z wizualizacji matematycznej .

Inne ważne zastosowania geometrii obliczeniowej obejmują robotykę (planowanie ruchu i problemy widoczność), systemów informacji geograficznej (GIS) (geometrycznego położenia oraz wyszukiwanie, planowanie trasy), układ scalony projektowe (IC projektowania geometrii i weryfikacji), inżynierii wspomaganej komputerowo (CAE) (generowanie siatek), wizja komputerowa (rekonstrukcja 3D).

Teoria uczenia się komputerowego

Główny artykuł: Teoria uczenia obliczeniowego

Teoretyczne wyniki uczenia maszynowego dotyczą głównie uczenia się indukcyjnego zwanego uczeniem nadzorowanym. W uczeniu nadzorowanym algorytm otrzymuje próbki, które są oznaczone w jakiś użyteczny sposób. Na przykład próbki mogą być opisami grzybów, a etykiety mogą wskazywać, czy grzyby są jadalne. Algorytm pobiera te wcześniej oznaczone próbki i wykorzystuje je do wywołania klasyfikatora. Ten klasyfikator to funkcja, która przypisuje etykiety do próbek, w tym próbek, które nigdy wcześniej nie były widziane przez algorytm. Celem nadzorowanego algorytmu uczenia się jest optymalizacja niektórych wskaźników wydajności, takich jak minimalizacja liczby błędów popełnianych na nowych próbkach.

Obliczeniowa teoria liczb

Główny artykuł: Obliczeniowa teoria liczb

Obliczeniowa teoria liczb , znana również jako algorytmiczna teoria liczb , zajmuje się badaniem algorytmów wykonywania obliczeń w teorii liczb . Najbardziej znanym problemem w tej dziedzinie jest faktoryzacja liczb całkowitych .

Kryptografia

Główny artykuł: Kryptografia

Kryptografia to praktyka i nauka technik bezpiecznej komunikacji w obecności osób trzecich (tzw. adwersarzy ). Mówiąc bardziej ogólnie, chodzi o konstruowanie i analizowanie protokołów , które przezwyciężyć wpływ przeciwników i które są związane z różnymi aspektami w zakresie bezpieczeństwa informacji , takich jak dane dotyczące poufności , integralności danych , uwierzytelniania i niezaprzeczalności . Współczesna kryptografia przecina dyscypliny matematyki , informatyki i elektrotechniki . Zastosowania kryptografii obejmują karty bankomatowe , hasła komputerowe i handel elektroniczny .

Współczesna kryptografia jest mocno oparta na teorii matematycznej i praktyce informatycznej; Algorytmy kryptograficzne są zaprojektowane w oparciu o założenia dotyczące twardości obliczeniowej , co sprawia, że ​​takie algorytmy są trudne do złamania w praktyce przez każdego przeciwnika. Teoretycznie możliwe jest złamanie takiego systemu, ale jest to niewykonalne w jakikolwiek znany praktyczny sposób. Schematy te są zatem określane jako bezpieczne obliczeniowo; postępy teoretyczne, np. udoskonalenia algorytmów faktoryzacji liczb całkowitych , oraz szybsze technologie obliczeniowe wymagają ciągłego dostosowywania tych rozwiązań. Istnieją teoretycznie bezpieczne schematy, których dowodem nie da się złamać nawet przy nieograniczonej mocy obliczeniowej – przykładem jest jednorazowy pad – ale te schematy są trudniejsze do wdrożenia niż najlepsze teoretycznie możliwe do złamania, ale obliczeniowo bezpieczne mechanizmy.

Struktury danych

Główny artykuł: Struktura danych

Struktura danych jest szczególnym sposobem organizowania danych w komputerze tak, że może on być stosowany skutecznie .

Różne rodzaje struktur danych są dostosowane do różnych rodzajów aplikacji, a niektóre są wysoce wyspecjalizowane do określonych zadań. Na przykład bazy danych używają indeksów B-drzewa dla niewielkich procentów pobierania danych i kompilatorów, a bazy danych używają dynamicznych tabel mieszających jako tabel wyszukiwania.

Struktury danych zapewniają środki do efektywnego zarządzania dużymi ilościami danych do zastosowań takich jak duże bazy danych i usługi indeksowania w Internecie . Zwykle wydajne struktury danych są kluczem do projektowania wydajnych algorytmów . Niektóre formalne metody projektowania i języki programowania kładą nacisk na struktury danych, a nie algorytmy, jako kluczowy czynnik organizujący w projektowaniu oprogramowania. Przechowywanie i wyszukiwanie może odbywać się na danych przechowywanych zarówno w pamięci głównej, jak iw pamięci dodatkowej .

Obliczenia rozproszone

Główny artykuł: Obliczenia rozproszone

Obliczenia rozproszone badają systemy rozproszone. System rozproszony to system oprogramowania, w którym komponenty znajdujące się na komputerach w sieci komunikują się i koordynują swoje działania poprzez przekazywanie wiadomości . Komponenty współdziałają ze sobą, aby osiągnąć wspólny cel. Trzy istotne cechy systemów rozproszonych to: współbieżność komponentów, brak zegara globalnego i niezależna awaria komponentów. Przykłady systemów rozproszonych różnią się od systemów opartych na architekturze SOA do gier Massively Multiplayer Online do sieci peer-to-peer i blockchain sieciach takich jak Bitcoin .

Program komputerowy działający w systemie rozproszonym nazywany jest programem rozproszonym , a programowanie rozproszone to proces pisania takich programów. Istnieje wiele alternatyw dla mechanizmu przekazywania komunikatów, w tym łączniki typu RPC i kolejki komunikatów . Ważnym celem i wyzwaniem systemów rozproszonych jest przejrzystość lokalizacji .

Złożoność oparta na informacjach

Główny artykuł: złożoność oparta na informacjach

Złożoność oparta na informacjach (IBC) bada optymalne algorytmy i złożoność obliczeniową dla ciągłych problemów. IBC badał zagadnienia ciągłe, takie jak całkowanie po torze, równania różniczkowe cząstkowe, układy równań różniczkowych zwyczajnych, równania nieliniowe, równania całkowe, punkty stałe i całkowanie bardzo wysokowymiarowe.

Metody formalne

Główny artykuł: Metody formalne

Metody formalne są szczególnym rodzajem technik opartych na matematyce , służących do specyfikacji , rozwoju i weryfikacji systemów oprogramowania i sprzętu . Zastosowanie metod formalnych do projektowania oprogramowania i sprzętu jest motywowane oczekiwaniem, że, podobnie jak w innych dyscyplinach inżynierskich, wykonanie odpowiedniej analizy matematycznej może przyczynić się do niezawodności i odporności projektu.

Metody formalne najlepiej można opisać jako zastosowanie dość szerokiej gamy podstaw teoretycznych informatyki, w szczególności rachunków logicznych , języków formalnych , teorii automatów i semantyki programów , ale także systemów typów i algebraicznych typów danych do problemów w specyfikacji oprogramowania i sprzętu oraz weryfikacja.

Teoria informacji

Główny artykuł: Teoria informacji

Teoria informacji jest gałęzią matematyki stosowanej , elektrotechniki i informatyki obejmujących ilościową z informacji . Teoria informacji została opracowana przez Claude'a E. Shannona w celu znalezienia podstawowych ograniczeń operacji przetwarzania sygnału, takich jak kompresja danych oraz niezawodnego przechowywania i przekazywania danych. Od momentu powstania rozszerzyła się, aby znaleźć zastosowanie w wielu innych dziedzinach, w tym wnioskowaniu statystycznym , przetwarzaniu języka naturalnego , kryptografii , neurobiologii , ewolucji i funkcji kodów molekularnych, selekcji modeli w statystyce, fizyce termicznej, informatyce kwantowej , lingwistyce , wykrywaniu plagiatów, rozpoznawanie wzorców , wykrywanie anomalii i inne formy analizy danych .

Zastosowania podstawowych zagadnień teorii informacji obejmują bezstratną kompresję danych (np. pliki ZIP ), stratną kompresję danych (np. MP3 i JPEG ) oraz kodowanie kanałów (np. dla cyfrowej linii abonenckiej (DSL) ). Dziedzina ta znajduje się na przecięciu matematyki , statystyki , informatyki , fizyki , neurobiologii i elektrotechniki . Jego wpływ był kluczowy dla sukcesu misji Voyager w kosmos, wynalezienia płyty kompaktowej, wykonalności telefonów komórkowych, rozwoju Internetu , badania lingwistyki i ludzkiej percepcji, zrozumienia czarnych dziur , i wiele innych dziedzin. Ważne sub-dziedziny teorii informacji są źródłem kodowanie , kodowanie kanału , algorytmicznej teorii złożoności , algorytmicznej teorii informacji , bezpieczeństwo informacji, teoretyczny , a środki informacji.

Nauczanie maszynowe

Główny artykuł: Uczenie maszynowe

Uczenie maszynowe to dyscyplina naukowa zajmująca się konstruowaniem i badaniem algorytmów, które mogą uczyć się na podstawie danych. Takie algorytmy działają poprzez budowanie modelu opartego na danych wejściowych i wykorzystywanie go do przewidywania lub podejmowania decyzji, zamiast wykonywania wyłącznie wyraźnie zaprogramowanych instrukcji.

Uczenie maszynowe można uznać za poddziedzinę informatyki i statystyki . Ma silne powiązania ze sztuczną inteligencją i optymalizacją , które dostarczają metod, teorii i dziedzin zastosowań w terenie. Uczenie maszynowe jest wykorzystywane w szeregu zadań obliczeniowych, w których projektowanie i programowanie jawnych algorytmów opartych na regułach jest niewykonalne. Przykładowe zastosowania obejmują filtrowanie spamu , optyczne rozpoznawanie znaków (OCR), wyszukiwarki i wizja komputerowa . Uczenie maszynowe jest czasami mylone z eksploracją danych , chociaż skupia się ono bardziej na eksploracyjnej analizie danych. Uczenie maszynowe i rozpoznawanie wzorców „można postrzegać jako dwa aspekty tej samej dziedziny”.

Obliczenia równoległe

Główny artykuł: obliczenia równoległe

Obliczenia równoległe to forma obliczeń, w której wiele obliczeń jest wykonywanych jednocześnie, działając na zasadzie, że często duże problemy można podzielić na mniejsze, które następnie rozwiązuje się „równolegle” . Istnieje kilka różnych form przetwarzania równoległego: bit-poziom , poziom instrukcje , dane i równoległość zadanie . Równoległość jest stosowana od wielu lat, głównie w obliczeniach o wysokiej wydajności , ale zainteresowanie nią wzrosło ostatnio ze względu na fizyczne ograniczenia uniemożliwiające skalowanie częstotliwości . Ponieważ zużycie energii (a w konsekwencji wytwarzanie ciepła) przez komputery stało się problemem w ostatnich latach, przetwarzanie równoległe stało się dominującym paradygmatem w architekturze komputerowej , głównie w postaci procesorów wielordzeniowych .

Programy komputerowe równoległe są trudniejsze do napisania niż sekwencyjne, ponieważ współbieżność wprowadza kilka nowych klas potencjalnych błędów oprogramowania , z których najczęstsze są wyścigi . Komunikacja i synchronizacja między różnymi podzadaniami to zazwyczaj jedne z największych przeszkód w uzyskaniu dobrej wydajności programów równoległych.

Maksymalne możliwe przyspieszenie pojedynczego programu w wyniku zrównoleglenia jest znane jako prawo Amdahla .

Semantyka programu

Główny artykuł: Semantyka programu

W programowaniu teorii języka , semantyka jest pole dotyczy rygorystycznego badania matematycznego sensu języków programowania . Czyni to, oceniając znaczenie syntaktycznie prawidłowych ciągów znaków zdefiniowanych przez określony język programowania, pokazując związane z tym obliczenia. W takim przypadku, gdy ocena będzie składała się z niedozwolonych składniowo ciągów, wynik byłby nieobliczalny. Semantyka opisuje procesy, za pomocą których komputer wykonuje program w tym konkretnym języku. Można to wykazać, opisując związek między danymi wejściowymi i wyjściowymi programu lub wyjaśniając, jak program będzie wykonywał się na określonej platformie , tworząc w ten sposób model obliczeń .

Obliczenia kwantowe

Główny artykuł: obliczenia kwantowe

Komputer kwantowy to system obliczeniowy , który bezpośrednio wykorzystuje zjawiska mechaniki kwantowej , takie jak superpozycja i splątanie , do wykonywania operacji na danych . Komputery kwantowe różnią się od komputerów cyfrowych opartych na tranzystorach . Podczas gdy komputery cyfrowe wymagają zakodowania danych w postaci cyfr binarnych ( bitów ), z których każdy znajduje się zawsze w jednym z dwóch określonych stanów (0 lub 1), obliczenia kwantowe wykorzystują kubity (bity kwantowe), które mogą znajdować się w superpozycji stanów. Modelem teoretycznym jest kwantowa maszyna Turinga , znana również jako uniwersalny komputer kwantowy. Komputery kwantowe mają podobieństwa teoretyczne z komputerami niedeterministycznymi i probabilistycznymi ; jednym z przykładów jest zdolność przebywania w więcej niż jednym stanie jednocześnie. Dziedzina obliczeń kwantowych została po raz pierwszy wprowadzona przez Yuri Manina w 1980 roku i Richarda Feynmana w 1982 roku. Komputer kwantowy ze spinami jako bitami kwantowymi został również sformułowany do użytku jako kwantowa czasoprzestrzeń w 1968 roku.

Od 2014 r. obliczenia kwantowe wciąż są w powijakach, ale przeprowadzono eksperymenty, w których kwantowe operacje obliczeniowe zostały wykonane na bardzo małej liczbie kubitów. Trwają zarówno praktyczne, jak i teoretyczne badania, a wiele rządów krajowych i wojskowych agencji finansujących wspiera badania w zakresie obliczeń kwantowych w celu opracowania komputerów kwantowych zarówno dla celów cywilnych, jak i bezpieczeństwa narodowego, takich jak kryptoanaliza .

Obliczenia symboliczne

Główny artykuł: symboliczne obliczenia

Algebra komputerowa , zwana również obliczeniami symbolicznymi lub obliczeniami algebraicznymi, jest dziedziną naukową, która odnosi się do badania i rozwoju algorytmów i oprogramowania do manipulowania wyrażeniami matematycznymi i innymi obiektami matematycznymi . Chociaż, właściwie mówiąc, algebra komputerowa powinna być poddziedziną obliczeń naukowych , są one ogólnie uważane za odrębne dziedziny, ponieważ obliczenia naukowe są zwykle oparte na obliczeniach numerycznych z przybliżonymi liczbami zmiennoprzecinkowymi , podczas gdy obliczenia symboliczne kładą nacisk na dokładne obliczenia za pomocą wyrażeń zawierających zmienne , które nie dowolna podana wartość i dlatego są manipulowane jako symbole (stąd nazwa obliczenia symbolicznego ).

Aplikacje programowe , które wykonują obliczenia symboliczne, nazywane są systemami algebry komputerowej , przy czym termin system odnosi się do złożoności głównych aplikacji, które obejmują co najmniej metodę reprezentacji danych matematycznych w komputerze, język programowania użytkownika (zwykle inny niż język używany do implementacji), dedykowany menedżer pamięci, interfejs użytkownika do wprowadzania/wyprowadzania wyrażeń matematycznych, duży zestaw procedur do wykonywania zwykłych operacji, takich jak uproszczenie wyrażeń, różnicowanie za pomocą reguły łańcucha , faktoryzacja wielomianowa , integracja nieograniczona itp. .

Integracja na bardzo dużą skalę

Główny artykuł: VLSI

Integracja na bardzo dużą skalę ( VLSI ) to proces tworzenia układu scalonego (IC) poprzez połączenie tysięcy tranzystorów w jednym układzie scalonym. VLSI rozpoczęło się w latach 70., kiedy opracowywano złożone technologie półprzewodnikowe i komunikacyjne . Mikroprocesor jest urządzenie VLSI. Przed wprowadzeniem technologii VLSI większość układów scalonych miała ograniczony zestaw funkcji, które mogły wykonywać. Układ elektroniczny może składać się z procesora , pamięci ROM , pamięci RAM i innych logiki kleju . VLSI pozwala producentom układów scalonych na dodanie wszystkich tych obwodów do jednego układu.

Organizacje

Czasopisma i biuletyny

Konferencje

Zobacz też

Uwagi

  1. ^ "SIGACT" . Źródło 2017-01-19 .
  2. ^ „Każdy klasyczny algorytm matematyczny, na przykład, można opisać skończoną liczbą angielskich słów” (Rogers 1987:2).
  3. ^ Dobrze zdefiniowany w odniesieniu do agenta wykonującego algorytm: „Istnieje agent obliczeniowy, zwykle człowiek, który może reagować na instrukcje i wykonywać obliczenia” (Rogers 1987:2).
  4. ^ "algorytm jest procedurą obliczania funkcji (w odniesieniu do pewnego wybranego zapisu liczb całkowitych) ... to ograniczenie (do funkcji numerycznych) nie powoduje utraty ogólności" (Rogers 1987:1).
  5. ^ „Algorytm ma zero lub więcej danych wejściowych, tj. ilości, które są mu podane na początku przed rozpoczęciem algorytmu” (Knuth 1973:5).
  6. ^ „Procedura, która ma wszystkie cechy algorytmu, z wyjątkiem tego, że prawdopodobnie brakuje jej skończoności, może być nazwana 'metodą obliczeniową'” (Knuth 1973:5).
  7. ^ "Algorytm ma jedno lub więcej wyjść, tj. wielkości, które mają określony związek z wejściami" (Knuth 1973:5).
  8. ^ To, czy proces z losowymi procesami wewnętrznymi (bez danych wejściowych) jest algorytmem, jest dyskusyjne. Rogers jest zdania, że: „obliczenia są przeprowadzane w sposób dyskretny, krok po kroku, bez użycia metod ciągłych lub urządzeń analogowych (…) deterministycznie, bez uciekania się do losowych metod lub urządzeń, np. kości” Rogers 1987:2.
  9. ^ „Definicja robocza NIH bioinformatyki i biologii obliczeniowej” (PDF) . Inicjatywa Biomedycznej Nauki i Technologii Informacyjnej. 17 lipca 2000. Zarchiwizowane z oryginału (PDF) w dniu 5 września 2012 . Źródło 18 sierpnia 2012 .
  10. ^ „O CCMB” . Centrum Komputerowej Biologii Molekularnej . Źródło 18 sierpnia 2012 .
  11. ^ Rivest, Ronald L. (1990). „Kryptologia”. W J. Van Leeuwen (red.). Podręcznik informatyki teoretycznej . 1 . Elsevier.
  12. ^ Bellare, Mihir; Rogaway, Phillip (21 września 2005). "Wstęp". Wprowadzenie do współczesnej kryptografii . P. 10.
  13. ^ Menezes, AJ; van Oorschota, PC; Vanstone, SA (1997). Podręcznik Kryptografii Stosowanej . Numer ISBN 978-0-8493-8523-0.
  14. ^ Paul E. Black (red.), wpis dotyczący struktury danych w Słowniku algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . 15 grudnia 2004. Wersja online Dostęp 21 maja 2009.
  15. ^ Struktura danych wejściowychw Encyclopædia Britannica (2009) Wpis online dostępny w dniu 21 maja 2009 r.
  16. ^ B Coulouris George; Jean Dollimore ; Tima Kindberga; Gordona Blaira (2011). Systemy rozproszone: koncepcje i projektowanie (wyd. 5). Boston: Addison-Wesley. Numer ISBN 978-0-132-14301-1.
  17. ^ Andrews (2000) . Dolew (2000) . Ghosh (2007) , s. 10.
  18. ^ RW Butler (2001-08-06). „Co to są metody formalne?” . Źródło 2006-11-16 .
  19. ^ C. Michael Holloway. „Dlaczego inżynierowie powinni rozważyć metody formalne” (PDF) . XVI Konferencja Systemów Awioniki Cyfrowej (27-30 października 1997). Zarchiwizowane z oryginału (PDF) w dniu 16 listopada 2006 . Źródło 2006-11-16 . Cytowanie dziennika wymaga |journal=( pomoc )
  20. ^ Monin, s. 3-4
  21. ^ F. Rieke; D. Warland; R. Ruyter van Steveninck; W. Białek (1997). Spikes: Odkrywanie kodu neuronowego . Prasa MIT. Numer ISBN 978-0262681087.
  22. ^ Huelsenbeck, JP; Ronquist, F.; Nielsen R.; Bollback, JP (2001-12-14). „Bayesowskie wnioskowanie filogenezy i jego wpływ na biologię ewolucyjną”. Nauka . Amerykańskie Stowarzyszenie Postępu Naukowego (AAAS). 294 (5550): 2310-2314. Kod Bib : 2001Sci...294.2310H . doi : 10.1126/science.1065889 . ISSN  0036-8075 . PMID  11743192 . S2CID  2138288 .
  23. ^ Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider , Michael Dean (1998) Organizacja genu ABCR: analiza sekwencji połączeń promotora i splicingu, Gene 215 : 1, 111-122
  24. ^ Burnham, KP i Anderson DR (2002) Wybór modelu i wnioskowanie wielomodelowe: praktyczne podejście teoretyczne, wydanie drugie (Springer Science, New York) ISBN  978-0-387-95364-9 .
  25. ^ Jaynes, ET (1957.05.15). „Teoria informacji i mechanika statystyczna”. Przegląd fizyczny . Amerykańskie Towarzystwo Fizyczne (APS). 106 (4): 620–630. Kod bib : 1957PhRv..106..620J . doi : 10.1103/physrev.106.620 . ISSN  0031-899X .
  26. ^ Charles H. Bennett, Ming Li i Bin Ma (2003) Listy łańcuchowe i historie ewolucyjne , Scientific American 288 : 6, 76-81
  27. ^ David R. Anderson (1 listopada 2003). „Pewne tło wyjaśniające, dlaczego ludzie zajmujący się naukami empirycznymi mogą chcieć lepiej zrozumieć metody teorii informacji” (PDF) . Zarchiwizowane z oryginału (PDF) 23 lipca 2011 . Źródło 2010-06-23 .
  28. ^ Ron Kovahi; Foster Provost (1998). „Słownik terminów” . Uczenie maszynowe . 30 : 271–274. doi : 10.1023/A: 1007411609915 .
  29. ^ B C.M. Bishop (2006). Rozpoznawanie wzorców i uczenie maszynowe . Skoczek. Numer ISBN 978-0-387-31073-2.
  30. ^ Wernick, Yang, Brankov, Yourganov i Strother, Uczenie maszynowe w obrazowaniu medycznym, IEEE Signal Processing Magazine , tom. 27, nie. 4, lipiec 2010, s. 25-38
  31. ^ Mannila, Heikki (1996). Eksploracja danych: uczenie maszynowe, statystyki i bazy danych . Konf. Zarządzanie naukowymi i statystycznymi bazami danych. Stowarzyszenie Komputerowe IEEE.
  32. ^ Friedman, Jerome H. (1998). „Eksploracja danych i statystyki: jaki jest związek?”. Informatyka i statystyka . 29 (1): 3-9.
  33. ^ Gottlieb, Allan; Almasi, George S. (1989). Wysoce równoległe przetwarzanie . Redwood City, Kalifornia: Benjamin/Cummings. Numer ISBN 978-0-8053-0177-9.
  34. ^ SV Adve i in. (listopad 2008). „Parallel Computing Research w Illinois: Agenda UPCRC” zarchiwizowane 09.12.2008 w Wayback Machine (PDF). Parallel@Illinois, Uniwersytet Illinois w Urbana-Champaign. „Główne techniki zapewniające te korzyści w zakresie wydajności – zwiększona częstotliwość zegara i inteligentniejsze, ale coraz bardziej złożone architektury – uderzają teraz w tak zwaną ścianę mocy. Przemysł komputerowy zaakceptował, że przyszły wzrost wydajności musi w dużej mierze wynikać ze zwiększenia liczby procesorów (lub rdzeni). ) na kostce, zamiast przyspieszać pojedynczy rdzeń."
  35. ^ Asanovic i in. Stara [konwencjonalna mądrość]: Moc jest darmowa, ale tranzystory są drogie. Nowa [konwencjonalna mądrość] mówi, że energia jest droga, ale tranzystory są „darmowe”.
  36. ^ Asanovic, Krste i in. (18 grudnia 2006). „The Landscape of Parallel Computing Research: A View from Berkeley” (PDF) . Uniwersytet Kalifornijski w Berkeley. Raport techniczny nr UCB/EECS-2006-183. „Stara [konwencjonalna mądrość]: Zwiększanie częstotliwości zegara jest podstawową metodą poprawy wydajności procesora. Nowa [konwencjonalna mądrość]: Zwiększanie równoległości jest podstawową metodą poprawy wydajności procesora… Nawet przedstawiciele Intela, firmy ogólnie kojarzonej z ' wyższa częstotliwość zegara jest lepszą pozycją, ostrzegł, że tradycyjne podejście do maksymalizacji wydajności poprzez maksymalizację częstotliwości zegara zostało zepchnięte do granic możliwości”.
  37. ^ Hennessy, John L.; Patterson, David A.; Larus, James R. (1999). Organizacja i projektowanie komputera: interfejs sprzęt/oprogramowanie (2. ed., 3rd print. ed.). San Francisco: Kaufmann. Numer ISBN 978-1-55860-428-5.
  38. ^ Artykuł" Quantum Computing with Molecules " w Scientific American autorstwa Neila Gershenfelda i Isaaca L. Chuanga
  39. ^ Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [ Obliczalne i Nieobliczalne ] (po rosyjsku). Sov.Radio. s. 13–15. Zarchiwizowane od oryginału w dniu 10 maja 2013 roku . Źródło 4 marca 2013 .
  40. ^ Feynman, RP (1982). „Symulowanie fizyki za pomocą komputerów”. Międzynarodowy Czasopismo Fizyki Teoretycznej . 21 (6): 467–488. Kod bib : 1982IJTP...21..467F . CiteSeerX  10.1.1.45.9310 . doi : 10.1007/BF02650179 . S2CID  124545445 .
  41. ^ Deutsch, David (1992-01-06). „Obliczenia kwantowe”. Fizyka Świat . 5 (6): 57–61. doi : 10.1088/2058-7058/5/6/38 .
  42. ^ Finkelstein, David (1968). „Struktura czasoprzestrzenna w interakcjach o wysokiej energii”. W Gudehus, T.; Kaiser, G. (red.). Podstawowe interakcje przy wysokiej energii . Nowy Jork: Gordon & Breach.
  43. ^ „Nowa kontrola kubitów dobrze wróży przyszłości obliczeń kwantowych” . Pobrano 26 października 2014 .
  44. ^ Mapa drogowa informatyki kwantowej i technologii, aby zorientować się, dokąd zmierzają badania.
  45. ^ B c d e 2007 australijski Ranking konferencji ICT zarchiwizowanej 2009-10-02 w Wayback Maszyna : warstwy A +.
  46. ^ MFK 2017
  47. ^ CSR 2018
  48. ^ B c d e f g h i j 2007 australijski Ranking konferencji ICT zarchiwizowanej 2009-10-02 w Wayback Maszyna : warstwa A.
  49. ^ FCT 2011 (pobrano 03.06.2013)

Dalsza lektura

Zewnętrzne linki