Calling Prolog from Foreign Languages

When you define Prolog clauses for global predicates  as being of foreign language, those predicates may be called from foreign languages. They will have parameter access and entry and exit code, including register preservation, as for the language specified.

Example:predicate called from .pro in C language

/* Program hello_p.pro */

global predicates

char prohello_msg(string) - (i) language c

hello_c - language c

clauses

prohello_msg(S,C) :-

write(S," (press any key)"), readchar(C).

goal

prohello_msg("Hello from  Prolog"),

hello_c.

The global predicate prohello_msg is now accessible from C and can be called just like any other C function:

Multiset data structure implementation in java

Multiset  is a generalized version set structure.Similar to set, multiset only stores data values without  guarantee of any particular ordering of its contents. On the other hand, it allows storing of multiple items with the same value (ie. supports non-unique keys).

It can be implemented using list but for optimal result i.e O(1) hash table structure should be used. Otherwise it  takes steps, where is number of distinct elements stored.

Source Code (JAVA)
01. /**

02.* Multiset implemented using two lists (list of values, list of occurrences)

03.* @author Pavel Micka

04.* @param <ENTITY> type parameter of the contained value

05.*/

06.public class Multiset<VALUE> {

07. 

08.private List<VALUE> values;

09.private List<Integer> occurences;

10. 

set data structure implementation in java

Set refers an abstract data structure used for storing data elements. Analogy with the mathematical term set, it does not guarantee any particular order of the stored elements and contains every value at most once (i.e. contains only unique values).

Similarly we can define multiset (bag) – a set, which may contain each value more than once. we can implement disjoint,union and difference of these set like in set theory of mathematics.

Source Code(JAVA)

/**
 * Set implemented as a list (using ArrayList)
 * @author Pavel Micka
 * @param <ENTITY> Type parameter of the contained value
 */
public class Set<ENTITY> {
    private List<ENTITY> list;
    /**
     * Constructor
     * @param initialCapacity initial capacity of the underlying ArrayList
     */
    public Set(int initialCapacity){
        list = new ArrayList<ENTITY>(initialCapacity);
    }

Prune and Search Alogrithm and implemetation in java

Prune and search is a method for finding an optimal value by iteratively dividing a search space into two parts – the promising one, which contains the optimal value and is recursively searched and the second part without optimal value, which is pruned (thrown away). This paradigm is very similar to well know divide and conquer algorithms.




* Prune and search

* @param array array to be searched in

* @param index order of the searched value (indexed starting at 0)

.* @param left first elemenent, which can be touched

* @param right first element, which cant be touched

* @return n-th largest value

*/

public static int pruneAndSearch(int[] array, int index, int left, int right) {

int boundary = left;

for (int i = left + 1; i < right; i++) {

if (array[i] > array[left]) {

 //place after the pivot every value, which is larger than the pivot

swap(array, i, ++boundary);

}

}

Interpolation Search implementation in java

The interpolation search is an improvement of the binary search for instances, where the values in the array are ordered and uniformly distributed.

The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element. Interpolation search calculates a position , where the value should be placed in accordance to the distribution of values a splits the array at . If the array contains numbers and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found). The interpolation search calculates the probable position (index 9) and immediately finds the value. The expected complexity of the interpolation search in .




/* Interpolation search

* @param array array with uniformly distributed values in ascending order

* @param value searched value

* @param from first index that might be touched

* @param to last index that might be touched

* @return index index of the searched value in the array, -1 if not found

*/

public static int interpolationSearch(int[] array, int value, int from, int to){

if(array[from] == value) return from;

else if(from == to || array[from] ==  array[to]) return -1; //not found

//probable position of the searched value

int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);

if(array[index] == value) return index;//found

//continue in the right part of the array

else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);

//continue in the left part of the array

else return interpolationSearch(array, value, from, index - 1);

}

Depth First Search Algorithm and implementation in c++

DFS is the basic tree search technique in which goal,data is searched by moving downward until a leaf,end node, is reached.Then it backtrack and repeat the moving down to leaf process.This process is repeated until the searching data is found.

Algorithm

An algorithm for the depth – first search is the same as that for breadth first search except in the ordering of the nodes.

1. Place the starting node s on the top of the stack.
2. If the stack is empty, return failure and stop.
3. If the element on the stack is goal node g, return success and stop. Otherwise,
4. Remove and expand the first element , and place the children at the top of the stack.
5. Return to step 2.
    
   #include <iostream>

   #include <ctime>

   #include <malloc.h>

   using namespace std;

   struct node{

       int info;

       struct node *next;

   };

    

Breadth-First Search Algorithm and implementation in c++

