Non-deterministic programs
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Non-deterministic programs

  1. #1
    Join Date
    May 2017
    Posts
    6

    Non-deterministic programs

    Hello everyone

    Is there anyone who can help me understand the notion of non-determinist program; What I know is that a non-deterministic program is a program for the same inputs it gives me diffrent resulats. Can you give me a simple program that helps me understand the concept of non derminism

    thank you in advance

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,452

    Re: Non-deterministic programs

    [Moved to General Programming as not c++ related]

    For a first start, have a look at https://en.wikipedia.org/wiki/Nondet...ic_programming and the links. It refers to two non-deterministic programming
    languages.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  3. #3
    Join Date
    Feb 2017
    Posts
    99

    Re: Non-deterministic programs

    Quote Originally Posted by amal ayadi View Post
    What I know is that a non-deterministic program is a program for the same inputs it gives me diffrent resulats.
    That definition is somewhat problematic because given the same input a program will always produce the same result.

    With (current) computers you can only approximate non-determinism and that is by using random number generators. Still, a program or algorithm that makes use of a random number generator (in one way or another) could (with some good will) be called non-deterministic. There are several areas of computing where this is done routinely, for example Monte Carlo methods and Genetic Algorithms.

    The canonical example of a Monte Carlo method is to estimate PI: You inscribe a circle in a square. Then you generate many points at random inside the square. Some will end up inside the circle and some outside. Comparing these two point fractions will give you an estimate of PI, the more points the better.

    https://www.youtube.com/watch?v=VJTFfIqO4TU

    An example of a deterministic alternative would be to estimate PI by evaluating a series,

    http://mathworld.wolfram.com/PiFormulas.html
    Last edited by wolle; May 30th, 2017 at 09:28 AM.

  4. #4
    Join Date
    May 2017
    Posts
    6

    Re: Non-deterministic programs

    Thank you for your reply. But I need a small non-deterministic algorithm that does not exceed the 5 instructions and without having used the random. I made this program using the random draw, which we have, a text t and a randomly drawn alphabet p and we check whether this alphabet exists in t or not:
    If it is in t and p ∈ to vowels alphabet (P ∈ listV) then:
    The variable z should contain one word of text t that contain the alphabet p drawn randomly.
    We put in n an index indicates where is p; otherwise z=0 and n=0

    As you can see for the same inputs (the text t and the randomly drawn alphabet p) we get different result of z and n which create the non-determinism. Now I need an idea of a small non-deterministic algorithm (that does not exceed the 4-5 instructions) without using the random draw


    This is my program

    Code:
    #include <stdlib.h>
    #include <time.h>
    #include <string>
    #include <iostream>
    #include <vector>
    #include <stdio.h>
    #include <ctype.h>
    
    using namespace std;
    
    
    //
    int generate_bounds(int, int);
    void initialize_rand(unsigned int);
    
    int call_srand = 0;
    
    int generate_bounds(int min, int max)
    {
        if(call_srand!= 1)
            initialize_rand((unsigned)time(NULL));
        return rand()%(max-min+1) + min;
    }
    
    void initialize_rand(unsigned int n)
    {
        srand(n);
        call_srand = 1;
    }
    //
    int random(int a, int b){
        //  Initialization of rand
    	srand((unsigned int)time(NULL));
        return rand()%(b-a) +a;
    }
    
    
    vector<string> Conversion (string s)
    {      vector<string> v ;
            string x ="";
            int index = 0 ;
        //Check the word
         for ( std::string::iterator it=s.begin(); it!=s.end(); it++)
         {
    
             if ( *it != ' ' ) {
                    if ( isalnum(*(it)) ){
                    x+=*it ;
                    }
             }
             else {
                     v.push_back(x);
                     x ="";
             }
             index ++ ;
         }
         return v ;
    }
    
    
        bool isExist(char x , vector<char> v)
        {
            for ( vector<char>::iterator it=v.begin(); it!=v.end(); ++it)
             {
                if (*(it) == x ) return true ;
             }
    
        }
        bool isVowel(char x)
        {
            char listV [6] = { 'a' , 'e' , 'i' , 'o' , 'u' ,'y' } ;
            for ( int i=0; i!=6; ++i)
             {
                if (listV[i] == x ) return true ;
             }
            return false ;
        }
    
        char listV [6] = { 'a' , 'e' , 'i' , 'o' , 'u' ,'y' } ;
    
    
    
    int main()
    {
    
    while (1)
    {
    
    //  we can change the text
        
    
       string Text = "Relative Correctness is the property of a program to be more correct than another with respect to a given specification whereas absolute correctness with respect to a specification r divides candidate programs into two classes, correct and incorrect, relative correctness defines a partial ordering between candidate programs, whose maximal elements are the absolutely correct programs. Correctness Enhancement is the process of mapping a program P1 into a program P2 that is more correct than P with respect to a specification r ";
        
    
        std::string alphabet ("abcdefghigklmnopqrstuvwxyz");
        char caracter ;
        std::string z ;
    	std::vector<int> n ,n_char ;
        int index = 0 , a = 0 ;
    
        //Preparation of our table from the given text
        Text+=" ";
        vector<string> v = Conversion(Text) ;
        string tab [v.size()];
        for ( unsigned int i=0; i!=v.size(); ++i)
             {
                tab[i] = v[i] ;
             }
        //End of table preparation
        //Choice of character with random number
        index = random(0,26);
        caracter = *(alphabet.begin()+index);
         //end choice
        //Verification of the character in each word
        //See the character family
        //Vérification du mot
        if ( isVowel(caracter) ){
    
                for ( int i = 0 ; i<v.size() ; i++)
                {
                     for ( string::iterator it=tab[i].begin(); it!=tab[i].end(); ++it)
                     {
                         if ( *it == caracter ) {
                            n.push_back(i);
                            break ;
                         }
                     }
                }
    
                index = 0 ;
    
                for ( int i=0 ; i<Text.size(); i++)
                {
                    if ( Text[i] == caracter ) {
    
                        if (0< index < Text.size()) {
                            n_char.push_back(index);
                        }
                    }
                    index ++ ;
                }
                if (n.size() == 0) {
                    z="The random alphabet character does not exist in the text";
                }
    
        }
        else
        {
                    z = "The randomly drawn alphabet character does not belong to the vowel letters" ;
        }
    
        //End alphabet character specification
         //end verification
    
    
        //Research result
                std::cout << "___________________________________________________________________________" <<  '\n';
                std::cout << "                             Program 1  " <<  '\n' ;
                
                std::cout << "___________________________________________________________________________" <<  '\n' <<  '\n';
                std::cout << "The randomly drawn alphabet caracter is = '" << caracter << "'"<< '\n';
                std::cout << "The text is = '" << Text << "'"<<'\n' <<  '\n';
                std::cout << "________________________________" <<  '\n';
                std::cout << "THE EXECUTION RESULT: " << '\n';
                std::cout << "________________________________" <<  '\n';
                std::cout << "* z = " ;
                index = 0 ;
                if ( n.size()>0) {
                        index = random(0,n.size()) ;
                        cout <<  tab[ n[index] ] << " " ;
                        std::cout << '\n';
                        index = generate_bounds(0,n_char.size()-1) ;
                        std::cout << "* n = " <<  n_char[index]+1 <<  '\n';
                }
                else {  cout << z ;
                std::cout << '\n';
                std::cout << "* n = " << 0 << '\n';
                }
                std::cout << '\n'<< '\n'<< '\n'<< '\n'<< '\n'<< '\n'<< '\n';
        system("pause");
        }
        return 0;
    }
    Last edited by 2kaud; May 31st, 2017 at 05:39 AM. Reason: Added code tags

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,452

    Re: Non-deterministic programs

    [Moved back to c++ as now apparent c++ related. Doh!]
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,452

    Re: Non-deterministic programs

    When posting code, please use code tags. Go Advanced, select the formatted code and click '#'.

    What c++ compiler are you using? as
    Code:
    string tab[v.size()];
    for (unsigned int i = 0; i != v.size(); ++i)
    {
        tab[i] = v[i];
    }
    is not valid standard c++ as the size of array is not known at compile time. For standard c++ try
    Code:
    vector<string> tab(v);
    which also copies v to tab without the for loop.

    Also
    Code:
    if (0< index < Text.size()) {
    probably doesn't work the way expected. Consider
    Code:
    if (0< index && index < Text.size()) {
    Last edited by 2kaud; May 31st, 2017 at 06:03 AM.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  7. #7
    Join Date
    Feb 2017
    Posts
    99

    Re: Non-deterministic programs

    Quote Originally Posted by amal ayadi View Post
    As you can see for the same inputs (the text t and the randomly drawn alphabet p) we get different result of z and n which create the non-determinism. Now I need an idea of a small non-deterministic algorithm (that does not exceed the 4-5 instructions) without using the random draw
    I remember now that you presented that algorithm here first in French,

    http://forums.codeguru.com/showthrea...-code-source-C

    You seem to have implemented it to your satisfaction. You now post your solution here, not because you have questions about it, but simply as an example of a non-deterministic algorithm. What you want is another example of a non-deterministic algorithm that doesn't use a random number generator. Is that correct? Is that what you want?

    Well, as I said in my previous post, to get non-determinism you normally use a random number generator. This is because it has known statistical properties. But if you don't care about that you could use an un-initialized ordinary variable. This code snippet checks whether an unitialized integer happens to be odd or even,
    Code:
    void non_deterministic() { // checks whether an unitialized integer is odd or even
    	int i; // not initialized, could be anything
    
    	if ((i & 1) == 0) std::cout << "this time I am even" << std::endl;
    	else  std::cout << "this time I am odd" << std::endl;
    }
    As an alternative you could read the system clock for example. That would also be non-deterministic. This actually is how random number generators are often "seeded".

    But note that this still is not in accordance with your definition of a non-deterministic program. It is because both the un-initialized variable and the system clock are inputs to the program and with the same value they will produce the same result. That is the program is deterministic. But of course if you make a distinction between different kinds of input then you could possibly argue a program can be non-deterministic. If only what the user enters counts as input and reading an external event does not then okay, then a program probably could be called non-deterministic I guess.
    Last edited by wolle; May 31st, 2017 at 10:35 AM.

  8. #8
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,452

    Re: Non-deterministic programs

    Having looked at the code in post #4, as part of understanding it I've 'simplified' it somewhat to be more 'modern' c++11. Consider
    Code:
    #include <ctime>
    #include <string>
    #include <iostream>
    #include <vector>
    #include <cctype>
    #include <sstream>
    #include <algorithm>
    
    using namespace std;
    
    int random(int a, int b) {
    	return rand() % (b - a) + a;
    }
    
    void Conversion(string s, vector<string>& v)
    {
    	s.erase(remove_if(s.begin(), s.end(), [](char c) {return !(isalnum(c) || isspace(c)); }), s.end());
    
    	stringstream ss(s);
    	string x;
    
    	for (v.clear(); ss >> x; v.push_back(x));
    }
    
    bool isVowel(char x)
    {
    	return "aeiouy"s.find(x) != string::npos;
    }
    
    int main()
    {
    	srand((unsigned int)time(NULL));
    
    	const string Text = "Relative Correctness is the property of a program to be more correct than another with respect to a given specification whereas absolute correctness with respect to a specification r divides candidate programs into two classes, correct and incorrect, relative correctness defines a partial ordering between candidate programs, whose maximal elements are the absolutely correct programs. Correctness Enhancement is the process of mapping a program P1 into a program P2 that is more correct than P with respect to a specification r ";
    
    	while (true) {
    		const char caracter = (char)(random(0, 26) + 'a');
    
    		cout << "___________________________________________________________________________" << '\n';
    		cout << "                             Program 1  " << '\n';
    
    		cout << "___________________________________________________________________________" << '\n' << '\n';
    		cout << "The randomly drawn alphabet caracter is = '" << caracter << "'" << '\n';
    		cout << "The text is = '" << Text << "'" << '\n' << '\n';
    		cout << "________________________________" << '\n';
    		cout << "THE EXECUTION RESULT: " << '\n';
    		cout << "________________________________" << '\n';
    
    		vector<string> v;
    		Conversion(Text, v);
    
    		if (isVowel(caracter)) {
    			vector<int> n;
    
    			for (size_t i = 0; i < v.size(); ++i)
    				if (v[i].find(caracter) != string::npos)
    					n.push_back(i);
    
    			if (n.size() == 0)
    				cout << "The random vowel character does not exist in the text";
    			else {
    				vector<int> n_char;
    
    				for (size_t pos = 0, old = 0; (old = Text.find(caracter, pos)) != string::npos; pos = old + 1)
    					n_char.push_back(old);
    
    				cout << "* z = " << v[n[random(0, n.size())]] << "\n" << "* n = " << n_char[random(0, n_char.size())] + 1 << '\n';
    			}
    		} else
    			cout << "The randomly drawn alphabet character does not belong to the vowel letters";
    
    		cout << string(6, '\n');
    		system("pause");
    	}
    
    	return 0;
    }
    As I understand it,
    string Text contains the text to examine
    vector v contains the words from the string Text with non alpha-numeric chars removed
    char caracter contains a random lower-case letter
    vector n contains the indexes of v for those words that contain caracter when caracter is a vowel
    vector n_char contains the positions in Text for caracter when caracter is a vowel

    If caracter is a vowel and it appears in Text then the output is
    - z - a random word that contains that vowel
    - n - a random position in Text (starting from 1) that contains the vowel


    random is used three times in the code
    - to obtain a letter
    - display an element from v
    - to display an index for Text

    Are you now looking for the same text analysis without using random but will produce potentially different output each time run?
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,452

    Re: Non-deterministic programs

    This code snippet checks whether an unitialized integer happens to be odd or even,
    Code:
    void non_deterministic() { // checks whether an unitialized integer is odd or even
    	int i; // not initialized, could be anything
    
    	if ((i & 1) == 0) std::cout << "this time I am even" << std::endl;
    	else  std::cout << "this time I am odd" << std::endl;
    }
    With VS2017, this gives an error C4700 that uninitialized local variable 'i' used.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  10. #10
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,452

    Re: Non-deterministic programs

    As an alternative you could read the system clock for example. That would also be non-deterministic. This actually is how random number generators are often "seeded".
    Another ways are
    - the time in milliseconds since the computer was powered on
    - the time in milliseconds taken for a user to reply to a question (ie Do you want to continue [Y/N]: ) This can be a good one in the right circumstances

    Ideally, you want to 'result' to be different each time you use it in a program. So reading from a memory location may give a 'random' number each time a program is run, but is unlikely to give different values if used more than once in a program.

    You can obtain a hardware random number generator that can be plugged into a computer that will produce a true random number each time it is accessed as these are based on a physical process such as thermal noise etc. See https://en.wikipedia.org/wiki/Hardwa...mber_generator
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  11. #11
    Join Date
    Feb 2017
    Posts
    99

    Re: Non-deterministic programs

    Quote Originally Posted by 2kaud View Post
    With VS2017, this gives an error C4700 that uninitialized local variable 'i' used.
    It's a warning actually. C++ allows you to not initialize variables.

    In previous versions of VS it was easy to disregard warnings but it seems more complicated in VS 2017.

  12. #12
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,452

    Re: Non-deterministic programs

    Quote Originally Posted by wolle View Post
    It's a warning actually. C++ allows you to not initialize variables.

    In previous versions of VS it was easy to disregard warnings but it seems more complicated in VS 2017.
    Its an error with my version of VS2017 using Toolset v141 with release build and produces a failed compilation - and no, I haven't got 'Treat warnings as errors' set.

    Code:
    1>c:\develop\vc\test64\source.cpp(23): error C4700: uninitialized local variable 'i' used
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  13. #13
    Join Date
    May 2017
    Posts
    6

    Re: Non-deterministic programs

    I'm looking for an idea of another simple non-deterministic program (different from this one) without having used the random

  14. #14
    Join Date
    Feb 2017
    Posts
    99

    Re: Non-deterministic programs

    Quote Originally Posted by amal ayadi View Post
    I'm looking for an idea of another simple non-deterministic program (different from this one) without having used the random
    With "the random" do you mean a random number generator? You don't want to use that? I still don't understand why but you could do this for example,

    Code:
    int non_deterministic() {
    	int* p = new int;
    	int i = *p;
    	delete p;
    	return i;
    }
    
    void test() {
    	for (int i = 0; i < 25; ++i) {
    		std::cout << non_deterministic() << std::endl;
    	}
    }
    It allocates an uninitialized int on the heap and just returns it. So the random number will be an int that happens to be somewhere in memory. I've tested it and it must be run in release mode (not debug). If works if the int is deleted but better if it is not (but then you get a memory leak so you may prefer to delete).

    Non_deterministic() is based on the fact that in C++ an uninitialized variable is undefined. Unlike an ordinary random number generator the statistical properties are unknown.
    Last edited by wolle; May 31st, 2017 at 01:57 PM.

  15. #15
    Join Date
    Feb 2017
    Posts
    99

    Re: Non-deterministic programs

    Quote Originally Posted by 2kaud View Post
    Its an error with my version of VS2017 using Toolset v141 with release build and produces a failed compilation - and no, I haven't got 'Treat warnings as errors' set.
    I had the same problem. Strangely enough I could run the code in #14 without problems.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)