•  
  • Theory Of Computation (19)

Optimization under risk constraints

Tags: No Tags
Comments: No Comments
Published on: March 9, 2010

Today, Professor Vazquez-Abad talked about a case study which was a project that she has contributed to for optimizing scheduling and operating of transportation at Melbourne Airport at Australia. The problem is to better analyze and operate the transportation system at Melbourne Airport. The risk constraints for this project are: financial investments, communication and network, chemical and environmental factors, economic modeling of strategic decisions and meet industry standards.

The setup is as following: buses are empty at departures, buses go to arrivals, and random numbers of passengers are waiting for the bus (numbers of passengers are not known), random loading time (the amount of time required to load the passengers are not known), buses go around the parking lots to pick up passengers, again there is random amount of passengers.  Passengers queue at the stations.

One of the objective functions is to reduce the waiting time of the passengers and provide feasible service to the passengers so that everyone will be able to take the buses and go to the desired destination within the terminal. Another objective function is not letting passengers wait more than 10 minutes.

The problem and solutions provided uses Dynamic Programming and Greedy approaches. In the optimization solutions, there are objective functions, feasibility and principle of optimality, minimum and maximum constraints, greedy criterions. Given the objective functions, there are probabilistic mathematical models, queue’ing model and greedy approaches provided as feasible solutions to the problems.

My interest in this topic would be processing large amount of data using distributed systems principles, paradigms and applications. Professor mentioned that the data they are working on is very large and hard to process. I would be interested in working on such large data sets and processing them and making them meaningful. Moreover, I would be interested in analyzing the dynamic programming approach and greedy approach to the problem.

Theory of Computation – Tutorial

Categories: Theory Of Computation
Comments: No Comments
Published on: December 17, 2009

I used to study for this tutorial when i was taking formal languages class.

Clear, helpfull and worth reading.

http://www.seas.upenn.edu/~cit596/notes/dave/syllabus.html

Theory of Computation – Definition of Computation

Comments: No Comments
Published on: December 14, 2009

Since early 1900s , Scientists have been trying to formally define Computation.

Alanzo Church – Lambda Calculus
Alan Turing – Turing Machine
Godel – Recursion Theorem
Davis and Weyuker – A theoretical programming language
Melvin Fitting – a basic abacus like structure

All these definitions are equivalent.

Definition of computation is clear, however definition of algorithm hasn’t been informally defined.

Church-Turing Thesis gives a almost universally acceptable definition for an algorithm however these days if you open the Glorious CLRS book or the Sipser’s book, you ll see that definition of information starts with “Informally algorithm is …”.

Chomsky Hierarcy

Categories: Theory Of Computation
Tags: No Tags
Comments: No Comments
Published on: November 28, 2009
Type Grammar Machine Application
3 Regular Grammar Finite Automaton, NFA, DFA Pattern Matching, Regular Expressions
2 Context Free Grammar Pushdown Automata, PDA (Uses Stack) Programming Languages
1 Context Sensitive Grammar Turing Machine with Bounded Tape Most Natural Languages
0 Recursively Enumerable Turing Machine with Infinite Tape

Theory of Computation, Recursively Enumerable Sets

Categories: Theory Of Computation
Comments: No Comments
Published on: November 24, 2009

Notes on Recursively Enumerable Sets

Theory of Computation, Complexity Theory

Categories: Theory Of Computation
Comments: No Comments
Published on: November 24, 2009

Here is some notes on Complexity Theory . There will be some other notes on Complexity Theory.

The Church-Turing Thesis: Story and Recent Progress

Categories: Theory Of Computation
Comments: No Comments
Published on: November 20, 2009

This is a very interesting talk. I liked it and recommend it.

Theory of Computation, Turing Machine

Categories: Theory Of Computation
Comments: No Comments
Published on: November 19, 2009

Alan Turing, is a fascinating, genius man, who defines computation with Turing Machines. In this note, I tried to define Turing Machine.

Turing Machine

Reference : Sipser’s book.

Theory of Computation, Definition of Information

Categories: Theory Of Computation
Comments: No Comments
Published on: November 19, 2009

Since the early 20th Century, Computer Scientists, Mathematicians have been trying to define Computation, Algorithm, and Information. For example; there are several formal definitions to “What is Computation?”. For example : Church’s Lambda Calculus, Godels Recursion Theory, Alan Turing’s Turing Machines and so on. All these abstract machines are identical. They can be reduced to each other and their purpose is to define, What is computation ?

In this post, We are trying to do define information.

Definition of Information

Reference: Sipser’s Book.

Studying Computer Science

Tags: No Tags
Comments: No Comments
Published on: November 17, 2009
studying_computer_science
studying_computer_science
page 1 of 2»

Welcome , today is Tuesday, February 7, 2012

Bad Behavior has blocked 251 access attempts in the last 7 days.