BFS is most useful searching technique in database.In this technique,form the tree of data, corresponding child nodes of current state node is selected first during the searching process.Then in next step the childrens' of these selected child nodes will be searched.In this way exploring all nodes at a given depth before proceeding to the next level this searching method is implemented.

Algorithm

BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search. The BFS algorithm proceeds as follows.

1. Place the starting node s on the queue.
2. If the queue is empty, return failure and stop.
3. If the first element on the queue is a goal node g, return success and stop Otherwise,
4. Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
5. Return to step 2.
   Source Code 
   #include <iostream>

   #include <ctime>

   using namespace std;

   struct node {

       int info;

       node *next;

   };

   
   

Monkey- Banana Problem in Prolog

Monkey-Banana Problem is the famous problem in AI. Where there is a room containing a monkey, a chair, and bananas that have been hung from the center of the ceiling of the room; out of reach from monkey. If the monkey is cleaver enough, he can reach the bananas by placing the chair directly below the bananas and climbing on the top of the chair.

Now the problem is to use FOPL to represent this monkey-banana problem and prove that monkey can reach the bananas.

The program is given below. Before running the program, think carefully what are the essential objects of the problem and how should them be arranged in predicate logic. 

PREDICATES

in_room(symbol)

dexterous(symbol)

tall(symbol)

can_move(symbol,symbol,symbol)

can_reach(symbol,symbol)

get_on(symbol,symbol)

can_climb(symbol,symbol)

close(symbol,symbol)

under(symbol,symbol)

can_climb(symbol,symbol)

 

Class Diagram for Software Design

INTRODUCTION

 CLASS DIAGRAM

•       A class diagram shows the existence of classes and their relationships in the logical view of a system

•       UML modeling elements in class diagrams are:

–      Classes, their structure and behavior.

–      relationships components among the classes like association, aggregation, composition, dependency and inheritance

–      Multiplicity and navigation indicators

–      Role names or labels.

Basic two types  of classes

Concrete classes

•       A concrete class is a class that is instantiable;  that is it can have different instances.

•       Only concrete classes may be leaf classes in the inheritance tree.

Abstract classes

•        is a class that has no direct instance but whose descendants classes have direct instances.

•       can define the protocol for an operation without supplying a corresponding method we call this as an abstract operation.

operation defines the form of operation, for which each concrete subclass should provide its own implementation

Types of Relationships between classes

•       Association

•       Aggregation

•       Composition

•       Inheritance

•       Dependency

•       Instantiation

FOPL and Prolog In AI part 04

Introduction

First Order Predicate Logic (FOPL) is a generalisation of Propositional Logic. Logic Programs are written in a sub-language of FOPL and therefore derive their meaning and formal properties from it.

FOPL has two major extensions over Propositional Logic:

1. Propositions are renamed "predicates" and may possess an internal structure. In fact the predicates of FOPL have precisely the same syntactic structure as they have in Prolog - i.e. a predicate name with terms as arguments, each term being aa

-constant,

-variable, or

-funcion with term(s) as argument(s).

2. Variables must be quantified by either

A meaning "for all" or

E " "there exists"

e.g Ex P(x) means "some unspecified constant has property P". Each quantifier has a SCOPE which is defined as the textual area in which it binds occurrences of its variable. This scope is usually delimited by brackets, unless it is obvious as in the example above.

Constraint satisfaction problems In AI part 03

Introduction

            Constraint programming is a useful tool in formulating and solving problems that can be defined in terms of constraint among a set of variables. In fact real world problems are constraint satisfaction problems defined in terms of some variables that bear some constraints. Finding a set of variables, that are within the constraints given(or observed) is a solution to that problem.

            Let us consider a problem, that can be represented by some relations of the variables x, y and z. We have a domain Dx, Dy, Dz from where the variables can take a value. The constraint is given by a set C and may have a number of constraints C₁,C₂,C₃,etc each relating some or all of the variables x,y and z. Now a solution (or solutions) to the problem is a set dx,dy,dz such that dx   Dx,  dy   Dy and dz   Dz and all the constraints of the set C are satisfied.

Eight queens problem

            Eight queens problem is a constraint satisfaction problem. The task is to place eight queens in the 64 available squares in such a way that no queen attacks eachother. So the problem can be formulated with variables x₁,x₂,x₃,x₄,x₅,x₆,x₇,x₈ and y₁,y₂,y₃,y₄,y₅,y_6, y₇,y₈; the xs represent the rows and ys the column. Now a solution for this problem is to assign values for x and for y such that the constraint is satisfied.

The problem can be formulated as

P={(x₁,y₁),(x₂,y₂),……………………..(x₈,y₈)}

