# Все вопросы: [computer-science]

192 вопросов

3ответов
17471 просмотров

### In Natural language processing, what is the purpose of chunking?

In Natural language processing, what is the purpose of chunking?

2ответов
988 просмотров

### Is there a simple way I can tokenize a string without a full-blown lexer?

I'm looking to implement the Shunting-yard Algorithm, but I need some help figuring out what the best way to split up a string into its tokens is. If you notice, the first step of the algorithm is "read a token." This isn't exactly a non-trivial thing to do. Tokens can consist of numbers, oper...

6ответов
4471 просмотров

### Hilbert System - Automate Proof

I'm trying to prove the statement ~(a-&gt;~b) =&gt; a in a Hilbert style system. Unfortunately it seems like it is impossible to come up with a general algorithm to find a proof, but I'm looking for a brute force type strategy. Any ideas on how to attack this are welcome.

8ответов
2903 просмотров

### Context Free Grammar for Unary Addition

Given an alphabet of 1s I want to parse addition of the form 1^k + 1^j = 1^k+j This is pretty easy to represent with a pushdown automaton simply by pushing a 1 on to the stack on each of the first two 1s, and then popping on the last set of 1s. However, I can't seem to figure out how to repre...

3ответов
16605 просмотров

### What is the difference between monotonicity and the admissibility of a heuristic?

