Dijkstras algoritm

en algoritm för att hitta den kortaste vägen mellan två givna noder i ett nätverk. – Det finns också en variant av Dijkstras algoritm som beräknar de kortaste avstånden från en enda given nod till var och en av de andra noderna i nätverket. – Dijkstras algoritm kan användas för allt som kan avbildas som nätverk, till exempel vägnät, vilket var vad den utvecklades för. Den har också fått användning i analys och konstruktion av stora datornätverk. Det förutsätts att avstånden mellan noderna är kända och tillgängliga för algoritmen. Vid behov kan algoritmen också ta hänsyn till kostnaden för de olika alternativa vägarna. – Uppkallad efter sin upphovsman, den nederländska datorvetaren Edsger Dijkstra (1930–2002), som utvecklade den med papper och penna 1956 och publicerade den 1959.  En tillämpning av Dijkstras algoritm är protokollet OSPF. – Mer i Wikipedia.

[matematik] [nätverk] [transport och logistik] [ändrad 30 april 2022]

dödläge

(deadlock) – när inget händer i en programkörning därför att två processer väntar på att den andra processen ska bli klar och släppa ifrån sig en resurs. Det kan också vara tre eller flera processer i en kedja. Ingen av processerna kan avslutas innan den andra avslutas. Båda väntar på den andra. – Den nederländska programmeringsexperten Edsger Dijkstra (se Wikipedia) har utveck­lat en algoritm för hur man und­viker att det upp­står dödläge: bankmannaalgoritmen (se Wikipedia). – Se också contention, gridlock och aktivt dödläge (livelock). – Språkligt: Benämningen baklås för deadlock förekommer ibland på svenska, bland annat i den svenska artikeln om dödläge i Wikipedia. Men baklås är en missvisande benämning, eftersom baklås är något annat än dödläge: baklås är när ett lås krånglar så att det inte går att låsa upp på normalt sätt. Det är inte en låsning som inbegriper två eller flera ömsesidigt beroende parter. ”Dödlås”, som man också ser ibland, är inte ens svenska.

[programmering] [ändrad 4 april 2018]

separation of concerns

uppdelning i problemområden – i systemutveckling: det att olika delproblem i ett program hålls i sär så att man kan hantera dem separat. En ändring i ett problemområde ska alltså kunna genomföras utan att det påverkar hela systemet. Exempel: man bör hålla i sär lönesystemet och listan över personalens adresser. Man bör också hålla i sär det grafiska användargränssnittet (presentationen) och den kod som gör beräkningar och sökningar. Detta gör att det blir lättare att hitta och rätta till fel och att göra förbättringar. Det minskar risken för att fel i en funktion stör andra funktioner. Det gör det också enklare att återanvända delar av programkoden. – Principen om uppdelning i problemområden formulerades först av Edsger Dijkstra (1930—2002, se Wikipedia), men den hade tillämpats i praktiken tidigare. – Se också sepa­ration of duties.

[systemutveckling] [ändrad 7 juli 2019]

ätande filosoferna

(the dining philosophers) – ett klassiskt datorvetenskapligt problem om tillgång till gemensamma resurser: Fem filosofer sitter runt ett matbord och ska äta ris. Men det finns bara fem ätpinnar, placerade mellan filosoferna. Varje filosof har alltså en ätpinne till vänster och en till höger, så varje pinne ligger mellan två filosofer. Och för att äta behöver man ju två pinnar, så alla kan inte äta samtidigt. Man får inte ta två pinnar på en gång, utan man måste först ta en, sedan (utan att man behöver släppa den första) den andra. Risken är att alla blir sittande med var sin ätpinne och väntar. – Utmaningen är att hitta ett regelsystem som gör att alla med minsta möjliga väntetid får disponera två pinnar så att de kan äta. Problemet formulerades av programmeringsexperten Edsger Dijkstra (se Wikipedia). – Mer om de ätande filosoferna i Wikipedia. – Läs också om aktivt dödläge och contention samt om det spelteoretiska problemet middagsätarens dilemma.

[datorvetenskap] [programmering] [ändrad 18 december 2019]