Przeskocz do treści

pierwsza strona

Wydanie Delty - luty 2020 r.

Problem komiwojażera w praktyce

Łukasz Kowalik

o artykule ...

  • Publikacja w Delcie: luty 2020
  • Publikacja elektroniczna: 1 lutego 2020
  • Autor: Łukasz Kowalik
    Afiliacja: Instytut Informatyki, Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (687 KB)

Korzystając z popularnych serwisów internetowych, błyskawicznie znajdziemy najkrótszą trasę między dwoma miastami. A co, gdybyśmy chcieli znaleźć najkrótszą trasę, która pozwoli po wyruszeniu z domu odwiedzić wszystkie interesujące nas miasta i wrócić do punktu wyjścia?

artykuły

Astronomia

  1. Astronomia Niebo jak własna kieszeń

    Niebo w lutym (2020)

    Luty to pierwszy miesiąc z wyraźnie wydłużającymi się dniami i skracającymi nocami. W ciągu miesiąca, który w tym roku ma 29 dni (2020 jest rokiem przestępnym), wysokość górowania Słońca zwiększy się z  ○ 21 do  ○ |30 , w związku z czym czas jego przybywania na nieboskłonie wzrośnie prawie do 11 godzin...

  2. Astronomia Prosto z nieba

    Zaskakująco dużo gazu w „martwych” galaktykach

    Jedno z fundamentalnych stwierdzeń współczesnej astronomii zakłada, że gwiazdy powstają w zimnym gęstym gazie molekularnym. Wszystkie modele tworzenia i ewolucji galaktyk, które przecież składają się między innymi z milionów gwiazd, oparte są bezpośrednio na tym założeniu. Wspierane jest ono przez obserwacje astronomiczne, które wskazują, że galaktyki aktywnie tworzące gwiazdy - zazwyczaj spiralne o niebieskim kolorze - posiadają duże zapasy zimnego gazu molekularnego, przez co szybka produkcja gwiazd może być w nich podtrzymywana. Z kolei w drugiej klasie galaktyk, charakteryzujących się kolorem czerwonym, produkcja gwiazd zanikła i wypełniają je jedynie stare gwiazdy, będące u schyłku swojego życia.

Astrofizyka

  1. Astrofizyka

    Spadek swobodny z księżycowej orbity

    Siła grawitacji sprawia, że jakikolwiek upuszczony przedmiot spada ruchem jednostajnie przyspieszonym. Wartość przyspieszenia ziemskiego znamy na pamięć. Można więc obliczyć położenie ciała i jego prędkość w dowolnej chwili. Również czas spadania wyznaczymy natychmiast, jeżeli tylko znamy wysokość początkową. Trudno o mniej wymagające zadanie z dynamiki.

Fizyka

Zastosowania fizyki

  1. Zastosowania fizyki

    Komputer kwantowy Google'a – przełom czy PR?

    Obliczenia kwantowe wykorzystują ideę superpozycji kwantowej, która pozwala na przygotowanie układów kwantowych w "wielu stanach jednocześnie", w celu uzyskania nieosiągalnego na komputerach klasycznych zrównoleglenia obliczeń i rozwiązania bardzo trudnych problemów matematycznych w czasie nieosiągalnym dla tradycyjnych urządzeń liczących. Przykładem obliczeń prostych dla komputerów kwantowych, a trudnych dla klasycznych, jest rozkład liczby na czynniki pierwsze. Trudność tego problemu jest kluczowa dla bezpieczeństwa ogromnej większości zaszyfrowanej komunikacji internetowej.

Algorytmy

  1. Algorytmy

    Problem komiwojażera w praktyce

    Korzystając z popularnych serwisów internetowych, błyskawicznie znajdziemy najkrótszą trasę między dwoma miastami. A co, gdybyśmy chcieli znaleźć najkrótszą trasę, która pozwoli po wyruszeniu z domu odwiedzić wszystkie interesujące nas miasta i wrócić do punktu wyjścia?

Matematyka

Analiza

Geometria

Geometrie nieeuklidesowe

Teoria liczb

  1. obrazek

    Teoria liczb

    Trudniej, a łatwiej

    Są twierdzenia łatwe i trudne do udowodnienia. Zazwyczaj im mocniejsze sformułowanie, obejmujące więcej przypadków, tym trudniej się je dowodzi. Tak jest na przykład z twierdzeniem cosinusów i twierdzeniem Pitagorasa, które jest jego szczególnym przypadkiem. Łatwiej jest udowodnić twierdzenie Pitagorasa; można to zrobić nawet w sposób zrozumiały dla przedszkolaka (zobacz rysunek obok). Do dowodu twierdzenia cosinusów trzeba przynajmniej wiedzieć, co to cosinus, w szczególności kąta rozwartego.

  2. Teoria liczb

    Trójkąt harmoniczny – bliźniak trójkąta Pascala

    Trójkąt Pascala zna praktycznie każdy. Widoczny poniżej z lewej strony trójkąt ma tę własność, że każda liczba jest sumą dwóch liczb stojących bezpośrednio nad nią (z wyłączeniem wierzchołka trójkąta oraz jego prawego i lewego boku, gdzie znajdują się jedynki). Z kolei w trójkącie po prawej stronie każda liczba jest sumą dwóch liczb stojących bezpośrednio pod nią. Na jego prawym oraz lewym boku znajdują się odwrotności kolejnych liczb naturalnych - liczby harmoniczne. Taki obiekt nazywa się trójkątem harmonicznym. Konstrukcję obu trójkątów można oczywiście kontynuować w nieskończoność...

Topologia

  1. Topologia

    Zabawa zapałkami

    Jeśli czytasz ten tekst, to świetnie się składa, możesz poznać drobny fragment topologii i zmierzyć się z następującym pytaniem: Ile topologicznie różnych figur można ułożyć na płaszczyźnie z sześciu zapałek, które stykają się tylko końcami?

Biologia

zadania


tematy

stałe rubryki

autorzy