I'm reading over my AI textbook and I'm curious about what the difference is between monotonicity and admissibility of heuristics (I know they aren't mutually exclusive). As far as I can tell, an admissible heuristic simply means you are ensured to get the shortest path to a solution if one exi...

5ответов
15721 просмотров

### How to keep up to date on latest computer science?

I was re-reading some of my Steve McConnell books and this quote got me thinking 'scientists build in order to learn, engineers learn in order to build'. On the vein of 'learning in order to build' I was wondering: How are the software engineers keeping up to date on the latest technologies and ...

8ответов
909 просмотров

### How to compute the absolute minimum amount of changes to convert one sortorder into another?

Goal How to encode the data that describes how to re-order a static list from a one order to another order using the minimum amount of data possible? I have a feeling there is an algorithm or computer science term that will help me but right now I'm too stuck on the problem to figure out other ...

6ответов
5079 просмотров

### comparisons of data structures, algorithms, basic computer science, online resources

I am searching for an online resource referring to data structures and algorithms. Basicaly what I am interested in, is a kind of comprehensive list of things such as: when a data structure or algorithm is used, pros and cons compared to each other, real life-problem usage, etc. I have a couple ...

2ответов
1463 просмотров

### How can I modify the breadth-first search algorithm to also include the solution path?

I have the following pseudo-code in my book for a breadth-first search: function breadth_first_search: begin open := [Start] closed := []; while open != [] do begin remove leftmost state from open, call it X; if X is a g...

2ответов
1177 просмотров

### How to argue that if we could solve the halting problem, then we could solve busy beaver?

This is one of the tasks of my assignment. I have a Turing machine simulation which can simulate a busy beaver function. I have done some research about proving this problem, but still don't get it so I guess maybe you can help me here. A good source for me to go to or example of how to argue th...

2ответов
911 просмотров

If I have the input space of (1,2,....999). And I have a concept class C, with 10 concepts: C0,C1,C2...C9. Given an input, that input is an element of ci if the it contains the digit i. For example, the number 123 is an element of c1 and c2 and c3. What is the VC Dimension of this concept clas...

1ответов
1067 просмотров

### Binary Tree Isomorphism

I have an assignment to write among other things, a set of prolog predicates that determine if any two binary tree's are isomorphic to each other. The predicate must also be able to provide all of the isomorphic graphs to any given binary tree. Here is what I have so far, it works except for re...

4ответов
178 просмотров

### Looking for a good reference on calculating permutations

As a programmer, I frequently need to be able to know the how to calculate the number of permutations of a set, usually for estimation purposes. There are a lot of different ways specify the allowable combinations, depending on the problem at hand. For example, given the set of letters A,B,C...

12ответов
2589 просмотров

### How can I learn higher-level programming-related math without much formal training?

I haven't taken any math classes above basic college calculus. However, in the course of my programming work, I've picked up a lot of math and comp sci from blogs and reading, and I genuinely believe I have a decent mathematical mind. I enjoy and have success doing Project Euler, for example. I ...

6ответов
258 просмотров

### Are there useful static analysis tools for databases?

Is there a tool for examining the configuration and schema of a database for dubious fields, relationships and configuration, similar to how static analysis tools like lint will flag dubious lines of code? I'm not necessarily asking for normalization, but surely there's stupid stuff that can be ...

1ответов
1404 просмотров

### How can I modify the backtracking algorithm so it can run on "and/or" graphs?

In Artificial Intelligence we studied the backtracking algorithm. Here is the pseudocode our book offers: function backtrack; begin SL:= [Start]; NSL := [Start]; DE := [] CS := Start; while NSL != [] do begin if CS = goal (or meets goal description) t...

4ответов
2388 просмотров

### Permutations of letters and numbers in a phone number

For my computer science class, we need to write a program (in C++) that takes an input of characters and outputs the possible permutations of it according to the dial pad on a phone, leaving non-digit characters in place. For example, inputing 2 outputs 2, A, B, C. Inputing 23 outputs 23, A3, B3...

3ответов
1548 просмотров

### Coinduction - clear, concise description

I am studying coinduction(not induction) as part of a class on static analysis. Rummaging around the internet, I am simply not finding clear, concise description of: What coinduction is How coinduction actually proves something(it seems that coinduction is like waving a magic hand in the treatm...

6ответов
1637 просмотров

### Create a program that inputs a regular expression and outputs strings that satisfy that regular expression

I think that the title accurately summarizes my question, but just to elaborate a bit. Instead of using a regular expression to verify properties of existing strings, I'd like to use the regular expression as a way to generate strings that have certain properties. Note: The function doesn't ne...

16ответов
433781 просмотров

### What is the difference between statically typed and dynamically typed languages?

I hear a lot that new programming languages are dynamically typed but what does it actually mean when we say a language is dynamically typed vs. statically typed?

4ответов
537 просмотров

### Secret computing: does such an animal exist?

A question in theory of Computer Science Today I can secretly store files in the cloud (say, amazon s3), by having them encrypted before I store them and decrypt them after I download. The storage provider cannot obtain any information from the stored files - everything is encrypted safely, and ...

1ответов
243 просмотров

### What class of language can Perl regular expressions be used against?

I know that some of the capabilities of the Perl regular expression engine are not regular. However, what class is it? It might be context-free, but CS theory was never my strongest subject.

23ответов
15445 просмотров

### O(log N) == O(1) - Why not?

Whenever I consider algorithms/data structures I tend to replace the log(N) parts by constants. Oh, I know log(N) diverges - but does it matter in real world applications? log(infinity) &lt;100 for all practical purposes. I am really curious for real world examples where this doesn't hold....

4ответов
4338 просмотров

### Memory-efficient way of computing the median of a large data set?

If one computer can only hold 1 million numbers, how to find out the median number from 100 million numbers?

2ответов
978 просмотров

### Logic question (universal and existential quantifications)

I have a logical statement that says "If everyone plays the game, we will have fun". In formal logic we can write this as: Let D mean the people playing. Let G be the predicate for play the game. Let F be the predicate for having fun. Thus [VxeD, G(x)] -&gt; [VyeD, F(y)] V is the computer sci...

4ответов
1805 просмотров

### Closest grid square to a point in spherical coordinates

I am programming an algorithm where I have broken up the surface of a sphere into grid points (for simplicity I have the grid lines parallel and perpendicular to the meridians). Given a point A, I would like to be able to efficiently take any grid "square" and determine the point B in the square ...

7ответов
1042 просмотров

### What are the most valuable parts of Computer Science studies for Cocoa developers?

What are the most valuable parts of Computer Science studies for Cocoa developers? Another way I might word this question is: If I’m not going to go to school for Computer Science but want to be a developer working primarily with Cocoa, what are the things I should make sure I learn that I oth...

3ответов
2716 просмотров

### How can I write a program to generate a sorting decision tree?

In class we were given a simple decision tree for sorting 3 elements (a,b,c). (source: brpreiss.com) While looking at this, it makes sense to me. I was able to follow it. However, I now have to make a decision tree for 4 elements (a,b,c,d) and the number of leafs just shot up to 24. I'm ...

5ответов
150 просмотров

### Most efficient way to encode 2 positions between 0 and 64?

I have 64 bit values that I want to compress by exploiting the fact that only a portion somewhere in the middle contains data and before and after that are zeroes. Say the actual data is l bits long and padded with n 0s in front and m 0s at the end such that n + l + m = 64. Instead of transmitti...

4ответов
284 просмотров

### Resources for Beginning CS

I have been writing PHP, Ruby, ColdFusion, and javascript (not a language, I know), for several years. But I am really wanting to get more into the world of Computer Science and writing in lower-level languages. What are some good resources for starting out? It seems like every book I have g...