Transcript Document

Computer Systems Lab
TJHSST
Philosophy
• Creativity
• Opensource accessibility to knowledge,
information and resources
• Research and development
• Writing and documentation of your
research
2
Research Areas in CS
• Artificial Intelligence and Machine Learning:
Can I write a program that can learn on its own to
accomplish a particular task or solve a problem?
• 3D Computer Graphics:
Can I visualize a physical
situation realistically with a computer program?
• Computer Vision:
Can a computer program see,
distinguish, and analyze objects in an image?
• Modeling of Complex Systems, numerically
and graphically: Can I simulate a complex
environment and mathematical model. How closely can my
simulation match and predict reality?
3
Research Areas in CS
• Distributed and Parallel Programming
methods for high performance computing: For a
complex programming task, can I take advantage of
processing in parallel across multiple processors?
• Software Design, Object Oriented
Programming: What are optimal techniques for large
scale applications with large user bases and a need for long
term modifications and updates?
4
TJ Techabs Portfolio Skills
•
•
•
•
•
•
•
Writing – Technical Research Paper
Visual presentation – Digital poster
Oral presentation – PPT slides of the research
Research – Your project
Long term project development – iterative models
Record keeping - Logs
Peer evaluation
5
Computer Systems Research
Lab Requirements
•
•
•
•
•
•
Project proposal
Formal research paper
Oral presenations
Poster display
Project website/notebook folder
Logs
6
Electives – Computer Systems Lab
• Artificial Intelligence
• High Performance Computing and
Supercomputer Applications
• Computer Architecture
• Comparative Languages
7
Artificial Intelligence
• Search techniques for problem solving
– Uninformed: depth first, breadth first
– Heuristic: hill climbing, best first, A Star
• Game playing and adversarial search
– Minimax trees
– Alpha-beta pruning
• Machine Learning
– Evolutionary computation, genetic algorithms
8
Supercomputer and High
Performance Computing
• Parallel Computing
– Speedup of processing: Time/# of processors
– Sorts, searches, image processing across
matrices, fractal images
• MPI – Message Passing Interface
– Message sending topologies, ring/broadcast
– Time vs number of processors
• Computer Graphics in OpenGL
– 3D transformations, lighting for realism
9
Computer Architecture
• Organization of Computer Systems
• High level language implementations down
to the digital logic level
• SPIM simulator for assembly language
• History of the development of computing
machines
– Evaluate current platforms
– Analyze future forecasts
10
Comparative Languages
• Evolution of programming languages
• Syntax and semantics representation
• Machine parsing of grammars, building a
compiler
• Some issues: Exception handling,
Concurrency, Garbage collection
• Language approaches: imperative, object
oriented, functional, logic based
11
Research Models
(from Pasteur's Quadrant (1997) Donald Stokes)
• Pure basic research: Can I create a logarithmic,
randomly accessible data structure? Can I create a hybrid
machine learning system?
• Use-inspired basic research: Can I create a 3D
visualization package for graphics modeling for a Physics
course? Can I create a program that can learn on its own
how to translate text from one language to another for
people to obtain web-based translations?
• Pure applied research: Can I write a student Intranet
program for a high school? The program needs to be robust
and maintainable by future students for many years.
12
Research Models
(from Pasteur's Quadrant (1997) Donald Stokes)
13
Software Testing and Analysis of
Your Program
• Dynamic Testing: Random tests, Structural tests,
Functional tests, Path and branch testing.
• Process Modeling: - Finding a formula to verify and
validate your program's behavior.
• Requirements and Specifications: - Defining
requirements and the specifications for verifying these
requirements.
14
Lifecycle Models for the
Development Process
(from Rapid Development by McConnell)
• Spiral Model - breaks a software project up into
miniprojects. Each miniproject addresses one or more
major risks. Each iteration moves your project to a larger
scale.
• Evolutionary Prototyping - develop the system
concept as you move through the project. You may begin
by developing the most visible aspects of the system.
Useful when requirements may change throughout your
project or when you're unsure of the optimal architecture or
algorithms to use.
• Staged Delivery - you show software results in
successively refined stages. Unlike evolutionary
prototyping, when you use staged delivery, you know
exactly what you're going to build when you set out.
15
Linux Resources and Software
Tools – Opensource availability
• Programming
– C/C++, Java, Fortran, Python, Lisp
– PHP, Perl, HTML for WWW
– OpenGL – computer graphics
•
•
•
•
•
Image processing – Gimp
2D/3D analysis - Gnuplot
Openoffice for ppt, publishing
LaTex, PDF, PS for scientific writing
“planner” - Gantt charts, “dia” - flow charts, network
diagrams, UML – objects, electronic diagrams...
16
Computer Systems Lab
Example Projects
17
Student Intranet – Software
Engineering
• A new platform is developed implementing
paradigms in object-oriented programming
and collaborative development.
18
Development of
an ObjectOriented
Module-based
Extensible
Student Intranet
Web Application
in PHP5
A new platform, known as
Intranet2, implements
paradigms in Object-Oriented
programming and
collaborative development in
the creation of a new student
Intranet.
19
Implementation of Steganographic
Techniques - Cryptography
• The purpose of this project is to design a
steganographic program in C++ capable of
hiding a message within a WAV file, and
then later extracting the hidden message. It
should be able to work with any WAV
formatted sound file, and the message
ideally will not be detectable.
20
Implementation
of
Steganographic
Techniques
The purpose of this research will be
to investigate various methods of
steganography (hiding data within
different media). I will develop a
new program to hide data within
the WAVE file type. The first part
of the program itself will be able to
accept two inputs: the 'clean' file
and the hidden message. It will
then combine the two and output a
'doctored' file with the hidden
message inside it. The second part
of the program will be able to
reverse the process, receiving a
'doctored' file as input and
extracting the hidden message.
21
NetChat Communications System –
Software Engineering, Distributed
platforms
• The creation of a network communication
system that will use methods of transferring
data between a server and a client using an
XML protocol.
22
NetChat
Communication
s Systems
The project involves creating
a method of transferring data
between a server and client
using an XML-based protocol.
This framework would be
extended into the form of an
application called “NetChat”.
Using the developed
framework, NetChat would be
capable of sending data back
and forth in the form of instant
messages, email, news feeds,
along with various other
means of communication.
23
Image Filter Techniques – Image
Processing, Computer Vision
• This project explores digital image filtering
techniques by comparing the median and
frequency filters. By testing the filters with
images varying in object type (people,
landscapes, or objects) and noise
composition, the project determines the
advantages and disadvantages of each in
specific situations.een a server and a client
using an XML protocol.
24
Image Filter
Techniques
This project explores digital
image filtering techniques by
comparing the median and
frequency filters. By testing the
filters with images varying in
object type (people, landscapes,
or objects) and noise
composition, the project
determines the advantages and
disadvantages of each in specific
situations.
25
Logarithmic Randomly Accessible
Data Structure - Algorithms
• Making a data structure that performs like a
dynamic array but functions in logarithmic
time for all operations is the goal. By using
a binary tree in which values are stored at
the leaf nodes and each node keeps track of
how many leaves there are below it, we can
quickly achieve logarithmic random access,
insertion and deletion in the average case
but all operations are linear on the worst
case.
26
Logarithmic
Randomly
Accessible Data
Structure
Making a data structure that
performs like a dynamic array
but functions in logarithmic time
for all operations is the goal. By
using a binary tree in which
values are stored at the leaf nodes
and each node keeps track of
how many leaves there are below
it, we can quickly achieve
logarithmic random access,
insertion and deletion in the
average case by all operations are
linear on the worst case.
27
Graphical Display of a Physics
Simulation – Computer Modeling
• The purpose is to make a physics simulation
that will display objects placed by the user
graphically and display information about
those objects on a graphical user interface.
The goal is to allow the user to place any
combination of objects, including particles,
springs, and ramps, in a graphical display,
input values for these objects, and run a
simulation that will track these values and
display the interactions and positions of the
28
objects graphically in two-dimensions.
Computer
Graphics and
Physics
Simulations
A physics simulation, in order to
adequately demonstrate physical
laws and predict an unlimited
number of scenarios, must
implement a broad range of
mathematical equations and
provide the user with the ability
to set up a scenario with
whatever number of objects and
arrangements of these objects
that he desires. The goal of this
project is to create such a
simulation.
29
Modeling of Complex Systems:
Economics
• The stock market is an example of a
complex system, made up of millions of
interactions between different investors and
affected by every action made by thousands
of companies. Economic theory suggests
that the actions of investors are governed by
few well informed primary investors.
Primary catalysts may be news reports,
press releases, income reports, etc, and it
may be possible to predict trends across the
30
market by analyzing news on stocks.
Economic
Modeling
My project is involved with using
data mining techniques on the
internet in order to gather enough
information for the use of a
genetic algorithm in trend
analysis of a complex system;
e.g., the stock market. The most
fundamental element of my
program is creating a correlation
between news about a company
and its stock and the price of the
stock itself.
31
Creation of a Domain Specific
Computer Language – Computer
Language Design
• A domain-specific language (DSL) is a
programming language designed to be used
for a specific and limited set of tasks. Using
metaprogramming techniques, I designed
IFAlpha, a DSL hosted within Ruby for
creating interactive fiction games. My goal
was to create an intuitive and expressive
language for creating Interactive Fiction
(IF) games while hiding the details of
implementation from the programmer.
32
Creation of a
DomainSpecific
Computer
Language
The purpose of my project is to
explore programming language
design and metaprogramming
techniques in Ruby through the
creation of a DSL for creating
Interactive Fiction games. My
vision is to create an intuitive
interface for the game writer. The
value in the project is to be found
in both the technical
implementation and the design of
the interface. My goal is to
create a programming language
interface that is easy for a nonprogrammer end-user to use
writing IF games that hides
33
Decentralized Distributed
Processing – Distributed
Programming
• The purpose of this project is to produce a
medium for distributing the load of
enormous tasks to networked peers with
varying computing power in an efficient
manner. This will distribute the work load
from one computer to other computers
within a network of peer computers by
sending portions of the data and the proper
analytical tools to all of the specified peers
while also computing various peer's tasks.
34
Decentralized
Distributed
Processing
With the enormous amount of
data being collected every day, a
single computer's CPU's
computational ability to analyze
the data and to utilize meaning
behind the data is less than
satisfactory. In order to mine
through of the data within certain
time constraints, a collection of
computers is needed. The
purpose of this project is to
produce a medium for
distributing the load of enormous
tasks to networked peers with
varying computing power in an
efficient manner.
35
Machine Learning and
Computational Linguistics
• Using statistical processes in text
translation.
36
French/English
Translation and
Computational
Linuguistics
This project uses computational
linguistics to serve students of
French or English as a second
language as well as those who
know only one of these
languages. The program will
translate French to English and
English to French well enough to
be understandable to someone
who knows only the output
language. This is useful for
surfing the web, reading texts in
a foreign language, and
communication with someone
from another country. It can also
be used for students to check
their writing by translating back
to their native tongue.
37
Machine Learning Processes:
Genetic Algorithms
• The program works like a general genetic
evolutionary process. First, the parameters,
cost, and cost function are defined. An
initial population is created, and the cost is
evaluated for each individual in the
population. Pairs are selected to reproduce,
and mutations may occur. The resulting
population is tested and if the desired result
is obtained the program stops. Otherwise,
the process begins again with the cost
38
evaluation step.
Machine Learning Algorithms
The purpose of this project is to create a program that can play a game at an expert level.
The program will probably use alpha-beta pruning or genetic algorithms, two common
algorithms of AI. Genetic algorithms use parent states to create child states, while alphabeta pruning looks for the best move at the moment. The results of the genetic algorithm
39
and the alpha-beta pruning can be compared to find an optimum AI for playing the game.
The Dynamics of Cellular Automata
– Artificial Life
• John Conway's Game of Life showed that
simple rules can generate amazingly
complex patterns. Using variations of the
rules he devised, one can learn about the
advantages of different sets of rules and the
implications for simple evolution and chaos
theory.
40
Cellular
Automata
Dynamics
Cellular automata grids can be
used to show that simple rules
can generate complex patterns.
Using variations of rules devised
from John Conway's Game of
Life, one can learn about the
advantages of different sets of
rules and the implications for
simple evolution and chaos
theory.
41
Computer Modeling: TJ's Hallways
and Student Traffic
• The purpose of this project is to create a
simulation of the students and teachers at
Jefferson moving around the building. This
simulation is meant to be accurate based on
time and location.
42
TJ Hall
Modeling
The purpose of this project is to
model TJ students in their school
environment throughout a typical
school day. The goal is to have
dots to represent the students
moving on the basis of
probability to various parts of the
building. If the project were
completed it would allow the
user to control various aspects of
the day. This project is worth
doing to demonstrate just how
big the need is for a new
building; to indirectly show that
TJ is overcrowded. Students and
teachers alike might be interested
in seeing the results, mostly to
avoid the crowded areas during
their travels.
43
Modular Architecture for Game
Design – Software Engineering,
Object Oriented Programming
• Common current game architectures limit
program flexibility and modularity. With the
advent of middleware and the increasing
complexity of games, this is no longer
acceptable. This project attempts to design
and implement a modular, Data-centered
architecture based on the "System of
Systems" approach.
44
Modular
Architecture for
Game Design
Common current game
architectures limit program
flexibility and modularity. In this
project I will attempt to design
and implement a highly modular,
Data-centered architecture based
on the "System of Systems"
approach. The final
implementation need not have
any significant complexity within
each system (e.g. graphics, AI,
etc.) but rather must demonstrate
the successful interaction of
independent systems.
45
Music Compositional Software
Development – Computer Music
• Music editing software may be expensive,
complicated, and could be improved as a
teaching tool. A new, free software designed
for amateur composers and music students
requires a less powerful editing system and
can incorporate learning tools to aid
teachers in teaching music theory to
students.
46
Compositional
Software
Development
The purpose of this project is to
make an easy to use composition
aid software that incoporates a
simple and intuitive GUI into a
robust highly capable system of
music display.
47
Map Path Finding with Realistic
Conditions – AI Search Algorithms
• An abstract representation of a map will be
used to incorporate realistic conditions
along with a visual display. The project can
be used as a tool for educating students on
different types of search algorithms,
memory efficiency, and runtimes. Realistic
aspects of traffic movement such as traffic
light and stop sign delays can provide better
paths through a map.
48
Map Path
Finding and
Efficient Search
Techniques
My project will deal with maps
and pathfinding. The primary
goal of the project would be to
use an extension of the A* search
algorithm to find both the
shortest distance path and the
fastest path through a given
graph - an abstract representation
of a real life map. Eventually, I
hope to include realistic artificial
intelligence concepts such as
speed limits and street lights. A
random graph generator will also
be created.
49
Human Cognitive Emulation –
Computer Modeling in Psychology
• This project attempts to recreate accurate
human responses to stimuli. Using a survey
format, this experiment hopes to produce a
unique response to a stimuli based on
information gained about the user. This lab
can perhaps draw broad conclusions about
groups of people and how they respond,
combined with other techniques of
emulating human thought patterns,
computers can become closer and closer to
accurately representing a human cognition. 50
Human
Cognitive
Emulation
This project attempts to
accurately model human
responses to stimuli. Using a
survery format, this research
hopes to produce a unique
responce to a stimuli based on
information gained about the
user. Analyzed solely on its own,
the ramification of this project
can perhaps draw broad
conclusions about groups of
people and how they respond.
When combined with other
techniques of emulating human
thought patterns, computer
programs can come closer to
representing accurately human
responses.
51
Evolution Simulator – Computer
Modeling of Environments, Artificial
Life
• Simulate the evolution of different
organisms within an environment. There
will be a genetic variability that will allow
the organism species to evolve, or die out.
The hope is a demonstration of natural
selection, showing that after many
generations the collective gene will be more
advanced than the original.
52
Evolution
Simulator
The purpose of this project is to
create an AGENT-based model that
simulates the evolution of different
organisms within an environment.
These organisms will be a
simulation of real-world organisms,
with the need for food, the ability
to breed and die, and so on. Their
function and lifespan will be based
on dozens of genetic
characteristics, such as metabolism,
eyesight, etc., and these
characteristics will be passed on to
offspring. There will be a genetic
variability that will allow the
organism species to evolve, or
devolve. The hope is a
demonstration of natural selection,
and after several generations the
collective gene will be more
advanced than the original.
53
Applications of Neural Networks –
Machine Learning
• Neural networks are a powerful way of
finding patterns and functions. Traditional
methods and algorithms can have trouble
finding patterns in data when there are noisy
data and imperfections. Neural networks are
designed to handle noise and be able to find
complex patterns in noisy data. In that way,
they are ideal for applications like
predicting the stock market, compressing
data and analyzing musical compositions.
54
Applications of
Neural
Networks
Neural networks are a powerful
way of finding patterns and
functions. Traditional methods
and algorithms often have trouble
finding patterns in data when
there are noisy data and
imperfections. Neural networks
are designed to handle noise and
be able to find complex patterns
in noisy data. In that way, they
are ideal for applications like
predicting the stock market,
compressing data and analyzing
musical compositions.
Furthermore, different types of
neural networks have different
strong points; this project will
attempt each of the applications
with various types of neural
55
Traffic Light Simulation – Computer
Modeling, Traffic
• This project simulates a busy traffic light.
The cars follow all necessary rules of the
road so that the simulation is realistic. The
program recognizes patterns in the
intersection and makes the light as efficient
as possible by minimizing waiting time and
queue length plus maximizing green light
usage for cars. The patterns in the
intersection can change hourly to match the
real world.
56
Traffic Light
Simulation
This project is meant to simulate
a busy traffic light. The program
tries to recognize patterns in the
intersection and make the light as
efficient as possible by
minimizing waiting time for cars,
both average waiting and total
waiting time. The patterns would
be related to the time of day and
the day of the week. At first I
would purposely input
recognizable patterns and see if
the program would catch it, but
eventually the plan would be to
possibly use this program using a
real intersection's data.
57
3D Visualization Package –
Computer Graphics
• Develop a 3D graphics simulation engine
designed to simplify the task of coding 3D
simulations, while still giving the developer
control over every aspect of the rendering
and simulation process.
58
Development of
a 3D
Visualization
Engine
The purpose of my project is to
investigate the workings of a 3D
graphics simulation engine, and
develop an engine designed to
simplify the task of coding 3D
simulations, while still giving the
developer control over every aspect
of the rendering and simulation
process. Hopefully, this engine will
simplify the visualization process to
the point where it is worthwhile to
code a 3D representation of some
problem. I also hope to make it
possible for the developer to use my
engine without any knowledge of
OpenGL or SDL, but rather do all the
necessary code behind the scenes
when using the default rendering
methods.
59
Hybrid Machine Learning System –
Machine Learning
• Designing a system that combines the
capabilities of multiple types of AI and
machine learning systems, such as neural
networks and subsumption architectures, to
produce a more flexible and versatile hybrid
system.
60
Hybrid AI and
Machine
Learning
Systems
The purpose of this project is to
design a system that combines the
capabilities of multiple types of AI
and machine learning systems, such
as neural networks and subsumption
architectures, to produce a more
flexible and versatile hybrid system.
The end goal is to produce a set of
basic library functions and
architecture descriptions for the easy
manipulation of the AI/ML
subsystems (particularly neural
networks), and use those to build an
AI system capable of teaching itself
how to complete tasks specified by a
human-defined heuristic via either
supervised training or trial-and-error
and inference, and of altering learned
behaviors to cope with changes in its
operational environment with
minimal human intervention.
61
Unique-Bid Auction Modeling and
Analysis – Computer Modeling,
Economics, Game Theory
• To create an auction environment that
allows human and robotic bidders to
compete for a fictitious auction items.
62
Unique-Bid
Auction
Modeling and
Analysis
The purpose of this project is to
simulate a unique-bid auction
environment and to economically
analyze the auction results. When
completed, this project would be
an exercise in complex systems
modeling, computer networking,
artificial intelligence, and
graphical interfaces and displays.
When the environment program
is perfected, I will alter the size
and access to information and
track the changes in the auction's
performace.
63
Hallway Traffic Simulator –
Computer Modeling
• This project is intended to spot flaws in
school hallway design and find an ideal
layout. My primary goal for the first quarter
will be to program an algorithm in fortran
that will write basic movements of
individuals to a text file. I will also write a
viewer in java to read from the text file and
display these movements in a GUI.
64
Hallway Traffic
Simulator
This project is intended to spot
flaws in school hallway design
and find an ideal layout. My
primary goal for the first quarter
will be to program an algorithm
in fortran that will write basic
movements of individuals to a
text file. I will also write a
viewer in java to read from the
text file and display these
movements in a GUI.
65
Machine Learning Applications:
Othello
• The purpose of this research project is to
implement machine learning with artificial
intelligence. A purpose is to gain a deeper
understanding of machine learning.
66
Machine
Learning
Applications in
Othello
The purpose of this research
project is to implement machine
learning with artificial
intelligence. This research will
gain a deeper understanding of
machine learning, a subject
which I am very interested in.
Anyone who is interested in
having a significant Othello
challenge will be interested in the
results of this project.
67
3D Graphics Module – Software
Engineering
• The purpose of this research project is to
write a program that allows the user to
graph functions of two variables. The
program will incorporate elements of 3D
graphics by allowing the user to rotate,
shrink, and stretch the graphs. The program
may be included in the student Intranet as a
module and will thus include elements of
modular design.
68
3D Graphics
Module
My project will be an addition to
the Intranet. Currently, the
Intranet has a module for
calculator registration in case
someone loses their calculator.
However, there is no module to
replace the functionality of a
graphing calculator while it is
lost.
The purpose of my project is to
create an Intranet module
containing a regular 4-function
calculator along with a graphing
utility and matrix and list editors.
I will try to include every matrix,
graph, and statistical operations
contained on the TI-83.
69
End-to-end Bittorent Publication –
Computer Networks
• End-to-end publication through Bittorrent
involves creating a .torrent metadata file,
communicating with peers through a central
“tracker,” and an initial “seed” with a
complete copy of the file. This project aims
to simplify this process by providing a
complete package that provides all the parts
of this process.
70
End-to-end
Bittorent
Publication
Bittorrent is a peer-to-peer network
that always allows for fast
download speeds despite the
number of peers downloading the
file. Currently, there exist tools to
make .torrent files, tools to "track"
the peers downloading the file, and
tools to host .torrent files. This
project aims to unify this process
by making an end-to-end software
suite that simplifies the process of
publishing a file on the Bittorrent
network for download. It will
involve a complete implementation
of the Bittorrent protocol, including
encoding torrent files, peer-totracker and peer-to-peer
communication.
71
An Investigation of Chaos Theory
Using Supercomputing Techniques –
High Performance Computing
• The purpose of this project is to investigate
Chaos Theory while applying advanced
supercomputing algorithms using the
Message Passing Interface (MPI). Through
an analysis of more simple chaotic systems,
I hope to learn about more sophisticated
systems.
72
An Investigation
of Chaos Theory
Using
Supercomputing
Techniques
The purpose of this project is to
investigate Chaos Theory while
applying advanced supercomputing
algorithms using the Message
Passing Interface (MPI). Through an
analysis of more simple chaotic
systems, I hope to learn about more
sophisticated systems.
73
Ant Colony Optimization (ACO) –
Algorithms, Machine Learning, Path
Finding
• Finding optimal paths in a complex
network. ACO is an algorithm that is used
to find near optimal solutions to NP
problems.
74
Ant Colony
Optimization
Algorithms
Ant Colony Optimization (ACO)
is an algorithm that is used to
find near optimal solutions to NP
problems. This research aims to
study the differences in strengths
and weaknesses between various
implementations of ACO (as
applied to the Traveling
Salesman Problem), suggest or
conduct development into
improving performance of ACO
algorithms, and study the general
application of ACO algorithms to
the Traveling Salesman Problem.
75
76
Computer Systems Lab
Mentorship
• TASC Component Architecture and
Simulation Environment: Systems Modeling,
Northrop Grumman IT
• Implementation of Artificial Physics Using
AIBO Robot and the Pyro Programming
Environment: AI Robotics, NRL
• Development of a Practical Social Network
Analysis Program: IT.COM
77
Computer Systems Lab
Mentorship
• Fairness and Justness in Non-Cooperative
Game Theory: Experimental Economics
Modeling, GMU
• Analysis of Driver Patterns in a Simulated
Environment: Computer Modeling, TurnerFairbank Highway Research Center
• Advanced Speed Guidance for Merging
and Sequencing Techniques: MITRE
78
Computer Vision: Edge Detections
Vertical diff., Roberts, Sobels
79
Thanks and have fun computing!