where (x₁,y₁) gives the position of the first queen and so on.

            So it can be clearly seen that the domains for x_i and y_i are

Dx = {1,2,3,4,5,6,7,8}and Dy ={1,2,3,4,5,6,7,8} respectively.

BackTracking in Artificial Intelligence part 02

Backtracking

As has already been seen prolog has built in backtracking mechanism. It tries to prove a goal with all possible instantiations. Automatic backtracking is a useful programming concept because it reveals the programmer of the burden of backtracking explicitly. However in some cases this feature degrades the efficiency of the program.

For example in cases where one solution is sufficient, backtracking to find all the solutions is not a good idea. Similarly, in case of mutually exclusive rules(clauses) when one rule has been proved then it is known in advance that no other rules can succeed. So this backtracking can be controlled by the use of ‘cut’, (“!”).

The disadvantage of using cut is that we tend to move away from the declarative nature of the prolog because when we have used the cut the order of the clauses may make difference in the result we get.

              

Consider the function shown in the above figure. The relation between X and Y can be specified by the following three rules.

Rule 1: if X<3 then Y=0

Rule 2: if 3=<X <6 then Y=2

Rule 3: if 6<X then Y=4

This can be programmed as

PREDICATES

f(integer,integer)

CLAUSES

f(X,0):-

                X<3.

f(X,2):-

                3<=X,X<6.

               

f(X,4):-

                6<X.

               

GOAL

f(2,X).

 Assignment1.)

Now modify the program using cut and observe the difference between the two modules. Comment on the difference.

Solution:

Introduction to Prolog for AI programming part 01

PROLOG is what is known as a declarative language. This means that given the necessary facts and rules, Prolog will use deductive reasoning to solve problems. This is in the contrast to traditional computer languages, such as C, BASIC and Pascal, which are procedural languages. We can also use prolog as any other programming languages in a procedural manner.

So prolog can be viewed as a tool to solve problems in the field of artificial intelligence or it can be very well used a general programming language.  

Prolog enforces the different problem solving paradigm complementary to traditional programming languages so it is believed that a student of computer should learn programming in prolog.

With Visual Prolog, applications such as customized knowledge bases, expert systems, natural language interfaces, and smart information management systems are easy to develop. 

Data types in prolog

There are mainly three data types in prolog which are:

a)      Atoms and numbers

b)      Variables

c)      Structures

a) Atoms and numbers

Atoms can be constructed in three different ways

• Strings of letters, digits, and the underscore character starting with a lower case letter.    
•  For example: man, ram, comp_students, pc_ct_063
• Strings of special characters.                                                                                           

    For example: < ----- >                                                                                                    

•   Care should be taken not to use the character combination that may some built in meaning.
• Strings of characters enclosed in quotes.                                                                            

Cracking Zip Password Files

FZC uses multiple methods of cracking - bruteforce (guessing passwords systematically until the program gets it) or wordlist attacks (otherwise known as dictionary attacks. Instead of just guessing passwords systematically, the program takes passwords out of a "wordlist", which is a text file that contains possible passwords. You can get lots of wordlists at www.theargon.com.).

You can get it anywhere - just use a search engine such as altavista.com.

------------------------------------------------------------------------------
Bruteforce
--------------------------------------------------------------------------------


The command line you'll need to use for using brute force is:

fzc -mb -nzFile.zip -lChr Lenght -cType of chars

Now if you read the bforce.txt that comes with fzc you'll find the description of how works Chr Lenght and the Type of chars, but hey, I'm gonna explain this too. Why not, right?... (but remember look at the bforce.txt too)

Very Important Sorting Algorithms

Selection  Sort

Insertion Sort

Shell Sort

Merge Sort

Radix sort

Selection  Sort

      i)Declare and initialize necessary variables such as array [ ] , i, j , large, n .
      ii)For ( i=n-1 ; i > 0 ; i -- )  repeat following steps
               large=x[ 0 ]
               index=0
              ii.a  For ( j=1;j<=i ; j++)
                 IF (x[ j ]>large)
                         large=x[ j ]
                         index=j
             ii.b x[index] =x[ i ]
                          x[ i ]=large
      iii)Display the sorted array'

Insertion Sort

    i) i)Declare and initialize necessary variables such as array [ ] , i, j , large, n 
    ii)Insert each x[ ] into sorted file i.e.
           for  k=1 to k<n ,repeat
                temp=x[ k ]
                ii.a Move down one position all elements greater than temp i.e.
                      for ( i=k-1 ; j>=0  && temp<x [ i ] ; i ++)
                             x[i+1]=x[ i ]
                 ii.b   x[i+1]=temp
     iii)Display the sorted array
