Ugrás a tartalomhoz

problem

A Wikiszótárból, a nyitott szótárból

Albán

Főnév

problem

  1. probléma

Angol

Kiejtés

  • IPA: /pɹɒbləm/
  • hallgatás (US)ⓘ

Főnév

problem (tsz. problems)

  1. probléma

További információk

Dán

Főnév

et problem sn

  1. probléma

Lengyel

Kiejtés

  • IPA: /ˈprɔb.lɛm/

Főnév

problem hn

  1. probléma

További információk

Norvég bokmål

Főnév

problem sn

  1. probléma

Svéd

Főnév

problemet sn

  1. probléma

Szerbhorvát

Főnév

problem hn (cirill írás проблем)

  1. probléma

További információk

Walesi

Főnév

problem nn

  1. probléma

Angol

Főnév

problem (tsz. problems)

  1. (informatika)

Classic computer science problems have been widely studied and solved using various algorithms, data structures, and computational techniques. Here’s a list of some well-known problems and their solutions:

1. Searching Problems

  • Binary Search (Efficient search in a sorted list, O(log n))
  • Linear Search (Simple but inefficient for large datasets, O(n))

2. Sorting Problems

  • Bubble Sort (Simple but inefficient, O(n²))
  • Merge Sort (Efficient divide-and-conquer approach, O(n log n))
  • Quick Sort (Fast in practice, O(n log n) average case)
  • Heap Sort (Uses a heap structure, O(n log n))

3. Graph Problems

  • Shortest Path Problem (Solved by Dijkstra’s Algorithm, Bellman-Ford, A*)
  • Minimum Spanning Tree (MST) (Solved by Kruskal’s and Prim’s algorithms)
  • Topological Sorting (Solved using Kahn’s algorithm or DFS)
  • Graph Traversal (Solved using BFS and DFS)

4. Dynamic Programming Problems

  • Fibonacci Sequence (Solved using memoization or bottom-up DP)
  • Knapsack Problem (0/1 Knapsack and Fractional Knapsack)
  • Longest Common Subsequence (LCS)
  • Matrix Chain Multiplication
  • Subset Sum Problem
  • Edit Distance (String Similarity)
  • Coin Change Problem

5. Computational Geometry Problems

  • Convex Hull Problem (Solved using Graham’s scan or Jarvis’s march)
  • Closest Pair of Points (Solved using Divide and Conquer)
  • Line Intersection Problem (Sweep line algorithm)

6. String Processing Problems

  • Pattern Matching (Solved by KMP, Rabin-Karp, Boyer-Moore algorithms)
  • Suffix Array and Suffix Tree Problems (Used for fast substring search)
  • Palindrome Checking (Manacher’s Algorithm for longest palindromic substring)

7. Number Theory and Cryptography

  • Greatest Common Divisor (GCD) (Solved using Euclidean algorithm)
  • Primality Testing (Miller-Rabin, AKS primality test)
  • Integer Factorization (Pollard’s rho algorithm)
  • Modular Exponentiation (Used in cryptography)

8. Artificial Intelligence and Machine Learning

  • Game Playing (Minimax Algorithm) (Used in chess, tic-tac-toe, etc.)
  • Neural Networks (Backpropagation Algorithm)
  • Clustering (K-Means Algorithm)
  • Decision Trees and Random Forests

9. Parallel and Distributed Computing

  • MapReduce (Used for distributed computing)
  • Load Balancing Algorithms
  • Synchronization Problems (Solved using semaphores, locks)

10. Computational Complexity and NP-Hard Problems

  • Traveling Salesman Problem (TSP) (Solved using Dynamic Programming or Approximation Algorithms)
  • Graph Coloring Problem (Backtracking or Greedy approaches)
  • Boolean Satisfiability Problem (SAT) (Solved using the DPLL algorithm)

These problems have been extensively studied, and efficient solutions exist for most of them. However, for NP-hard problems, exact solutions may not be feasible, and approximations or heuristics are used.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=problem&oldid=3490051”