| dbo:abstract
|
- La teoria de complexitat computacional és la part de la teoria de la computabilitat que estudia els recursos requerits durant el càlcul per resoldre un problema. Els recursos comunament estudiats són el temps (nombre de passos d'execució d'un algorisme per resoldre un problema) i l'espai (quantitat de memòria utilitzada per soldre un problema). Poden estudiar-se igualment altres paràmetres, com el nombre de processadors necessaris per resoldre el problema en paral·lel. La teoria de la complexitat difereix de la teoria de la computabilitat en què aquesta última s'ocupa de la factibilitat d'expressar problemes com algorismes efectius sense tenir en compte els recursos necessaris per aconseguir-ho. Els problemes que tenen una solució amb ordre de complexitat lineal són els problemes que es resolen en un temps que es relaciona linealment amb la seva mida. Avui en dia les màquines resolen problemes mitjançant algorismes que tenen com a màxim una complexitat o cost computacional polinòmic, és a dir, la relació entre la mida del problema i el seu temps d'execució és polinòmic. Aquests són els problemes agrupats en el conjunt P. Els problemes amb cost factorial o estan agrupats en el conjunt NP. Aquests problemes no tenen una solució pràctica, és a dir, una màquina no pots resoldre'ls en un temps raonable. (ca)
- In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm. Moreover, for designing efficient algorithms, it is often fundamental to compare the complexity of a specific algorithm to the complexity of the problem to be solved. Also, in most cases, the only thing that is known about the complexity of a problem is that it is lower than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory. As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function n → f(n), where n is the size of the input and f(n) is either the worst-case complexity (the maximum of the amount of resources that are needed over all inputs of size n) or the average-case complexity (the average of the amount of resources over all inputs of size n). Time complexity is generally expressed as the number of required elementary operations on an input of size n, where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. Space complexity is generally expressed as the amount of memory required by an algorithm on an input of size n. (en)
- Der Begriff Komplexität wird in der Informatik in verschiedenen Teilbereichen verwendet. Die Komplexitätstheorie befasst sich dabei mit dem Ressourcenverbrauch von Algorithmen, die Informationstheorie dagegen verwendet den Begriff für den Informationsgehalt von Daten, die Praktische Informatik wiederum bewertet damit Software oder Softwareteile hinsichtlich der Anzahl von Interaktionen. (de)
- Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów. Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, będąca drugą ważną gałęzią teorii obliczeń. Wyniki, jakie podaje t.z.o., można podzielić na dwie kategorie: pozytywne i negatywne, czyli na takie, które podają, co i jak można obliczyć, oraz takie, w których dowodzi się, czego nie da się obliczyć, wykorzystując określoną ilość zasobów. Wyniki pozytywne są łatwiejsze do uzyskania i zwykle mają postać algorytmu rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów. (pl)
- A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si. Neste contexto, um problema computacional é entendido como uma tarefa que é, em princípio, passível de ser resolvida por um computador (o que basicamente significa que o problema pode ser descrito por um conjunto de instruções matemáticas). Informalmente, um problema computacional consiste de instâncias do problema e soluções para essas instâncias do problema. Por exemplo, o teste de primalidade é o problema de determinar se um dado número é primo ou não. As instâncias deste problema são números naturais, e a solução para uma instância é sim ou não, dependendo se o número é primo ou não. Um problema é considerado como inerentemente difícil se a sua solução requer recursos significativos, qualquer que seja o algoritmo usado. A teoria formaliza esta intuição através da introdução de modelos matemáticos de computação para estudar estes problemas e quantificar os recursos necessários para resolvê-los, tais como tempo e armazenamento. Outras medidas de complexidade também são utilizadas, tais como a quantidade de comunicação (usada em complexidade de comunicação), o número de portas em um circuito (usado na ) e o número de processadores (usados em computação paralela). Um dos papéis da teoria da complexidade computacional é determinar os limites práticos do que os computadores podem e não podem fazer. Campos intimamente relacionados com a ciência da computação teórica são a análise de algoritmos e a teoria da computabilidade. Uma distinção chave entre a análise de algoritmos e teoria da complexidade computacional é que a primeira é dedicada a analisar a quantidade de recursos necessários para um determinado algoritmo resolver um problema, enquanto o segundo faz uma pergunta mais geral sobre todos os possíveis algoritmos que podem ser usados para resolver o mesmo problema. Mais precisamente, ele tenta classificar os problemas que podem ou não podem ser resolvidos com os recursos devidamente restritos. Por sua vez, impondo restrições sobre os recursos disponíveis é o que distingue a complexidade computacional da teoria da computabilidade: a segunda pergunta que tipos de problemas podem, em princípio, ser resolvidos através de algoritmos. (pt)
- Komplexitet beskriver inom beräkningsvetenskap hur omfattande och resurskrävande ett problem är. Vanligen löses beräkningsproblem med hjälp av en algoritm. Den lägsta komplexitet man känner till för en algoritm att lösa ett problem utgör en övre gräns för problemets komplexitet. När ett problems komplexitet ska bestämmas väljer man först en lösningsmodell och vilken storlek indata mäts i. För att bestämma en undre gräns krävs ofta matematiska beräkningar eller användningen av en trivial gräns. När den övre och undre gränsen överensstämmer med varandra har man bestämt problemets komplexitet. Inom datorprogrammering finns mätmetoder för att kvantitativt bestämma komplexitet av en metod/funktion eller en modul/klass:
* McCabe-tal, eller cyklomatisk komplexitet, som anger antal vägar genom en metod
* Efferent Couplings, antal beroenden till andra metoder, moduler eller klasser (till exempel referenser till externa data, metoder etc.)
* Infferent Couplings, antal beroenden från andra metoder, moduler eller klasser (till exempel referenser till externa data, metoder etc.)
* antal rader kod per metod, klass/modul
* arvsdjup (för klasser) (sv)
- Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми . Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжёра длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра). В частности, теория сложности вычислений определяет NP-полные задачи, которые недетерминированная машина Тьюринга может решить за полиномиальное время, тогда как для детерминированной машины Тьюринга полиномиальный алгоритм неизвестен. Обычно это сложные задачи оптимизации, например, задача коммивояжёра. С теоретической информатикой тесно связаны такие области как анализ алгоритмов и теория вычислимости. Связующим звеном между теоретической информатикой и алгоритмическим анализом является тот факт, что их формирование посвящено анализу необходимого количества ресурсов определённых алгоритмов решения задач, тогда как более общим вопросом является возможность использования алгоритмов для подобных задач. Конкретизируясь, попытаемся классифицировать проблемы, которые могут или не могут быть решены при помощи ограниченных ресурсов. Сильное ограничение доступных ресурсов отличает теорию вычислительной сложности от вычислительной теории, последняя отвечает на вопрос какие задачи, в принципе, могут быть решены алгоритмически. (ru)
- Складність обчислювальних процесів — це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу та пам'яті) необхідних для виконання алгоритму.
* Часова складність — час
* Просторова складність — пам'ять (uk)
|
| rdfs:comment
|
- Der Begriff Komplexität wird in der Informatik in verschiedenen Teilbereichen verwendet. Die Komplexitätstheorie befasst sich dabei mit dem Ressourcenverbrauch von Algorithmen, die Informationstheorie dagegen verwendet den Begriff für den Informationsgehalt von Daten, die Praktische Informatik wiederum bewertet damit Software oder Softwareteile hinsichtlich der Anzahl von Interaktionen. (de)
- Складність обчислювальних процесів — це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу та пам'яті) необхідних для виконання алгоритму.
* Часова складність — час
* Просторова складність — пам'ять (uk)
- La teoria de complexitat computacional és la part de la teoria de la computabilitat que estudia els recursos requerits durant el càlcul per resoldre un problema. Els recursos comunament estudiats són el temps (nombre de passos d'execució d'un algorisme per resoldre un problema) i l'espai (quantitat de memòria utilitzada per soldre un problema). Poden estudiar-se igualment altres paràmetres, com el nombre de processadors necessaris per resoldre el problema en paral·lel. La teoria de la complexitat difereix de la teoria de la computabilitat en què aquesta última s'ocupa de la factibilitat d'expressar problemes com algorismes efectius sense tenir en compte els recursos necessaris per aconseguir-ho. (ca)
- In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. (en)
- Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów. Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, będąca drugą ważną gałęzią teorii obliczeń. (pl)
- Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми . Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах (ru)
- Komplexitet beskriver inom beräkningsvetenskap hur omfattande och resurskrävande ett problem är. Vanligen löses beräkningsproblem med hjälp av en algoritm. Den lägsta komplexitet man känner till för en algoritm att lösa ett problem utgör en övre gräns för problemets komplexitet. När ett problems komplexitet ska bestämmas väljer man först en lösningsmodell och vilken storlek indata mäts i. För att bestämma en undre gräns krävs ofta matematiska beräkningar eller användningen av en trivial gräns. När den övre och undre gränsen överensstämmer med varandra har man bestämt problemets komplexitet. (sv)
- A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si. Neste contexto, um problema computacional é entendido como uma tarefa que é, em princípio, passível de ser resolvida por um computador (o que basicamente significa que o problema pode ser descrito por um conjunto de instruções matemáticas). Informalmente, um problema computacional consiste de instâncias do problema e soluções para essas instâncias do problema. Por exemplo, o teste de primalidade é o problema de determinar se um dado número é primo ou não. As instâncias deste problema são números naturais, e a solução para uma instância é sim (pt)
|
