-
X-Received: by 10.140.83.165 with SMTP id j34mr375476qgd.8.1427536455790; Sat, 28 Mar
2015 02:54:15 -0700 (PDT)
X-Received: by 10.140.83.165 with SMTP id j34mr375476qgd.8.1427536455790; Sat, 28 Mar
2015 02:54:15 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news.glorb.com!
h15no211253igd.0!news-out.google.com!q90ni547qgd.1!nntp.google.com!q107no77584q
gd.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Sat, 28 Mar 2015 02:54:15 -0700 (PDT)
In-Reply-To: <f...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=178.36.122.220;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 178.36.122.220
References: <4...@g...com>
<d...@g...com>
<meti4e$osd$1@srv.chmurka.net>
<f...@g...com>
<mevfpd$gpa$1@srv.chmurka.net>
<e...@g...com>
<mf1tnf$d48$1@srv.chmurka.net>
<d...@g...com>
<e...@g...com>
<f...@g...com>
<b...@g...com>
<4...@g...com>
<f...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <8...@g...com>
Subject: Re: poprawność algorytmu
From: "M.M." <m...@g...com>
Injection-Date: Sat, 28 Mar 2015 09:54:15 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:207689
[ ukryj nagłówki ]On Saturday, March 28, 2015 at 9:45:23 AM UTC+1, g...@g...com wrote:
> W dniu sobota, 28 marca 2015 05:04:04 UTC+1 użytkownik M.M. napisał:
>
> > > W takim razie zgoda -- tego rodzaju "poprawność" jest niemożliwa do uzyskania.
> > > Należy jednak mieć na uwadze, że z formalnego punktu widzenia poprzez
> > > "poprawność" dowodu rozumie się to, czy każdy krok jest zgodny z regułami,
> > > natomiast w tym przypadku raczej należałoby użyć słowa "adekwatność"
> > > (na przykład teza Churcha-Turinga postuluje adekwatność maszyny Turinga
> > > jako modelu ujmującego intuicyjne rozumienie obliczalności)
> >
> > Mój (hipotetyczny) klient zamawia najlepszy program do gry w
> > szachy o łącznym rozmiarze kodu i danych nie większym niż 1MB. Napisałem
> > taki program. Jak mam przeprowadzić dowód, że nie istnieje w
> > ramach tego rozmiaru lepszy program?
>
> To akurat nie jest problem metody dowodowej,
Właśnie, tego nie da się udowodnić, a jest to też ważny aspekt
programu. A w testach tak się robi, porównuje się kilka
różnych algorytmów dla różnych danych.
> tylko nieprecyzyjnej
> specyfikacji. Co to znaczy,że "w ramach określonego rozmiaru program
> jest lepszy od innego programu"?
Zakładamy że specyfikacja jest dobra. To jest kwestia jakości
użytych algorytmów/heurystyk.
> Zresztą cechy użytkowe nie są czymś, co dowodzi się formalnie
> (bo są subiektywne). Formalnie chcemy dowodzić raczej pewnych
> inwariantów -- że na przykład w programie wielowątkowym nie dojdzie
> do sytuacji dead-locku (klasyczne zastosowane logik temporalnych),
Nie słyszałem o logice temporalnej. Może się mylę, ale to się
wydaje łatwe. Dla mnie taki dowód sprowadza się do tego, aby
wszystkie pary kodu, który może wykonać się równolegle, były
opatrzone semaforami w tej samej kolejności w sensie wykonania i
w odwrotnej kolejności (też w sensie wykonania).
> że dla określonej klasy danych wejściowych program się zatrzyma,
> że zużycie zasobów w czasie działania programu będzie ograniczona
> określoną funkcją od czasu działania i rozmiaru danych wejściowych
> itd.
To czasami może być trudne, np. problem Collatza. Pytanie czy
czas wykonania i inne zasoby są znanymi/łatwymi funkcjami danych
wejściowych. Jeśli zapotrzebowanie na zasoby w danym programie
nawet da się rozbić na wiele małych-łatwych funkcji, to może
potem wyjść: f1(N) * f2(N) * f3(N) * f4(N) * f5(N). Można
wziąć maksimum każdej z tych pięciu funkcji i podać, jako oszacowanie
górne, iloczyn maksimów. Ale w praktyce oszacowanie górne
może nie mieć nic wspólnego z rzeczywistością, gdy f1
przyjmuje maksimum, to pozostałe funkcje mogą przyjmować
małe wartości. Zależności fi od fj (i!=j) może być bardzo
skomplikowana...
Pozdrawiam
Następne wpisy z tego wątku
- 28.03.15 11:46 M.M.
- 28.03.15 11:54 Andrzej Jarzabek
- 28.03.15 13:08 Andrzej Jarzabek
- 28.03.15 18:22 Maciej Sobczak
- 28.03.15 19:38 Roman W
- 28.03.15 19:43 Roman W
- 28.03.15 19:50 A.L.
- 28.03.15 19:51 A.L.
- 28.03.15 21:16 Andrzej Jarzabek
- 29.03.15 00:13 Maciej Sobczak
- 29.03.15 15:21 Andrzej Jarzabek
- 29.03.15 23:18 Maciej Sobczak
- 30.03.15 00:49 Andrzej Jarzabek
- 30.03.15 00:59 Andrzej Jarzabek
- 30.03.15 01:19 Roman W
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-07-02 Realme 7 Na co zmienić?
- 2024-06-27 Prywatny parking? Pierwsze 10 minut bezplatnie
- 2024-07-02 znalazłem samochód ;)
- 2024-07-02 Pierwszeństwo łamane
- 2024-07-02 zamek
- 2024-07-02 Akumulatory VRLA
- 2024-07-03 Białystok => Inżynier DevOps Conexa First (Kontraktor) <=
- 2024-07-03 MĂźnchen => Test Development Engineer (m/w/d) <=
- 2024-07-03 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-07-03 Warszawa => Programista Full Stack (.Net Core) <=
- 2024-07-02 Kraków => Spedytor międzynarodowy <=
- 2024-07-02 Poznań => Senior React Native Developer <=
- 2024-07-02 Rzeszów => Frontend Developer (React) <=
- 2024-07-02 Warszawa => Fullastack (Java) Developer <=
- 2024-07-02 reparacje