note:: in above algorithm we take x[0] as sorted file initially.

What is Hufffman Algorithm?

 Huffman Algorithm is an encoding technique for symbols where most frequently occurring symbols are represented with short length bit strings and least frequently occurring symbols are represented with long bit strings.


Algorithm
 Huffman(c: symbols a[i] with frequencies w[i]=1,2,3.......n)

F: forest of n rooted trees,each consisting of the single vertex a[i] and assigned weight w[i] in ascending order of w[i] while F is not a tree.

i)Start
  Replace the rooted trees T and T ' of least weight from F with w(T ) >= w(T ') with a tree hvaing a new root that has T as its left sub tree and T ' as its right sub tree label new edge to T with 0 and new edge to T ' with 1
Assign w(T) + w(T ') as weight of new tree.

Binary Tree and its Implementation in Database

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subset of tree.The first subset contains a single element called the root and other two are left and right sub trees which

can be also empty.Each element of a binary tree is called nodes of the tree.

A rooted tree is called binary tree if every internal vertex has no more than two children.

Types of Binary tree:_

a)Strictly / fully binary tree

b)complete binary tree

c)almost complete binary tree

what TREE refers to in DataBase

Tree is a non-linear data structure which consists of non-empty set of vertices(or nodes) and a set of edges where each nodes are connected to each other with no multiple edges or loops(i.e. no simple circuits)


Terminologies on tree:

Implementation of Linked List

Linked list is the special list of data elements linked to one another.Logical ordering is represented by having each elements pointing to next element.Each element in called node which has two fields-info to store data and next to point next node.It can be easily implemented to grow or shrink depending upon operation mode.Entire lined list is accessed from an external  pointer that contains the address of first node but it is not included in the linked list.The next address of last node contains special value called NULL represented by electrical ground symbol.Linked  list with no node is called EMPTY linked list.

In c,we can create  a node using structure as
                 struct node{
                               int info;
                              node *next;
                              }list;

Following operation can be done to linked list
1)Inserting Nodes to the front of  the Linked-List

2)Inserting  Nodes at end of the Linked-List

3)Inserting node after the given Node

4)Inserting node before the given node

5)Deleting the first Node

6)Deleting the last Node

7)Deleting the node after given node

8)Deletion the node before given node

Data Structure and Algorithm of QUEUE

A queue is an ordered collection of items from which items may be deleted at one end(called front and head of the queue) and into which items may be inserted at the other end (called the rear end on tail of the queue). It is First-In-First-Out(FIFO).There are two types of queue-Linear Queue and Circular Queue.

En-queue is the process of appending data to queue.

De-queue is the process of removing data from queue.

Algorithms for Linear Queue

What are STACK in DataBase and its alogrithms

A stack is an ordered collection of items into which new items may be inserted and from which items can be deleted at one end,called top of stack.It is First In Last Out(FILO) type of data structure.
Stack can be thought as pile of plates one on other.One which is put first stay at last or bottom of pile and one that is pile last is always on top.Also to take out a plate form it one which is  on top is remove first and other later.That's why it is called FILO. 

Push is the process of adding data on top of stack.
Pop  is the process of removing data from top of stack.

Stack Algorithms:

There are basically two methods implement stack:-

"Hello World " servlet in Net Beans

By default there is no web application in Net Beans 7.1 so you have to install plugin of web application.In order to do that, go to tool>plugin.A window will pop-up where all updates,available plugins,downloaded, installed  plugins option are available.In order to install these plugins you must be connected to internet.

In available plugins,click reload catalog which will update available plugins.From the list select 

--web application

--Glassfish

--Css preview

 and install, it make take few minutes .After installation you need to restart Net beans IDE.

Now you are done. Go File>new project ,now you have option for JAVA web in category then select web application in project.click next,then give name for project and location for project to save.Then in next, select server from drop down list which is Glassfish that we installed before,you can add other server like tomcat instead.Select java EE version as java EE 6  and click finish.

connecting and using MySQL database in netbeans

1.Download and install MySQL server
2.Run MySQL server
3.Run NetBeans
4.Connect MySQL with NetBeans
5.Edit database in Net Beans MySQL editor

1.Download and install MySQL server
   First step  is easy and simple ,just  download MySQL server from http://dev.mysql.com/downloads/mysql/  as per your system platform (e.g. 32-bit or 64-bit or mac or Ubuntu ) and install.After installation you have to configure MySQL server,leave all as default ,you just set password.

2.Run MySQL server

   Now for test  run installed  MySQL server console(command line client ).Enter password and you will see welcome secren.Type " SHOW  databases; " as command which give output of table of  inbuilt databases and table name is Databases.